【二叉树（链式结构的存储）实现 详解】
Hello,许久不见。你有没有坚持学习呢？
这篇是初阶基本的几种数据结构的实现的最后一篇，下一篇我们就要开始进行排序的学习。在初阶数据结构学习完成之后，我会带量大家进入C++的学习，在C++期间我可能会将lunix的学习穿插进进来，供大家更好的学习。当然在C++阶段，我们的代码量会增加很多，我可能也会时不时的发布一些算法和精选的题目。
所以，在初阶数据结构的阶段我希望大家把最基本的几种数据结构学习好，为后期的学习打好良好的基础。
好了，步入正题。上两篇博客讲的是二叉树（堆）的顺序存储，堆排序和Top-K问题。那二叉树既然有顺序存储结构，那么当然也有链式存储结构（基于二叉链）
1 . 回顾引入
回顾二叉树的概念，二叉树分为空树和非空树，非空二叉树由根节点，根节点的左子树和根节点的右子树组成。
根节点的左子树和右子树分别又是由子树节点，子树节点的左子树和子树节点的右子树组成的，因此二叉树定义是递归式的，后续链式二叉树的操作中基本都是按照该概念实现的。
2 . 遍历规则的介绍
2.1 前序遍历
前序遍历又称先序遍历：访问根节点的操作发生在遍历其左右子树之前。
访问顺序：根节点，左子树，右子树
2.2 中序遍历
中序遍历：访问根节点的操作发生在遍历其左右子树之中（间）。
访问顺序：左子树，根节点，右子树
2.3 后序遍历
后序遍历：访问根节点的操作发生在遍历其左右子树之后。
访问顺序：左子树，右子树，根节点
3 . 链式二叉树的实现
在这里我们还是将其实现的部分分为三个部分：tree.h(二叉树的节点的结构的定义以及函数的声明部分），tree.c(函数功能的实现部分），test.c(函数功能的测试部分）
3.1 tree.h(二叉树的节点的结构的定义以及函数的声明部分）
#pragma once #include <stdio.h> #include <assert.h> #include<stdlib.h> #include<stdbool.h> //链式结构树的节点的定义以及函数的声明 typedef int BTDatatype; typedef struct TreeNode {BTDatatype data;struct TreeNode* left;struct TreeNode* right; }BTNode;//前序遍历 void PreOrder(BTNode* root); //中序遍历 void InOrder(BTNode* root); //后序遍历 void PostOrder(BTNode* root);//二叉树节点的个数 int BinaryTreeSize(BTNode* root); //二叉树叶子节点的个数 int BinaryTreeLeafSzie(BTNode* root); //二叉树第k层节点的个数 int BinaryTreeLevelKSzie(BTNode* root,int k); //二叉树的深度 int BinaryTreeDepth(BTNode* root);//在二叉树中查找值为x 的节点 BTNode* BinaryTreeFind(BTNode* root, int x);//二叉树的销毁 void BinaryTreeDestroy(BTNode* root);//二叉树的层序遍历 void LevelOrder(BTNode* root);//判断二叉树是否为完全二叉树 bool BinaryTreeComplete(BTNode* root);ps:目前，我们在最开始学习二叉树的时候对二叉树的限制较少，在这里实现插入，删除之类的操作没有意义，后续会给大家更新到平衡树或者红黑树，二叉树会有限制，敬请期待！
3.2 tree.c(函数功能的实现部分）
3.2.1 前，中，后序遍历的实现
注意：可以结合前面的遍历规则进行理解！！！
//前序遍历 void PreOrder(BTNode* root) {if (root == NULL){return;}printf("%d ", root->data);PreOrder(root->left);PreOrder(root->right); } //中序遍历 void InOrder(BTNode* root) {if (root == NULL){return;}InOrder(root->left);printf("%d ", root->data);InOrder(root->right); } //后序遍历 void PostOrder(BTNode* root) {if (root == NULL){return;}PostOrder(root->left);PostOrder(root->right);printf("%d ", root->data); }除此之外，需要认真的队2二叉树的递归式定义好好理解。在这里函数的实现的部分体现的尤为明显。
3.2.2 其余函数功能的实现
//二叉树节点的个数 int BinaryTreeSize(BTNode* root) {if (root == 0){return 0;}return BinaryTreeSize(root->left) + BinaryTreeSize(root->right) + 1; } //二叉树叶子节点的个数 int BinaryTreeLeafSzie(BTNode* root) {if (root == NULL){return 0;}if (root->left == NULL && root->right == NULL){return 1;}return BinaryTreeLeafSzie(root->left) + BinaryTreeLeafSzie(root->right) ; } //二叉树第k层节点的个数 int BinaryTreeLevelKSzie(BTNode* root, int k) {if (root == NULL){return 0;}if (k == 1)//判断是不是第k层{return 1;}//如果不是第k层就向下遍历return BinaryTreeLevelKSzie(root->left, k - 1) + BinaryTreeLevelKSzie(root->right, k - 1);} //二叉树的深度 左右子树分别遍历取较大值 int BinaryTreeDepth(BTNode* root) {if (root == NULL){return 0;}int leftDep = BinaryTreeDepth(root->left);int rightDep = BinaryTreeDepth(root->right);return leftDep > rightDep ? leftDep + 1 : rightDep + 1;} //在二叉树中查找值为x 的节点 BTNode* BinaryTreeFind(BTNode* root, int x) {if (root == NULL){return NULL;}if (root->data == x){return root;}BTNode* leftfind = BinaryTreeFind(root->left, x);if (leftfind){return leftfind;}BTNode* rightfind = BinaryTreeFind(root->right, x);if (rightfind){return rightfind;}return NULL; }//二叉树的销毁 注意理解： 销毁我们需要通过形参改变实参 通过递归销毁 //先销毁的是左子树 其次是右子树 最后是根节点 void BinaryTreeDestroy(BTNode** root) {if (root == NULL){return;}BinaryTreeDestroy((*root)->left);BinaryTreeDestroy((*root)->right);free(*root);*root = NULL; }//二叉树的层序遍历 void LevelOrder(BTNode* root) {//这需要利用队列的性质进行遍历//注意：这里是将节点的地址放进队列之中Queue q;QueueInit(&q);QueuePush(&q, root);while (!QueueEmpty(&q)){//取队头的节点的地址BTNode* front = QueueFront(&q);printf("%d ", front->data);//让队头的节点进项出栈,如果当前节点的左右节点不为空，就让进栈QueuePop(&q);if (front->left){QueuePush(&q, front->left);}if (front->right){QueuePush(&q, front->right);}}printf("\n");QueueDestroy(&q); }//判断二叉树是否为完全二叉树 bool BinaryTreeComplete(BTNode* root) {Queue q;QueueInit(&q);QueuePush(&q, root);while (!QueueEmpty(&q)){//取队头的节点的地址BTNode* front = QueueFront(&q);//让队头的节点进项出栈,如果当前节点的左右节点不为空，就让进栈QueuePop(&q);if (front == NULL){break;}QueuePush(&q, front->left);QueuePush(&q, front->right);}while (!QueueEmpty(&q)){BTNode* front = QueueFront(&q);QueuePop(&q);if (front){QueueDestroy(&q);return false;}}QueueDestroy(&q);return true; }值得注意的是在实现层序遍历和判断二叉树是否为完全二叉树的时候我们用到了前面所学的队列这一数据结构的性质，来帮助实现层序遍历和判断二叉树是否为完全二叉树。
3.3 test.c(函数功能的测试部分）
#define _CRT_SECURE_NO_WARNINGS #include "tree.h" BTNode* BuyNode(int x) {BTNode* newnode = (BTNode*)malloc(sizeof(BTNode));if (newnode == NULL){perror("malloc fail");exit(1);}newnode->data = x;newnode->left = newnode->right = NULL;return newnode; }int main() {BTNode* node1 = BuyNode(10);BTNode* node2 = BuyNode(5);BTNode* node3 = BuyNode(19);BTNode* node4 = BuyNode(4);BTNode* node5 = BuyNode(8);BTNode* node6 = BuyNode(13);BTNode* node7 = BuyNode(24);// 10node1->left = node2, node1->right = node3;// 5 19node2->left = node4, node2->right = node5;// 4 8 13 24node3->left = node6, node3->right = node7;BTNode* phead = node1;printf("前序遍历的结果:");PreOrder(phead);printf("\n");printf("中序遍历的结果:");InOrder(phead);printf("\n");printf("后序遍历的结果:");PostOrder(phead);printf("\n");printf("二叉树的节点的个数为:%d\n", BinaryTreeSize(phead));printf("二叉树的叶子节点的个数为:%d\n", BinaryTreeLeafSzie(phead));printf("二叉树的第%d层节点的个数为:%d\n",3, BinaryTreeLevelKSzie(phead,3));if (BinaryTreeFind(phead,13)){printf("找到了\n");}else printf("未找到\n");printf("层序遍历的结果为:");LevelOrder(phead);bool a=BinaryTreeComplete(phead);if (a){printf("该二叉树是完全二叉树\n");}else printf("该二叉树不是完全二叉树\n");BinaryTreeDestroy(&phead);return 0; }运行结果如下：
以上是测试代码，注意自己每写完一个函数功能就去测试，不要等着所有的函数写完才去测试。上面的测试代码所建立的二叉树正是前面的遍历规则中个大家所呈现的二叉树。大家可以前后对照着理解。不要只看，记得自己动手实现一下。养成良好的代码习惯在必要的时候也会事半功倍的！！！