二叉树的存储方式和遍历方式

二叉树：

二叉树的每个节点至多有两个子树。如这个二叉树，其中1,2有两个子树，3只有左子树，5有右子树，4,6,7没有子树。

二叉树有两种存储方式：

第一种，数组表示。用数组存储方式就是用一组连续的存储单元存储二叉树的数据元素。

两颗树分别用数组表示为：

用下标就可以直接找到那个节点，也可以找这个节点的左孩子2n+1,右孩子2n+2.找父节点（n-1）/2

但是数组也有缺陷，比如第二个就会浪费存储空间。

若设二叉树的深度为h，除第 h 层外，其它各层 (1~h-1) 的结点数都达到最大个数，第 h 层所有的结点都连续集中在最左边，这就是完全二叉树。完全二叉树就适合用数组表示。

满二叉树就是除了叶结点外每一个结点都有左右子叶且叶结点都处在最底层的二叉树。也适合用数组表示。

完全二叉树不是满二叉树，满二叉树就是完全二叉树。

第二种，链表存储表示。其中又有二叉链表结构和三叉链表结构。

左图就是二叉链表结构，右图是三叉链表结构。

二叉链表里有leftchild指针，rightchild指针和数据。三叉链表里不仅有leftchild指针，rightchild指针和数据还有parent指针，能找到父节点。

二叉的遍历方式有四种：

第一种：前序遍历。先访问根节点，再访问左子树，最后访问右子树。

第二种：中序遍历。先访问左子树，再访问根节点，最后访问右子树。

第三种：后序遍历。先访问左子树，再访问右子树，最后访问根节点。

第四种：层序遍历。一层层节点依次遍历。   

这颗二叉树的前序遍历：1-2-4-5-7-3-6

中序遍历：4-2-5-7-1-6-3

后序遍历：4-7-5-2-6-3-1

层序遍历：1-2-3-4-5-6-7

代码实现：

[html] view plain copy

1. #pragma once  
2. #include <iostream>  
3. #include <assert.h>  
4. using namespace std;  
5. #include <queue>  
6. template <class T>  
7. struct BinaryTreeNode  
8. {  
9.     T _data;  
10.     BinaryTreeNode<T>* _leftchild;  
11.     BinaryTreeNode<T>* _rightchild;  
12.   
13.     BinaryTreeNode(const T& x)//构造函数  
14.         :_data(x)  
15.         , _leftchild(NULL)  
16.         , _rightchild(NULL)  
17.     {}  
18. };  
19.   
20. template <class T>  
21. class BinaryTree  
22. {  
23.     typedef BinaryTreeNode<T> Node;  
24. public:  
25.     BinaryTree()//无参构造函数  
26.         :_root(NULL)  
27.     {}  
28.     BinaryTree(T* a, size_t n, const T& invalid = T())//构造函数  
29.     {  
30.         size_t index = 0;  
31.         _root = _GreateTree(a, n, invalid, index);  
32.     }  
33.     BinaryTree(const BinaryTree<T>& t)//拷贝构造  
34.     {  
35.         _root = _copy(t._root);  
36.     }  
37.     BinaryTree<T>& operator=(const BinaryTree<T>& t)  
38.     {  
39.         if (this != &t)  
40.         {  
41.             Node* newRoot = _copy(t._root);  
42.             _Destroy(_root);  
43.             _root = newRoot;  
44.         }  
45.         return *this;  
46.     }  
47.     ~BinaryTree()//析构函数  
48.     {  
49.     void _Destory();  
50.     }  
51.     void PrevOrder()//前序遍历递归  
52.     {  
53.         _PrevOrder(_root);  
54.         cout << endl;  
55.     }  
56.     void InOrder()//中序遍历递归  
57.     {  
58.         _InOrder(_root);  
59.         cout << endl;  
60.     }  
61.     void PostOrder()//后序遍历递归  
62.     {  
63.         _PostOrder(_root);  
64.         cout << endl;  
65.     }  
66.     void LeveIOrder()//层序遍历,运用队列，以当前层带下一层  
67.     {  
68.         queue<Node*> q;  
69.         if (_root)  
70.             q.push(_root);  
71.         while (!q.empty())//队列不为空  
72.         {  
73.             Node* front = q.front();//取队头  
74.             cout << front->_data << " ";  
75.             q.pop();//删除队头  
76.             if (front->_leftchild)  
77.                 q.push(front->_leftchild);  
78.             if (front->_rightchild)  
79.                 q.push(front->_rightchild);  
80.         }  
81.         cout << endl;  
82.     }  
83.     size_t Size()//节点的个数  
84.     {  
85.         return _Size(_root);  
86.     }  
87.     size_t Depth()//树的深度  
88.     {  
89.         return _Depth(_root);  
90.     }  
91.     size_t LeafSize()//叶子节点的个数  
92.     {  
93.         return _LeafSize(_root);  
94.     }  
95.     size_t GetKLevel(size_t k)//第k层节点的个数  
96.     {  
97.         assert(k > 0);  
98.         return _GetKLevel(_root, k);  
99.     }  
100.     Node* Find(const T& x)//找节点x  
101.     {  
102.         return _Find(_root, x);  
103.     }  
104. protected:  
105.     Node* _copy(Node* root)//拷贝  
106.     {  
107.         if (root == NULL)  
108.             return NULL;  
109.         Node* newNode = new Node(root->_data);  
110.         newNode->_leftchild = _copy(root->_leftchild);  
111.         newNode->_rightchild =_copy(root->_rightchild);  
112.         return newNode;  
113.     }  
114.     void _Destroy(Node* root)//销毁  
115.     {  
116.         if (root == NULL)  
117.             return;  
118.         _Destroy(root->_leftchild);  
119.         _Destroy(root->_rightchild);  
120.         delete root;  
121.     }  
122.     Node* _Find(Node* root, const T& x)//找节点x的调用函数  
123.     {  
124.         if (root == NULL)  
125.             return NULL;  
126.         if (root->_data == x)  
127.             return root;  
128.         Node* tmp = _Find(root->_leftchild, x);  
129.         if (tmp)  
130.             return tmp;  
131.         return _Find(root->_rightchild, x);  
132.     }  
133.     size_t _GetKLevel(Node* root,size_t k)//第k层节点的调用函数  
134.     {  
135.         if (root == NULL)  
136.             return 0;  
137.         if (k == 1)  
138.         {  
139.             return 1;  
140.         }  
141.         return _GetKLevel(root->_leftchild, k - 1) + _GetKLevel(root->_rightchild, k - 1);  
142.     }  
143.     size_t _LeafSize(Node* root)//叶子节点的调用函数  
144.     {  
145.         if (root == NULL)  
146.             return 0;  
147.         if (root->_leftchild == NULL && root->_rightchild == NULL)  
148.         {  
149.             return 1;  
150.         }  
151.         return _LeafSize(root->_leftchild) + _LeafSize(root->_rightchild);  
152.     }  
153.     size_t _Depth(Node* root)//树的深度调用函数  
154.     {  
155.         if (root == NULL)  
156.             return 0;  
157.         int left = _Depth(root->_leftchild);  
158.         int right = _Depth(root->_rightchild);  
159.         return left > right ? left + 1: right + 1;  
160.     }  
161.     size_t _Size(Node* root)//节点的个数  
162.     {  
163.         if (root == NULL)  
164.             return 0;  
165.         return (_Size(root->_leftchild) + _Size(root->_rightchild))+1;  
166.     }  
167.     void _PostOrder(Node* root)//后序遍历调用函数  
168.     {  
169.         if (root == NULL)  
170.             return;  
171.         _PostOrder(root->_leftchild);  
172.         _PostOrder(root->_rightchild);  
173.         cout << root->_data << " ";  
174.     }  
175.     void _InOrder(Node* root)//中序遍历的调用函数  
176.     {  
177.         if (root == NULL)  
178.             return;  
179.         _InOrder(root->_leftchild);  
180.         cout << root->_data << " ";  
181.         _InOrder(root->_rightchild);  
182.     }  
183.     void _PrevOrder(Node* root)//前序遍历的调用函数  
184.     {  
185.         if (root == NULL)  
186.             return;  
187.         cout << root->_data << " ";  
188.         _PrevOrder(root->_leftchild);  
189.         _PrevOrder(root->_rightchild);  
190.     }  
191.     Node* _GreateTree(T* a, size_t n, const T& invalid, size_t& index)//构造函数的调用函数  
192.     {  
193.         Node* root = NULL;  
194.         if ((index< n) && (a[index] != invalid))  
195.         {  
196.             root = new Node(a[index]);  
197.             root->_leftchild = _GreateTree(a, n, invalid, ++index);  
198.             root->_rightchild = _GreateTree(a, n, invalid, ++index);  
199.         }  
200.         return root;  
201.     }  
202. protected:  
203.     Node* _root;  
204. };  
205.   
206. void BinaryTreeTest()//测试  
207. {  
208.     int a[] = { 1, 2, 3, '#', '#', 4, '#', '#', 5, 6 };  
209.     BinaryTree<int> t1(a, sizeof(a) / sizeof(a[0]), '#');  
210.     t1.PrevOrder();  
211.     t1.LeveIOrder();  
212.     t1.InOrder();  
213.     t1.PostOrder();  
214.     cout << "节点的个数：" << t1.Size() << endl;  
215.     cout << "深度：" << t1.Depth() << endl;  
216.     cout << "叶子节点的个数：" << t1.LeafSize() << endl;  
217.     cout << "第k层：" << t1.GetKLevel(2) << endl;  
218.     BinaryTree<int> t2(t1);  
219.     t2.PostOrder();  
220.     BinaryTree<int> t3;  
221.     t3 = t1;  
222. }  
223.   
224. int main()  
225. {  
226.     BinaryTreeTest();  
227.     return 0;  
228. }