35.树与二叉树练习（1）（王道第5章综合练习）

【所用的树，队列，栈的基本操作详见上一节代码】

试题1（王道5.3.3节第3题）：

编写后序遍历二叉树的非递归算法。

参考：34.二叉链树的C语言实现_北京地铁1号线的博客-CSDN博客https://blog.csdn.net/qq_54708219/article/details/133581706

试题2（王道5.3.3节第4题）：

给出二叉树自下而上，从右到左的层次遍历算法。

这道题很显然就是层次遍历算法调个个，加个栈即可实现：

//层次遍历（自下而上，从右到左）
void LevelOrder2(BiTree T){
    Queue q;
    InitQueue(q);
    Sqstack S;
    InitStack(S);
    BiTree p = T;
    InsertQueue(q, p);
    while(!IsQueueEmpty(q)){
        p = DeleteQueue(q, p);
        InsertSqstack(S, p);
        if(p->lchild!=NULL)
            InsertQueue(q, p->lchild);
        if(p->rchild!=NULL)
            InsertQueue(q, p->rchild);
    }
    while(S.top != -1){
        p = DeleteSqstack(S, p);
        printf("%c", p->data);
    }
}

输出：

输入二叉树的前序序列，#代表空子树:
ABD##E##C##
二叉树创建成功！
二叉树的层次遍历序列是：ABCDE
二叉树的层次遍历（自下而上，自右向左）序列是：EDCBA

试题3（王道5.3.3节第5题）：

设计非递归算法求二叉树的高度。

此题采用层次遍历，附设一个指针a：

//利用层次遍历实现非递归计算树的深度
int LevelOrderDepth(BiTree T){
    int Depth = 0;
    if(!T)
        return Depth;
    else{
        Queue q;
        InitQueue(q);
        BiTree p = T;
        InsertQueue(q, p);
        Depth = 1;
        int a = q.rear;  //指针a指向队尾，也就是这一层最后一个元素
        while(!IsQueueEmpty(q)){
            if(q.front==a){  //这个时候说明这一层出完了，此时rear就是下一行的末尾结点
                a = q.rear;
                Depth = Depth + 1;
            }
            p = DeleteQueue(q, p);
            if(p->lchild!=NULL)
            InsertQueue(q, p->lchild);
            if(p->rchild!=NULL)
            InsertQueue(q, p->rchild);
        }
        return Depth;
    }
}

输出：

输入二叉树的前序序列，#代表空子树:
ABD##E##C##
二叉树创建成功！
二叉树的深度是（非递归算法）：3

试题4（王道5.3.3节第6题）：

设一棵二叉树中各结点的值互不相同，其先序遍历序列和中序遍历序列分别存放在两个数组A和B中，试编写算法建立该二叉树的二叉链表。

仍需要采用递归操作，这里要想办法根据前序序列找到根结点，然后在中序序列找根结点，从而确定哪些结点属于左子树，哪些结点属于右子树。

//由先序序列和中序序列建立二叉树
BiTree CreateBiTreeviaOrders(char a[],char b[],int x1,int y1,int x2,int y2){
    //x1,y1工作在前序序列中，x2,y2工作在中序序列中
    BiTree T;
    T = (BiTree)malloc(sizeof(BiTNode));
    T->data = a[x1];  //前序序列的第一个结点就是根结点
    int llen, rlen;
    for (int i = x2; i <= y2; i++){  //在中序序列找根结点
        if(b[i] == a[x1]){
            llen = i - x2;  //左子树的序列长度（结点个数）
            rlen = y2 - i;  //右子树的序列长度（结点个数）
        }
    }
    if (llen == 0)
        T->lchild = NULL;
    else
        T->lchild = CreateBiTreeviaOrders(a, b, x1 + 1, x1 + llen, x2, x2 + llen - 1);
    if (rlen == 0)
        T->rchild = NULL;
    else
        T->rchild = CreateBiTreeviaOrders(a, b, y1 - rlen + 1, y1, y2 - rlen + 1, y2);
    return T;
}
 
int main(){
    BiTree T;
    char a[6] = {'A', 'B', 'C', 'D', 'E', 'F'};  //先序序列
    char b[6] = {'C', 'B', 'A', 'E', 'D', 'F'};  //中序序列
    T = CreateBiTreeviaOrders(a, b, 0, 5, 0, 5);  //初始必须是0和数组长度减一
    printf("该二叉树的后序遍历序列是：");
    PostOrderTraverse(T);  //输出后序序列进行验证
    return 0;
}

这里以王道5.3.3节单选15题进行验证，输出结果就是A选项。

该二叉树的后序遍历序列是：CBEFDA

试题5（王道5.3.3节第7题）：

二叉树按二叉链表存储，写一个判别给定二叉树是否是完全二叉树的算法。

此题的思路是借助层次遍历和队列，当队列中输出空结点的时候，如果此时队列还有非空结点说明不是完全二叉树。注意这里输入和验证的都是扩展二叉树，所以去掉了层次遍历中的结点非空判断。

//判断是否是完全二叉树
bool IfCompleteTree(BiTree T){
    Queue q;
    InitQueue(q);
    BiTree p = T;
    if(!p)
        return true;
    InsertQueue(q, p);
    while(!IsQueueEmpty(q)){
        p = DeleteQueue(q, p);
        if(p!=NULL){
            InsertQueue(q, p->lchild);
            InsertQueue(q, p->rchild);
        }
        else{
            int a = q.front;
            while(a!=q.rear){
                if(q.data[a]!=NULL)
                    return false;
                a = (a + 1) % MAXSIZE;
            }
            return true;
        }   
    }
}
 
int main(){
    BiTree T;
    printf("输入二叉树的前序序列，#代表空子树:\n");
    CreateBiTree(T);
    printf("二叉树创建成功！\n");
    printf("该二叉树是否是完全二叉树？%d", IfCompleteTree(T));
    return 0;
}

输出：

输入二叉树的前序序列，#代表空子树:
ABD##E##C##
二叉树创建成功！
该二叉树是否是完全二叉树？1
 
输入二叉树的前序序列，#代表空子树:
AB##CD##E##
二叉树创建成功！
该二叉树是否是完全二叉树？0

试题6（王道5.3.3节第8题）：

设二叉树采用二叉链表存储结构，设计算法计算给定二叉树的双分支结点个数。

递归算法：

//判断是否是完全二叉树
int TwobranchNodes(BiTree T){
    if(T==NULL)
        return 0;
    else if(T->lchild!=NULL&&T->rchild!=NULL)
        return TwobranchNodes(T->lchild) + TwobranchNodes(T->rchild) + 1;
    else
        return TwobranchNodes(T->lchild) + TwobranchNodes(T->rchild);
}

非递归算法（层次遍历逐个结点检查）：

//判断是否是完全二叉树
int TwobranchNodes(BiTree T){
    int a = 0;
    Queue q;
    InitQueue(q);
    BiTree p = T;
    InsertQueue(q, p);
    while(!IsQueueEmpty(q)){
        p = DeleteQueue(q, p);
        if(p->lchild!=NULL && p->rchild!=NULL)
            a = a + 1;
        if(p->lchild!=NULL)
            InsertQueue(q, p->lchild);
        if(p->rchild!=NULL)
            InsertQueue(q, p->rchild);
    }
    return a;
}

试题7（王道5.3.3节第9题）：

设树B是一棵采用链式结构存储的二叉树，编写一个把树B中所有结点的左右子树进行交换的函数。

此题同题6一样也可以用递归或层次遍历的方法，这里给出非递归的方法：

//把二叉树的左右子树交换
int ChangeTwobranch(BiTree &T){
    Queue q;
    InitQueue(q);
    BiTree p = T;
    BiTree r;
    InsertQueue(q, p);
    while(!IsQueueEmpty(q)){
        p = DeleteQueue(q, p);
        if(p->lchild!=NULL || p->rchild!=NULL){
            r = p->lchild;
            p->lchild = p->rchild;
            p->rchild = r;
        }
        if (p->lchild != NULL)
            InsertQueue(q, p->lchild);
        if(p->rchild!=NULL)
            InsertQueue(q, p->rchild);
    }
    return 0;
}

输出：

输入二叉树的前序序列，#代表空子树:
ABD##E##C##
二叉树创建成功！
该二叉树的层次遍历序列是：ACBED

试题8（王道5.3.3节第10题）：

假设二叉树采用二叉链存储结构存储，设计算法求先序遍历序列中第k个结点的值。

这里使用一个计数器即可：

//输出前序遍历的第x个元素
void PreOrderx(BiTree T,int x){
    int a = 0;
    BiTree p = T; //p是遍历指针
    Sqstack S;
    InitStack(S);
    while(p != NULL|| !IsStackEmpty(S)){
        if(p){
            a = a + 1;
            if(a == x){
                printf("第%d个元素是：%c", x, p->data);
                break;
            }  
            InsertSqstack(S, p);
            p = p->lchild;
        }
        else{
            p = DeleteSqstack(S, p);
            p = p->rchild;
        }
    }
}

当然也可以采用递归，注意这里的计数器必须写在全局变量里，否则每次调用递归都会从零开始：

//输出前序遍历的第x个元素
int a = 0;  //计数器
void PreOrderx(BiTree T,int x){
    if (T!=NULL){
        a = a + 1;
        if(a==x)
            printf("前序遍历序列的第%d个元素是：%c", x, T->data);
        PreOrderx(T->lchild,x);
		PreOrderx(T->rchild,x);
	}
}
 
int main(){
    BiTree T;
    printf("输入二叉树的前序序列，#代表空子树:\n");
    CreateBiTree(T);
    printf("二叉树创建成功！\n");
    PreOrderx(T, 3);
    return 0;
}

输出：

输入二叉树的前序序列，#代表空子树:
ABD##E##C##
二叉树创建成功！
前序遍历序列的第3个元素是：D

试题9（王道5.3.3节第11题）：

已知二叉树以二叉链表存储，编写算法完成：对于树中的每个值为x的结点，删去以它为根的子树，并释放相应空间。

仍然是与层次遍历结合：

//这个函数用来删除树T
void Free(BiTree &T){
    if(T!=NULL){
        Free(T->lchild);
        Free(T->rchild);
        free(T);
    }
}
 
//对值为x的结点，删除以它为根的子树
void Freex(BiTree &T,char x){
    Queue q;
    InitQueue(q);
    BiTree p = T;
    InsertQueue(q, p);
    while(!IsQueueEmpty(q)){
        p = DeleteQueue(q, p);
        if(p->data == x){
            Free(p->lchild);  //这样写保留了当前结点
            Free(p->rchild);
            p->lchild = NULL;
            p->rchild = NULL;
        }
        if(p->lchild!=NULL)
            InsertQueue(q, p->lchild);
        if(p->rchild!=NULL)
            InsertQueue(q, p->rchild);
    }
}
 
int main(){
    BiTree T;
    printf("输入二叉树的前序序列，#代表空子树:\n");
    CreateBiTree(T);
    printf("二叉树创建成功！\n");
    printf("当前二叉树的层次遍历序列是：");
    LevelOrder(T);
    printf("\n");
    Freex(T, 'B');  //删除以B为根结点的树
    printf("当前二叉树的层次遍历序列是：");
    LevelOrder(T);
    printf("\n");
    return 0;
}

输出：

输入二叉树的前序序列，#代表空子树:
ABD##E##C##
二叉树创建成功！
当前二叉树的层次遍历序列是：ABCDE
当前二叉树的层次遍历序列是：ABC
 
输入二叉树的前序序列，#代表空子树:
ABD###CE##F##
二叉树创建成功！
当前二叉树的层次遍历序列是：ABCDEF
当前二叉树的层次遍历序列是：ABCEF

试题10（王道数据结构5.3.3节第12题）：

编写算法打印值为x的结点的所有祖先，假设值为x的结点不多于一个。

此题的算法十分典型：它用的是非递归后序遍历算法，这种算法需要借助栈来实现，当访问到值为x的结点的时候，栈中所有元素就是该结点的祖先，依次打印输出即可。有关非递归后序遍历算法的代码在上一节。

//寻找给定结点的所有祖先结点，采用后续遍历的非递归算法
void FindParents(BiTree T,char x){
    Sqstack S;
    InitStack(S);
    BiTree p = T;
    BiTree r = NULL;  //r用来记录访问结点的前一个结点
    while(p||!IsStackEmpty(S)){
        if(p){
            InsertSqstack(S, p);
            p = p->lchild;
        }
        else{
            p = S.data[S.top];  //读栈顶元素（但不出栈）
            if(p->rchild&&p->rchild!=r){
                p = p->rchild;
            }
            else{
                p = DeleteSqstack(S, p);
                if(p->data == x){
                    printf("%c", p->data);
                    break;
                }
                r = p;
                p = NULL;
            }
        }
    }
    while(!IsStackEmpty(S)){  //这个时候栈里的元素全部是结点的祖先
        p = DeleteSqstack(S, p);
        printf("%c", p->data);
    }
}
 
int main(){
    BiTree T;
    printf("输入二叉树的前序序列，#代表空子树:\n");
    CreateBiTree(T);
    printf("二叉树创建成功！\n");
    printf("当前二叉树的层次遍历序列是：");
    LevelOrder(T);
    printf("\n");
    printf("当前二叉树中结点E的祖先结点是：");
    FindParents(T, 'E');
    return 0;
}

输出：

输入二叉树的前序序列，#代表空子树:
ABD##E##C##
二叉树创建成功！
当前二叉树的层次遍历序列是：ABCDE
当前二叉树中结点E的祖先结点是：EBA

试题11（王道数据结构5.3.3节第13题）：

给出二叉链树中两个结点的指针p和q，试编写算法求解p和q的公共祖先结点r。

此题和上一题很像，分别求出p和q的祖先然后比较即可。

//寻找给定结点的所有祖先结点，采用后续遍历的非递归算法，和上一题不同的是，本题以栈的形式返回
Sqstack FindParents(BiTree T,char x){
    Sqstack S;
    InitStack(S);
    BiTree p = T;
    BiTree r = NULL;  //r用来记录访问结点的前一个结点
    while(p||!IsStackEmpty(S)){
        if(p){
            InsertSqstack(S, p);
            p = p->lchild;
        }
        else{
            p = S.data[S.top];  //读栈顶元素（但不出栈）
            if(p->rchild&&p->rchild!=r){
                p = p->rchild;
            }
            else{
                p = S.data[S.top];
                if(p->data == x){
                    break;
                }
                p = DeleteSqstack(S, p);
                r = p;
                p = NULL;
            }
        }
    }
    return S;
}
//有了两个栈我们就可以遍历然后找到祖先结点了
//注意这里最差也能返回整棵二叉树的根结点，或者返回其中一个结点时，代表一个结点就是另一个结点的祖先
BiTree FindSameParents(BiTree T,char a,char b){
    Sqstack S1 = FindParents(T, a);
    Sqstack S2 = FindParents(T, b);
    int same = -1;  //same用来遍历两个栈，并指向最后一个相同的祖先结点
    while(S1.data[same+1] == S2.data[same+1]){
        same = same + 1;
    }
    printf("%c", S1.data[same]->data);
    return S1.data[same];
}
 
int main(){
    BiTree T;
    printf("输入二叉树的前序序列，#代表空子树:\n");
    CreateBiTree(T);
    printf("二叉树创建成功！\n");
    printf("当前二叉树的层次遍历序列是：");
    LevelOrder(T);
    printf("\n");
    printf("当前二叉树中结点E，F的祖先结点是：");
    FindSameParents(T, 'E', 'F');  //求E,F的祖先结点
    return 0;
}

输出：

输入二叉树的前序序列，#代表空子树:
ABD###CE##F##
二叉树创建成功！
当前二叉树的层次遍历序列是：ABCDEF
当前二叉树中结点E，F的祖先结点是：C

试题12（王道数据结构5.3.3节第14题）：

假设二叉树采用二叉链表存储，设计一个算法求非空二叉树的宽度（也就是结点数最多的那一层的结点个数）。

此题仍然可以利用层次遍历把每层的结点数输出，存在一个数组里面然后找出最大值：

//求非空二叉树的宽度，借助层次遍历把每层的结点数都求出来
int LevelOrderWidth(BiTree T){
    Queue q;
    InitQueue(q);
    BiTree p = T;
    InsertQueue(q, p);
    int a = q.front;  //a指针指向这一层的第一个结点
    int b = q.rear;  //b指针指向这一层的第一个结点
    int num = 1;     //输出这一层的结点个数
    int numarray[10];  //把各层的结点个数存在一个数组里
    int depth = 0;  //深度，实际深度是depth+1，因为numarray数组下标从0开始
    numarray[depth] = num;
    while(!IsQueueEmpty(q)){
        if(q.front == b){  //说明这一层出完了
            a = q.front;  //a指向下一层第一个结点
            b = q.rear;  //b指向下一层最后一个结点
            num = (b - a > 0) ? (b - a) : (b - a + MAXSIZE);  //循环队列三目运算符判断
            depth = depth + 1;
            numarray[depth] = num;
        }
        p = DeleteQueue(q, p);
        if(p->lchild!=NULL)
            InsertQueue(q, p->lchild);
        if(p->rchild!=NULL)
            InsertQueue(q, p->rchild);
    }
    //到此numarray存储了每层的结点数，接下来找其中的最大值输出
    num = 1;
    for (int i = 0; i <= depth;i++){
        printf("%d", numarray[i]);
        if(numarray[i] > num)
            num = numarray[i];
    }
    return num;
}
 
int main(){
    BiTree T;
    printf("输入二叉树的前序序列，#代表空子树:\n");
    CreateBiTree(T);
    printf("二叉树创建成功！\n");
    printf("当前二叉树的层次遍历序列是：");
    LevelOrder(T);
    printf("\n");
    printf("各层的结点数是：");
    printf("二叉树的宽度是：%d",LevelOrderWidth(T));
    return 0;
}

输出：

输入二叉树的前序序列，#代表空子树:
ABDF##G##E##CH###
二叉树创建成功！
当前二叉树的层次遍历序列是：ABCDEHFG
各层的结点数是：1232二叉树的宽度是：3

试题13（王道数据结构5.3.3节第15题）：

设有一棵满二叉树（所有结点值均不同），已知先序序列pre，设计算法求后序序列post。

此题和前面的试题4也就是根据前序序列和中序序列建立二叉树的算法高度相似，也是要用递归解决，甚至此题比试题4简单，因为满二叉树左右子树的长度必然一样。

//根据满二叉树的前序序列求后序序列
void PreToPost(ElemType pre[],int l1,int h1,ElemType post[],int l2,int h2){
    //l1和h1工作在pre前序序列，l2和h2工作在post后序序列
    if(h1>=l1){
        post[h2] = pre[l1];
        int length = (h1 - l1) / 2;
        PreToPost(pre, l1 + 1, l1 + length, post, l2, l2 + length - 1);
        PreToPost(pre, l1 + length + 1, h1, post, l2 + length, h2 - 1);
    }
}
 
int main(){
    ElemType pre[7] = {'A', 'B', 'C', 'D', 'E', 'F', 'G'};
    ElemType post[7];
    PreToPost(pre, 0, 6, post, 0, 6);
    printf("后序序列是：");
    for (int i = 0; i <= 6; i++){
        printf("%c", post[i]);
    }
    return 0;
}

输出：

后序序列是：CDBFGEA