文章目录

• 二叉树的链式结构
• 链式结构的遍历
• 二叉树链式存储的实现
• • 二叉树节点的创建
  • 前序遍历
  • 中序遍历
  • 后序遍历
  • 二叉树元素个数
  • 叶节点的个数
  • 第k层节点的个数
  • 查找元素
  • 二叉树销毁
  • 二叉树的层序遍历
  • 判断是否为完全二叉树

二叉树的链式结构

二叉树的存储结构有顺序结构和链式结构两种，顺序结构我已经在上篇进行了详细的讲解，地址：数据结构-二叉树的顺序存储与堆（堆排序），本篇我们就主要讲解二叉树的链式存储。

二叉树的链式存储结构是指，用链表来表示一棵二叉树，即用链来指示元素的逻辑关系。 通常的方法是链表中每个结点由三个域组成，数据域和左右指针域，左右指针分别用来给出该结点左孩子和右孩子所在的链结点的存储地址 。链式结构又分为二叉链和三叉链，其结构如下图：

三叉链在后面讲解红黑树时再讲解，本篇我们主要先来以二叉链来学习一下二叉树的实现。

链式结构的遍历

我们知道二叉树的结构不是线性的，每一个节点都有两个子树，那如果我们想要访问一个二叉树中的所以元素时，我们应该以什么样的规律去访问呢，是先访问根节点还是先访问子树？这就涉及到了二叉树的遍历问题。
所谓遍历(Traversal)是指沿着某条搜索路线，依次对树中每个结点均做一次且仅做一次访问。访问结点所做的操作依赖于具体的应用问 题。 遍历是二叉树上最重要的运算之一，是二叉树上进行其它运算之基础。
遍历顺序一共分为4种，分别是：

1. NLR：前序遍历(Preorder Traversal 亦称先序遍历)——访问根结点的操作发生在遍历其左右子树之前。先根遍历
2. LNR：中序遍历(Inorder Traversal)——访问根结点的操作发生在遍历其左右子树之中（间）。中根遍历
3. LRN：后序遍历(Postorder Traversal)——访问根结点的操作发生在遍历其左右子树之后。后根遍历
4. 层序遍历：设二叉树的根节点所在层数为1，层序遍历就是从所在二叉树的根节点出发，首先访问第一层的树根节点，然后从左到右访问第2层上的节点，接着是第三层的节点，以此类推，自上而下，自左至右逐层访问树的结点的过程就是层序遍历。

简单来说，前，中，后序遍历就是以访问根节点的时间不同来划分的
前序：根->左子树->右子树
中序：左子树->根->右子树
后续：左子树->右子树->根

不同的遍历顺序有什么差异呢，比如我们现在想要遍历下面这个二叉树

我们可以发现不同的遍历顺序访问元素的顺序确实是不一样的。
二叉树的前，中，后序遍历属于深度优先的遍历方式，一般用递归实现。
层序遍历属于广度优先的遍历方式，一般借助队列实现。
他们的实现我就放在后面链式存储的实现中了。

二叉树链式存储的实现

在实现二叉树之前，我们要先创建一个二叉树节点的结构体类型，然后我们可以通过根节点对这个二叉树进行操作。

typedef char BTDataType;
typedef struct BinaryTreeNode
{
	struct BinaryTreeNode* left;  // 指向当前节点左孩子
	struct BinaryTreeNode* right; // 指向当前节点右孩子
	BTDataType data;              // 当前节点值域
}BTNode;

二叉树节点的创建

BTNode* CreateTreeNode(BTDataType x)
{
	BTNode* node = (BTNode*)malloc(sizeof(BTNode));
	node->data = x;
	node->left = NULL;
	node->right = NULL;
	return node;
}

1.动态开辟一个空间存放我们节点的值，把左右指针置空，返回节点的地址。
（该接口可以用来创建二叉树的所有节点）

前序遍历

根据根，左子树，右子树的顺序访问二叉树的所以值

void PrevOrder(BTNode* root)
{
	if (root == NULL)
	{
		printf("NULL ");
		return;
	}
	//根  左子树  右子树
	printf("%c ", root->data);
	PrevOrder(root->left);
	PrevOrder(root->right);
}

1.先判断节点是否为空，空就返回。
2.前序遍历，先访问根节点，那就是节点当前的值，在访问左子树，再访问右子树，使用递归的方法实现。

大伙可以看下面的流程图来更好的理解前序遍历的递归过程
我们还是遍历上图中的哪个二叉树。

中序遍历

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

1.判断是否为空树。
2.先递归访问左树，再访问节点自身，在访问右树。

我们还是来看图来观察一下递归的过程

后序遍历

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

1.判断节点是否为空，空就返回。
先访问左子树，再访问右子树，再访问自己。

老规矩，直接上图

二叉树元素个数

可以使用任意一种遍历顺序遍历二叉树，然后统计节点的个数

void TreeSize(BTNode* root, int* size)
{
	if (root == NULL)
	{
		return;
	}
	(* size)++;
	TreeSize(root->left,size);
	TreeSize(root->right,size);
}

需要注意的是，如果我们在函数里面定义size，那么在遍历递归时，我们是无法实现size叠加的功能的，因为每调用一次，就会对size进行一次临时拷贝，改变这个拷贝的值过后，当这一层的调用完成，栈帧销毁，size也被销毁了，改变没有起到任何效果，所以我们要在函数外面定义size，然后传入size的地址，通过地址就可以对size进行改变了。
如果我们不想在外面定义size，还要一种方法

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

即使用递归的方法计算节点个数，节点的个数就等于左子树的节点个数加右子树的节点个数在加自己的这一个，如果是空节点就返回0。

叶节点的个数

叶节点就是度为0的节点，即没有子树，与计算节点个数的递归方法类似，我们也可以使用递归的方法计算叶节点的个数

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

1.如果一个节点为空，那它的叶节点个数肯定为0
2.如果一个节点的左子树和右子树同时为空，说明这是一个叶节点，如果不是，就计算它的左子树的叶节点和右子树的叶节点之和就是当前节点以下的所以叶节点。
3.根节点进入函数后，就先判断根节点是不是叶节点，如果不是，就计算根节点左右子树的叶节点的和，形成递归。

第k层节点的个数

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

同样是使用递归的方法
1.如果节点为空，那节点的个数就为0.
2.如果我们要计算第k层的元素个数，我们先从根节点开始，假设我们每向下一层k就减1，那么当k=1时，表示我们来到了第k层，然后计算k=1时的节点个数返回相加即可。

查找元素

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

1.如果节点为空，就返回空。
2.如果节点的值等于要查找的值，就返回节点的坐标。
3.如果节点不为空，值也不是我们要查找的值，就查找节点的左子树，如果查找的结果不为空，就代表找到了，就返回。
4.如果左子树的查找结果为空，就查找右子树，如果找到就返回，找不到就返回空。

二叉树销毁

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

销毁二叉树需要把二叉树的每个节点都销毁，所以首先，我们的销毁顺序应该是后序。
其次，我们节点里存放的是左右孩子的指针，如果我们传节点的指针类型的话，那么函数里面的左右孩子的地址就是一份临时拷贝，在函数里我们用这个拷贝的地址释放节点没问题但是我们无法对每个节点的指针进行置空，所以销毁二叉树时我们要传二级指针。

二叉树的层序遍历

层序遍历就是一层一层的遍历，在链式储存中，我们一般借助队列来实现层序遍历。
我们先把我们前面实现的栈的代码复制到我们现在的工程中（链接在数据结构-栈和队列详解），然后包含好栈的头文件。
我们利用的就是队列的先进先出的性质，
1.先让根入队。
2.出队头的数据，再让队头数据的左右孩子入队。
看一下下面的流程图就明白了

图里的小红圆圈代表空（手不太稳，可能与圆有那么一点点的偏差），我们每从队头删除掉一个元素，就让这个元素的两个孩子入队，直到队列为空为止，最后我们访问的顺序刚好就是层序遍历的顺序，下面我们就对这个代码进行实现吧。

void TreeLevelOrder(BTNode* root)
{
	Queue q;
	QueueInit(&q);
	if (root)
	{
		QueuePush(&q, root);
	}
	while (!QueueEmpty(&q))
	{
		BTNode* front = QueueFront(&q);
		QueuePop(&q);
		printf("%c ", front->data);
		if (front->left)
		{
			QueuePush(&q, front->left);
		}
		if (front->right)
		{
			QueuePush(&q, front->right);
		}
	}
	printf("\n");
	QueueDestory(&q);
}

1.首先我们要创建一个队列，对队列进行初始化。
2.让二叉树的根入队（注意修改队列元素的类型）。
3.判断队列是否为空，如果队列为空，说明遍历已经结束了，换一个行然后销毁队列。
4.如果队列不为空，就让把队头的节点拷贝出来，然后删除队头的节点，把刚刚拷贝的节点的数据打印一遍，然后让拷贝接节点的左右孩子先后入队。如果孩子没有子节点，相当于把NULL入队，并不影响结果。

判断是否为完全二叉树

其思想与二叉树的层序遍历类似，如果一个树不是完全二叉树时，那么但我们对它进行层序遍历时，其节点的中间就会有NULL，我们就可以通过这一点来判断是否为完全二叉树。

bool BinaryTreeComplete(BTNode* root)
{
	Queue q;
	QueueInit(&q);
	if (root)
	{
		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)
		{
			return false;
		}
	}
	QueueDestory(&q);
	return true;
}

1.前半部分与二叉树的层序遍历一样，建队列，根入队，队列不为空，进入while循环，在循环中删队头节点，然后让该节点的左右孩子入队。
2.这里循环停止的条件还要加上一个即堆顶的元素为空，在跳出循环后，有两种情况，第一种是队列已经空了，节点之间没有空，表明是一个完全二叉树，返回true，第二种情况是队列并不为空，只是在访问队头节点时访问到了NULL，这时我们要再次进行循环，如果队列不为空，我们就进入循环挨个查找并删除队头的节点，如果发现一个不为空的节点，就说明节点之间有NULL相隔，说明不是完全二叉树，返回false。