数据结构（二叉树-2）

一、 实现链式结构二叉树

　　1.1 Tree.h

　　1.2 Tree.c 前中后序遍历

　　　　前序遍历

　　　　中序遍历

　　　　后续遍历

　　1.2 Tree.c 结点个数

　　1.3Tree.c 叶子节点个数

　　1.4 Tree.c 二叉树的高度

　　1.5 Tree.c 层序遍历

　　1.6 判断是否为完全二叉树

　　1.7 销毁二叉树

　　test.c

一、 实现链式结构二叉树

1.1 Tree.h

#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>
 
//定义二叉树的链式结构
//二叉树结点的结构
typedef int BTDataType;
typedef struct BinaryTreeNode
{
	int data;
	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, BTDataType x);
 
// ⼆叉树销毁
void BinaryTreeDestory(BTNode** root);
 
//层序遍历
void LevelOrder(BTNode* root);
 
//判断二叉树是否为完全二叉树
bool BinaryTreeComplete(BTNode* root);

 前序遍历

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

输出结果为： 1 2 4 3

其他两种遍历方式的递归过程也是一样的做法，下面就只展示代码部分了。

中序遍历

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

输出结果为： 4 2 1 3 

后续遍历

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

输出结果为： 4 2 3 1

1.2 Tree.c 结点个数

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

1.3Tree.c 叶子节点个数

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

•  当一棵二叉树中的节点的左右孩都为空时，证明他就是最后的结点，也叫做 “叶子节点” ，上述代码就运用了这一特点进行函数递归 ，if (root->left == NULL && root->right == NULL) 成立则返回 1 ，不成立就继续对其左右孩创建函数栈帧进行递归。

1.4 Tree.c 二叉树的高度

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

•  此处的递归方式与查找节点个数的递归方式相同，但是这里是求树的高度，所以当我们返回根节点的左右孩子的节点个数时（也就是求出左孩和右孩分别的高度），要进行比较，选出较高的树的高度，此高度就是整棵树的高度。

1.5 Tree.c 层序遍历

在上述构建好的二叉树中，如果要对其进行层序遍历的话，期待输出的结果为 1 2 3 4 ，

此时我们可以借助队列这一数据结构实现，所以在编写代码时先要包括 “Queue.h” 的头文件，具体队列的实现可以参考 数据结构（队列）-CSDN博客。

void LevelOrder(BTNode* root)
{
	Queue q;
	QueueInit(&q);
	QueuePush(&q, root);
	while (!QueueEmpty(&q))
	{
		//取队头，打印
		BTNode* front = QueueFront(&q);
		printf("%d ", front->data);
		QueuePop(&q);
		//队头节点的左右孩子入队列
		if (front->left)
			QueuePush(&q, front->left);
		if (front->right)
			QueuePush(&q, front->right);
	}
	//队列为空
	QueueDestroy(&q);
}

1.6 判断是否为完全二叉树 

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

•  如果是完全二叉树，跳出一个循环之后队列中剩下的全是NULL节点；
•  如果不是完全二叉树，跳出一个循环之后队列还有非空节点。

1.7 销毁二叉树

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

• 销毁左子树 + 销毁右子树 + 销毁根节点

test.c

#include"Tree.h"
 
BTNode* buyNode(BTDataType x)
{
	//创建结点
	BTNode* newnode = (BTNode*)malloc(sizeof(BTDataType));
	if (newnode == NULL)
	{
		perror("malloc fail!");
		exit(1);
 
	}
	newnode->data = x;
	newnode->left = newnode->right = NULL;
 
	return newnode;
}
 
void treetest()
{
	BTNode* node1 = buyNode(1);
	BTNode* node2 = buyNode(2);
	BTNode* node3 = buyNode(3);
	BTNode* node4 = buyNode(4);
 
	node1->left = node2;
	node1->right = node3;
	node2->light = node4;
}
 
 
int main()
{
	treetest();
	return 0;
}

未完待续~~