二叉树链式存储实现及其遍历_链式存储的图如何广度遍历

1 二叉树的链式存储

1.1 链式存储实现方式

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

1.2 二叉树结点

如图所示
代码可以这样定义

typedef struct BinaryTreeNode
{
	BinaryTreeDataType _data;
	struct BinaryTreeNode* _left;
	struct BinaryTreeNode* _right;
} BTNode;
1
2
3
4
5
6

每个结点的左右指针不可以胡乱指向，我们可以这样初始化结点：

BTNode* CreateBinTreeNode(int x)
{
	BTNode* node = (BTNode*)malloc(sizeof(BTNode));
	node->_data = x;
	node->_left = NULL;
	node->_right = NULL;
	return node;
}
1
2
3
4
5
6
7
8

2 二叉树的遍历

2.1 深度优先遍历

所谓遍历（Traversal）是指沿着某条搜索路线，依次对树中每个结点均做一次且仅做一次访问。访问结点所作的操作依赖于具体的应用问题。遍历是二叉树最重要的运算之一，是二叉树进行其他运算的基础。
那么什么是深度优先遍历呢？
简单来说就是沿着二叉的一条路径走到尾从根结点到叶子结点遍历，直接上图

前/中/后序遍历都是深度优先遍历。

2.1.1 前序遍历

任何一颗二叉树都可以看作根结点（N）、左子树(L)、右子树®。那么根据访问根节点的先后顺序可以把深度优先遍历二叉树分为这三种顺序。
NLR：（preorder traversal）也称为先根遍历-----访问结点的操作发生在遍历左右子树之前即：根、左子树、右子树。每个子树都要按照这个顺序遍历，你会发现遍历一颗二叉树是一个递归的过程。


代码实现如下：

void PrevOrder(BTNode* root)
{
	if (root == NULL)
	{
		printf("NULL ");
		return;
	}
	printf("%c ", root->_data);
	PrevOrder(root->_left);
	PrevOrder(root->_right);
}
1
2
3
4
5
6
7
8
9
10
11

2.1.2 中序遍历

LNR:(inorder traversal)也称为中根遍历—访问结点的操作发生在遍历左右子树之间即：左子树、根、右子树。每个子树都要按照这个顺序遍历。

代码实现如下：

void InOrder(BTNode* root)
{
	if (root == NULL)
	{
		printf("NULL ");
		return;
	}
	InOrder(root->_left);
	printf("%c ", root->_data);
	InOrder(root->_right);
}
1
2
3
4
5
6
7
8
9
10
11

2.1.3 后序遍历

LRN:(inorder traversal)也称为后根遍历—访问结点的操作发生在遍历左右子树之间即：左子树、右子树、根。每个子树都要按照这个顺序遍历。
有了前序和中序的图，后序的就比较好理解了，直接给出遍历结果：

代码实现：

void PostOrder(BTNode* root)
{
	if (root == NULL)
	{
		printf("NULL ");
		return;
	}
	PostOrder(root->_left);
	PostOrder(root->_right);
	printf("%c ", root->_data);
}
1
2
3
4
5
6
7
8
9
10
11

2.2 广度优先遍历

二叉树的层序遍历其实是广度优先遍历。
其实顾名思义，如果把根结点作为第一层从最外层一层一层剥开就把二叉树遍历完了。
层序遍历不需要递归，需要用其他的基本数据结构作为辅助，要用到队列。

代码实现如下：

void BinaryTreeLevelOrder(BTNode* root)
{
	Queue q;
	QueueInit(&q);
	if (root == NULL)
	{
		QueueDestory(&q);
		return;
	}
	//不等于NULL就先把root送进队列
	QueuePush(&q, root);
	while (!QueueEmpty(&q))
	{
		BTNode* front = QueueFront(&q);
		QueuePop(&q);
		printf("%c ", front->_data);
		//把front的左右孩子也送进队列,空队列的不进入队列了
		if (front->_left)
		{
			QueuePush(&q, front->_left);
		}
		if (front->_right)
		{
			QueuePush(&q, front->_right);
		}
	}
	QueueDestory(&q);
	printf("\n");
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

3 二叉树的最大深度&k层结点个数&叶子结点个数&

3.1 二叉树的深度

有了上面的递归遍历的知识，求二叉树的深度就比较好理解了，假定根结点是第一层，则最大深度为：1+左右子树深度的较大值。
代码实现如下：

int TreeDepth(BTNode* root)
{
	if (root == NULL)
	{
		return 0;
	}
	//把左子树和左子树的深度先保存
	//否则重复计算太多
	int leftDepth = TreeDepth(root->_left);
	int rightDepth = TreeDepth(root->_right);

	return leftDepth > rightDepth ? leftDepth + 1 : rightDepth + 1;
}
1
2
3
4
5
6
7
8
9
10
11
12
13

3.2 二叉树结点个数

等于根结点(1)+左子树和右子树的结点个数之和。
代码实现如下：

int TreeSize(BTNode* root)
{
	if (root == NULL)
	{
		return 0;
	}
	return 1 + TreeSize(root->_left) + TreeSize(root->_right);
}
1
2
3
4
5
6
7
8

3.3 二叉树叶子结点个数

当left 和 right同时为空的时候为叶子结点，二叉树的结点个数等于左子树的叶子结点个数+右子树的叶子结点个数
代码实现如下：

int TreeLeafSize(BTNode* root)
{
	if (root == NULL)
	{
		return 0;
	}
	if (root->_left == NULL && root->_right == NULL)
	{
		return 1;
	}
	return TreeLeafSize(root->_left) + TreeLeafSize(root->_right);
}
1
2
3
4
5
6
7
8
9
10
11
12

3.4 二叉树第K层结点个数

求第K层的结点个数其实和处理叶子结点个数的方法相似。
当前树的第K层结点个数可以转换成左右子树的第k-1层结点个数之和，当k==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);

}
1
2
3
4
5
6
7
8
9
10
11
12
13

完整代码链接在此：
https://github.com/CZH214926/C_repo.git