二叉树的性质：
二叉树是一棵特殊的树，二叉树每个节点最多有两个孩子结点，分别称为左孩子和右孩子。
例：
实例代码：
|
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
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
|
#include <iostream> #include <Windows.h> #include <stack> using namespace std; template <class T> struct BinaryTreeNode { int _data; BinaryTreeNode<T>* _left; //左孩子 BinaryTreeNode<T>* _right; //右孩子 BinaryTreeNode(const T& data) :_data(data) , _left(NULL) , _right(NULL) {} }; template <class T> class BinaryTree { typedef BinaryTreeNode<T> Node; public: BinaryTree() :_root(NULL) {} BinaryTree(T* arr, size_t n, const T& invalid=T()) { size_t index = 0; _root = _CreatTree(arr, n, invalid, index); } void PreOrderR() //前序遍历 递归 { _PreOrderR(_root); } void PreOrder() //前序遍历 非递归 { _PreOrder(_root); } void InOrderR() //中序遍历 递归 { _InOrderR(_root); } void InOrder() //中序遍历 非递归 { _InOrder(_root); } void PostOrderR() //后序遍历 左 右 根 递归 { _PostOrderR(_root); } void PostOrder() //后序遍历 左 右 根 非递归 { _PostOrder(_root); } ~BinaryTree() {} protected: //建树 arr:建树使用的数组 n：数组大小 invalid:非法值 index:当前下标 Node* _CreatTree(T* arr, size_t n, const T& invalid, size_t& index) { Node* root = NULL; if (index < n && arr[index] != invalid) { root = new Node(arr[index]); //根节点 root->_left = _CreatTree(arr, n, invalid, ++index); root->_right = _CreatTree(arr, n, invalid, ++index); } return root; } void _PreOrderR(Node* root) //前序遍历 递归 { if (root == NULL) { return; } cout << root->_data << " "; _PreOrderR(root->_left); _PreOrderR(root->_right); } void _PreOrder(Node* root) //前序遍历 非递归 { stack<Node*> tty; while (root != NULL || !tty.empty()) { if (root) { cout << root->_data << " "; tty.push(root); root = root->_left; } else { Node* temp = tty.top(); tty.pop(); root = temp->_right; } } } void _InOrderR(Node* root) //中序遍历 递归 { if (root == NULL) { return; } _InOrderR(root->_left); cout << root->_data << " "; _InOrderR(root->_right); } void _InOrder(Node* root) //中序遍历 非递归 { if (root == NULL) { return; } stack<Node*> tty; while (root != NULL || !tty.empty()) { while (root) { tty.push(root); root = root->_left; } //此时出了循环走到了最左叶子节点 Node* temp = tty.top(); tty.pop(); cout << temp->_data << " "; root = temp->_right; } } void _PostOrderR(Node* root) //后序遍历 左 右 根 递归 { if (root == NULL) { return; } _PostOrderR(root->_left); _PostOrderR(root->_right); cout << root->_data << " "; } void _PostOrder(Node* root) //后序遍历 左 右 根 非递归 { if (root == NULL) { return; } stack<Node*> tty; Node* PreNode = NULL; //上一个访问的结点 tty.push(root); while (!tty.empty()) { Node* cur = tty.top(); //访问的当前节点左右孩子均为空或者当前节点左右子树均已经访问过 if ((cur->_left == NULL && cur->_right == NULL) || ((PreNode != NULL) && (PreNode == cur->_left || PreNode == cur->_right))) { cout << cur->_data << " "; tty.pop(); PreNode = cur; } else { if (cur->_right != NULL) { tty.push(cur->_right); } if (cur->_left != NULL) { tty.push(cur->_left); } } } } protected: Node* _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
25
26
27
28
29
30
31
32
33
34
35
36
37
|
#include "源.h" void Test() { int array[10] = { 1, 2, 3, '#', '#', 4, '#', '#', 5, 6 }; BinaryTree<int> p(array, sizeof(array) / sizeof(array[0]), '#'); cout << "前序递归遍历： " << ""; p.PreOrderR(); cout << endl; cout << "前序非递归遍历： " << ""; p.PreOrder(); cout << endl; cout << "中序递归遍历： " << ""; p.InOrderR(); cout << endl; cout << "中序非递归遍历： " << ""; p.InOrder(); cout << endl; cout << "后序递归遍历： " << ""; p.PostOrderR(); cout << endl; cout << "后序非递归遍历： " << ""; p.PostOrder(); cout << endl; } int main() { Test(); system("pause"); return 0; } |
实现效果：
以上就是数据结构二叉树的详解，如有疑问请留言或者到本站社区交流讨论，感谢阅读，希望能帮助到大家，谢谢大家对本站的支持！
原文链接：http://blog.csdn.net/weixin_36125166/article/details/76100329
