目录
1.二叉树的定义
2.创建二叉树
3.递归遍历二叉树
1）前序遍历
2）中序遍历
3）后序遍历
4.层序遍历
5.计算节点个数
6.计算叶子节点个数
7.计算第K层节点个数
8.计算树的最大深度
9.查找值为x的节点
10.二叉树的销毁
从二叉树的概念中我们知道任何二叉树都难被分为，根，左子树，右子树，而左子树依然能被分为，根，左子树，右子树。右子树也是，所以我们这里可以采用递归的玩法来操作二叉树。
1.二叉树的定义
typedef int BTDataType;
typedef struct BinaryTreeNode
{
BTDataType data;
struct BinaryTreeNode* left;
struct BinaryTreeNode* right;
}BTNode;2.创建二叉树
由于是初学，为了便于观察，我们这里手搓一个二叉树
BTNode* CreateTree()
{
BTNode* n1 = (BTNode*)malloc(sizeof(BTNode));
assert(n1);
BTNode* n2 = (BTNode*)malloc(sizeof(BTNode));
assert(n2);
BTNode* n3 = (BTNode*)malloc(sizeof(BTNode));
assert(n3);
BTNode* n4 = (BTNode*)malloc(sizeof(BTNode));
assert(n4);
BTNode* n5 = (BTNode*)malloc(sizeof(BTNode));
assert(n5);
BTNode* n6 = (BTNode*)malloc(sizeof(BTNode));
assert(n6);
BTNode* n7 = (BTNode*)malloc(sizeof(BTNode));
assert(n7);
n1->data = 1;
n2->data = 2;
n3->data = 3;
n4->data = 4;
n5->data = 5;
n6->data = 6;
n1->left = n2;
n1->right = n4;
n2->left = n3;
n2->right = NULL;
n3->left = NULL;
n3->right = n7;
n4->left = n5;
n4->right = n6;
n5->left = NULL;
n5->right = NULL;
n6->left = NULL;
n6->right = NULL;
n7->left = NULL;
n7->right = NULL;
n7->data = 7;
return n1;
}注意：上述代码并不是创建二叉树的方式，真正创建二叉树方式后序详解重点讲解。
3.递归遍历二叉树
根，左子树，右子树，遍历顺序的不同导致访问的结果也不同，先学习这三种遍历，这里递归较为简单，为我们后面做一些二叉树的oj题目打下基础。
按照规则，二叉树的遍历有：前序/中序/后序的递归结构遍历：
1）前序遍历
前序遍历(Preorder Traversal 亦称先序遍历)——访问根结点的操作发生在遍历其左右子树之前。
// 二叉树前序遍历
void PreOrder(BTNode* root)
{
if (root == NULL)
{
printf("NULL ");
return;
}
printf("%d ", root->data);
PreOrder(root->left);
PreOrder(root->right);
}2）中序遍历
中序遍历(Inorder Traversal)——访问根结点的操作发生在遍历其左右子树之中（间）。
// 二叉树中序遍历
void InOrder(BTNode* root)
{
if (root == NULL)
{
printf("NULL ");
return;
}
InOrder(root->left);
printf("%d ", root->data);
InOrder(root->right);
}3）后序遍历
后序遍历(Postorder Traversal)——访问根结点的操作发生在遍历其左右子树之后。
// 二叉树后序遍历
void PostOrder(BTNode* root)
{
if (root == NULL)
{
printf("NULL ");
return;
}
PostOrder(root->left);
PostOrder(root->right);
printf("%d ", root->data);
}4.层序遍历
层序遍历，自上到下，自左到右依次访问数的结点就是层序遍历。
思想（借助一个队列）：
1、先将根节点入队，然后开始从队头出数据
2、出队头的数据同时将队头左右子树的结点入队（遇到NULL则不入队）
3、重复第二步，直到队列为空
//层序遍历
void TreeLevelOrder(BTNode* root)
{
Queue q;
QueueInit(&q);
if (root)
{
QueuePush(&q, root);
}
while (!QueueEmpty(&q))
{
BTNode* front = QueueFront(&q);
QueuePop(&q);
printf("%d ", front->data);
if (front->left)
QueuePush(&q, front->left);
if (front->right)
QueuePush(&q, front->right);
}
printf("\n");
}5.计算节点个数
求树的结点总数时，可以将问题拆解成子问题：
1.若为空，则结点个数为0。
2.若不为空，则结点个数 = 左子树结点个数 + 右子树结点个数 + 1（自己）
int TreeSize(BTNode* root)
{
return root == NULL ? 0 :
TreeSize(root->left) + TreeSize(root->right) + 1;
}
6.计算叶子节点个数
子问题拆解：
1.若为空，则叶子结点个数为0。
2.若结点的左指针和右指针均为空，则叶子结点个数为1。
3.除上述两种情况外，说明该树存在子树，其叶子结点个数 = 左子树的叶子结点个数 + 右子树的叶子结点个数。
//叶子节点个数
int TreeLeaSize(BTNode* root)
{
if (root == NULL)
return 0;
return (root->left == NULL && root->right == NULL) ? 1
: TreeLeaSize(root->left) + TreeLeaSize(root->right);
}7.计算第K层节点个数
这里我们要控制好递归的深度，我们依然把他给转换为子问题思考。
思路：
1、为空和非法时，结点个数为0个
2、为第一层时，结点个数为1个
3、不为空且合法时，第K层的结点个数=第K-1层的左子树结点个数+第K-1层的右子树结点个数
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);
}8.计算树的最大深度
我们如何找出最深的那一条途径？这里是一个选择的问题。如果一条途径递归到倒数第二层，左边有一个叶子节点，右边无节点，那么我们应该选择左边作为它的最深途径。
思路：
1.若为空，则深度为0。
2.若不为空，则树的最大深度 = 左右子树中深度较大的值 + 1。
int TreeHeigh(BTNode* root)
{
if (root == NULL)
return 0;
return TreeHeigh(root->left) > TreeHeigh(root->right) ? TreeHeigh(root->left) + 1 :
TreeHeigh(root->right) + 1;
}9.查找值为x的节点
思路：
1.先判断根结点是否是目标结点。
2.再去左子树中寻找。
3.最后去右子树中寻找。
BTNode* TreeFind(BTNode* root, BTDataType x)
{
if (root == NULL)
{
return NULL;
}
if (root->data == x)
{
return root;
}
//先去左树找
BTNode* lret = TreeFind(root->left, x);
if (lret)
return lret;
//再去右树找
BTNode* rret = TreeFind(root->right, x);
if (rret)
return rret;
return NULL;
}
10.二叉树的销毁
void BinaryTressDestory(BTNode* root)
{
if (root == NULL)
return;
BinaryTressDestory(root->left);
BinaryTressDestory(root->right);
free(root);
}
