用C语言把一棵普通二叉树安排得明明白白

1. 树的相关术语

结点的度：一个结点含有的子树的个数称为该结点的度；如上图：A的为6

叶结点或终端结点：度为0的结点称为叶结点；如上图：B、C、H、I...等结点为叶结点

非终端结点或分支结点：度不为0的结点；如上图：D、E、F、G...等结点为分支结点

双亲结点或父结点：若一个结点含有子结点，则这个结点称为其子结点的父结点；如上图：A是B的父结点

孩子结点或子结点：一个结点含有的子树的根结点称为该结点的子结点；如上图：B是A的孩子结点

兄弟结点：具有相同父结点的结点互称为兄弟结点；如上图：B、C是兄弟结点

树的度：一棵树中，最大的结点的度称为树的度；如上图：树的度为6

结点的层次：从根开始定义起，根为第1层，根的子结点为第2层，以此类推；

树的高度或深度：树中结点的最大层次；如上图：树的高度为4

堂兄弟结点：双亲在同一层的结点互为堂兄弟；如上图：H、I互为兄弟结点

结点的祖先：从根到该结点所经分支上的所有结点；如上图：A是所有结点的祖先

子孙：以某结点为根的子树中任一结点都称为该结点的子孙。如上图：所有结点都是A的子孙

森林：由m（m>0）棵互不相交的树的集合称为森林；

满二叉树：深度为k且有 $2^{k}-1$ 个结点的二叉树。在满二叉树中，每层结点都是满的，即每层结点都具有最大结点数。

满二叉树的顺序表示：从二叉树的根开始，按层间从上到下，层内从左到右的顺序进行编号（0，1，2，……，n-1）。

完全二叉树：深度为k，结点数为n的二叉树，如果其结点0~n-1的位置序号分别与等高的满二叉树的结点1~n-1的位置序号一一对应，则为完全二叉树。完全二叉树的特点为：(1)叶子结点只可能出现在最后两层；(2)度数为1的结点个数为0或1。

2. 二叉树的性质

性质1：在二叉树的第i层上至多有 $2^{i-1}$ 个结点（i>=1）

性质2：深度为k的二叉树至多有 $2^{k}-1$ 个结点(k>=1)

性质3：对任意一棵二叉树T，若终端结点数为 $n_{1}$ ，而其度数为2的结点数为 $n_{2}$ ，则 $n_{1} = n_{2}+1$

性质4：具有n个结点的完全二叉树的深度为 $(log_{2}n)+1$

性质5：对于具有n个结点的完全二叉树，如果按照从上到下，从左到右的顺序对完全二叉树中的所有结点从0开始编号，则对于任意序号为i的结点，其双亲结点的序号为 (i-1)/2，左孩子的序号为2*i+1，右孩子的序号为2*i+2。

证明略，但是上面的性质5在堆中有较为重要价值，在上一篇文章中有证明：全面详解堆-CSDN博客

1. 二叉树的声明以及要实现的接口

typedef char BTDataType;

typedef struct BinaryTreeNode
{
	BTDataType data;
	struct BinaryTreeNode* left;
	struct BinaryTreeNode* right;
}BTNode;

// 通过前序遍历的数组"ABD##E#H##CF##G##"构建二叉树
BTNode* BinaryTreeCreate(BTDataType* a, int n, int* pi);
// 二叉树销毁
void BinaryTreeDestory(BTNode** root);
// 二叉树节点个数
int BinaryTreeSize(BTNode* root);
// 二叉树叶子节点个数
int BinaryTreeLeafSize(BTNode* root);
// 二叉树第k层节点个数
int BinaryTreeLevelKSize(BTNode* root, int k);
// 二叉树查找值为x的节点
BTNode* BinaryTreeFind(BTNode* root, BTDataType x);
// 二叉树前序遍历 
void BinaryTreePrevOrder(BTNode* root);
// 二叉树中序遍历
void BinaryTreeInOrder(BTNode* root);
// 二叉树后序遍历
void BinaryTreePostOrder(BTNode* root);
// 层序遍历
void BinaryTreeLevelOrder(BTNode* root);
// 判断二叉树是否是完全二叉树
int BinaryTreeComplete(BTNode* root);
//树的高度
int TreeHeight(BTNode* root);

2. 通过前序遍历数组构建二叉树

在对二叉树进行操作之前，我们需要有一棵二叉树。

根据二叉树的用途不同，在二叉树中插入元素的方式繁多且复杂，在初学阶段不需要太多的了解。

于是，我们可以采用暴力构建二叉树的方式，也就是手动实现结点之间的相互链接关系：

BTNode* BuyNode(BTDataType x)
{
	BTNode* newnode = (BTNode*)malloc(sizeof(BTNode));
	if (newnode == NULL)
	{
		perror("malloc fail");
		exit(-1);
	}

	newnode->data = x;
	newnode->left = NULL;
	newnode->right = NULL;

	return newnode;
}

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

但是，按照这种方式来构建树，每个不同的树都需要我们编写逻辑来实现，十分的麻烦。

由于包含空指针表示的前序遍历序列与二叉树之间存在着一一对应的关系，所以，我们可以采用将前序遍历数组还原为树的方式来构建树（前序最好理解，中序后序调整子树创建顺序即可）：

// 通过前序遍历的数组"ABD##E#H##CF##G##"构建二叉树
BTNode* BinaryTreeCreate(BTDataType* a, int n, int* pi)
{
	if (*pi >= n || a[*pi] == '#')
	{
		(*pi)++;
		return NULL;
	}
	else
	{
		BTNode* root = BuyNode(a[*pi]);
		(*pi)++;
		root->left = BinaryTreeCreate(a, n, pi);
		root->right = BinaryTreeCreate(a, n, pi);
		return root;
	}
}

a为存放前序遍历序列的数组，'#'表示当前结点为空指针；

n表示数组a的元素个数；

pi为表示当前数组下标的变量的指针，初始值为0，每有一个元素加入到树中，(*pi)++。

3. 二叉树销毁

这里采用的是后序遍历来释放结点，否则需要定义变量来记录左右子树的根结点。

// 二叉树销毁
void BinaryTreeDestory(BTNode** root)
{
	if (*root == NULL)
		return;
	else
	{
		BinaryTreeDestory(&((*root)->left));
		BinaryTreeDestory(&((*root)->right));
		free(*root);
		*root = NULL;
	}
}

4. 二叉树的结点个数

利用递归即可解决，整棵树的结点数 = 左子树的结点数 + 根结点（1个）+ 右子树的结点数。

同理，左右子树也是相同的逻辑。

某棵子树（某结点的左子树或右子树）为空时，返回0。

// 二叉树节点个数
int BinaryTreeSize(BTNode* root)
{
	if (root == NULL)
		return 0;

	return BinaryTreeSize(root->left) + BinaryTreeSize(root->right) + 1;
}

5. 二叉树的叶子结点数

与上面的算法相似，但是此处我们只统计叶子结点数。

叶子结点区别于其他结点的特点是，其左右孩子都为空，如果当前结点符合条件我们就返回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);
}

6. 二叉树第k层的结点数

同样的递归思路，第k层结点数 = 左子树第k-1层结点数 + 右子树第k-1层结点数。

但是我们需要一个参数k来判断当前结点位于第几层，以及是否需要返回。

每深入一层，k就减1，当k等于1时返回1，表示已找到一个所求结点。

// 二叉树第k层节点个数
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);
}

7. 查找值为x的结点

如果当前结点的值为x，则直接返回当前结点。

否则，先到左子树进行寻找，若左子树没有（返回值为NULL）就找右子树。

// 二叉树查找值为x的节点
BTNode* BinaryTreeFind(BTNode* root, BTDataType x)
{
	if (root == NULL)
		return NULL;
	if (root->data == x)
		return root;

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

8.二叉树的递归与非递归遍历

二叉树的递归遍历较为简单，但是非递归算法却十分复杂，需要用到栈来模拟递归进行实现。

在该文章中有详细介绍：栈与递归的实现-CSDN博客

9. 树的高度

树的高度指树中结点的最大层次。

所以树的高度 = 左子树与右子树中较高者的高度 + 1（根结点）。

//树的高度
int TreeHeight(BTNode* root)
{
	if (root == NULL)
		return 0;

	int leftHeight = TreeHeight(root->left);
	int rightHeight = TreeHeight(root->right);
	return (leftHeight > rightHeight ? leftHeight : rightHeight) + 1;
}

10. 层序遍历

层序遍历也就是广度优先遍历，实现这个算法需要用到队列的帮助。

由于C语言不支持队列，所以在这里写了一个简易的队列。

其中，Get函数会在获取队头结点的同时将其出队，这样实现对于我们当前算法的实现来说，使用起来更加方便。

当然，下面这段代码只是帮助理解，直接忽略也可，只要你知道我对队列进行了什么操作。

typedef BTNode* QDataType;

// 链式结构：表示队列 
typedef struct QListNode
{
	struct QListNode* _next;
	QDataType _data;
}QNode;

// 队列的结构 
typedef struct Queue
{
	QNode* _front;
	QNode* _rear;
	int size;
}Queue;

//初始化
void Inite(Queue* q)
{
	q->size = 0;
	q->_front = NULL;
	q->_rear = NULL;
}

//入队
void Push(Queue* q, QDataType x)
{
	QNode* newnode = (QNode*)malloc(sizeof(QNode));
	if (newnode == NULL)
	{
		perror("malloc fail");
		exit(-1);
	}

	newnode->_data = x;
	newnode->_next = NULL;

	if (q->_rear == NULL)
	{
		q->_front = q->_rear = newnode;
	}
	else
	{
		q->_rear->_next = newnode;
		q->_rear = newnode;
	}
	q->size++;
}

//出队
QDataType Get(Queue* q)
{
	if (q->size == 0)
		return NULL;
	QDataType temp = q->_front->_data;
	QNode* del = q->_front;
	if (q->size == 1)
	{
		q->_rear = NULL;
	}
	q->_front = q->_front->_next;
	free(del);
	q->size--;

	return temp;
}

//销毁队列
void DestroyQueue(Queue* q)
{
	QDataType temp;
	while (q->_front)
	{
		temp = Get(q);
	}
}

基本思路就是：

1. 出队得到一个结点并访问。

2. 如果当前结点有孩子，则将其孩子全部入队。

3. 不断重复以上两步，知道队中无结点。

// 层序遍历
void BinaryTreeLevelOrder(BTNode* root)
{
	Queue q;
	Inite(&q);
	Push(&q, root);
	BTNode* cur = NULL;
	while (cur = Get(&q))
	{
		printf("%c ", cur->data);
		if(cur->left != NULL)
		Push(&q, cur->left);
		if(cur->right != NULL)
		Push(&q, cur->right);
	}
	DestroyQueue(&q);
}

11. 判断二叉树是否是完全二叉树

根据完全二叉树的特点，我们总结出以下判断标准：

1. 如果某个结点只有右孩子而没有左孩子，则该树一定不是完全二叉树。

2. 如果某个结点不是满的（缺少左孩子或右孩子），则位置序号在其之后的结点一定既没有左孩子，又没有右孩子，否则就是非完全二叉树。

// 判断二叉树是否是完全二叉树
int BinaryTreeComplete(BTNode* root)
{
	Queue q;
	Inite(&q);
	Push(&q, root);
	BTNode* cur = NULL;
	do
	{
		cur = Get(&q);
		if (cur->left == NULL && cur->right != NULL)
			return 0;
		else if(cur->left != NULL && cur->right != NULL)
		{
			Push(&q, cur->left);
			Push(&q, cur->right);
		}
	} while (cur->right);

	while (q.size != 0)
	{
		cur = Get(&q);
		if (cur->left != NULL || cur->right != NULL)
			return 0;
	}
	return 1;

	DestroyQueue(&q);
}

12. oj练习

12.1 单值二叉树. - 力扣（LeetCode）

第一种思路：保存根结点的值，然后用其与所有结点进行比较。

bool judge(struct TreeNode* root, int com)
{
    if(root == NULL)
    return true;
    if(root->val != com)
    return false;

    return judge(root->left, com) && judge(root->right, com);
}

bool isUnivalTree(struct TreeNode* root) {
    int com = root->val;
    return judge(root, com);
}

为了提高代算法的效率，也可以将com变量改为全局变量。

第二种思路：我们找到题目要求的一个等价条件——除了叶子结点，所有结点的值都与自己孩子的值相等。

bool isUnivalTree(struct TreeNode* root) {
    if(root == NULL)
    return true;
    
    if(root->left && root->left->val != root->val || root->right && root->right->val != root->val)
    return false;

    return isUnivalTree(root->left) && isUnivalTree(root->right);
}

12.2 相同的树. - 力扣（LeetCode）

采用递归的思路，两棵树相同意味着他们：根结点相同，左子树相同，右子树相同。

左右子树相同，包括左右子树都为空的情况。

bool isSameTree(struct TreeNode* p, struct TreeNode* q) {
    if(p == NULL && q == NULL)
    return true;
    if(p == NULL || q == NULL || p->val != q->val)
    return false;

    return isSameTree(p->left, q->left) && isSameTree(p->right, q->right);
}

12.3 对称的树. - 力扣（LeetCode）

观察示例可以发现，这道题可以采用与上道题如出一辙的思路，只不过我们要比较的两棵树是根结点的左右子树。

同时，比较的逻辑也需要更改，左子树的右孩子应该与右子树的左孩子比较，左子树的左孩子应该与右孩子的右子树比较。

bool judge(struct TreeNode* root1, struct TreeNode* root2)
{
    if(root1 == NULL && root2 == NULL)
    return true;
    if(root1 == NULL || root2 == NULL || root1->val != root2->val)
    return false;

    return judge(root1->left, root2->right) && judge(root1->right, root2->left);
}

bool isSymmetric(struct TreeNode* root) {
    return judge(root->left, root->right);
}

12.4 另一棵树的子树. - 力扣（LeetCode）

这道题可以利用到“相同的树”那道题的函数，我们只需要遍历root，然后将其的子树依次与subRoot进行比较即可。

bool isSameTree(struct TreeNode* p, struct TreeNode* q) {
    if(p == NULL && q == NULL)
    return true;
    if(p == NULL || q == NULL || p->val != q->val)
    return false;

    return isSameTree(p->left, q->left) && isSameTree(p->right, q->right);
}

bool isSubtree(struct TreeNode* root, struct TreeNode* subRoot){
    if(root == NULL)
    return false;
    if(isSameTree(root, subRoot))
    return true;

    return isSubtree(root->left, subRoot) || isSubtree(root->right, subRoot);
}

12.5 二叉树的前序遍历. - 力扣（LeetCode）

这道题并不是简单地对二叉树进行前序遍历，而是要求我们返回存储前序遍历序列的数组。

首先需要动态开辟一个存储结果的数组，但问题是开辟多少合适呢？

当然，在这道题中我们可以直接开辟100个空间的数组。

假如我们不知道这么一个条件呢？

可以用动态的顺序表来管理，但鉴于需要我们自己实现，似乎就有点麻烦。

这时，我们就可以用到上面的BinaryTreeSize函数了，先求出树中的结点个数，再进行我们接下来的操作。

与利用前序遍历数组构建二叉树相同，我们这里也需要一个pi来指示数组当前的下标。

下面的这段代码中，直接用returnSize来充当了这个pi。

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

void pretraversal(struct TreeNode* root, int* arr, int* pi)
{
    if(root == NULL)
    return;

    arr[*pi] = root->val;
    (*pi)++;
    pretraversal(root->left, arr, pi);
    pretraversal(root->right, arr, pi);
}

int* preorderTraversal(struct TreeNode* root, int* returnSize) {
    int* arr = (int*)malloc(sizeof(arr) * TreeSize(root));
    *returnSize = 0;
    pretraversal(root, arr, returnSize);
    return arr;
}