前言

二叉树的遍历及应用主要是运用了递归、分治的思想。在这一篇文章，小编将介绍二叉树的前序遍历、中序遍历、后序遍历，求二叉树结点个数、叶节点个数、第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);
}