二叉树
两种特殊二叉树
- 满二叉树（下图左）：除叶子节点外的所有分支节点都含有2个非空子节点的二叉树
- 完全二叉树（下图右）：除了最后一层，其余层都是“满”的，这样的二叉树是完全二叉树
二叉树定理
1）任意二叉树度数为2节点的个数等于叶节点个数减1
当只有1个节点时，度为0。每派生出1度，就会多出1个节点。派生出的度和派生出的节点数一定相等。那么就得出了总度数和节点总数的关系：
节点总数 = 总度数 + 1
设度数为2的节点数为X2，度数为1的节点数为X1，度数为0的节点数为X0。可以得出如下关系式：
X2 + X1 + X0 = 2X2 + X1 + 1，推出 X2 = X0 - 1
因此，度数为2的节点个数等于叶节点数减1
2）满二叉树定理：非空满二叉树的叶节点数等于其分支节点数加1
如果已知前一个结论，那么这个定理显然成立。下面分析如果不知道前一个结论，怎么证明
对于只有1个节点的树，该定理成立。从这开始思考，每产生1个分支节点(度数为2)。叶子节点数也会加1。因为要产生一个分支节点，那么这个新的分支节点必然是原来的叶子节点，而新的分支节点又生成了2个新的叶子节点。因此叶子节点的总数先是减1然后加2，因此总数加1。因此，产生n个分支节点时，也产生了n个叶子节点，由于最初只有1个叶子节点，所以该定理成立
3）一颗非空二叉树空子树的数目等于其节点数目加1
考虑只有1个根节点的二叉树：它有2个空子树，1个节点，因此结论成立。从这里开始考虑，每产生1个节点。空子树便会先减1然后加2。就和上面结论中每多出1个分支节点，叶子节点的变化一样。因此在原来结论的基础上，由于空子树和节点等量增长。所以结论成立
前中后序遍历
- 前序遍历：根->左->右
- 中序遍历：左->根->右
- 后序遍历：左->右->根
假设树节点的定义如下：
1struct TreeNode {
2 int val;
3 TreeNode *left;
4 TreeNode *right;
5 TreeNode(int x) : val(x), left(NULL), right(NULL) {}
6};
递归版
1//前序遍历
2void preorderTraversalRecursion(TreeNode *node)
3{
4 if(!node) return;
5 cout << node->val << " ";//操作当前节点
6 preorderTraversalRecursion(node->left);
7 preorderTraversalRecursion(node->right);
8}
9
10//中序遍历
11void inorderTraversalRecursion(TreeNode *node)
12{
13 if(!node) return;
14 inorderTraversalRecursion(node->left);
15 cout << node->val << " ";//操作当前节点
16 inorderTraversalRecursion(node->right);
17}
18
19//后序遍历
20void postorderTraversalRecursion(TreeNode *node)
21{
22 if(!node) return;
23 postorderTraversalRecursion(node->left);
24 postorderTraversalRecursion(node->right);
25 cout << node->val << " ";//操作当前节点
26}
迭代版
需要使用一个栈作为辅助空间
1//前序遍历
2void preorderTraversalIteration(TreeNode *root)
3{
4 stack<TreeNode*> st;
5 if(root)
6 st.push(root);
7
8 while(!st.empty()){
9 TreeNode *nd = st.top();
10 st.pop();
11
12 cout << nd->val << " ";//操作当前节点
13
14 if(nd->right)
15 st.push(nd->right);
16 if(nd->left)
17 st.push(nd->left);
18 }
19}
20
21//中序遍历：
22void inorderTraversalIteration(TreeNode *root)
23{
24 stack<TreeNode*> st;
25
26 TreeNode *curr = root;
27
28 while(curr || !st.empty()){
29 if(curr){
30 st.push(curr);
31 curr = curr->left;
32 }
33 else{
34 curr = st.top();
35 st.pop();
36
37 cout << curr->val << " ";//操作当前节点
38
39 curr = curr->right;
40 }
41 }
42}
43
44//后序遍历
45void postorderTraversalIteration(TreeNode *root)
46{
47 stack<TreeNode*> st;
48 TreeNode *pre;
49
50 if(root)
51 st.push(root);
52
53 while(!st.empty()){
54 TreeNode *nd = st.top();
55 /*
56 * 出栈条件：
57 * 对于叶子节点：直接弹出
58 * 对于非叶子节点：如果已经遍历过其左子节点或右子节点，则弹出
59 */
60 if((!nd->left && !nd->right) || (pre && (nd->left == pre || nd->right == pre))){
61 st.pop();
62 cout << nd->val <<" ";//操作当前节点
63 pre = nd;
64 }
65 else{//说明是一个非叶子节点，并且还未访问其左右孩子
66 if(nd->right)
67 st.push(nd->right);
68 if(nd->left)
69 st.push(nd->left);
70 }
71 }
72}
对于后序遍历，由于其访问序列为：左->右->根。因此还有一种方法，可以按类似前序遍历的方式：根->右->左，然后对得到的结果反序