浅谈二叉树

前言

(初级数据结构鲨我)
之前寒假集训的时候基础数据结构就学的不太好,很多还是眼高手低,这几天正好开始准备PTA天梯赛的题,L2的题都是这种基础数据结构模拟题,欠账出来都是要还的,今天正好趁着刚学的热乎劲写一下理解,供日后参考

二叉树的三种遍历

四种主要的遍历思想为:

前序遍历:根结点 —> 左子树 —> 右子树

中序遍历:左子树—> 根结点 —> 右子树

后序遍历:左子树 —> 右子树 —> 根结点

层次遍历:只需按层次遍历即可
在这里插入图片描述
对于这个树来说

  • 前序遍历:

    124753689

    1
    2
    3
    4
    5
    6
    7
    8
    9
    void pre_read(node *tree)
    {
    if (tree != NULL)
    {
    cout << tree->num << " ";
    pre_read(tree->lchild);
    pre_read(tree->rchild);
    }
    }
  • 中序遍历:

    742513869

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    void in_read(node *tree)
    {
    if (tree != NULL)
    {
    pre_read(tree->lchild);
    cout << tree->num << " ";
    pre_read(tree->rchild);
    }
    }

  • 后序遍历:

    745289631

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    void post_read(node *tree)
    {
    if (tree != NULL)
    {
    post_read(tree->lchild);
    post_read(tree->rchild);
    cout << tree->num << " ";
    }
    }

  • 层序遍历:
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    void floor_read(node *tree) //层序遍历
    {
    queue<node *> q;
    q.push(tree);
    while (!q.empty())
    {
    node *remp;
    remp = q.front();
    q.pop();
    cout << remp->num << " ";
    if (remp->lchild != NULL)
    {
    q.push(remp->lchild);
    }
    if (remp->rchild != NULL)
    {
    q.push(remp->rchild);
    }
    }
    }
  • 那么这三种遍历有什么特点呢?*

    三种遍历构建二叉树

  • 已知前序和中序
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
int inorder[maxn];   //中序
int preorder[maxn]; //先序
int postorder[maxn]; //后序
struct node
{
int num;
node *lchild;
node *rchild;
};

node *build(int pre[], int in[], int len)
{
if (len == 0)
return NULL;
int rootnode = 0;
for (rootnode = 0; in[rootnode] != pre[0]; rootnode++)
;
node *tree = new node;
tree->num = pre[0];
tree->lchild = build(pre + 1, in, rootnode);
tree->rchild = build(pre + rootnode + 1, in + rootnode + 1, len - rootnode - 1);
return tree;
}
main函数:
main()
{
node *head = new node;
head = build(preorder, inorder, N);
}
  • 已知后序和中序构建二叉树
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
int inorder[maxn];   //中序
int preorder[maxn]; //先序
int postorder[maxn]; //后序
struct node
{
int num;
node *lchild;
node *rchild;
};

node *create(int post[], int in[], int len)
{
if (len == 0)
return NULL;
int rootnode = 0;
for (rootnode = 0; in[rootnode] != post[len - 1]; rootnode++)
;
node *tree = new node;
tree->num = post[len - 1];
tree->lchild = create(post, in, rootnode);
tree->rchild = create(post + rootnode, in + 1 + rootnode, len - rootnode - 1);
return tree;
}
main()
{
node *head = new node;
head = create(postorder, inorder, N);
}
  • 已知前序后序
  • 无解!!!
    仅仅知道前序和后序无法构造唯一二叉树!
    *

    三种遍历构建完全二叉树

  • 知后序构建完全二叉树且求其层序遍历
    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
    #include <bits/stdc++.h>
    using namespace std;
    #define maxn 100000
    // 知后序,构建完全二叉树以及层序的遍历
    int post[maxn];
    int tree[maxn];
    int node = 1; //标识后序遍历
    int n; //节点数
    void build(int tree[], int cnt)
    {
    if (cnt > n)
    return;
    build(tree, cnt * 2);
    build(tree, cnt * 2 + 1);
    tree[cnt] = post[node++];
    }
    int main()
    {
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
    cin >> post[i];
    }
    int cnt = 0;
    build(tree, 1);
    cout << tree[1];
    for (int i = 2; i <= n; i++)
    cout << " " << tree[i];
    return 0;
    }
  • 知前序构造完全二叉树且求其层序遍历
    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
    #include <bits/stdc++.h>
    using namespace std;
    #define maxn 100000
    // 知前序,构建完全二叉树和层序遍历
    int pre[maxn];
    int tree[maxn];
    int node = 1; //标识后序遍历
    int n; //节点数
    void build(int tree[], int cnt)
    {
    if (cnt > n)
    return;
    tree[cnt] = pre[node++];
    build(tree, cnt * 2);
    build(tree, cnt * 2 + 1);
    }
    int main()
    {
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
    cin >> pre[i];
    }
    int cnt = 0;
    build(tree, 1);
    cout << tree[1];
    for (int i = 2; i <= n; i++)
    cout << " " << tree[i];
    return 0;
    }

大杂烩

读前序后序中序数组一定要从下标0开始读!(别问我怎么知道的)

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
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
#include <bits/stdc++.h>
using namespace std;
// 二叉树知前序中序后序构造二叉树+前序后序层序遍历二叉树
#define maxn 50
int N;
int inorder[maxn]; //中序
int preorder[maxn]; //先序
int postorder[maxn]; //后序
struct node
{
int num;
node *lchild;
node *rchild;
};
node *build(int pre[], int in[], int len)
{
if (len == 0)
return NULL;
int rootnode = 0;
for (rootnode = 0; in[rootnode] != pre[0]; rootnode++)
;
node *tree = new node;
tree->num = pre[0];
tree->lchild = build(pre + 1, in, rootnode);
tree->rchild = build(pre + rootnode + 1, in + rootnode + 1, len - rootnode - 1);
return tree;
}
node *create(int post[], int in[], int len)
{
if (len == 0)
return NULL;
int rootnode = 0;
for (rootnode = 0; in[rootnode] != post[len - 1]; rootnode++)
;
node *tree = new node;
tree->num = post[len - 1];
tree->lchild = create(post, in, rootnode);
tree->rchild = create(post + rootnode, in + 1 + rootnode, len - rootnode - 1);
return tree;
}
void floor_read(node *tree) //层序遍历
{
queue<node *> q;
q.push(tree);
while (!q.empty())
{
node *remp;
remp = q.front();
q.pop();
cout << remp->num << " ";
if (remp->lchild != NULL)
{
q.push(remp->lchild);
}
if (remp->rchild != NULL)
{
q.push(remp->rchild);
}
}
}
void pre_read(node *tree)
{
if (tree != NULL)
{
cout << tree->num << " ";
pre_read(tree->lchild);
pre_read(tree->rchild);
}
}
void in_read(node *tree)
{
if (tree != NULL)
{
pre_read(tree->lchild);
cout << tree->num << " ";
pre_read(tree->rchild);
}
}
void post_read(node *tree)
{
if (tree != NULL)
{
post_read(tree->lchild);
post_read(tree->rchild);
cout << tree->num << " ";
}
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
cin >> N;
for (int i = 0; i < N; i++)
{
cin >> inorder[i];
}
for (int i = 0; i < N; i++)
{
cin >> preorder[i];
}
for (int i = 0; i < N; i++)
{
cin >> postorder[i];
}
node *head = new node;
// head = build(preorder, inorder, N);
head = create(postorder, inorder, N);
floor_read(head);
cout << endl;
pre_read(head);
cout << endl;
in_read(head);
cout << endl;
post_read(head);
cout << endl;
return 0;
}

我自己造的输入样例:

1
2
3
4
7
1 2 3 4 5 6 7
4 1 3 2 6 5 7
2 3 1 5 7 6 4

输出样例:

1
2
3
4
4 1 6 3 5 7 2        
4 1 3 2 6 5 7
1 3 2 4 6 5 7
2 3 1 5 7 6 4

在这里插入图片描述

自勉

在这里插入图片描述
醍醐灌顶!以此自勉!