二叉树的算法专项提高

二叉树的算法专项提高

临近期末，所以以此为专题巩固算法与数据结构能力。值得注意的是，以下几个题目有些比较有难度，考试的时候并不会以代码的方式呈现，然而掌握这些算法终究是好的，便于理解底层算法知识，对于自己构造起来也十分方便。
下面开始我们的算法题目练习，当然此次只写算法函数，不涉及主函数的编写。本次算法不使用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;
            }
        }
    }
}

总结

以上就是常见的关于二叉树的算法题目，一般平时考试并不会考代码，但如果是考研的化，会有一些算法设计题，写法也同上面所写，只要写出算法函数式就行了。当然二叉树的关键就是遍历了，其他都是通过遍历来转换的。希望有所帮助。