由遍历顺序构建二叉树(前序+中序;后序+中序)

由遍历顺序构建二叉树(前序+中序;后序+中序)

前序+中序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
BiTree PreAndInCreateTree(int prel,int prer, int inl,int inr){
    if(prel>prer){
        return NULL;
    }
    BiTNode *root;
    int index=0;
    root=(BiTNode*)malloc(sizeof(BiTNode));				//记住分配空间
    root->data=preF[prel];			//前序遍历的第一个结点是根结点
    int i;
    for(i=inl;i<=inr;i++)
    {
        if(preF[prel]==inF[i]){
            index=i;
            break;
            //找到了根结点，目的是在中序遍历中划分左右子树
        }
    }
    //则其左子树节点个数为index-inl
    //前序遍历的第一个结点是根结点,所以新的递归区间是prel+1,到prel+index-inl,
    //中序遍历是左根右，所以新的递归区间是inl,index-1
    root->lchild=PreAndInCreateTree(prel+1,prel+index-inl,inl,index-1);
    //前序遍历是根左右，所以新的递归区间是prel+index-inl+1,prep
    //中序遍历是左根右，所以新的递归区间是index+1,inr
    root->rchild=PreAndInCreateTree(prel+index-inl+1,prer,index+1,inr);
    return root;
}

后序+中序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
BiTree PostAndInCreateTree(int postl,int postr, int inl,int inr){
    if(postl>postr){
        return NULL;
    }
    BiTNode *root;
    int index=0;
    root=(BiTNode*)malloc(sizeof(BiTNode));
    root->data=posts[postr];	//后序遍历的最后一个结点是根结点
    for (int i = inl; i <=inr ; ++i) {
        if(posts[postr]==ins[i])
        {
            index =i;
            break;
            //找到了根结点，目的是在中序遍历中划分左右子树
        }
    }//则其左子树节点个数为index-inl
    //后续遍历的最后一个结点是根节点，所以新的递归区间是，postl,postl+index-inl-1
    //中序遍历是左根右，所以新的递归区间是inl,index-1
    root->lchild=PostAndInCreateTree(postl,postl+index-inl-1,inl,index-1);
    //后序遍历是左右根，所以新的递归区间是postl+index-inl,postr-1
    //中序遍历是左根右，所以新的递归区间是index+1,inr
    root->rchild=PostAndInCreateTree(postl+index-inl,postr-1,index+1,inr);
    return root;
}

完整代码示例

前序+中序；后序+中序。递归调用可视化查看：(有助于理解递归调用过程)

Python Tutor - Visualize Python, Java, C, C++, JavaScript, TypeScript, and Ruby code execution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
#include <bits/stdc++.h>
using namespace std;
typedef struct BiTNode{
    int data;							//数据域
    struct BiTNode *lchild,*rchild;			//左右孩子指针
}BiTNode,*BiTree;
//tree
int preF[6]={4,2,1,3,5,6};		//前序遍历
int inF[6]={1,2,3,4,6,5};		//中序遍历
//trees
int posts[7]={2,3,1,5,7,6,4};	//后序遍历
int ins[7]={1,2,3,4,5,6,7};		//中序遍历
BiTree PreAndInCreateTree(int prel,int prer, int inl,int inr){
    if(prel>prer){
        return NULL;
    }
    BiTNode *root;
    int index=0;
    root=(BiTNode*)malloc(sizeof(BiTNode));				//记住分配空间
    root->data=preF[prel];			//前序遍历的第一个结点是根结点
    int i;
    for(i=inl;i<=inr;i++)
    {
        if(preF[prel]==inF[i]){
            index=i;
            break;
            //找到了根结点，目的是在中序遍历中划分左右子树
        }
    }
    //则其左子树节点个数为index-inl
    //前序遍历的第一个结点是根结点,所以新的递归区间是prel+1,到prel+index-inl,
    //中序遍历是左根右，所以新的递归区间是inl,index-1
    root->lchild=PreAndInCreateTree(prel+1,prel+index-inl,inl,index-1);
    //前序遍历是根左右，所以新的递归区间是prel+index-inl+1,prep
    //中序遍历是左根右，所以新的递归区间是index+1,inr
    root->rchild=PreAndInCreateTree(prel+index-inl+1,prer,index+1,inr);
    return root;
}
BiTree PostAndInCreateTree(int postl,int postr, int inl,int inr){
    if(postl>postr){
        return NULL;
    }
    BiTNode *root;
    int index=0;
    root=(BiTNode*)malloc(sizeof(BiTNode));
    root->data=posts[postr];	//后序遍历的最后一个结点是根结点
    for (int i = inl; i <=inr ; ++i) {
        if(posts[postr]==ins[i])
        {
            index =i;
            break;
            //找到了根结点，目的是在中序遍历中划分左右子树
        }
    }//则其左子树节点个数为index-inl
    //后续遍历的最后一个结点是根节点，所以新的递归区间是，postl,postl+index-inl-1
    //中序遍历是左根右，所以新的递归区间是inl,index-1
    root->lchild=PostAndInCreateTree(postl,postl+index-inl-1,inl,index-1);
    //后序遍历是左右根，所以新的递归区间是postl+index-inl,postr-1
    //中序遍历是左根右，所以新的递归区间是index+1,inr
    root->rchild=PostAndInCreateTree(postl+index-inl,postr-1,index+1,inr);
    return root;
}
void LevelOrder(BiTree T)
{
    queue<BiTree> q;
    q.push(T);
    while (!q.empty()){
        BiTNode *tmp =q.front();
        q.pop();
        cout<<tmp->data;
        if(tmp->lchild!=NULL){
            q.push(tmp->lchild);
        }
        if(tmp->rchild!=NULL){
            q.push(tmp->rchild);
        }
    }
}
int main()
{

    BiTree tree;
    tree=NULL;
    tree=PreAndInCreateTree(0,5,0,5);
    cout<<"输入为前序加中序遍历，输出他的层序遍历："<<endl;
    LevelOrder(tree);
    cout<<endl;
    BiTree trees;
    trees=NULL;
    cout<<"输入为后序加中序遍历，输出他的层序遍历："<<endl;
    trees=PostAndInCreateTree(0,6,0,6);
    LevelOrder(trees);
    return 0;
}

程序输出

1
2
3
4
输入为前序加中序遍历，输出他的层序遍历：
425136
输入为后序加中序遍历，输出他的层序遍历：
4163572