临近期末，所以以此为专题巩固算法与数据结构能力。值得注意的是，以下几个题目有些比较有难度，考试的时候并不会以代码的方式呈现，然而掌握这些算法终究是好的，便于理解底层算法知识，对于自己构造起来也十分方便。
下面开始我们的算法题目练习，当然此次只写算法函数，不涉及主函数的编写。本次算法不使用C++ STL里面的容器。
你的三连就是我创作的最大动力，后续还有关于数据结构、计算机硬件等的复习纲要嗷！
本次二叉树的结构代码
typedef struct BTNode{
Keytype data;
struct BTNode *lchild;
struct BTNode *rchild;
}BTNode;//为什么我这里不写*BTree，因为我后面用C++格式引用,就不用二级指针了
线索二叉树的结构代码
typedef struct TBTNode{
char data;
int ltag,rtag;
struct TBTNode *lchild;
struct TBTNode *rchild;
}TBTNode;
目录
- 求后缀表达式
- 求二叉树的深度
- 查询结点
- 层次遍历
- 中序遍历建立线索二叉树
- 先序＋中序->构造二叉树
- 满二叉树的遍历
- 非递归遍历
- 总结
题目1：表达式（a-(b+c))*(d/e)存储在一颗以二叉链表的二叉树中（节点为char型），编写程序计算表达式。
很明显这是一个后缀表达式的题目，运用的知识点有二叉树、栈。
int op(int A,int B,char C){
//返回以C运算符，A,B操作数的数值
}
int comp(BTNode *p){
int A,B;
if(p){
if(p->lchild!=NULL&&p->rchild!=NULL){
A=comp(p->lchild);//一直遍历至叶子
B=comp(p->rchild);
return op(A,B,p->data);
}
else return p->data-'0'//叶子一定是数
}
else return 0;
}
求二叉树的深度
题目2：写一个算法求一棵二叉树的深度。
很明显,分别求出左子树和右子树深度，然后比较大小返回最大。（分治法）
int getDepth(BTNode *p){
int LD,RD;
if(p==NULL) return 0;
else{
LD=getDepth(p->lchild);
RD=getDepth(p->rchild);
return (LD>RD?LC:RD)+1;
}
}
查询结点
题目3：在一棵二叉树中，查询data域等于key的结点是否存在，如果存在使q指向该结点。
遍历+剪枝操作
void search(BTNode *p,BTNode *&q){//q要改变所以为引用型
if(p!=NULL){
if(p->data==key) a=p;
else{
search(p->lchild,q);
//如果没有找到才去右树找
if(q==NULL){
search(p->rchild,q);
}
}
}
}
层次遍历
题目4：写一个算法求层次遍历时输出的结点信息
层次遍历就是从上到下，从左到右的遍历。当然需要队列来辅助操作。
void level(BTNode *p){
int front,rear;
BTNode *que;
front=0,rear=0;
BTNode *q;
if(p){
rear=(rear+1)%Maxsize;
que[rear]=p;//进队
while(front!=rear){
front=(front+1)%Maxsize;
q=que[front];//出队
visit(q);
//为什么后面都是操作q，因为q已经是根节点了。
if(q->lchild!=NULL){//先让左子树进队，因为从左到右遍历
rear=(rear+1)%Maxsize;
que[rear]=q->lchild;
}
if(q->rchild!=NULL){
rear=(rear+1)%Maxsize;
que[rear]=q->rchild;
}
}
}
}
中序遍历建立线索二叉树
题目5：写一个算法中序遍历与建立线索二叉树
注意要设置2个指针，一个是正在访问的结点，一个是前驱指针
void InTread(TBTNode *p,TBTNode *&pre){
if(p){
InTread(p->lchild,pre);//先让左子树线索化
if(p->lchild==NULL){//如果是为空，那么线索为1，同时使左孩指向前驱中序的结点，下面同理
p->lchild=pre;
p->ltag=1;
}
if(pre!=NULL&&pre->rchild==NULL){
pre->rchild=p;
pre->rtag=1;
}
pre=p;//赋给前驱结点
InTread(p->rchild,pre);
}
}
//建立
void Creat(TBTNode *root){
TBTNode *pre=NULL;
if(root){
InTread(root,pre);
pre->rchild=NULL;//处理最后一个结点，因为是中序遍历，所以肯定在右孩
pre->rtag=1;
}
}
先序＋中序->构造二叉树
题目6：已知二叉树的结点按先序遍历的序列保存在pre[l1…r1]中,按中序遍历的序列存在in[l2…r2]中,其中结点信息互不相同。试写出通过pre,in数组构造二叉树
BTNode* CreatBT(char pre[],char in[],int l1,int r1,int l2,int r2){//本函数返回二叉树的根节点
BTNode *s;
int i;
if(l1>r1) return NULL;
s=(BTNode *)malloc(sizeof(BTNode));
s->lchild=s->rchild=NULL;
for(i=l2;i<=r2;i++){
if(in[i]==pre[l1]) break;//找到了根节点，然后开始分两半来看
}
s->data=in[i];
//分界点i，参照前面的建立左子树和右子树，注意赋给s的左右指针上。
s->lchild=CreatBT(pre,in,l1+1,l1+i-l2,l2,i-1);
s->rchild=CreatBT(pre,in,l1+i-l2+1,r1,i+1,r2);
return s;
}
满二叉树的遍历
题目7：假设满二叉树的先序序列已经在数组中，设计一个算法将其转换为后序遍历序列。
其实本质就是数组转换。
void change(char pre[],int L1,int R1,char post[],int L2,int R2){
//原序列在pre[],转换后在post[]
if(L1<=R1){
post[R2]=pre[L1];//将Pre第一元素放在最后
//递归处理pre前一半序列，将其放在post对应的前一半
change(pre,L1+1,(L1+1+R1)/2,post,L2,(L2+R2-1)/2);
change(pre,(L1+1+R1)/2+1,R1,post,(L2+R2-1)/2+1,R2-1);
}
}
非递归遍历
题目8：设计一个算法遍历先序非递归遍历，并输出。
这个很平常，就是结合栈一起操作
先序：
先让根结点入栈出栈，然后依次让其左右结点入栈，注意右孩子先进去，左孩子后入，因为对左孩子访问先于右孩。
void preorder(BTNode *bt){
BTNode *stack[Maxsize];
int top=-1;
BTNode *p;
if(bt!=NULL){
Stack[++top]=bt;
while(top!=-1){
p=stack[top--];
visit(p);
if(p->rchild){
stack[++top]=p->rchild;
}
if(p->lchild){
stack[++top]=p->lchild;
}
}
}
}
总结
以上就是常见的关于二叉树的算法题目，一般平时考试并不会考代码，但如果是考研的化，会有一些算法设计题，写法也同上面所写，只要写出算法函数式就行了。当然二叉树的关键就是遍历了，其他都是通过遍历来转换的。希望有所帮助。
