【数据结构与算法】详解二叉树下：实践篇————通过链式结构深入理解并实现二叉树

   💓 博客主页：倔强的石头的CSDN主页

           📝Gitee主页：倔强的石头的gitee主页

⏩ 文章专栏：《数据结构与算法》

    期待您的关注

一、二叉树前置知识

二、二叉树链式结构实现的结构定义

三、二叉树的基本实现

🍃创建

🍃销毁

四、二叉树的遍历

🍃前序遍历

🍃中序遍历

🍃后序遍历

🍃层序遍历

五、二叉树的扩展功能

🍃求节点个数

🍃求叶子节点个数

🍃求第K层节点个数

🍃求二叉树的高度

🍃查找值为X的节点

在计算机科学中，二叉树是一种重要的数据结构，它以其独特的结构和性质在数据存储、搜索和算法设计中发挥着重要作用。链式结构作为二叉树的一种常见表示方式，通过节点间的指针连接，实现了对二叉树的高效存储和访问。

一、二叉树前置知识

参考前置文章：二叉树理论篇

【数据结构与算法】详解二叉树上：理论篇——二叉树的基本概念与性质-CSDN博客

二、二叉树链式结构实现的结构定义

二叉树的每个节点包括三个部分：

数据部分，这里称为data
左指针，指向节点的左孩子，这里称为left指针。如果左孩子为空，则指向NULL
右指针，指向节点的右孩子，这里称为right指针。如果右孩子为空，则指向NULL

结构如下图所示：

结构定义如下：

typedef char BTDataType;//数据类型重命名typedef struct BinaryTreeNode
{BTDataType data;struct BinaryTreeNode* left;struct BinaryTreeNode* right;
}BTNode;//结构体重命名

三、二叉树的基本实现

🍃创建

因为使用链式结构实现，所以二叉树不需要初始化，只需定义好单个申请节点的函数，每次插入节点调用节点创建函数即可

BTNode* BuyNode(BTDataType x)//申请新节点
{BTNode* newnode = (BTNode*)malloc(sizeof(BTNode));if (newnode == NULL){perror("newnode\n");exit(1);}newnode->data = x;newnode->left = newnode->right = NULL;return newnode;
}

二叉树的一般插入意义不大，跟手动插入无异，后面会在搜索二叉树篇章讲解二叉树插入的实现

🍃销毁

递归调用完成销毁，每棵树先释放左孩子和右孩子，再返回去销毁根，因此使用后序遍历的方法最为合适（不需要记录孩子，只需要正常遍历销毁即可）

后序遍历，文章的后面便会介绍，如果不太理解，可以直接点击目录查看遍历部分

调用函数
如果节点为空，直接返回
如果节点非空

先调用函数释放左子树
再调用函数释放右子树
最后释放节点自身

void BinaryTreeDestory(BTNode* root)//后序遍历并销毁
{if (root== NULL)return;BinaryTreeDestory(root->left);//左BinaryTreeDestory(root->right);//右free(root);//根
}

四、二叉树的遍历

二叉树的遍历是二叉树的基本操作之一，它指的是按照某种规则访问二叉树中的所有节点，并且每个节点只被访问一次。二叉树的遍历方式有多种，其中最常见的有四种：前序遍历（Pre-order Traversal）、中序遍历（In-order Traversal）、后序遍历（Post-order Traversal）和层序遍历（Level-order Traversal）。

前序遍历（根左右）
中序遍历（左根右）
后序遍历（左右根)
层序遍历（逐层访问）

这里以每次遍历节点打印节点数据为例（指针走到空打印N）

🍃前序遍历

使用递归的方法实现：

访问根节点
前序遍历左子树
前序遍历右子树

接收一个指针（地址）
指针从二叉树的根结点开始遍历

递归的结束条件: 指针指向空，则打印N，return
不满足递归条件，向深处递推:
1. 打印指针指向的节点的数据（相当于访问根节点）
2. 调用函数自己，传递节点左孩子的地址作为参数（相当于访问左子树）
3.调用函数自己，传递节点右孩子的地址作为参数（相当于访问右子树）

// 二叉树前序遍历 
void BinaryTreePrevOrder(BTNode* root)
{if (root == NULL){printf("N");return;}printf("%c", root->data);BinaryTreePrevOrder(root->left);BinaryTreePrevOrder(root->right);}

🍃中序遍历

使用递归的方法实现：

中序遍历左子树
访问根节点
中序遍历右子树

接收一个指针（地址）
指针从二叉树的根结点开始遍历

递归的结束条件:指针指向空，则打印N，return
不满足递归条件，向深处递推:
1. 调用函数自己，传递节点左孩子的地址作为参数（相当于访问左子树）
2.打印本节点的数据（相当于访问根节点）
3.调用函数自己，传递节点右孩子的地址作为参数（相当于访问右子树）

// 二叉树中序遍历
void BinaryTreeInOrder(BTNode* root)
{if (root == NULL){printf("N");return;}BinaryTreeInOrder(root->left);printf("%c", root->data);BinaryTreeInOrder(root->right);
}

🍃后序遍历

使用递归的方法实现：

后序遍历左子树
后序遍历右子树
访问根节点

接收一个指针（地址）
指针从二叉树的根结点开始遍历

递归的结束条件:指针指向空，则打印N，return
不满足递归条件，向深处递推:
1. 调用函数自己，传递节点左孩子的地址作为参数（相当于访问左子树）
2.调用函数自己，传递节点右孩子的地址作为参数（相当于访问右子树）
3.打印本节点数据（相当于访问根节点）

void BinaryTreePostOrder(BTNode* root)
{if (root == NULL){printf("N");return;}BinaryTreePostOrder(root->left);BinaryTreePostOrder(root->right);printf("%c", root->data);}

🍃层序遍历

层序遍历（Level-order Traversal）

从根节点开始，按层次从上到下、从左到右遍历二叉树

通常使用队列（Queue）来实现层序遍历。

如果树不为空，将它的根结点的地址作为数据，入队列

对队列的节点访问:
每次取队首的节点访问，将它的地址记录下来并出队列，同时将它的左右孩子（如果存在的话)入队列
当队列为空时，二叉树的层次遍历完成

层次遍历直接借用了以前已经实现好的队列，详细内容可以参考前置文章

【数据结构与算法】使用单链表实现队列：原理、步骤与应用_利用循环单链表(如下图)模拟实现队列操作,请给出入队enqueue过程,要求时间复-CSDN博客

// 层序遍历
void BinaryTreeLevelOrder(BTNode* root)
{Queue queue;QueueInit(&queue);//队列初始化if (root)//树的根节点入队列QueuePush(&queue, root);while (!QueueEmpty(&queue))//结束条件是队列为空{BTNode* tmp = QueueFront(&queue);//取队首元素打印数据并出队列printf("%c", tmp->data);QueuePop(&queue);//左右子树若不为空，入队列if (tmp->left)QueuePush(&queue, tmp->left);if (tmp->right)QueuePush(&queue, tmp->right);}printf("\n");QueueDestroy(&queue);
}

五、二叉树的扩展功能

🍃求节点个数

两种方式:

方式一:计数器方式
这种方式需要考虑的坑比较多——想要求得树的节点个数就得递归调用，所以用局部变量计数不可行（每次调用都会重置变量），静态局部变量也不可行（一次调用可行，多次调用会将值累加）

全局变量可行，但得在外部每次调用的时候对全局变量置零
指针的方式也可行:实参多传递一个变量的地址，形参用指针接收，多次调用也需要重新创建变量或置零

这两种方式的实现思路:
如果节点为空，返回
否则计数器++
再调用函数对左子树求个数
调用函数对右子树求值
函数不需要返回值，会通过全局变量/指针带出

方式一并不推荐，实现复杂容易出错，所以这里就不给出实现代码了、

方式二: 递归方式（推荐）

递归调用相加对于给定的二叉树节点，如果节点为空（NULL），则返回0（表示没有节点）。
否则，返回1（表示当前节点本身）加上左子树和右子树的节点数（递归调用）

// 二叉树节点个数
int BinaryTreeSize(BTNode* root)
{if (root == NULL)return 0;return 1 + BinaryTreeSize(root->left) + BinaryTreeSize(root->right);
}

🍃求叶子节点个数

解决方式与求二叉树的节点数量类似，同样使用递归实现，只是细节略有差异:

递归调用:

对于给定的二叉树节点，如果节点为空（NULL），则返回0（表示没有节点）。
如果节点左右孩子都为空，返回1（表示当前节点为叶子节点）
如果上面两个return都没有执行，说明该节点既不为空也不是叶子节点，返回左子树+右子树的叶子节点数（递归调用）

// 二叉树叶子节点个数
int BinaryTreeLeafSize(BTNode* root)
{if (root == NULL)return 0;if (root->left == NULL && root->right == NULL)return 1;return BinaryTreeLeafSize(root->left) + BinaryTreeLeafSize(root->right);
}

🍃求第K层节点个数

实现思路:
用递归的思路将问题分解

假设根结点为第一层，那么对于第一层，要求的是第k层；对于第二层，要求的是第k-1层……逐层分解，对于第k层，求的就是第一层

具体实现逻辑：

递归调用函数，参数有两个，分别是节点地址和k
如果节点为空，返回0
上述判断不成立，再判断如果k==1，返回1
如果上述都没有执行，说明节点既不为空，也不是第k层
递归调用函数，返回该节点的左孩子的k-1层的节点数+右孩子的k-1层的节点数（如果下一层k==1，则直接返回结果；如果不是，还会继续递归调用）

// 二叉树第k层节点个数
int BinaryTreeLevelKSize(BTNode* root, int k)
{if (root == NULL)return 0;if (k == 1)//走到这里，说明节点不为空return 1;return BinaryTreeLevelKSize(root->left, k - 1) + BinaryTreeLevelKSize(root->right, k - 1);}

🍃求二叉树的高度

二叉树的高度（或深度）是指从根节点到最远叶子节点的最长路径上的节点数。一个空树的高度定义为0

对于非空二叉树，其高度可以通过递归的方式计算：

如果树是空的，那么高度是0。
否则，高度是左子树和右子树高度的最大值加1（加1是因为要算上根节点）。

不过这里有一个坑要避免一下:

如果用三目操作符完成return语句，即:return（ root-＞left)＞（root-＞right)？（ root-＞left)+1:（root-＞right)+1

在树比较大时，时间会出现极端的增长
原因是第一次计算的结果没有被记录下来，每次都要重复计算两次，但第一层计算两次，第二层就多计算2*2次，第三层计算2*2*2次，以此类推，将会是一个非常恐怖的计算量

解决方式也很简单:
如果树是空的，那么高度是0。

否则，先求得左右孩子的高度记录并记录下来，两个值比较，将较大的值+1返回

//求树的高度
int BinaryHeight(BTNode* root)
{if (root == NULL)return 0;int leftHeight = BinaryHeight(root->left);int rightHeight = BinaryHeight(root->right);return leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;
}

🍃查找值为X的节点

实现思路:
递归遍历二叉树，查找值为x的节点
但有一个关键且容易被忽略的点，就是如何在递归调用的过程中，将查找到的节点的地址通过返回值带出来（因为是递归调用，所以必须让函数的第一层带出返回值）

实现方法：

递归调用函数

如果节点为空，返回NULL
上述未执行，再判断节点的值是否为x，如果是的话，返回该节点的地址（注意此处返回只能返回给上一层，不能跳出整个函数）

如果上述都未执行，再进一步判断:
调用函数获取左子树返回的值，如果该值不为空，说明获得了值为x的节点的地址，将该值返回给上一层
如果调用左子树未返回值，再调用函数获取右子树返回的值，如果改值不为空，说明获得了值为x的节点的地址，将该值返回给上一层

上述表达式都未返回结果，说明查不到值为X的节点，返回NULL

// 二叉树查找值为x的节点
BTNode* BinaryTreeFind(BTNode* root, BTDataType x)
{if (root == NULL)return NULL;if (root->data == x)return root;BTNode* n1 = BinaryTreeFind(root->left, x);if (n1)return n1;BTNode* n2 = BinaryTreeFind(root->right, x);if (n2)return n2;return NULL;
}