【数据结构】二叉树自下而上从右到左遍历

谁践踏了优雅 2023-06-07 12:04 55阅读 0赞

二叉树自下而上从右到左遍历实际上就是层序遍历的逆向操作，下面是层序遍历的代码

void LayerOrder(BiTree BT) {
        if (BT == NULL)
            return;
        queue<BiTree> B;
        BiTNode *p = BT;
        B.push(p);
        while (!B.empty()) {
            p = B.front();
            if (p->lchild)
                B.push(p->lchild);
            if (p->rchild)
                B.push(p->rchild);
            cout<<p->data<<" ";
            B.pop();
        }
    }

遍历过程如图所示

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0RYSDkyNA_size_16_color_FFFFFF_t_70][]

可以看二叉树自下而上从右到左遍历实际上就是对这个队列进行反向输出，自然而然可以想到应该利用栈

所以可以直接在节点入队的同时压入栈中，当所有节点压入栈（队空）时，出栈的序列即为所求

#include<iostream>
    #include<queue>
    #include<stack>
    using namespace std;
    typedef struct BiTNode {
        char data;
        BiTNode *lchild, *rchild;
    }BiTNode, *BiTree;
    
    BiTree CreateBT() {
        BiTree BT;
        char a;
        cin>>a;
        if (a == '.')
            return NULL;
        BT = new BiTNode;
        BT->data = a;
        BT->lchild = CreateBT();
        BT->rchild = CreateBT();
        return BT;
    }
    
    void ReverseOrder(BiTree BT) {
        if (BT == NULL)
            return;
        queue<BiTree> B;
        stack<BiTree> S;
        BiTNode *p = BT;
        B.push(p);
        while (!B.empty()) {
            p = B.front();
            // 队头压栈，栈中得到逆层次遍历序列
            S.push(p);
    
            if (p->lchild)
                B.push(p->lchild);
            if (p->rchild)
                B.push(p->rchild);
            B.pop();
        }
        while (!S.empty()) { // 打印栈中内容
            cout<<S.top()->data<<" ";
            S.pop();
        }
    }
    
    int main() {
        BiTree BT = CreateBT();
        ReverseOrder(BT);
        return 0;
    }

// 测试用例
    ABDG.J..HK...EI...CF...
    
    // 遍历结果
    K J I H G F E D C B A

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0RYSDkyNA_size_16_color_FFFFFF_t_70]: /images/20230601/0edfa7b074b44739b6b080d7326777cb.png