数据结构——原来二叉树可以这么学？（4.链式二叉树）

用户11295429

发布于 2024-10-16 17:08:11

710

发布于 2024-10-16 17:08:11

文章被收录于专栏：王的博客专栏

前言：

在前两篇小编讲述了二叉树的顺序结构存储方式，从而讲到了一个特殊的二叉树——堆，通过对于堆的实现来帮助我们对于顺序结构存储方式的实现，下面小编将要讲述二叉树的另一种存储方式——链式结构，链式二叉树来喽，那么废话不多说，代码时间到~

正文：

1.链式二叉树的创建

1.1.二叉树结点的创建

本文的标题就已经表明了此时的二叉树我们肯定使用链表实现的，即用链来指各元素之间的逻辑关系。结点的创建方法有很多种，下面小编就先给读者朋友介绍我用的结点创建方法，小编就把这种方法称之为左右子树法（这不是官方的名字，这是小编自己造的），就是在结点的结构体中，我们存有数值，以及左右指针，左右指针分别存放左孩子和右孩子的地址，下面小编直接上代码来给各位展示此结点的结构：

typedef int BTDataType;  

typedef struct  BinaryTreeNode {
	//存数据
	BTDataType data;    //可以理解为数据域
	//左结点（左孩子）
	struct  BinaryTreeNode* left;
	//右节点（右孩子）
	struct  BinaryTreeNode* right;
}BT;

1.2.手动创建二叉树

可能很多读者朋友看到这个会很疑惑，为什么链式二叉树需要我们去手动创建，而不是通过函数来进行创建，小编其实在学习的时候也很疑惑，之后老师也做出了解释，我们需要手动创建二叉树的原因是因为二叉树的限制其实不多，它对于结点的插入并没有什么硬性的需求，所以此时我们没必要写函数去实现，之后的二叉搜索树什么的就有很大的要求，那个时候我们就不可以手搓二叉树了，就得通过函数实现了，所以此时我们仅需手动创建二叉树即可，对于二叉树的手动创建是蛮容易的，此时我们需要用到一个我们的老朋友函数：新结点创建的函数，这个函数小编在以前多次写到过，此时我就不在多赘述了，下面先给出创建新结点的函数：

BT* newbuynode(BTDataType x)
{
	BT* pour = (BT*)malloc(sizeof(BT));
	assert(pour);
	pour->data = x;
	pour->left = pour->right = NULL;
	return pour; //别忘记return
}

之后我们仅需手动去创建多个结点，然后通过左右子树把他们连起来即可，类似我们链表的连法，下面小编直接给出代码：

	BT* node1 = newbuynode(1);
	BT* node2 = newbuynode(2);
	BT* node3 = newbuynode(3);
	BT* node4 = newbuynode(4);
	node1->left = node2;
	node1->right = node3;
	node2->left = node4;   //建立二叉树

等一会小编讲述下面内容的时候小编会拿上面这个简短的二叉树来进行了解，这里先给各位读者朋友解释一下，下面我们就要进入二叉树的遍历喽~

2.前中后序遍历

2.1.前序遍历（先序遍历）

2.1.1.前序遍历的理论讲解

可能很多读者朋友对前序遍历这个名字是感到有点陌生的，前序遍历其实就是访问根结点的顺序在左右子树之前，也就是说我们是先访问根结点的数据，然后在取访问根结点的左右孩子，从而我们可以知道前序遍历的遍历顺序是根结点——左子树——右子树（俗称根，左，右），此时我们想要打印二叉树结点的数据就可以用前序遍历的方式进行打印，我们需要先打印根结点的数据，然后在分别打印左孩子，左孩子也得通过前序遍历的方式进行打印，等左孩子打印完之后，我们就可以进行打印右孩子的数据了，右孩子同样也需要进行前序遍历的方式进行打印，打印完之后，我们就可以实现出一个二叉树的前序遍历，这便就是理论部分，下面小编将会讲述代码部分（准备开始递归风暴吧~）

2.1.2.前序遍历的代码实现

在经过理论部分的解释，可能有读者朋友想到了我们在C语言阶段学习的一个大头——函数的递归，没错，前序遍历就是依靠函数的递归进行实现的，函数递归的特点就是把一个大的事情划分wield好几个小事情进行解决，直到子问题不能在进行拆分了，递归就结束了，这正好就符合了前序遍历的打印，当然，我们一定要在函数内部设置一个结束递归的条件，不然就会一直递归下去从而导致栈溢出，对于前序遍历函数的实现其实是很容易的，但是，理解下来可能就不会这么容易了，下面小编先来说一下这个题目的代码怎么写。

首先，我们肯定是要先设置递归条件的，这个条件的设置也很容易，当我们递归到空结点的时候，此时就无法在往下递归了，此时我们直接return结束这个函数栈帧就好，之后我们根据根，左，右的原则，我们先打印此时结点的值，然后在递归左孩子，右孩子即可，此时我们就写完了这个函数，是不是感觉写起来很简单？下面小编先给出代码，然后在通过这个代码给各位读者朋友更详细的解释：

//前序遍历二叉树（根左右）
void PreOrder(BT* root)
{
	if (root == NULL)
	{
		return;
	}
	printf("%d ", root->data);
	PreOrder(root -> left);
	PreOrder(root -> right);	
}

2.1.3.前序遍历的代码解释

对于上述的代码，对于对函数递归还感到很陌生的读者朋友可能会有疑惑，小编此时通过图文的方式来帮助各位读者朋友去更好的了解：

刚开始，我们先借助我们刚刚手动创建的二叉树先生成一颗二叉树：

之后我们就要开始进行递归了，看代码，首先我们先要判断此时结点是否为空，很明显根结点此时并不为为空，我们直接打印它的数值，也就是1，然后我们开始左子树的递归：

还是先判断一下左孩子是否为空的结点，很明显不是，然后我们打印完数值2以后，继续往下去进行左孩子的递归：

之后我们先判空，不是后打印数值4，此时我们仍需完成左孩子的递归，此时我们可以知道这时的左孩子已经是空了，然后我们向右递归右孩子，也是空的，此时我们就结束了4这个函数的栈帧，我们开始往上进行传递：

之后我们再去判断2这个结点的右孩子是否为空，很明显右孩子的确是空的，此时直接返回就好了，然后2这个函数栈帧也结束了，我们继续往上走：

此时我们回到了根结点，此时我们在进行判断右孩子是否为空，很明显不为空，此时我们打印完3之后，继续左孩子右孩子递归，很明显左孩子和右孩子都是空的，所以我们仅需返回就好，此时3这个函数栈帧结束，返回后也代表着最初的函数成功递归完成，函数功能完成，函数栈帧销毁：

此时这个函数就已经完成，小编在前序遍历详细讲一讲递归的过程，之后的中序遍历和后续遍历小编就可能一笔带过了，因为其实原理都是一样的，下面给出这个代码的运行图：

2.2.中序遍历

2.2.1.中序遍历的理论部分

中序遍历通过它的名字我们就可以知道，根结点是在左子树和右子树之间进行访问的，所以从这我们就可以知道，前中后序遍历，其实是通过访问根结点的顺序来进行区分的，所以中序遍历的访问顺序是：左子树 ——根结点——右子树（俗称左根右），我们先访问左子树的值，然后在访问根结点的值，最后访问右子树的值，这样以来我们就实现了中序遍历，下面进入代码讲解。

2.2.2.中序遍历的代码实现

此时我们肯定也是用到了函数递归，第一步，我们依旧是确定递归的条件，此时递归的条件和前序遍历是一样的，我们仍需判断此时递归传过来的结点是不是空的结点，如果是空的结点，我们直接返回结束函数就好，之后我们打印的顺序自然是不能放在开头了，我们先递归左子树，然后打印结点的数据，之后在递归右子树，此时我们的函数也是写完了，与我们写前序遍历的函数是类似的，只不过此时打印的位置往后走了一下而已，下面小编给出代码图，然后在简单的各位读者朋友讲述一下原理：

void InOrder(BTNode* root)
{
	if (root == NULL)
	{
		return;
	}
	InOrder(root -> left);
	printf("%d ", root->date);
	InOrder(root->right);
}

2.2.3.中序遍历的代码讲解（极简版）

由于小编在前序遍历的时候就已经详细的解释了我们如何借助递归来实现前序遍历的，此时我们中序遍历不能说是和前序遍历一样，只能说差距不大，小编通过给出几行文字来帮助各位读者朋友进行了解。先给出前面我们创建的二叉树的图，防止读者朋友忘记：

首先，我们还是按照上面手动创建的二叉树为例，此时我们先判断结点是否为空，很明显不是，所以我们进行左子树的递归，此时到了2这个结点，然后我们继续判断是否为空，很明显不是，然后我们继续递归，此时到了4，这个结点也不是空的，我们需要继续递归，此时递归下去的结点就是空的，所以我们直接返回就好，然后我们就可以打印4这个数据了，然后我们往右进行递归，很明显右孩子也是空的，此时我们直接返回就好，4这个函数栈帧就结束了，以此递推，我们就完成了中序遍历，下面小编给出中序遍历的运行结果：

2.3.后序遍历

2.3.1.后序遍历的理论讲解

后序遍历通过它的名字我们便可以知道此时我们根结点肯定是放在最后面了，访问根结点的操作是放在了左右子树之后了，所以后序遍历的遍历顺序是：左子树——右子树——根结点（俗称左右根），我们先访问左子树的值，然后访问右子树的值，最后在访问根结点的值，在知道了前序遍历和中序遍历以后，后序遍历简直就是so easy，下面进行代码实现部分。

2.3.2.后序遍历的代码实现

后序遍历的代码实现也很轻松，首先涉及到递归，我们肯定要设置递归结束的条件，还是判断此时的结点是否为空，如果为空的话，我们直接return结束此函数即可，之后我们先往左子树进行递归，再往右子树进行递归，最后我们在打印数据即可，此时我们就完成了函数的实现，下面小编先给出代码，然后在更简短的讲述一下代码原理：

void PostOrder(BTNode* root)
{
	if (root == NULL)
	{
		return;
	}
	PostOrder(root -> left);
	PostOrder(root -> right);
	printf("%d ", root->date);
}

2.3.3.后序遍历的代码讲解（极简版）

在经过前面递归代码的摧残以后，小编相信读者朋友可能已经大致明白了我们如何通过递归实现遍历，但是可能有些读者朋友还会感到一些模糊，所以小编就在简单讲述一下原理，老规矩，先放上前面小编创建的二叉树：

首先我们还是先判断结点是否为空，很明显此时不为空，我们先往左进行递归到2，然后经过同样的处理，继续往左边递归到4，此时4的左右子树都是空的，所以此时我们打印完4以后就可以往上进行回归操作，此时回到2,2的右子树是空的，所以我们打印完2以后继续回归，回归到1以后，我们就可以进行向右递归判断，递归到3以后，可知3的左右孩子都是空的，所以打印完3以后就回归到1，此时1的左右子树递归完成，打印完1以后函数栈帧结束，此时函数功能实现，下面小编给出此时后序遍历的运行图：

此时我们就讲述完了前中后序遍历，下面我们就要开始进行二叉树其余功能的实现了，大家做好车，准备出发，去迎接递归风暴喽~

3.二叉树其余功能的实现

3.1.二叉树结点个数（int BinaryTreeSize(BTNode* root)）

3.1.1.功能解读

此功能是想让我们去求结点的个数，此时我们需要分别统计左子树和右子树的结点个数，之后再加上根结点1即可，这个功能说起来是很好实现的，但是当我们想要通过代码去实现的时候，可能会有一些困难，可能一些读者朋友认为可以设置一个全局变量，然后我们通过不断的递归，每递归一次这个变量就加1，来去实现这个功能就好了，小编当初也这么想过，经过打印后也确实做到了，不过这个指定是错误的，因为此时这个全局变量的值已经发生改变，当我们又再次想计算二叉树结点个数时，此时就相当于二叉树结点个数+二叉树结点个数，所以这个方法直接out掉，不过，这个方法有一半是正确的，就是这个题目的实现，我们还是需要用到递归来做，下面小编就给出此代码正确的代码实现。

3.1.2.代码实现

此函数涉及到了递归的知识，所以我们首先需要去写递归结束的条件，条件和上面的遍历的条件是一样的，如果此时的结点是空的话，我们直接返回0就好，之后我们仅需直接返回1（根结点）+递归左子树+递归右子树就可以实现出这个功能，此时这个函数就实现完成了，可能很多读者朋友会懵，这个题目就这么完成了？不要急，小编先给出代码，之后在给上代码解释：

int BinaryTreeSize(BTNode* root)
{
	if (root == NULL)
	{
		return 0;
	}
	return  BinaryTreeSize(root->left) + BinaryTreeSize(root->right) + 1;
}

3.1.3.代码讲解

下面小编会继续用上面创建的二叉树作为例子，来帮助各位读者朋友去明白这个代码的意义：

首先我们先去判断1这个结点是否为空，指定不是空的，之后我们便开始向左进行递归，然后继续判断是否为空，可看出2不为空，之后继续向左递归，此时4这个结点不是空，然后向左递归，发现为空，返回0，在向右结点递归，发现也为空，返回0，之后我们返回0+0+1也就是1，此时这个函数栈帧就结束了，销毁后开始往上回归：

回归到2这个结点以后，我们在递归2的右子树，发现右子树为空，此时返回的是0，然后2这个结点的函数返回1（左子树）+ 0 + 1（本身）也就是2后函数栈帧销毁，继续往上回归：

此时1这个根结点的左子树递归完毕，开始递归右子树，此时3这个结点不是空，不过它的左右子树都是空，此时我们返回0即可，之后3这个结点左右子树递归完毕，返回0+0+1也就是1之后，三这个子树递归完毕，此时1的右子树也递归完毕，同样的返回2 （左子树）+ 1（右子树） +1（本身）也就是4即可，此时这个函数栈帧也结束了，整个函数也已经结束，此时我们可以知道此二叉树的结点个数是4：

下面小编给出这个功能的运行图，然后我们继续下一个功能的实现：

3.2.叶子结点个数（int BinaryTreeLeafSize(BTNode* root)）

3.2.1.功能解读

叶子结点的概念可能很多读者朋友都已经忘记了，小编在这里先简单的带着各位回忆一下，叶子结点就是一个结点，没有左右孩子，此时这个结点被称之为叶子结点，此时这个题目想让我们去求叶子结点的个数，此时我们可以依靠它这个性质来去求解叶子结点，通过分别求左右子树的叶子结点从而做到求到整个树的叶子结点，下面小编在代码部分会告诉大家如何实现这个代码。

3.2.2.代码实现

此时我们想要求到左右子树的叶子结点，递归是不可或缺的，此时我们首先要知道递归的条件，此时递归的条件和上面是一样的，当结点为空时直接返回0即可，此时与上面不同的是，我们需要判断一个结点，如果它的左右子树都是空的话，说明这个是也子结点，直接返回1，最后我们返回左子树+右子树的值即可，此时这个函数就写完了，感觉写完了上面那个函数以后，这个函数写起来可以说是很轻松，下面小编给出代码：

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

3.2.3.代码讲解

为了防止各位读者朋友不太理解上面的代码，下面小编继续通过上面的例子来帮助各位理解这个代码：

此时1这个结点不是叶子结点，往左递归到2，2这个结点也不是叶子结点，继续往左递归到4，此时4这个结点的左右子树均为空，说明是叶子结点，返回1，然后回归到上一层：

之后我们递归2的右子树，可以知道2的右子树为空，所以返回0，此时2的函数栈帧已经结束，继续回归到1，然后递归1的右子树，可知3这个结点的左右子树都是空，所以是叶子结点，直接返回1,3的函数栈帧销毁，回归到1，然后1这个结点返回1+1后也完成了函数栈帧销毁，之后整个函数功能完成，我们也知道了叶子结点是2个：

下面小编给出运行图：

3.3.二叉树第k层结点的个数（int BinaryTreeLevelKSize(BTNode* root, int k)）

3.3.1.功能解读

此时我们已经来到了函数的第三个功能，这个功能通过名字我们就可以大致知道什么意思了，其实就是想让我们寻找某一层的结点个数，就比如我们想要寻找第二层的结点，通过上面的二叉树为例，我们可以知道结点个数是2个，所以这个功能就要考察我们去实现二叉树第k层结点的能力，这里我们也得分别求出左右子树第k层结点的个数，然后相加即可，下面小编就要用代码去实现它喽~

3.3.2.代码实现

通过功能解读，各位可以知道我们仍需要知道左右子树，所以我们还得用到本文最常出现的它——递归来实现，所以我们还需要写递归的判断条件，自然还是如果此结点为空，我们直接返回0即可，下面我们思考的方向就是我们如何去找到第k层的结点，其实也很容易，我们每次递归左右子树的时候，k都要去减1，当k==1的时候，此时便到了我们想要层数的结点的个数，我们直接返回1即可，之后我们仅需把左右子树递归的结果相加，然后返回即可，这便是这个题目的解题流程，可能有些读者朋友还会有些许疑惑，不要着急，小编在放完代码后还是会对代码进行讲解的，下面小编先给出代码：

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

3.3.3.代码讲解

此时小编还是通过上面的二叉树作为例子，此时我们就寻找二叉树第二层的结点个数：

此时我们先去判断1这个结点是否为空，很显然不为空，此时k也不等于1，此时我们先递归左子树，并且此时k-1到1，之后到了2这个结点，这个结点的k值正好为1，说明此时就是我们想要找的那一层，我们直接返回1：

之后我们去递归1的右子树，此时3这个结点的层数也符合我们想要寻找的层数，我们直接返回1，之后1这个结点的左右子树都已递归完毕，我们返回1+1后，此函数栈帧销毁，函数功能实现完毕：

此时函数功能实现完毕，下面我们来测试一下代码是否可以正常运行：

3.4.二叉树的高度/深度（int BinaryTreeDepth(BTNode* root)）

3.4.1.功能解读

这个功能其实读者朋友一读就可以明白，这个还是比较直观的，我们此时需要去求二叉树的高度，也就是说一共有几层二叉树，此时我们仍需知道左右子树，通过左右子树的比较大小，最大的那个就代表着二叉树有几层，下面我们开始进行代码实现。

3.4.2.代码实现

此时我们还是需要通过递归来实现这个题目，递归条件和上面一样，我们仅需判断结点是否为空，如果为空我们之间返回0即可，之后我们需要通过保存左右子树递归的值，然后我们通过判断左右子树递归的大小来寻找最大的值，之后我们让此值加一，至于我们为何去找最大的值，因为二叉树的高度取决于结点的位置而不是结点的个数，如果左子树结点多但是矮，右子树结点少但是高，那么二叉树的高度自然是按照右结点的高度来，此时我们就实现了这个函数，由于小编在前面讲述了不少递归的知识，小编来考验一下大家对于此代码的理解能力，对于此函数的解释各位先不看，看自己是否可以理解这个代码，下面给上代码：

int BinaryTreeDepth(BTNode* root)
{
	if (root == NULL)
	{
		return 0;
	}
	int left = BinaryTreeDepth(root->left);
	int right = BinaryTreeDepth(root->right);
	return left > right ? left + 1 : right + 1;
}

3.4.3.代码讲解

此时我们还是按照上面的二叉树进行讲解，图小编就不复制过来开了，各位读者朋友可以翻到上面看一看，此时我们首先要判断1这个结点是否为空，肯定不是空，然后我们向左疯狂递归，直到递归到4的左结点，此时可以知道结点为空，我们返回0即可，之后我们在递归4的右子树，也为空，此时我们就可以判断left和right的大小，此时左等于右，所以right+1也就是1，此时4的函数栈帧结束，回归到2这个结点：

之后我们递归2的右子树，此时为空返回0，然后比较left和right的大小，很显然我们返回left+1也就是2即可，之后我们就要判断1这个结点的右子树，然后在通过同样的方法得出right为1，此时left为2，所以我们返回3，函数栈帧结束，函数功能实现完毕，我们得出此时的层数是3：

老规矩，我们还是检测一下此时代码的正确性：

3.5.二叉树查找值为x的结点（BTNode* BinaryTreeFind(BTNode* root, BTDateType x)）

3.5.1.功能解读

这个功能也很好描述，这个功能名就说明了此时我们需要求二叉树中数值为x的结点，如果找到我们就返回该结点，如果没有找到我们直接传空就好，此时我们仍需需要找到左右子树，来寻找到我们想要的数值为x的结点，如果找到了我们直接返回结点即可，下面进入代码实现部分。

3.5.2.代码实现

此时我们仍需用到递归的知识来帮助我们找左右子树，此时我们还是要写递归的条件，与上面一样，当此时的结点为空时，我们返回NULL即可，之后还需要判断此时结点的值是否是x，如果是x的话，我们直接返回结点即可，之后我们递归左子树，当此时左子树递归到的结点的数据存放着x时，我们直接返回结点即可，如果还是没有，我们向右递归右子树，如果右子树递归到的结点的数据存放着x，我们还是返回结点即可，如果此时左右子树递归完毕我们还没有找到想要结点的时候，此时我们直接返回NULL即可，证明该二叉树中是没有我们想要找到的结点的，此时这个函数功能实现完毕，下面小编给出代码：

BTNode* BinaryTreeFind(BTNode* root, BTDateType x)
{
	if (root == NULL)
	{
		return NULL;
	}
	if (root->date == x)
	{
		return root;
	}
	BTNode* left = BinaryTreeFind(root->left, x);
	if (left->date == x)
	{
		return left;
	}


	BTNode* right = BinaryTreeFind(root->right, x);
	if (right->date == x)
	{
		return right;
	}

	return NULL;
}

3.5.3.代码讲解

为了帮助各位读者朋友去更好的掌握这个函数的知识点，小编还是简单的说一下此时的代码是如何来实现的，下面我们以上面创建的二叉树为例，然后x是2来作为例子进行讲解，此时我们先判断1这个结点是否为空，指定不是空的，我们在判断数据是否是2，也不是，开始往左子树进行递归，递归到2这个结点，这个不仅不是空的，而且此时的结点存放的数据正好是我们想要找的，此时我们直接返回该结点：

之后我们在进行完左子树递归的时候，此时我们触碰到下一个if语句，此时我们直接返回2这个结点即可，此刻1这个函数栈帧销毁，函数功能实现完毕，下面小编给出最后的流程图以及小编检测此时的代码是否可以正常运行：

3.6.二叉树的销毁（void BinaryTreeDestory(BTNode** root)）

3.6.1.功能解读

此时我们终于来到了最后一个功能的讲解，在我们实现完一系列的功能，此时二叉树的任务就完成辣，下面我们就要进行销毁结点的部分了，因为此时我们需要销毁根结点，想要彻底消除根结点，我们就需要去传根结点地址的地址，也就是用二级指针来进行接受，下面开始进入我们的代码实现部分：

3.6.2.代码实现

首先，因为我们还需要把左右子树进行销毁，所以我们还是要有递归的知识，递归条件还是如果此时结点为空，我们直接return即可，之后的操作其实就和我们上面写的后序遍历一样，我们需要先销毁左右子树的结点，最后我们在销毁根结点，所以我们先向左子树递归，再往右子树递归，之后我们直接把该结点free掉，然后让它指向空即可，养成好的代码习惯。减少野指针的出现，从你我做起，此时这个函数的功能就实现完毕了，下面小编展示一下代码：

void BinaryTreeDestory(BTNode** root)
{
	if (*root == NULL)
	{
		return;
	}
	BinaryTreeDestory(&((*root)-> left ));
	BinaryTreeDestory(&((*root)-> right ));
	free(*root);
	*root = NULL;
}

3.6.3. 代码讲解（简单说说了）

因为此时的代码和上面的后续遍历除了最后部分有差异其他其实都是一样的，所以我相信各位读者朋友可以很快了解这个代码，当然忘了的话也可以往前面看，小编就从这里简单的说一下这个代码的实现流程，首先我们还是看此时1这个结点是否为空，肯定不为空，然后想左递归，一直递归到4这个结点的时候，开始递归4的左右子树，很明显都是空，然后我们把4销毁后回归，然后以此销毁2,3,1后，此时我们就把整个二叉树进行销毁了，我们就正式的完成了这个代码的功能，各位读者朋友写完后一定要测试自己代码的正确性，小编刚才在调试的时候，在调用函数的时候，实现忘记&node1，而是直接node1，导致我找错误找了很久，所以读者朋友们一定好好的去写每一行代码，减少自己找错的机会。

此时小编已经写完了链式二叉树一些比较基本的功能，下面小编先给出链式二叉树所有的代码供各位读者朋友参考~

4.代码展示

4.1.Tree.h

#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>
#include<string.h>


//今天来复习一下链式二叉树的写法，得加快复习的脚步了~

typedef int BTDateType;

typedef struct BinaryTreeNode
{
	BTDateType date;
	struct BinaryTreeNode* left;//左孩子
	struct BinaryTreeNode* right;//右孩子
}BTNode;

//前序遍历
void PreOrder(BTNode* root);

//中序遍历
void InOrder(BTNode* root);

//后序遍历
void PostOrder(BTNode* root);

//二叉树结点个数
int BinaryTreeSize(BTNode* root);

//叶子结点的个数
int BinaryTreeLeafSize(BTNode* root);

//二叉树第k层结点的个数
int BinaryTreeLevelKSize(BTNode* root, int k);

//二叉树的高度/深度
int BinaryTreeDepth(BTNode* root);

//二叉树查找值位x的结点
BTNode* BinaryTreeFind(BTNode* root, BTDateType x);

//二叉树销毁
void BinaryTreeDestory(BTNode** root);

4.2.Tree.c

void PreOrder(BTNode* root)
{
	if (root == NULL)
	{
		return;
	}
	printf("%d ", root->date);
	PreOrder(root -> left);
	PreOrder(root -> right);
}

void InOrder(BTNode* root)
{
	if (root == NULL)
	{
		return;
	}
	InOrder(root -> left);
	printf("%d ", root->date);
	InOrder(root->right);
}


void PostOrder(BTNode* root)
{
	if (root == NULL)
	{
		return;
	}
	PostOrder(root -> left);
	PostOrder(root -> right);
	printf("%d ", root->date);
}


int BinaryTreeSize(BTNode* root)
{
	if (root == NULL)
	{
		return 0;
	}
	return 1 + BinaryTreeSize(root->left) + BinaryTreeSize(root->right);
}



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


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


int BinaryTreeDepth(BTNode* root)
{
	if (root == NULL)
	{
		return 0;
	}
	int left = BinaryTreeDepth(root->left);
	int right = BinaryTreeDepth(root->right);
	return left > right ? left + 1 : right + 1;
}


BTNode* BinaryTreeFind(BTNode* root, BTDateType x)
{
	if (root == NULL)
	{
		return NULL;
	}
	if (root->date == x)
	{
		return root;
	}
	BTNode* left = BinaryTreeFind(root->left, x);
	if (left->date == x)
	{
		return left;
	}


	BTNode* right = BinaryTreeFind(root->right, x);
	if (right->date == x)
	{
		return right;
	}

	return NULL;
}


void BinaryTreeDestory(BTNode** root)
{
	if ((*root) == NULL)
	{
		return;
	}
	BinaryTreeDestory(&((*root)-> left ));
	BinaryTreeDestory(&((*root)-> right ));
	free(*root);
	*root = NULL;
}

5.总结

终于讲完了链式二叉树，这是小编第二次写的万字博客，本来一下午就可以写完的，我硬生生的又拖了一天，小编这篇博客讲述的我自认为算是比较详细的了，当然小编有的还是偷了懒少写了点，不过无伤大雅，此时链式二叉树其实小编还有两个功能没有实现，那两个功能涉及到了队列的知识，小编先简单透露一下，如果本文有一些错误，欢迎各位读者朋友在评论区指出，小编看到消息后会及时更正，那么，我们下一篇博客见啦~

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2024-10-16，如有侵权请联系 cloudcommunity@tencent.com 删除

函数

本文分享自作者个人站点/博客前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体同步曝光计划，欢迎热爱写作的你一起参与！

登录后参与评论

0 条评论

热度