（线索）二叉树遍历练习
|
|
数据结构

5463 字
|
1.1 小时

非算法题

1、若一棵二叉树的前序遍历为a,e,b,d,c，后序遍历序列为b,c,d,e,a，则根结点的孩子结点可能是？

2、先序序列为a,b,c,d的不同二叉树的个数是？

阿Q先开始做这题还是把所有情况大致给画出来了（5 + 5 + 2 + 2）

如果就这样，这题阿Q就不会记录下来滴。

来换个思路：

我们已经知道先序序列 + 中序序列 能唯一的确定一棵二叉树，那么此题的思路就变成了：给出一个先序序列，有多少种后序序列呢？

那先序序列和后序序列间有什么关系嘛？王道书上原话：先序序列和中序序列的关系相当于：以先序序列为入栈次序，以中序序列为出栈次序，怎么理解这句话呢？看下图：

阿Q觉得很神奇，这样就把问题 先序序列为a,b,c,d的不同二叉树的个数 转化为了 入栈次序a,b,c,d 有多少种出栈次序？ 答案就显而易见了，为卡特兰数 1/(n + 1) * C(2n , n) = 1/(4 + 1) * C(8, 4) = 14 种。

当然先序序列中元素各不相同，才能满足上述条件哦。

算法题

二叉树（二叉链表存储）

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

// 和正常的层次遍历对称，可以用栈处理
void InvertLevel(Btree T){
    SqQueue Q;
    InitQueue(Q);
    SqStack S;
    InitStack(S);

    BtNode* Ptr = T;
    EnQueue(Q,Ptr);

    // 正常的层次遍历
    while(!QueueEmpty(Q)){
        DeQueue(Q,Ptr); 
        Push(S,Ptr);   // 出队 即 入栈
        
        if(Ptr->lchild) EnQueue(Q,Ptr->lchild);
        if(Ptr->rchild) EnQueue(Q,Ptr->rchild);
    }
    // 出栈 即为 自下而上、从右到左
    while(!StackEmpty(S)){
        Pop(S,Ptr);
        std::cout<< Ptr->data << "  ";
    }
}

2、设计一个非递归算法求二叉树的高度

阿Q首先对这题的思路是利用后序遍历，每个结点都算其当前的深度height，外层MaxHeight记录height的最大值，最后返回最大值即为二叉树的高度。

但阿Q就是没想用层次遍历/(ㄒoㄒ)/~~，用last记录每层的最右结点（注意：last[0]-当前层的最右结点，last[1]-去找下一层的最右结点，不能理所当然的认为当前层的最右结点的右孩子是下一层的最右结点），用level记录层数，很简单的解决了此问题；而且用这个方法可以用来处理 如：层的结点个数、树的最大宽度问题（如11题）。

int BtHeight(Btree T)
{   
    // 层次遍历解决该问题
    SqQueue Q;
    InitQueue(Q);

    BtNode *ptr = T;
    EnQueue(Q,ptr);

    // last[0]指针指向每层的最右结点；last[1]去找下一层的最右结点
    BtNode *last[2];
    last[0] = T;
    // level记录层数
    int level = 0;
    
    // 层次遍历
    while(!QueueEmpty(Q)){
        DeQueue(Q,ptr);
        if(ptr->lchild) {
            EnQueue(Q,ptr->lchild);
            last[1] = ptr->lchild;
        }
        if(ptr->rchild){
            EnQueue(Q,ptr->rchild);
            last[1] = ptr->rchild;
        }
        // 若此时的 ptr即为该层的最右结点，需要更新last指针和level值
        if(ptr == last[0]){
            level++;
            // last = ptr->rchild; // 找下一层last存在问题（不能理所当然的认为当前层的最右结点有右孩子）
            last[0]= last[1];
        }
    }
    return level;
}

课本中的解法为：用数组模拟队列（用下标移动代替出队操作），front指向逻辑出队元素下标，last指向下一层最右结点的下标，rear指向此时最后进队元素的下标，若front走到了last处，说明当前层结束，rear（不一定为 2 * i + 1 哟）赋值给last即可。

// 王道书中解法
int BtHeight_BOOK(Btree T){
    // 用数组模拟队列（用下标移动代替出队操作）
    // front指向逻辑出队元素下标，last指向下一层最右结点的下标，rear指向此时最后进队元素的下标

    BtNode *A[100];  // 申请足够大的数组空间
    int front, last, rear;
    front = rear = -1;

    BtNode *ptr;

    // 模拟队列
    A[++rear] = T;

    // 记录第一层最右元素
    last = rear;

    // 记录层数
    int level = 0;

    // 层次遍历
    while(front < rear){
        ptr = A[++front];
        if(ptr->lchild) A[++rear] = ptr->lchild;
        if(ptr->rchild) A[++rear] = ptr->rchild;

        // 若此时出队元素为当前层最右结点
        if(front == last){
            // 记录下一层的最右结点
            last = rear;
            level++;
        }
    }
    return level;
}

这题用递归去解决阿Q不建议，详情看递归遍历应用中的解法。

3、设一棵二叉树中各结点的值各不相同，其先序遍历序列和中序遍历序列分别存于两个一维数组A[1…n]和B[1…n]中，编写算法建立该二叉树 （有难度的）

首先要确定函数参数：

  • 数组 A、数组 B
  • 当前子树的 先序遍历的左右边界 及 中序遍历的左右边界

参数 有 2 + 2 + 2 = 6个

难点：怎么确定当前子树 先序遍历的左右边界 及 中序遍历的左右边界呢？看下图：

左子树：preleft更新为 preleft + 1， preright 更新为 preright – rlen（或者：preleft + llen）；inleft 仍为 inleft (当i = inleft, llen = 0，说明左子树建完了)，inright 更新为 inright + llen -1（或者：inright – rlen – 1）。
右子树：preleft 更新为 prerigt – rlen + 1（或者：preleft + llen + 1）；intleft 更新为 inright – rlen + 1（或者：inleft + len + 1）；preright 和 inright 不变（i = inright，rlen = 0，说明右子树建完了）。

说明递归中存在局部变量 rlen 和 llen，每个递归层都有不同的rlen和llen的值。（阿Q曾在此处犯了低级错误：用全局变量 rlen 和 llen，导致每层递归的时候都会覆盖掉上一层递归的 rlen 和 llen值）

// 数组中元素个数
#define n 5

// 返回创建的二叉树
// 调用时 preleft = inleft = 1; preright = inright = n; （此处阿Q就设置了默认参数）
Btree Pre_In_OrderCreateBtree(BtElemtype A[], BtElemtype B[], int preleft = 1, int preright = n, int inleft = 1, int inright = n){

    // 当前先序序列的第一个元素即为 （子树）根结点
    BtNode *root = new BtNode;
    root->data = A[preleft];

    // 找该元素在 中序序列的位置
    int i = inleft;
    while(B[i] != root->data) i++;

    // 找到了，局部变量 llen 和 rlen 保存当前层递归的左子树结点个数和右子树结点个数
    int llen = i - inleft;
    int rlen = inright - i;

    // 更新细节见图示
    if(llen){
        root->lchild = Pre_In_OrderCreateBtree(A, B, preleft + 1, preleft + llen , inleft, inleft + llen -1);
    }else{
        root->lchild = nullptr;  // 左子树已经建立完了
    }

    if(rlen){
        root->rchild = Pre_In_OrderCreateBtree(A, B, preright - rlen + 1, preright, inright - rlen + 1, inright);
    }else{
        root->rchild = nullptr; //右子树建立完了
    }
    return root;
}
// 测试
int main()
{
    BtElemtype A[6];
    A[1] = 'A';
    A[2] = 'B';
    A[3] = 'D';
    A[4] = 'E';
    A[5] = 'C';

    BtElemtype B[6];
    B[1] = 'D';
    B[2] = 'B';
    B[3] = 'E';
    B[4] = 'A';
    B[5] = 'C';

    Btree T = Pre_In_OrderCreateBtree(A,B);
    LevelOrder(T);
    return 0;
}
/*
输出结果：
A  B  C  D  E 
*/

4、编写一个判别给定二叉树是否为完全二叉树的算法

阿Q：用层次遍历过一遍数，node 记录结点总数，level 记录 树层数，最后判断（node == 2^level – 1）

或者 层次遍历不进行结点 左右孩子为空的判断，全部入队。当第一次检测到 null 时，再将当前队列元素全部出队，如果出队元素中有 真实结点（不为null），则说明不是完全二叉树。（若队列中全存null，说明树没结点了） 

bool ISCompleteBiTree(Btree T){
    SqQueue(Q);
    InitQueue(Q);

    BtNode *ptr = T;
    EnQueue(Q,ptr);

    // 层次遍历
    while(!QueueEmpty(Q)){
        DeQueue(Q,ptr);

        // 若ptr为空，则将当前队列全部出队，若有真实结点，则不为完全二叉树
        if(!ptr){
            while(!QueueEmpty(Q)){
                DeQueue(Q,ptr);
                if(ptr) return false;
            }
        }else{
            //否则 直接将左右孩子进队（不判断是否为空 ）
            EnQueue(Q,ptr->lchild);
            EnQueue(Q,ptr->rchild); 
        }
    }
    return true;
}

5、设计一个算法，计算一棵给定二叉树的所有双分支结点个数

阿Q解法：n2 = n0 + 1 （因此只需要计算叶子结点的个数即可）

其实用个层次遍历 + 判断就能 得到 所有分支 n0 ，n1，n2 的结果

int TwokidsNode(Btree T){
    SqQueue Q;
    InitQueue(Q);

    BtNode *ptr = T;
    EnQueue(Q, ptr);

    int n2 = 0; // 记录双分支结点个数
    // 层次遍历
    while(!QueueEmpty(Q)){
        DeQueue(Q,ptr);
        if(ptr->lchild && ptr->rchild) n2++;
        if(ptr->lchild) EnQueue(Q,ptr->lchild);
        if(ptr->rchild) EnQueue(Q,ptr->rchild);
    }
    return n2;
}

王道课本上使用了递归的思路，但阿Q觉得这种简单题无需使用递归。

int TwokidsNode(Btree T){
    // 空结点
    if(!T) return 0;

    // 双分支结点
    else if(T->lchild && T->rchild) return TwokidsNode(T->lchild) + TwokidsNode(T->rchild) + 1;

    // 单分支结点
    else return TwokidsNode(T->lchild) + TwokidsNode(T->rchild);
}

6、编写一个将二叉树中所有结点的左、右子树进行交换的函数

void swapNode(Btree &T){
    /*
        递归过程 十分简洁：
            1、交换 当前结点的左孩子的 左右子树
            2、交换 当前结点的右孩子的 左右子树
            3、交换当前结点的左右子树
    */
    if(T){
        swapNode(T->lchild);
        swapNode(T->rchild);

        BtNode *tmp;
        tmp = T->lchild;
        T->lchild = T->rchild;
        T->rchild = tmp;
    }
}

由于后序遍历中访问顺序有 沿右支返回的情况，因此阿Q就利用这段返回的路径来修改左右子树（非递归），详解看下图：

void swapNode(Btree &T){
    SqStack S;
    InitStack(S);
 
   Btree Ptr = T;
   Btree Pre = NULL;
   while(Ptr || !StackEmpty(S))
   {
        while(Ptr)
        {
            Push(S,Ptr);
            Ptr = Ptr->lchild;
        }

        GetTop(S,Ptr);

        if(Ptr->rchild && Ptr->rchild != Pre)   Ptr = Ptr->rchild;

        else   
        {
            // 沿右支返回
            if(Ptr->rchild == Pre){
                // 交换左右子树
                BtNode *tmp = Ptr->lchild;
                Ptr->lchild = Ptr->rchild;
                Ptr->rchild = tmp;
            }
            Pop(S,Ptr);
            Pre = Ptr;
            Ptr = NULL;
        }
   }
}

7、设计一个算法，求先序遍历序列中第k个结点的值（1 <= k <= n）

// 直接非递归解决呗
BtElemtype GetPreOrder_NValue(Btree T, int n)
{
    SqStack S;
    InitStack(S);

    Btree Ptr = T;

    // 记录当前访问的结点次序
    int k = 0;

    while(Ptr || !StackEmpty(S))
    {
        if(Ptr){
            Push(S,Ptr);
            k++;
            // 判断k是否为n
            if(k == n) break;

            Ptr = Ptr->lchild;
        }
        else{
            Pop(S, Ptr);
            if(!Ptr->rchild) Ptr = nullptr;
            else Ptr = Ptr->rchild;
        }
    }
    return Ptr->data;
}

王道课本中使用的是递归解法

// 设置全局变量，记录当前访问次序
int i = 1;
BtElemtype GetPreOrder_NValue_BOOK(Btree T, int n)
{
    /*
        可能情况：
            当前结点为空 - 返回特殊字符 '？'
            
            当前结点先序遍历次序为n，返回结果

            否则 遍历 左子树，遍历右子树
    */

    if(!T) return '?';

    if(i == n) return T->data;

    i++;

    BtElemtype ch = GetPreOrder_NValue_BOOK(T->lchild, n);
    if(ch != '?') return ch;

    ch = GetPreOrder_NValue_BOOK(T->rchild, n);
    return ch;
    
}

阿Q觉得 这个递归完成反而有点绕。

8、编写算法完成：对于树中每个元素值为x的结点，删除以它为根的子树，并释放空间

阿Q解法：后序遍历非递归完成，用 deletptr 指向第一个元素值为x的结点，后序遍历删除该结点的左右子树，再返回到 deletptr的位置时，将 deletptr指向NULL。

但此处存在问题，即：双亲结点的左/右指针置空操作难解决，不置空变成野指针咯
阿Q的处理办法：用 delParent 指向 第一个元素值为 x 的双亲结点，用 tag 记录待删结点为双亲结点的哪个分支，如图：

但有个问题：根结点的值为待删除元素呢？还得单独判断。
void DestoryTree(Btree &T){
    if(T){
        DestoryTree(T->lchild);
        DestoryTree(T->rchild);
        delete T;
        T = nullptr; // 注意：防止悬空指针出现
    }
}

void DeleteX_Btree(Btree &T, BtElemtype x){
    if(T){
        // 单独判断
        if(T->data == x){
            DestoryTree(T);
            return;
        }
        LiStack S;
        InitStack(S);
    
        Btree Ptr = T;
        Btree Pre = nullptr;

        // 记录待删除结点的双亲结点
        BtNode *delParent = nullptr;
        
        // 记录待删除结点在双亲结点的哪个分支上  0 - 左分支    1 - 右分支
        int tag = -1;

        while(Ptr || !StackEmpty(S)){
            while(Ptr){
                Push(S,Ptr);

                // 待删除指针为空才记录 (记录的永远是最上层的结点)
                if(delParent == nullptr && Ptr->lchild && Ptr->lchild->data == x){
                    delParent = Ptr;
                    // 在左孩子上
                    tag = 0;
                }

                Ptr = Ptr->lchild;
            }

            GetTop(S,Ptr);

            if(Ptr->rchild && Ptr->rchild != Pre) {
                // 某结点右孩子结点值为 x
                if(delParent == nullptr && Ptr->rchild && Ptr->rchild->data == x){
                    delParent = Ptr;
                    tag = 1;
                }
                Ptr = Ptr->rchild;
            }else  {
                Pop(S,Ptr);
                // 若待删除结点存在
                if(delParent){
                    // 当前出栈结点为 delparent左孩子，delparent左指针置空
                    if(tag == 0 && delParent->lchild == Ptr){
                        delParent->lchild = nullptr;
                        tag = -1;
                        delParent = nullptr;
                    }
                    // 当前出栈结点为 delparent右孩子, delparent右指针置空
                    else if(tag == 1 && delParent->rchild == Ptr){
                        delParent->rchild = nullptr;
                        tag = -1;
                        delParent = nullptr;
                    }
                    delete Ptr;
                }
                Pre = Ptr;
                Ptr = nullptr;
            }
        }
    }
}

经测试有效，但阿Q觉得比较麻烦（阿Q经典嫌弃自己），王道书上的解法思路相对简单。

用层次遍历去解决此问题，思路描述：

扫描到当前结点的左孩子，若存在且值为待删元素，遍历删除以左孩子为根的左子树，让当前结点的左指针设为空；否则经过正常的层次遍历操作。右孩子同理。

void DeleteTree(Btree &T){
    if(T){
        DeleteTree(T->lchild);
        DeleteTree(T->rchild);
        delete T;
        T = nullptr;  // 置空指针
        // 删除节点后，父节点的指针未置空会导致成为悬空指针。后续遍历时访问了已释放的内存，输出残留数据。
    }
}

// 对于树中每个元素值为x的结点，删除以它为根的子树，并释放空间
void LevelSearch(Btree &T, BtElemtype x){
    if(T){
        // 根节点的值为待删元素情况
        if(T->data == x){
            DeleteTree(T);
            return;
        }
        SqQueue Q;
        InitQueue(Q);

        BtNode *ptr = T;
        EnQueue(Q, ptr);

        // 层次遍历
        while(!QueueEmpty(Q)){
            DeQueue(Q,ptr);
            
            // 若左孩子存在
            if(ptr->lchild){
                // 左孩子的值为待删元素
                if(ptr->lchild->data == x){
                    DeleteTree(ptr->lchild);
                    ptr->lchild = nullptr;
                }else{
                    // 正常的层次遍历
                    EnQueue(Q, ptr->lchild);
                }
            }

            // 若右孩子存在
            if(ptr->rchild){
                // 右孩子为待删元素
                if(ptr->rchild->data == x){
                    DeleteTree(ptr->rchild);
                    ptr->rchild = nullptr;
                }else{
                    // 正常的层次遍历
                    EnQueue(Q, ptr->rchild);
                }
            }
        }
    }
}

9、在二叉树中查找值为x的结点，编写算法 – 打印值所有为x的结点的所有祖先

打印某结点的祖先结点，可以利用后序非递归实现，当出栈结点值为x时，访问此时栈内所有结点即为该结点的所有祖先。此题要求打印所有为x的结点的所有祖先，因此不能直接出栈所有结点（不能扰乱后序遍历过程），当然可以用两个栈来实现。

有方便的解法嘛？用数组去模拟栈咯（访问操作就不再是只能访问栈顶元素，而是整个栈内的元素）

void Print_X_Ancestors(Btree T, BtElemtype x){
    BtNode* S[100];  //申请足够大的空间

    // top指向当前栈顶的下一个元素
    int top = 0;

    BtNode *ptr = T;

    BtNode* pre = nullptr;
    
    // 记录有多少个结点值为 x
    int k = 0; 

    // 后序非递归
    while(ptr || top){
        // 进左支
        while(ptr){
            S[top++] = ptr;
            ptr = ptr->lchild;
        }
        // 取栈顶元素
        ptr = S[top - 1];
        
        // 若右孩子存在且 右孩子不是上一个访问结点，直接进入右子树
        if(ptr->rchild && ptr->rchild != pre){
            ptr = ptr->rchild;
        }else {
            // 访问操作
            ptr = S[--top];
            // 若当前结点的值为 x，则访问栈内结点
            if(ptr->data == x){
                k++;
                std::cout << "n." << k << " ancestors: ";
                for(int i = 0; i < top; i++){
                    std::cout << S[i]->data << " ";
                }
                std::cout << std::endl;
            }
            pre = ptr;
            ptr = nullptr;
        }
    }
}

王道课本中后序非递归算法实现新增了数据成员 tag，代替了 pre指针，阿Q觉得麻烦了


typedef struct{
    Btree t;
    int tag;  // tag - 0，本次顺着左支经过;  1 - 本次顺着右支经过 
}Stack;

10、设一棵二叉树的结点结构为（LLINK，INFO，RLINK），ROOT为指向该二叉树根结点的指针，p和q分别为指向该二叉树中任意两个结点的指针，试编写算法ANCESTOR(ROOT, p, q)，找到p和q的最近公共祖先r

用数组去模拟栈操作（查找 就不会局限于 栈顶）

// 后序非递归实现
BtNode* Ancestor(Btree Root, BtNode *p, BtNode *q){
    BtNode* S[100];  // 申请足够大的空间
    int top1 = 0;

    // 还需一个辅助模拟栈，当找到第一个结点时需要将 数组S 复制到 辅助数组内
    BtNode* Assist[100];
    int top2 = 0;
    
    // 此处存在一个问题：不知道p和q的先后顺序，如何解决？
    // 1、再给一个辅助模拟栈
    // 2、用tag 记录 p或q数组 是否复制到了 辅助数组内 (0 - 未复制   1 - 已复制)
    int tag = 0;

    BtNode *ptr = Root;
    BtNode *pre = nullptr;

    while(ptr || top1){
        while(ptr){
            S[top1++] = ptr;
            ptr = ptr->LLINK;
        }

        // 取栈顶元素
        ptr = S[top1 -1];

        // 进栈右支情况
        if(ptr->RLINK && ptr->RLINK != pre){
            ptr = ptr->RLINK;
        }else {
            // 进行访问操作
            ptr = S[--top1];

            if(ptr == p || ptr == q){
                // 若辅助数组 未被填充
                if(!tag){
                    for(int i = 0; i < top1; i++) Assist[top2++] = S[i];
                    tag = 1;
                }else{
                    // p数组 和 assist数组 进行对比即可（需要注意的是：S数组需要栈顶往回退 找最近的公共祖先）
                    for(int i = top1; i > -1; --i)
                        for(int j = 0; j < top2; j++)
                            if(S[i] == Assist[j]) return S[i];
                }
            }
            pre = ptr;
            ptr = nullptr;
        }
    }
    return nullptr;  // p 和 q 无公共祖先
}

11、设计算法，求非空二叉树b的宽度（即具有结点数最多的那一层的结点个数）

思路见 第2题

int BtWidth(Btree T)
{   
    if(!T) return 0;
    // 层次遍历解决该问题
    SqQueue Q;
    InitQueue(Q);

    BtNode *ptr = T;
    EnQueue(Q,ptr);

    BtNode *last[2];
    last[0] = T;
    // MaxLevelNode 记录各层结点数的最大值
    int MaxLevelNode = 0; 
    // LevelNode 记录各层结点数
    int LevelNode = 0;
    
    // 层次遍历
    while(!QueueEmpty(Q)){
        DeQueue(Q,ptr);
        LevelNode++;
        if(ptr->lchild){
            EnQueue(Q,ptr->lchild);
            last[1] = ptr->lchild;
        }
        if(ptr->rchild){
            EnQueue(Q,ptr->rchild);
            last[1] = ptr->rchild;
        }
        // 若此时的 ptr即为该层的最右结点，需要更新相应指针及变量值
        if(ptr == last[0]){
            last[0] = last[1];
            if(LevelNode > MaxLevelNode) MaxLevelNode = LevelNode;
            LevelNode = 0;
        }
    }
    return MaxLevelNode;
}
// 王道书中解法
int BtWidth_BOOK(Btree T)
{   
    BtNode *A[100]; // 申请足够大空间

    int front, rear, last;
    front = rear = -1;

    BtNode *ptr = T;

    A[++rear] = ptr;
    last = rear;

    // 记录 层的最大结点个数
    int MaxLevelNode = 0;
    
    // 记录每层的结点个数
    int LevelNode = 0;

    // 数组模拟队列
    while(front < rear){
        ptr = A[++front];
        LevelNode++;

        if(ptr->lchild) A[++rear] = ptr->lchild;
        if(ptr->rchild) A[++rear] = ptr->rchild;

        if(front == last){
            // 当前层结束
            last = rear;
            if(LevelNode > MaxLevelNode) MaxLevelNode = LevelNode;
            // 重新 计数下一层结点个数 
            LevelNode = 0;
        }
    }
    return MaxLevelNode;
}

12、设计一个算法将二叉树的叶结点按从左到右的顺序连成一个单链表，表头指针为head，链接时用叶结点的右指针域来存放单链表指针

这题 前/中/后序都能解决（访问叶结点都是从左到右），阿Q选择 中序解决此问题

BtNode* LinkLeafNode(Btree T){
    // preLeaf 指向 上一个叶子结点
    BtNode *preLeaf = nullptr;
    // 表头指针
    BtNode *head = nullptr;

    BtNode *ptr = T;
    SqStack S;
    InitStack(S);
    // 中序遍历
    while(ptr || !StackEmpty(S)){
        while(ptr){
            Push(S, ptr);
            ptr = ptr->lchild;
        }

        Pop(S, ptr);

        // 访问操作
        if(!ptr->lchild && !ptr->rchild){
            // 第一个叶子结点
            if(!preLeaf){
                head = ptr;
                preLeaf = ptr;
            }else {
                preLeaf->rchild = ptr;
                preLeaf = ptr;
            }
        }

        if(ptr->rchild) 
            ptr = ptr->rchild;
        else
            ptr = nullptr;
    }
    return head;
}

13、设计判断两棵二叉树是否相似的算法。所谓二叉树T1和T2相似，指的是T1和T2都是空的二叉树或都只有一个根结点；或T1的左子树和T2的左子树相似且T1的右子树和T2的右子树是相似的（结构相似）

此题当然可以两个树同时来一遍 遍历过程，若路劲不同 则 二叉树结构不同

此外此题递归算法思路清晰

bool similar(Btree T1, Btree T2){
    /*
        递归实现思路：
            1、若 T1 和 T2 为空树，则相同
            2、若 T1 和 T2 只有一个为空树，则不相同
            3、递归判断 T1 和 T2的左子树是否相同
            4、递归判断 T1和 T2的右子树是否相同
            5、返回3 && 4
    */

    if(!T1 && !T2) return true;
    else if(!T1 || !T2) return false;

    bool LeftSimilar = similar(T1->lchild, T2->lchild);
    bool RightSimilar = similar(T1->rchild, T2->rchild);
    return LeftSimilar && RightSimilar;
}

14、二叉树的带权路径长度（WPL）是二叉树中所有叶结点的带权路径长度之和。给定一棵二叉树T，结点结构为 （left，weight，right）。其中叶结点的weight域保存该结点的非负权值。设root为指向T的根结点的指针，请设计求T的WPL算法，要求：

1）给出算法的基本设计思路

2）给出二叉树结点的数据类型定义

3）根据设计思想，采用C/C++描述算法，关键之处给出注释

阿Q分析：累加所有 叶结点深度 * 权值。因此需要解决：

①每个叶结点的深度

②需维护累加变量

本题主要考点为：求每个叶结点的深度。

这题难度不大，用各个遍历都能解决（只需要 增加 · 全局/静态变量 wpl 记录带权路径长度； · 局部变量deep 记录当前深度即可）

阿Q下面用两种方法来解（先序递归 和 层次遍历）

2）二叉树结点的数据类型定义

typedef struct BtNode
{
    /* data */
    float weight;
    struct BtNode *left, *right;
    BtNode(float w = 0): weight(w), left(nullptr), right(nullptr){}
}BtNode,*Btree;
基于先序递归遍历的算法思想，用静态变量 wpl 记录带权路径长度，把每个结点的深度作为递归函数的一个参数deep（从0开始）传递，算法步骤如下：

若该结点为叶子结点，则 wpl = wpl + deep * weight

若该结点不为叶子结点，左子树不为空时，递归左子树；右子树不为空时，递归右子树；深度deep参数为本结点的深度参数 + 1。

最终返回wpl即可

代码如下：
float WPL_PreOrder(Btree T, int deep = 0){
    // 静态变量wpl (函数体外设置一个全局变量也行)
    static float wpl = 0;

    // 访问操作
    // 若为叶子结点
    if(!T->left && !T->right) wpl += deep * T->weight;

    // 若左子树不为空，递归左子树
    if(T->left) WPL_PreOrder(T->left, deep + 1);

    // 若右子树不为空，递归右子树
    if(T->right) WPL_PreOrder(T->right, deep + 1);

    // 返回静态变量 wpl的值
    return wpl;
}
基于层次遍历的算法思路，使用队列进行层次遍历，并需要记录当前的深度 deep，算法步骤如下：
当遍历到叶结点时，wpl = wpl + deep * weight

当遍历到非叶结点时，将子树进队

当遍历到当前深度的最后一个结点，deep = deep + 1

代码如下：
float WPL_LevelOrder(Btree T){
    // 局部变量 wpl记录带权路径长度
    float wpl = 0;

    // 用数组模拟队列
    BtNode* Q[100];  // 申请足够大空间
    int front, rear, last;
    
    rear = front = -1;

    // 层次遍历记录当前的深度(真实深度 - 1 - 路径长度)
    int deep = 0;

    BtNode *ptr = T;
    
    // 进队根结点
    Q[++rear] = ptr;
    last = rear;

    // 层次遍历
    while(front < rear){
        // 出队队头结点
        ptr = Q[++front];
        if(ptr->left) Q[++rear] = ptr->left;
        if(ptr->right) Q[++rear] = ptr->right;

        // 若出队为叶子结点 （此处与下一处的if判断不能颠倒，若颠倒，当前层的最右结点若是叶子结点，deep值会出现问题）
        if(!ptr->left && !ptr->right) wpl += ptr->weight * deep;
        
        // 若出队当前层的最后一个结点
        if(front == last){
            last = rear;
            deep++;
        }
    }
    
    return wpl;
}

15、设计一个算法，将给定的表达式树（二叉树）转换为等价的中缀表达式（通过括号反映操作符的计算次序）并输出。例如，当下列两棵表达式树作为算法输入时：

输出的等价中缀表达式分别为 (a + b) * (c * (-d)) 和 (a * b) + (-(c – d))

二叉树结点定义如下：

typedef struct node
{
    char data[10];     // 存操作数或操作符
    struct node *left, *right;
}Btree;

要求：

1）给出算法的基本设计思路

2）根据设计思想，采用C/C++语言描述算法，关键之处给出注释

阿Q分析（难表达，直接看图吧）：

在路径上判断操作符所处的deep，大于1路径上添加括号，否则直接输出

基于中序遍历策略，由于操作数均在叶子节点上，直接输出即可。当中序遍历访问到 操作符时，要判断其深度是否超过1，超过需要在遍历过程中加上左右括弧；否则直接输出操作符即可。

代码如下：

void BtreeToExp(Btree *T, int deep = 1){
    if(T){
        // 若为叶子节点（操作数），直接输出
        if(!T->left && !T->right) std::cout << T->data;
        // 否则为操作符
        else{
            // 若当前深度大于 1，需要加上左右括弧
            if(deep > 1) std::cout << "(";
            
            // 中序遍历
            BtreeToExp(T->left, deep + 1);
            // 访问该操作符
            std::cout << T->data;
            BtreeToExp(T->right, deep + 1);
            
            if(deep > 1) std::cout << ")";
        }
    }
}
为了方便测试，阿Q将结点定义修改如下 
#include <cstring> // 需要包含头文件以使用strncpy

typedef struct node{
    char data[10];
    struct node *left, *right;
    node(const char* d) : left(nullptr), right(nullptr) { // 使用const char*
        strncpy(data, d, 9); // 复制最多9个字符
        data[9] = '\0';      // 确保最后一个字符是终止符
    }
}Btree;

// 测试代码
int main(){
    Btree *root = new Btree("*");
    root->left = new Btree("+");
    root->left->left = new Btree("a");
    root->left->right = new Btree("b");

    root->right = new Btree("*");
    root->right->left = new Btree("c");
    root->right->right = new Btree("-");
    root->right->right->right = new Btree("d");

    BtreeToExp(root);

    return 0;
}

二叉树（顺序存储）

1、已知非空二叉树T的结点值均为正整数，数据结构定义如下：

typedef struct 
{
    int SqBiTNode[MAX_SIZE];  // MAX_SIZE为已定义常量
    int ElemNum;              // 实际占用的数组元素个数
}SqBiTree;

T中不存在的结点在数组SqBiTNode中用-1表示，例如下图的一颗非空二叉树T：

T的存储结果如下：

T1.SqBiTNode [ 40 , 25 , 60 , -1 , 30 , -1 , 80 , -1 , -1 , 27 ]
T1.ElemNum 10

设计一个尽可能高效的算法，判断一棵采用该方法存储的二叉树是否满足为二叉搜索树。要求：

1）给出算法的基本设计思路

2）根据设计思路，采用C/C++描述算法，关键之处给出注释

阿Q分析：二叉搜索树满足 左孩子结点值 < 当前结点值 < 右孩子结点值（左、根、右），那么中序遍历的序列必然是递增的。因此可以用中序遍历策略实现判断是否为二叉搜索树。

此外，还可以用层次遍历实现，每个结点依次与其左孩子和右孩子的值进行比较，若全满足 左 < 根 < 右，即为二叉搜索树。

根节点存在SqBiTNode[0]，那么对于 下标为 i 的结点，其左孩子下标为 2*i + 1，右孩子下标为 2*i + 2，双亲结点下标为 ( i – 1)/2 【与根结点存在 SqBiTNode[1] 不同】

采用中序递归遍历策略，采用静态变量 val 记录上一次访问结点的值，在中序遍历访问中比较当前结点和val的值，若 当前结点值 不大于 val，则不为二叉搜索树，若大于，则val 保留本结点值。

代码如下：
// 中序递归策略
// 需要全局记录中序遍历当前访问的值 val，需要有当前的结点下标(初始为0)
bool JudgeBST_InOrder(SeqBtree T, int index = 0){
    static int val = -2;  // 首先需要设置 val足够小（比中序遍历的第一个值要小）
    
    // 进入递归条件 (下标不能超过总结点数 && 当前结点需要有值)
    if(index < T.ElemNum && T.SqBiTNode[index] != -1){
        // 中序遍历
        // 左子树
        JudgeBST_InOrder(T, 2 * index + 1);

        // 根，访问操作
        // 若中序遍历 当前访问结点不比 val（上一个访问的结点）值大，则不为二叉搜索树
        if(T.SqBiTNode[index] <= val) return false;

        // 否则 val 记录本次访问的值
        val = T.SqBiTNode[index]; 

        // 右子树
        JudgeBST_InOrder(T, 2 * index + 2);
    }
    return true;  // 整个遍历都满足 左 < 根 < 右，则为二叉搜索树
}
将递归遍历改为非递归即可

代码如下：
// 中序非递归策略
bool JudgeBST_InOrder(SeqBtree T){
    int val = -2;

    // 栈内 存放 索引
    std::stack<int> INDEX;
    
    int index = 0;

    while(!INDEX.empty()){
        // 进栈左子树
        while(index < T.ElemNum && T.SqBiTNode[index] != -1){
            INDEX.push(index);
            index = 2 * index + 1;
        }

        // 根，访问操作
        // 出栈 栈顶结点
        index = INDEX.top();
        INDEX.pop();

        // 若中序遍历 当前访问结点不比 val（上一个访问的结点）值大，则不为二叉搜索树
        if(T.SqBiTNode[index] <= val) return false;
        // 否则 val 保存当前访问结点值
        val = T.SqBiTNode[index];

        // 访问右子树
        index = 2 * index + 2;
    }
    return true;
}
采用层次遍历策略，每个结点依次与其左孩子和右孩子的值进行比较，若全满足 左 < 根 < 右，即为二叉搜索树。

代码如下：
// 层次遍历策略
bool JudgeBST_LevelOrder(SeqBtree T){
    if(T.ElemNum <= 1) return true;
    
    // 倒数第二层的最右边下标 (最后一个节点的下标为 T.ElemNum - 1)
    int limit = (T.ElemNum - 2) >> 1;

    // 此处有个问题，若 T.ElemNum为偶数，则 2 * limit + 2 越界了，因此最后再判断
    for(int i = 0; i < limit; i++){
        // 当前节点不为空
        if(T.SqBiTNode[i] != -1){
            int leftchild = 2 * i + 1;
            int rightchild = 2 * i + 2;

            // 若左孩子存在，且左孩子的值 不小于 根结点，则不为二叉搜索树
            if(T.SqBiTNode[leftchild] != -1 && T.SqBiTNode[leftchild] >= T.SqBiTNode[i]) return false;

            // 若右孩子存在，且右孩子的值 不大于 根结点，则不为二叉搜索树
            if(T.SqBiTNode[rightchild] != -1 && T.SqBiTNode[rightchild] <= T.SqBiTNode[i]) return false;
        }
    }

    if(T.SqBiTNode[2 * limit + 1] >= T.SqBiTNode[limit]) return false;

    // T.ElemNum为偶数，则只需比较左孩子即可，否则需要比较右孩子
    if(T.ElemNum % 2 == 1)
        if(T.SqBiTNode[2 * limit + 2] <= T.SqBiTNode[limit]) return false;

    return true; // 全部结点都满足 左 < 根 < 右，则为二叉搜索树
}

满二叉树

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

一般的二叉树 先序和后序序列 是无法相互推导的，但是满二叉树却可以（左右子树结点数一致），具体过程如下：

用递归解决会很简洁，函数参数有：先序和后序数组，先序和后序边界 （6个）
终止条件：h1 < l1 ( 递归的倒数第二层 l1 = h1 => half = 0 ，最后一层 l1 => l1 + half + 1 = h1 + 1 > h1 )
typedef char BElemType;

#define n 7

// 由于先开始 先序边界和后序边界为 数组下标的上下界，阿Q就设置了默认值
void FullBiTree_PreToPost(BElemType Pre[], BElemType Post[], int l1 = 0, int h1 = n - 1, int l2 = 0, int h2 = n - 1){
    if(h1 >= l1){
        int half = (h1 - l1) >> 1;
        Post[h2] = Pre[l1];
        FullBiTree_PreToPost(Pre, Post, l1 + 1, l1 + half, l2, l2 + half -1);
        FullBiTree_PreToPost(Pre, Post, l1 + half + 1, h1, l2 + half, h2 - 1);
    }   
}

此题 和 二叉链表 算法题3 有点类似，都需要去模拟下一层递归的数组边界

线索二叉树

1、写出在中序线索二叉树里查找指定结点在后序的前驱结点的算法

在后序序列中，若结点p

  • 右孩子存在，则右孩子是其前驱
  • 若右孩子不存在，左孩子存在，则左孩子是其前驱
  • 若左右孩子均不存在，则需要沿中序左线索找到双亲结点 f
    • 若 f 有左孩子，则 f 的左孩子为结点p的前驱
    • 若 f 无左孩子，则需要沿中序前驱找双亲的双亲，直到找到第一个祖宗结点有左孩子，则此左孩子为结点p的前驱。（特殊的：若沿中序前驱找到双亲的双亲为NULL，则结点p无前驱）

如图：

// 写出在中序线索二叉树里查找指定结点在后序的前驱结点的算法
ThreadNode* InThreadTree_PreNodeInPoST(ThreadNode* node){
    // 右孩子存在，则右孩子是其前驱
    if(!node->rtag) return node->rchild;

    // 若右孩子不存在，左孩子存在，则左孩子是其前驱
    else if(!node->ltag) return node->lchild;

    // 若左右孩子均不存在，则需要沿中序左线索找到双亲结点 f
    if(node->ltag && node->rtag){
        ThreadNode *f = node->lchild;

        // 沿中序前驱找双亲的双亲，直到找到第一个祖宗结点有左孩子
        while(f){
            if(!f->ltag) return f->lchild;
            else f = f->lchild;
        }
        // 特殊的：若沿中序前驱找到祖宗为 NULL，则结点p无前驱 
        return nullptr;
    }
    return nullptr; // 结点node不在中序线索二叉树上
}
完整代码 

// 写出在中序线索二叉树里查找指定结点在后序的前驱结点的算法

#include<iostream>

typedef char ElemType;

typedef struct ThreadNode
{
    /* data */
    ElemType data;
    struct ThreadNode *lchild, *rchild;
    int ltag, rtag;
    // 方面建树,结构体初始化
    ThreadNode(ElemType x): data(x), lchild(nullptr), rchild(nullptr), ltag(0), rtag(0){}
}ThreadNode, *ThreadTree;

// 中序遍历 线索化 -> 中序线索二叉树
void InThread(ThreadNode *&P, ThreadNode *&Pre)
{
    // P指针不为NULL
    if(P)
    {
        // 线索化 左孩子
        InThread(P->lchild,Pre);
        
        // P的左子树为空
        // 说明当前访问结点的 中序遍历前驱 没有更改，因此要进行线索化
        if(!P->lchild)
        {
            // 访问当前结点，此处的访问为将 ltag设为1
            P->ltag = 1;
            P->lchild = Pre;
        }

        //若已经访问了结点（Pre不为空） && 上一个访问的结点的右子树为空:
        if(Pre && !Pre->rchild)
        {
            // 访问上一个结点，此处的访问为将 rtag设为1
            Pre->rtag = 1;
            Pre->rchild = P;
        }

        Pre = P;
        // 线索化 右孩子
        InThread(P->rchild,Pre);
    }
}

// 建立中序线索二叉树
void CreateInThread(ThreadTree &T)
{
    ThreadNode *Pre = nullptr;
    // 不是空树
    if(T)
    {
        InThread(T,Pre);
        // 处理最后一个访问结点的后继
        // 访问最后一个访问结点，此处的访问为将 rtag设置为1
        Pre->rtag = 1;
        Pre->rchild = nullptr;
    }
}


// 写出在中序线索二叉树里查找指定结点在后序的前驱结点的算法
ThreadNode* InThreadTree_PreNodeInPoST(ThreadNode* node){
    // 右孩子存在，则右孩子是其前驱
    if(!node->rtag) return node->rchild;

    // 若右孩子不存在，左孩子存在，则左孩子是其前驱
    else if(!node->ltag) return node->lchild;

    // 若左右孩子均不存在，则需要沿中序左线索找到双亲结点 f
    if(node->ltag && node->rtag){
        ThreadNode *f = node->lchild;

        // 沿中序前驱找双亲的双亲，直到找到第一个祖宗结点有左孩子
        while(f){
            if(!f->ltag) return f->lchild;
            else f = f->lchild;
        }
        // 特殊的：若沿中序前驱找到祖宗为 NULL，则结点p无前驱 
        return nullptr;
    }
    return nullptr; // 结点node不在中序线索二叉树上
}

int main(){
    ThreadTree Root = new ThreadNode('A');
    Root->lchild = new ThreadNode('B');
    Root->rchild = new ThreadNode('C');

    ThreadNode *p = new ThreadNode('D');
    Root->lchild->rchild = p;
    Root->rchild->lchild = new ThreadNode('F');

    ThreadNode *q = new ThreadNode('G');
    Root->rchild->rchild = q;

    CreateInThread(Root);

    ThreadNode* pre = InThreadTree_PreNodeInPoST(p);
    std::cout << "node-" << p->data << " PreNode In Post: ";
    if(pre) std::cout << pre->data << std::endl;
    else std::cout << "none" << std::endl;

    pre = InThreadTree_PreNodeInPoST(q);
    std::cout << "node-" << q->data << " PreNode In Post: ";
    if(pre) std::cout << pre->data << std::endl;
    else std::cout << "none" << std::endl;

    return 0;
}

/*
输出结果：
node-D PreNode In Post: none
node-G PreNode In Post: F
*/

总结

遍历算法是二叉树各种操作的基础。推荐常看

二叉树线索二叉树
暂无评论

发送评论 编辑评论 


				

			

						

				

					

						

							

								
							

							
						

					

				

				

					

						

							

								
							

							
						

					

				

				

					

						

							

								
							

							
							
													

					

				

			

			
			

				

					
				

			

				

											

							
							
						

																

							
							
						

																

							
							
						

										
					
									

			

			
			
		

	






上一篇
下一篇