【数据结构】二叉树的表示与遍历

淩亂°似流年 2021-11-04 19:26 268阅读 0赞

代码中包含二叉树的先序、中序和后序的递归和非递归实现，以及二叉树的层序遍历

#include<iostream>
    #include<stack>
    #include<queue>
    using namespace std;
    // 定义二叉树
    typedef struct BiTNode {
        char data;
        struct 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 PreOrder(BiTree BT) {
        if (BT) {
            cout<<BT->data;
            PreOrder(BT->lchild);
            PreOrder(BT->rchild);
        }
    }
    
    // 递归中序
    void InOrder(BiTree BT) {
        if (BT) {
            InOrder(BT->lchild);
            cout<<BT->data;
            InOrder(BT->rchild);
        }
    }
    
    // 递归后序
    void PostOrder(BiTree BT) {
        if (BT) {
            PostOrder(BT->lchild);
            PostOrder(BT->rchild);
            cout<<BT->data;
        }
    }
    
    // 非递归先序，将根节点的右孩子压栈后再访问左孩子
    void PreOrder2(BiTree BT) {
        stack<BiTree> B;
        BiTNode *p = BT;
        while (p || !B.empty()) {
            if (p) {
                if (p->rchild);
                    B.push(p->rchild);
                cout<<p->data;
                p = p->lchild;
            }
            else {
                p = B.top();
                B.pop();
            }
        }
    }
    
    // 非递归中序，先访问左子树，再访问右子树
    void InOrder2(BiTree BT) {
        stack<BiTree> B;
        BiTNode *p = BT;
        while (p || !B.empty()) {
            if (p) {
                B.push(p);
                p = p->lchild;
            }
            else {
                p = B.top();
                B.pop();
                cout<<p->data;
                p = p->rchild;
            }
        }
    }
    
    
    // 非递归后序，将先序遍历的左右访问顺序颠倒
    // 再将得到的序列压栈输出即为后序遍历序列
    void PostOrder2(BiTree BT) {
        stack<BiTree> B1;
        stack<BiTree> B2;
        BiTNode *p = BT, *rev;
        while (p || !B1.empty()) {
            if (p) {
                if (p->lchild);
                    B1.push(p->lchild);
                B2.push(p);
                p = p->rchild;
            }
            else {
                p = B1.top();
                B1.pop();
            }
        }
        while (!B2.empty()) {
            cout<<B2.top()->data;
            B2.pop();
        }
    }
    
    // 层序遍历，借助队列实现
    // 将根节点入队，再将其左右孩子依次入队
    // 根节点出队，再将队头的左右孩子依次入队
    // 直到队空，完成遍历
    void LayerOrder(BiTree BT) {
        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<<B.front()->data;
            B.pop();
        }
    }
    
    int main() {
        BiTree BT = CreateBT();
    
        cout<<"递归遍历"<<endl;
        cout<<"先序：";
        PreOrder(BT);
        cout<<endl;
        cout<<"中序：";
        InOrder(BT);
        cout<<endl;
        cout<<"后序：";
        PostOrder(BT);
        cout<<endl;
    
        cout<<"递归遍历"<<endl;
        cout<<"先序：";
        PreOrder2(BT);
        cout<<endl;
        cout<<"中序：";
        InOrder2(BT);
        cout<<endl;
        cout<<"后序：";
        PostOrder2(BT);
        cout<<endl;
        cout<<"层序：";
        LayerOrder(BT);
        cout<<endl;
    
        return 0;
    }

// 测试样例（先序建立，'.'表示NULL）
    // ABDG.J..HK...EI...CF...
    
    // 测试结果
    递归遍历
    先序：ABDGJHKEICF
    中序：GJDKHBIEAFC
    后序：JGKHDIEBFCA
    递归遍历
    先序：ABDGJHKEICF
    中序：GJDKHBIEAFC
    后序：JGKHDIEBFCA
    层序：ABCDEFGHIJK