1 typedef struct node{
2 int val;
3 struct node *left, *right;
4 }TreeNode;
5 //求二叉树的节点个数。
6 int GetNodeNum(TreeNode *pRoot){
7 if(pRoot == NULL)
8 return 0;
9 return GetNodeNum(pRoot->left) + GetNodeNum(pRoot->right) +;
10 }
11 //求二叉树的深度
12 int GetDepth(TreeNode* root){
13 if(root == NULL)
14 return 0;
15 int depth_left = GetDepth(root->left);
16 int depth_right = GetDepth(root->right);
17 return max(depth_right, depth_left) + 1;
18 }
19 //三种遍历方式
20 void PreOrderTraverse(TreeNode *root){
21 if(root == NULL)
22 return;
23 visit(root->val);
24 PreOrderTraverse(root->left);
25 PreOrderTraverse(root->right);
26 }
27 void InOrderTraverse(TreeNode *root){
28 if(root == NULL)
29 return;
30 InOrderTraverse(root->left);
31 visit(root->val);
32 InOrderTraverse(root->right);
33 }
34 void PostOrderTraverse(TreeNode *root){
35 if(root == NULL)
36 return;
37 PostOrderTraverse(root->left);
38 PostOrderTraverse(root->right);
39 visit(root->val);
40 }
41 //层序遍历二叉树
42 void LevelTraverse(TreeNode *root){
43 if(root == NULL)
44 return;
45 queue<TreeNode*> q;
46 q.push(root);
47 while(!q.empty()){
48 TreeNode *node = q.front();
49 q.pop();
50 visit(root->val);
51 if(node->left != NULL)
52 q.push(node->left);
53 if(node->right != NULL)
54 q.push(node->right);
55 }
56 return;
57 }
58 //求二叉树第k层的节点数
59 int GetNodeNumKthLevel(TreeNode *root, int k){
60 if(root == NULL || k < 1)
61 return 0;
62 if(k == 1)
63 return 1;
64 int numLeft = GetNodeNumKthLevel(root->left, k - 1);
65 int numRight = GetNodeNumKthLevel(root->right, k - 1);
66 return (numLeft + numRight);
67 }
68 //求二叉树叶子节点个数
69 int GetLeafNodeNum(TreeNode *root){
70 if(root == NULL)
71 return 0;
72 if(root->left == NULL && root->right == NULL)
73 return 1;
74 int numLeft = GetLeafNodeNum(root->left);
75 int numRight = GetLeafNodeNum(root->right);
76 return (numLeft + numRight);
77
78 }
79 //判断两颗二叉树是否结构相同
80 bool isSame(TreeNode *tree1, TreeNode *tree2){
81 if(tree1 == NULL && tree2 == NULL)
82 return true;
83 if(tree1 == NULL && tree2 != NULL || tree1 != NULL && tree2 == NULL ||
84 tree1->val != tree2->val)
85 return false;
86 return isSame(tree1->left, tree2->left) && isSame(tree1->right, tree2->right);
87 }
88 //判断二叉树是否是平衡二叉树
89 bool IsAVL(TreeNode *root, int &height){
90 if(root == NULL){
91 height = 0;
92 return true;
93 }
94 int heightLeft;
95 bool resultLeft = IsAVL(root->left, heightLeft);
96 int heightRight;
97 bool resultRight;
98 bool resultRight = IsAVL(root->right, heightRight);
99 height = max(heightLeft, heightRight) + 1;
100 if(resultLeft && resultRight && (abs(heightLeft - heightRight) <= 1)){
101 return true;
102 } else {
103 return false;
104 }
105 }
106 //求二叉树的镜像
107 void mirror(TreeNode *root){
108 if(root == NULL)
109 return;
110 if(root->left == NULL && root->right == NULL)
111 return;
112 TreeNode *temp;
113 temp = root->left;
114 root->left = root->right;
115 root->right = temp;
116 mirror(root->left);
117 mirror(root->right);
118 }
119 //求二叉树中两个节点的最低公共祖先节点
120
121 //求二叉树中节点的最大距离
122 //由前序遍历和中序遍历重建二叉树
123 //判断二叉树是不是完全二叉树
124 //将二叉查找树变为有序的双向链表
