七、二叉树之链式结构(递归）

一、前序：

前面章节所说二叉树的结构其实是递归的，为什么这样说呢？根节点有左右子树，根节点的左右孩子又有左右子树，以此类推，直到叶子节点，它的左右子树为NULL，开始返回。所以，我们把它分成一个又一个的子树来分析。因此，它的结构是递归的。

因为一开始接触二叉树，还不是熟悉，我们先来手动创建一个二叉树，此方法不是二叉树的创建方法，只是为了快速进入二叉树的学习，真正的创建下面会讲。

typedef int BTDataType;
typedef struct BinaryTreeNode
{
	BTDataType data;
	struct BinaryTreeNode* left;
	struct BinaryTreeNode* right;
}BTNode;
BTNode* CreatBinaryTree()
{
	BTNode* node1 = BuyNode(1);
	BTNode* node2 = BuyNode(2);
	BTNode* node3 = BuyNode(3);
	BTNode* node4 = BuyNode(4);
	BTNode* node5 = BuyNode(5);
	BTNode* node6 = BuyNode(6);

	node1->left = node2;
	node1->right = node4;
	node2->left = node3;
	node4->left = node5;
	node4->right = node6;
	return node1;
}

回顾一下二叉树的知识，二叉树： 

1.空树

2.非空：由根节点，根节点的左右子树组成。

二、二叉树的创建

所谓二叉树的遍历，就是按照某种特定的规则依次对二叉树中的节点进行相应的操作，并且每个节点只操作一次。

BTNode* BuyNode(BTDataType a)
{
	BTNode* newnode = (BTNode*)malloc(sizeof(BTNode));
	newnode->data = a;
	newnode->left = NULL;
	newnode->right = NULL;
	return newnode;
}

BTNode* BinaryTreeCreate(BTDataType* a, int* pi)
{
	if (a[*pi] == '#')
	{
		(*pi)++;
		return NULL;
	}
	BTNode* root = BuyNode(a[*pi]);
	(*pi)++;

	root->left = BinaryTreeCreate(a, pi);
	root->right = BinaryTreeCreate(a, pi);

	return root;
}

我相信这幅图已经非常清晰的解释了上段代码递归的理解，那么就可以理解树的结构是递归的 。我再解释一下：首先创建一个节点，根节点去寻找左孩子，左孩子又是左子树的根节点，继续去找，直到找到叶子节点，叶子节点的左右孩子存在，但是为空，开始返回，返回叶子节点的父亲节点，叶子节点的父亲节点又有右孩子，以此类推，直到返回到根节点（A）的右子树，那么就很好的诠释了树的结构是递归的。

三、二叉树的遍历 

3.1.二叉树的前序遍历

根节点、左子树、右子树。（根、左、右）遍历的结果是ABDGECF。

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

3.2.二叉树的中序遍历 

左子树、根节点、右子树。（左、根、右）遍历的结果是GDBEACF。

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

图和前序遍历基本上没有什么区别，只是打印的顺序不同了而已。 

3.3.二叉树的后序遍历

左子树、右子树、根节点。（左、右、根）遍历的结果是GDEBFCA。（也是一样的图理解）

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

3.4.二叉树的层次遍历

层次遍历就是一层一层的遍历，那么前面我们讲过了队列，如果对队列还不是很熟悉，请大家往回去看队列的博客。

就是把根节点放到队列中，根节点出队列时，就让其的左右孩子进队列。

关于队列的相关代码，大家可以去队列的相关博客观看。 

// 层序遍历
void LevelOrder(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);
}

四、二叉树的实现

4.1.二叉树的建立

BTNode* BuyNode(BTDataType a)
{
	BTNode* newnode = (BTNode*)malloc(sizeof(BTNode));
	newnode->data = a;
	newnode->left = NULL;
	newnode->right = NULL;
	return newnode;
}

BTNode* BinaryTreeCreate(BTDataType* a, int* pi)
{
	if (a[*pi] == '#')
	{
		(*pi)++;
		return NULL;
	}
	BTNode* root = BuyNode(a[*pi]);
	(*pi)++;

	root->left = BinaryTreeCreate(a, pi);
	root->right = BinaryTreeCreate(a, pi);

	return root;
}

4.2.二叉树的销毁

如果理解了上面所说的后序，使用后序来销毁是最方便的，因为后序最后才会返回根节点，前序和中序都是途中就会返回根节点，如果根节点已经被删掉了的话，就不方便进行下一步free，但可以定义一个变量来保存它的左右子树，则可以继续进行。

// 二叉树销毁
void BTreeDestory(BTNode* root)
{
	if (root == NULL)
	{
		return;
	}

	BTreeDestory(root->left);
	BTreeDestory(root->right);
	free(root);
}

4.3.二叉树的节点个数

也是递归，如果递归到最后为空节点了或者根节点本身就是空节点，就是为0，否则就是+1。

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

4.4.二叉树的叶子节点个数

很好理解，就是寻找它左右孩子都是为NULL的，就是叶子节点。

int BTreeLeafSize(BTNode* root)
{
	if (root == NULL)
		return 0;

	if (root->left == NULL && root->right == NULL)
		return 1;

	return BTreeLeafSize(root->left) + BTreeLeafSize(root->right);
}

4.5.二叉树查找值为X的节点

这个我们拿ABCDE五个节点建成的树简单展示一下。

// 二叉树查找值为x的结点
BTNode* BTreeFind(BTNode* root, BTDataType x)
{
	if (root == NULL)
		return NULL;

	if (root->data == x)
		return root;

	BTNode* ret1 = BTreeFind(root->left, x);
	if (ret1)
		return ret1;

	//return BTreeFind(root->right, x);
	BTNode* ret2 = BTreeFind(root->right, x);
	if (ret2)
		return ret2;

	return NULL;
}

4.6.第K层的节点个数，K>=1

只要是一个节点往下递归了，那么深度就是-1，直到k减为1，开始返回。

// 第k层的节点的个数，k >= 1
int BTreeKLevelSize(BTNode* root, int k)
{
	assert(k >= 1);

	if (root == NULL)
		return 0;

	if (k == 1)
		return 1;

	return BTreeKLevelSize(root->left, k - 1)
		+ BTreeKLevelSize(root->right, k - 1);
}

4.7.判断二叉树是否为完全二叉树

根据完全二叉树的形状，其实就是层次遍历，如果中有NULL节点，那么肯定就不是一个完全二叉树。

// 判断二叉树是否是完全二叉树
bool BTreeComplete(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)
		{
			QueueDestory(&q);
			return false;
		}
	}

	QueueDestory(&q);
	return true;
}

至此，二叉树的顺序结构和链式结构就结束了，学习完两篇，实现二叉树其实并不简单，不仅要明白递归，还需要使用队列。但是没有关系，学习嘛，就是这样子环环相扣，才能更加理解。

如果不正之处，欢迎大家私信我进行纠正，制作不易，感谢大家的点赞！