数据结构之树遍历

树在数据结构中占有重要的地位,这篇文章主要总结二叉树的知识点以及二叉树的遍历。

我认为真正的理解树,还是有必要去学习一点概念。
树

  • 结点:使用树结构存储的每一个数据元素都被称为“结点”。
  • 父节点、子节点和兄弟节点:对于图中的结点 A、B、C、D 来说,A 是 B、C、D 结点的父结点(也称为“双亲结点”),而 B、C、D 都是 A 结点的子结点(也称“孩子结点”)。对于 B、C、D 来说,它们都有相同的父结点,所以它们互为兄弟结点。
  • 根节点:每一个非空树都有且只有一个被称为根的结点。图中,结点A就是整棵树的根结点。

    树根的判断依据为:如果一个结点没有父结点,那么这个结点就是整棵树的根结点。

  • 叶子结点:如果结点没有任何子结点,那么此结点称为叶子结点(叶结点)。例如图中,结点 K、L、F、G、M、I、J 都是这棵树的叶子结点。
  • 子树:如图中,整棵树的根结点为结点 A,而如果单看结点 B、E、F、K、L 组成的部分来说,也是棵树,而且节点 B 为这棵树的根结点。所以称 B、E、F、K、L 这几个结点组成的树为整棵树的子树;同样,结点 E、K、L 构成的也是一棵子树,根结点为 E。

    单个结点也是一棵树,只不过根结点就是它本身。图 1中,结点 K、L、F 等都是树,且都是整棵树的子树。

  • 空树:如果集合本身为空,那么构成的树就被称为空树。空树中没有结点。
  • 度:对于一个结点,拥有的子树数(结点有多少分支)称为结点的度(Degree)。根结点 A 下分出了 3 个子树,所以,结点 A 的度为 3。

    一棵树的度是树内各结点的度的最大值。

  • 层次:从一棵树的树根开始,树根所在层为第一层,根的孩子结点所在的层为第二层,依次类推。

    一棵树的深度(高度)是树中结点所在的最大的层次。


二叉树

  • 二叉树:二叉树中各结点的度最多是 2,可以是 0,1,2。
  • 满二叉树:如果二叉树中除了叶子结点,每个结点的度都为 2,那么此二叉树为满二叉树。
  • 完全二叉树:如果二叉树除了最后一层外为满二叉树,最后一层的结点依次从左到右分布,此二叉树为完全二叉树。

二叉树性质

  • 1、二叉树中,第i层最多有2^(i-1)个节点
  • 2、如果二叉树的深度为K,那么此二叉树最有有2^K-1个节点
  • 3、一棵二叉树的叶子结点数为n0,度为2的结点数为n2,则n0 = n2 + 1。
  • 4、n 个结点的完全二叉树的深度为[log2n]+1,[]为向下取整。
  • 5、对于任意一个完全二叉树来说,将含有的结点按照层次从左到右依次标号,对于任意一个结点 i ,有以下几个结论:
    • 当 i > 1时,父亲结点为结点 [i / 2]
    • 如果 2*i > n ,则结点 i 肯定没有左孩子(为叶子结点);否则其左孩子是结点 2*i
    • 如果 2*i +1 > n ,则结点 i 肯定没有右孩子;否则右孩子是结点 2*i +1

树的遍历方式

  • 先序遍历:先访问根结点,再遍历左右子树。
  • 中序遍历:遍历左子树,之后访问根结点,然后遍历右子树。
  • 后续遍历:遍历完左右子树,再访问根结点。
    树
    先序遍历:

    12455367

中序遍历:

4251637

后序遍历:

4526731

只要给出三种遍历的两种,这课二叉树也可以唯一确定的。


树的递归遍历

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
#include <iostream>
using namespace std;
struct Node {
Node *left;
Node *right;
int val;
Node(int val=0) : val(val), left(NULL), right(NULL) {}
};
class Tree {
private:
Node *root;
public:
Tree() : root(NULL) {}
bool insert(Node *node) {
if (root == NULL) {
root = node;
return true;
}
Node *next = root;
Node *pre = NULL;
while (next != NULL) {
pre = next;
if (node->val < next->val) next = next->left;
else if(node->val > next->val) next = next->right;
else return false;
}
if (next == NULL) {
if (node->val > pre->val) pre->right = node;
else pre->left = node;
}
return true;
}
void PreOrderTraverse() {
PreOrderTraverse(root);
cout << endl;
}
void PreOrderTraverse(const Node *node) const {
if (node == NULL) return;
cout << node->val << " ";
PreOrderTraverse(node->left);
PreOrderTraverse(node->right);
}
void InOrderTraverse() {
InOrderTraverse(root);
cout << endl;
}
void InOrderTraverse(const Node *node) const {
if (node == NULL) return;
InOrderTraverse(node->left);
cout << node->val << " ";
InOrderTraverse(node->right);
}
void PostOrderTraverse() {
PostOrderTraverse(root);
cout << endl;
}
void PostOrderTraverse(const Node *node) const {
if (node == NULL) return;
PostOrderTraverse(node->left);
PostOrderTraverse(node->right);
cout << node->val << " ";
}
};
int main() {
int n;
Tree tree;
while (cin >> n) {
if (tree.insert(new Node(n))) {
cout << "insert success" << endl;
} else {
cout << "insert failed" << endl;
}
tree.PreOrderTraverse();
tree.InOrderTraverse();
tree.PostOrderTraverse();
}
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
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
#include <iostream>
#include <stack>
using namespace std;
struct Node {
Node *left;
Node *right;
int val;
Node(int val=0) : val(val), left(NULL), right(NULL) {}
};
class Tree {
private:
Node *root;
public:
Tree() : root(NULL) {}
bool insert(Node *node) {
if (root == NULL) {
root = node;
return true;
}
Node *next = root;
Node *pre = NULL;
while (next != NULL) {
pre = next;
if (node->val < next->val) next = next->left;
else if(node->val > next->val) next = next->right;
else return false;
}
if (next == NULL) {
if (node->val > pre->val) pre->right = node;
else pre->left = node;
}
return true;
}
void PreOrderTraverse() {
stack<Node *> sn;
sn.push(root);
while (!sn.empty()) {
Node *cur = sn.top();
cout << cur->val << " ";
sn.pop();
if (cur->right != NULL) sn.push(cur->right);
if (cur->left != NULL) sn.push(cur->left);
}
cout << endl;
}
void InOrderTraverse() {
stack<Node*> sn;
Node *next = root;
while(true) {
while (next != NULL) {
sn.push(next);
next = next->left;
}
if (sn.empty()) break;
Node *cur = sn.top();
cout << cur->val << " ";
sn.pop();
next = cur->right;
}
cout << endl;
}
void PostOrderTraverse() {
stack<Node*> sn;
sn.push(root);
Node *pre = NULL;
while (!sn.empty()) {
Node *cur = sn.top();
if ((cur->left == NULL && cur->right == NULL) ||
(pre != NULL && ((pre == cur->left) || (pre == cur->right)))) {
sn.pop();
cout << cur->val << " ";
pre = cur;
} else {
if (cur->right != NULL) sn.push(cur->right);
if (cur->left != NULL) sn.push(cur->left);
}
}
cout << endl;
}
};
int main() {
int n;
Tree tree;
while (cin >> n) {
if (tree.insert(new Node(n))) {
cout << "insert success" << endl;
} else {
cout << "insert failed" << endl;
}
tree.PreOrderTraverse();
tree.InOrderTraverse();
tree.PostOrderTraverse();
}
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
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
#include <iostream>
#include <stack>
#include <queue>
using namespace std;
struct Node {
Node *left;
Node *right;
int val;
Node(int val=0) : val(val), left(NULL), right(NULL) {}
};
class Tree {
private:
Node *root;
public:
Tree() : root(NULL) {}
bool insert(Node *node) {
if (root == NULL) {
root = node;
return true;
}
Node *next = root;
Node *pre = NULL;
while (next != NULL) {
pre = next;
if (node->val < next->val) next = next->left;
else if(node->val > next->val) next = next->right;
else return false;
}
if (next == NULL) {
if (node->val > pre->val) pre->right = node;
else pre->left = node;
}
return true;
}
void Traverse() const {
queue<Node *> qn;
qn.push(root);
while (!qn.empty()) {
int size = qn.size();
while (size--) {
Node *cur = qn.front();
qn.pop();
cout << cur->val << " ";
if (cur->left != NULL) qn.push(cur->left);
if (cur->right != NULL) qn.push(cur->right);
}
}
cout << endl;
}
};
int main() {
int n;
Tree tree;
while (cin >> n) {
if (tree.insert(new Node(n))) {
cout << "insert success" << endl;
} else {
cout << "insert failed" << endl;
}
tree.Traverse();
}
return 0;
}

参考资料:
二叉树的定义、性质、存储
Bubble sort
Selection sort