1.二叉树的前，中，后序
前序：按照访问顺序依次访问根，左子树，右子树
中序：按照访问顺序依次访问左子树，根，右子树
后序：按照访问顺序依次访问左子树，右子树，根
层序：一层一层的挨着遍历；
以上图为例：（N 表示NULL）
前序：1 2 4 N N 5 N N 3 6 N N 7 N N
中序：N 4 N 2 N 5 N 1 N 6 N 3 N 7 N
后序：N N 4 N N 5 2 N N 6 N N 7 3 1
层序：1 2 3 4 5 6 7
2.二叉树的前，中，后序遍历代码实现（递归）
前序遍历代码：
void PrevPrintf(BTNode* root) { if (root == NULL) { printf("N "); return; } printf("%d ",root->val); PrevPrintf(root->left); PrevPrintf(root->right); }
中序遍历代码：
void InPrintf(BTNode* root) { if (root == NULL) { printf("N "); return; } InPrintf(root->left); printf("%d ", root->val); InPrintf(root->right); }
后序遍历代码：
void PostPrintf(BTNode* root) { if (root == NULL) { printf("N "); return; } PostPrintf(root->left); PostPrintf(root->right); printf("%d ", root->val); }
2.实现几个函数
1.求树中结点个数
int TreeSize(BTNode* root);
代码思想：
要求树的结点，可以先求左右子树结点相加，求左右子树结点又可以先求左右子树的左右子树的结点相加；
实现代码：
//结点的个数 int TreeSize(BTNode* root) { if (root == NULL) return 0; return TreeSize(root->left) + TreeSize(root->right) + 1; }
2.求树中叶子结点的个数
int TreeLeafSize(BTNode* root);
代码思想：
叶子结点的特点是：左右子树都为NULL；
当根结点为NULL时，直接返回0；
当左右子树都为NULL时，返回1，
不满足上面条件就继续递归当前结点的左右子树；
实现代码：
// 叶子节点个数 int TreeLeafSize(BTNode* root) { if (root == NULL) return 0; if (root->left == NULL && root->right == NULL) return 1; return TreeLeafSize(root->left)+TreeLeafSize(root->right); }
3.求树中第k层结点的个数
int TreeKLevel(BTNode* root);
代码思想：
对于第一层来说时求第k层的结点个数，但是对于第二层来说是求第k-1层的节点个数，对于第二层来说求第k-层的结点数目，以此类推，对于k-1层来说是求第二层结点数；
实现代码：
//第k层的结点 int TreeKLevel(BTNode* root, int k) { assert(k > 0); if (root == NULL) return 0; if (k == 1) return 1; return TreeKLevel(root->left, k - 1) + TreeKLevel(root->right, k - 1); }
4.查找树中的值
BTNode* TreeFind(BTNode* root)
代码思想：
先与根比较，不是根再到左子树去找，左子树没有找到再到右子树中找
代码实现：
BTNode* FindBinaryTreeX(BTNode* root, int x) { if (root == NULL) return; if (root->val == x) return root; BTNode* ret = NULL; ret = FindBinaryTreeX(root->left, x); //如果ret不为空，就说明找到了，直接返回，不用到另一边去找 if (ret) return ret; ret = FindBinaryTreeX(root->right, x); if (ret) return ret; //找完了，没找到，返回空 return NULL; }
5.二叉树的层序遍历
void BinaryTreeLevelOrder(BTNode* root)
代码思想：
利用队列先进先出的特点，先将根结点入进去，取出队列最前面的数，进行打印，再将根结点Pop出队列时，再将该结点的左右子树入进去，如图解：
代码实现：
void BinaryTreeLevelOrder(BTNode* root) { Qu1 p; //队列的初始化 QueueInit(&p); //如果根结点不为空，将根入队列 if (root) QueuePush(&p, root); while (!QueueEmpty(&p)) { BTNode* front = QueueFront(&p); QueuePop(&p); printf("%d ",front->val); if(front->left!=NULL) QueuePush(&p, front->left); if (front->right!= NULL) QueuePush(&p, front->right); } //队列的销毁 QueueDestory(&p); }
6.二叉树的销毁
void BinaryTreeDestory(BTNode** root)
代码实现
// 二叉树销毁 void BinaryTreeDestory(BTNode* root) { if (root == NULL) return; BinaryTreeDestory(root->left); BinaryTreeDestory(root->right); free(root); //这里root是形参，对它改变不会改变实参; root = NULL; }
