二叉树的建立与遍历

末蓝、 2023-01-19 13:59 154阅读 0赞

**1.1** 给定一棵二叉树的先序遍历序列和中序遍历序列，建立这棵二叉树，并得出层序遍历序列和后序遍历序列。  
【分析】找出根结点，分别划分出左子树和右子树的先序、中序遍历序列，进行递归。

#include <iostream>
    #include <vector>
    #include <queue>
    
    using namespace std;
    
    typedef struct node {
        
        int data;
        struct node *lchild;
        struct node *rchild;
    }node,*BTree;
    
    vector<int> pre, in;
    
    node* createBTree(int preL,int preR,int inL,int inR) {
        
        //递归出口
        if (preL > preR) {
        
            return NULL;
        }
        //确定根节点
        int preRoot,inRoot;
        preRoot = preL;
        for (int i = inL; i <= inR; i++) {
        
            if (in[i] == pre[preL]) {
        
                inRoot = i;
                break;
            }
        }
        BTree no = new node;
        no->data = pre[preL];
        //确定左子树范围,递归创建
        no->lchild = createBTree(preL + 1, preL + inRoot - inL, inL, inRoot - 1);
        //确定右子树范围,递归创建
        no->rchild = createBTree(preL + inRoot - inL + 1, preR, inRoot + 1, inR);
        
        return no;
    }
    
    //层序遍历
    void squOrder(BTree T) {
        
        BTree s;
        queue<BTree> q;
        q.push(T);
        while (!q.empty()) {
        
            s=q.front();
            cout << s->data << " ";
            if(s->lchild!=NULL)
                q.push(s->lchild);
            if (s->rchild != NULL)
                q.push(s->rchild);
            q.pop();
        }
    }
    
    //后序遍历
    void postOrder(BTree T) {
        
        if (T != NULL) {
        
            postOrder(T->lchild);
            postOrder(T->rchild);
            cout << T->data<<" ";
        }
    }
    
    int main()
    {
        
        int n;
        cout << "输入结点个数：";
        cin >> n;
        
        int x;
        cout << "输入前序序列：";
        for (int i = 0; i < n; i++) {
        
            cin >> x;
            pre.push_back(x);
        }
        cout << "输入中序序列：";
        for (int i = 0; i < n; i++) {
        
            cin >> x;
            in.push_back(x);
        }
        BTree tree = createBTree(0, n-1, 0, n-1);
        cout << "层序遍历序列：";
        squOrder(tree);
        cout << "\n后序遍历序列：";
        postOrder(tree);
    }

![结果1][1]  
**练习：** Suppose that all the keys in a binary tree are distinct positive integers. Given the postorder and inorder traversal sequences, you are supposed to output the level order traversal sequence of the corresponding binary tree.

**1.2** 用非递归的方法实现二叉树的中序遍历。  
【分析】

1.  根节点进栈；
2.  左孩子一直进栈，直至左孩子为空；
3.  出栈一结点并访问，如果有右孩子，右孩子进栈，继续第2步，如果没有右孩子，继续第3步。

void inOrder(BTree T) {
        
        stack<BTree> s;
        BTree p = T;
        while (!s.empty()||p!=NULL) {
        
            if (p != NULL) {
        
                s.push(p);
                p = p->lchild;
            }
            else {
        
                cout << s.top()->data << " ";
                p = s.top()->rchild;
                s.pop();
            }
        }
    }

**练习：** 用非递归的方法实现二叉树的先序遍历。

**1.3** 用非递归的方法实现二叉树的后序遍历。

void postOrder(BTree T) {
        
        stack<BTree> s;
        BTree p = T,r=NULL;
        while (!s.empty() || p != NULL) {
        
            if (p != NULL) {
        
                s.push(p);
                p = p->lchild;
            }
            else {
        
                p = s.top();
                if (p->rchild!=NULL && r != p->rchild) {
        
                    p = s.top()->rchild;
                }
                else {
        
                    cout << s.top()->data << " ";               
                    s.pop();
                    r = p;
                    p = NULL;
                } 
            }
        }
    }

[1]: /images/20221021/1827bd63886945e1b73231c235d10de8.png