链式二叉树的基本操作（C语言版）

目录

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);
}

---