前言
二叉树的遍历及应用主要是运用了递归、分治的思想。在这一篇文章，小编将介绍二叉树的前序遍历、中序遍历、后序遍历，求二叉树结点个数、叶节点个数、第K层结点个数、二叉树的深度。
构建二叉树
手搓二叉树的结构
小编简单构建一个二叉树的结构，方便后面的测试
构建的方式比较简单，在树的结构中有当前结点的数据、当前结点的左节点、右节点。除此之外，还需要开辟结点。
有了 前面数据结构的学习，小编认为手搓一个二叉树的结构相对来说简单一些
typedef int Tdatatype; typedef struct Tree { Tdatatype data; struct Tree* left; struct Tree* right; }Tree; Tree* BuyTree(Tdatatype x) { Tree* node = (Tree*)malloc(sizeof(Tree)); if (node == NULL) { perror("malloc fail"); return NULL; } node->data = x; node->left = NULL; node->right = NULL; return node; } Tree* CreatTree() { Tree* node1 = BuyTree(1); Tree* node2 = BuyTree(2); Tree* node3 = BuyTree(3); Tree* node4 = BuyTree(4); Tree* node5 = BuyTree(5); Tree* node6 = BuyTree(6); Tree* node7 = BuyTree(7); node1->left = node2; node1->right = node4; node2->left = node3; node2->right = node7; node4->left = node5; node4->right = node6; return node1; }
前序遍历
若二叉树为空，则操作为空
否则：
（1）访问根节点
（2）先序遍历左子树
（3）先序遍历右子树
void PrevOrder(Tree* root) { if (root == NULL) { printf("N "); return; } PrevOrder(root->left); printf("%d ", root->data); PrevOrder(root->right); }
中序遍历
若二叉树为空，则操作为空
否则：
（1）中序遍历左子树
（2）访问根节点
（3）中序遍历右子树
void InOrder(Tree* root) { if (root == NULL) { printf("N "); return; } InOrder(root->left); printf("%d ", root->data); InOrder(root->right); }
后序遍历
若二叉树为空，则操作为空
否则：
（1）后序遍历左子树
（2）后序遍历右子树
（3）访问根节点
void PostOrder(Tree* root) { if (root == NULL) { printf("N "); return; } PostOrder(root->left); PostOrder(root->right); printf("%d ", root->data); }
二叉树的结点个数
求二叉树的结点个数还是用到递归的思想，即子问题分治，还需要有结束条件
子问题分治：左子树结点个数+右子树结点个数+1
返回条件：根节点为空
int TreeSize(Tree* root) { return root == NULL ? 0 : TreeSize(root->right) + TreeSize(root->right) + 1; }
二叉树的叶节点个数
求二叉树叶节点个数依然是递归思想
子问题分治：左子树叶子节点个数+右子树叶子节点个数
返回条件：根节点为空，，返回0；是叶子节点，返回1
int TreeLeaSize(Tree* root) { if (root == NULL) return 0; if (root->left == NULL && root->right == NULL) return 1; return TreeLeaSize(root->left) + TreeLeaSize(root->right); }
二叉树的高度
子问题分治：找左子树和右子树中高度较大的那一个，并+1
返回条件：根节点为空，返回0
int TreeHight(Tree* root) { if (root == NULL) return 0; int left = TreeHight(root->left); int right = TreeHight(root->right); return left > right ? left + 1 : right + 1; }
二叉树第K层结点个数
二叉树第k层的节点数=左子树的第k-1层的节点数+右子树第k-1层的节点数。
因为二叉树没有第0层，是从第一层开始的，所以k==1时，返回1。
int TreeLevelK(Tree* root, int k) { assert(k > 0); if (root == NULL) return 0; if (k == 1) return 1; return TreeLevelK(root->left, k - 1) + TreeLevelK(root->right, k - 1); }
