C语言二叉树详解

 

 

 

---

概念

---

 

一、二叉树的性质

二、实现二叉树

二叉树我们是用链表实现的，下面是结构：

#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <assert.h>
typedef char BTDataType;
typedef struct BTNode
{
	BTDataType data;
	struct BTNode* left;
	struct BTNode* right;
}BTNode;

我们可以看到一个节点中有三个变量，一个存放数据，一个指向左子树，一个指向右子树。将char类型重命名是为了后面更方便的更改类型，将结构体重命名为BTNode是为了更简单的写出指针类型。 

下面是实现的完整代码，然后我们依次进行讲解，在下面我们可以看到队列，这是因为二叉树的层序遍历和完全二叉树的判断用队列非常方便。

#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <assert.h>
typedef char BTDataType;
typedef struct BTNode
{
	BTDataType data;
	struct BTNode* left;
	struct BTNode* right;
}BTNode;
 
typedef BTNode* QueueDate;
typedef struct QueueNode
{
	struct QueueNode* next;
	QueueDate data;
}QueueNode;
 
typedef struct Queue
{
	QueueNode* head;
	QueueNode* tail;
	int size;
}Queue;
 
QueueDate QueueFront(Queue* ps)
{
	assert(ps);
	assert(ps->head);
	return ps->head->data;
}
 
bool QueueEmpty(Queue* ps)
{
	assert(ps);
	return ps->size == 0;
}
 
 
void QueuePop(Queue* ps)
{
	assert(ps);
	assert(ps->head);
	if (ps->head->next == NULL)
	{
		free(ps->head);
		ps->head = ps->tail = NULL;
	}
	else
	{
		QueueNode* tmp = ps->head->next;
		free(ps->head);
		ps->head = tmp;
	}
	ps->size--;
}
 
void QueuePush(Queue* ps, QueueDate x)
{
	assert(ps);
	QueueNode* newnode = (QueueNode*)malloc(sizeof(QueueNode));
	if (newnode == NULL)
	{
		perror("malloc:");
		exit(-1);
	}
	newnode->data = x;
	newnode->next = NULL;
	if (ps->head == NULL)
	{
		ps->head = ps->tail = newnode;
	}
	else
	{
		ps->tail->next = newnode;
		ps->tail = newnode;
	}
	ps->size++;
}
 
void QueueDestroy(Queue* ps)
{
	assert(ps);
	while (ps->head)
	{
		QueueNode* cur = ps->head->next;
		free(ps->head);
		ps->head = cur;
	}
	ps->head = ps->tail = NULL;
	ps->size = 0;
}
 
void QueueInit(Queue* ps)
{
	assert(ps);
	ps->head = NULL;
	ps->tail = NULL;
	ps->size = 0;
}
//二叉树的销毁
void BinaryTreeDestroy(BTNode* root)
{
	if (root == NULL)
	{
		return;
	}
	BinaryTreeDestroy(root->left);
	BinaryTreeDestroy(root->right);
	free(root);
}
 
//二叉树的前序遍历
void PrevOrder(BTNode* root)
{
	if (root == NULL)
	{
		printf("NULL ");
		return;
	}
	printf("%c ", root->data);
	PrevOrder(root->left);
	PrevOrder(root->right);
}
//二叉树的中序遍历
void middleOrder(BTNode* root)
{
	if (root == NULL)
	{
		printf("NULL ");
		return;
	}
	middleOrder(root->left);
	printf("%c ", root->data);
	middleOrder(root->right);
}
//二叉树的后序遍历
void AfterOrder(BTNode* root)
{
	if (root == NULL)
	{
		printf("NULL ");
		return;
	}
	AfterOrder(root->left);
	AfterOrder(root->right);
	printf("%d ", root->data);
}
//二叉树的节点数
int BinaryTreeSize(BTNode* root)
{
	if (root == NULL)
	{
		return 0;
	}
	return BinaryTreeSize(root->left) + BinaryTreeSize(root->right) + 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);
}
 
//二叉树的高度
int BinaryTreeHeight(BTNode* root)
{
	if (root == NULL)
	{
		return 0;
	}
	int Left = BinaryTreeHeight(root->left);
	int right = BinaryTreeHeight(root->right);
	return Left > right ? Left + 1 : right + 1;
}
//二叉树第K层节点数
int BinaryTreeKnode(BTNode* root,int k)
{
	if (root == NULL)
	{
		return 0;
	}
	if (k == 1)
	{
		return 1;
	}
	return BinaryTreeKnode(root->left, k - 1) + BinaryTreeKnode(root->right, k - 1);
}
//二叉树查找值为x的节点
BTNode* BinaryTree(BTNode* root,BTDataType x)
{
	if (root == NULL)
	{
		return NULL;
	}
	if (root->data == x)
	{
		return root;
	}
	BTNode* left = BinaryTree(root->left, x);
	if (left)
	{
		return left;
	}
	BTNode* right = BinaryTree(root->right, x);
	if (right)
	{
		return right;
	}
	return NULL;
}
// 通过前序遍历的数组"ABD##E#H##CF##G##"构建二叉树
BTNode* BinaryTreeCreate(BTDataType* str, int n, int* i)
{
	if (str[*i] == '#')
	{
		(*i)++;
		return NULL;
	}
	BTNode* newnode = (BTNode*)malloc(sizeof(BTNode));
	newnode->data = str[(*i)++];
	newnode->left = BinaryTreeCreate(str, n, i);
	newnode->right = BinaryTreeCreate(str, n, i);
	return newnode;
}
//层序遍历
void BinaryTreeLevelOrder(BTNode* root)
{
	Queue sl;
	QueueInit(&sl);
	if (root)
	{
		QueuePush(&sl, root);
	}
	while (!QueueEmpty(&sl))
	{
		BTNode* tmp = QueueFront(&sl);
		QueuePop(&sl);
		printf("%d ", tmp->data);
		if (tmp->left)
		{
			QueuePush(&sl, tmp->left);
		}
		if (tmp->right)
		{
			QueuePush(&sl, tmp->right);
		}
	}
	printf("\n");
	QueueDestroy(&sl);
}
//判断是否为完全二叉树
int BinaryTreeComplete(BTNode* root)
{
	Queue sl;
	QueueInit(&sl);
	if (root)
	{
		QueuePush(&sl, root);
	}
	while (!QueueEmpty(&sl))
	{
		BTNode* tmp = QueueFront(&sl);
		QueuePop(&sl);
		if (tmp==NULL)
		{
			break;
		}
		else
		{
			QueuePush(&sl, tmp->left);
			QueuePush(&sl, tmp->right);
		}
	}
	while (!QueueEmpty(&sl))
	{
		BTNode* tmp = QueueFront(&sl);
		QueuePop(&sl);
		if (tmp)
		{
			QueueDestroy(&sl);
			return 0;
		}
	}
	QueueDestroy(&sl);
	return 1;
}
 
int main()
{
	/*BTNode* n1 = (BTNode*)malloc(sizeof(BTNode));
	BTNode* n2 = (BTNode*)malloc(sizeof(BTNode));
	BTNode* n3 = (BTNode*)malloc(sizeof(BTNode));
	BTNode* n4 = (BTNode*)malloc(sizeof(BTNode));
	BTNode* n5 = (BTNode*)malloc(sizeof(BTNode));
	BTNode* n6 = (BTNode*)malloc(sizeof(BTNode));
	n1->data = 1;
	n2->data = 2;
	n3->data = 3;
	n4->data = 4;
	n5->data = 5;
	n6->data = 6;
	n1->left = n2;
	n1->right = n4;
	n2->left = n3;
	n2->right = n5;
	n3->left = NULL;
	n3->right = NULL;
	n4->left = n6;
	n4->right = NULL;
	n5->right = NULL;
	n5->left = NULL;
	n6->left = NULL;
	n6->right = NULL;*/
	/*PrevOrder(n1);
	printf("\n");
	middleOrder(n1);
	printf("\n");
	AfterOrder(n1);
	printf("\n");
	printf("%d\n", BinaryTreeSize(n1));
	printf("%d\n", BinaryTreeLeafSize(n1));
	printf("%d\n", BinaryTreeHeight(n1));
	printf("%d\n", BinaryTreeKnode(n1,1));
	BTNode* tmp = BinaryTree(n1, 10);
	if (tmp == NULL)
	{
		printf("tmp=NULL\n");
	}
	else
	{
		printf("tmp=%d\n", tmp->data);
	}*/
	/*BinaryTreeLevelOrder(n1);
	printf("%d\n", BinaryTreeComplete(n1));*/
	/*BinaryTreeDestroy(n1);*/
	char str[100];
	scanf("%s", str);
	int i = 0;
	BTNode* tmp = BinaryTreeCreate(str, 100, &i);
	middleOrder(tmp);
	printf("\n");
	PrevOrder(tmp);
	BinaryTreeDestroy(tmp);
	return 0;
}

 先看第一个：二叉树遍历

1.前序遍历：先遍历根 然后是左子树 然后是右子树

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

 

如图所示，在递归的过程中，第一个节点为1，1不为空打印1然后递归1的左子树，1的左子树为2，不为空打印2，然后递归2的左子树，2的左子树为空打印NULL然后返回刚刚2的那个函数，2的左子树已经递归了所以该2的右子树，2的右子树为空打印NULL然后返回2的函数，2的函数执行完了返回1的函数，这时候1的左子树递归完成了，现在递归1的右子树，这里与1的左子树递归出来是一样的，然后成功用前序遍历出这棵树。后面的中序遍历就是先去遍历左子树不打印，然后左子树遍历完了在打印节点然后再去遍历右子树。

2.中序遍历：先遍历左子树，然后遍历根，再遍历右子树

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

 

 与前序相同就不再讲述。

3.后序遍历：先遍历左子树，然后遍历右子树，最后遍历根节点。

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

 第二个：求二叉树的节点数

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

 求二叉树的节点很简单，当这个节点为空时就返回0否则就返回这个节点的左子树的节点加右子树的节点再加自己。单靠代码可能不好看出来，那么我们画个图看看。

相信大家也看懂这个图了，本质就是计算一个节点的左子树的节点+右子树的节点再加自己。

第三个：求二叉树的叶子节点数

叶子节点我们在上篇已经讲过，就是度为0的节点。我们从这个角度出发，度为0就是左子树为空并且右子树为空，所以只需要将上面的代码稍微修改即可。

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

 在这里一定要注意，当树为空要返回0否则就是死递归。下面是递归图：

 我们可以看到求叶子节点的递归非常简单，只需要记得当树为空返回0，如果没有这个条件当一棵树或者一个节点只有左边没有右边时就会死递归。

第四个：求树的高度

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

 求树的高度只需要看一棵树中它的左子树高还是右子树高，我们返回高的那个然后再加上根的一层就是总高度，当一样高时随便返回一颗子树的高度即可。在这里需要注意的是一定要用两个值去分别记录左右子树的高度，否则效率非常差每一层递归都要重新计算高度。

如递归图所示当有变量记录其左右高度时会比直接递归快很多。

第五个：求第K层节点数

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

怎么求第K层节点数呢？我们发现当我们要求一棵树的第三层时，从根节点的角度看是第三层，从第二层的角度看是第二层，从第三层的角度看是第一层，也就是说每次都可以转化为这个节点的左子树的K-1层的节点+这个节点的右子树的K-1层节点，当K=1也就是自己就是第一层时那么只有自己一个节点，所以返回1即可。

第六个：二叉树查找值为x的节点

BTNode* BinaryTree(BTNode* root,BTDataType x)
{
	if (root == NULL)
	{
		return NULL;
	}
	if (root->data == x)
	{
		return root;
	}
	BTNode* left = BinaryTree(root->left, x);
	if (left)
	{
		return left;
	}
	BTNode* right = BinaryTree(root->right, x);
	if (right)
	{
		return right;
	}
	return NULL;
}

 查找值为x的节点我们要考虑几个问题，第一个是如果找到了这个节点能否直接返回，第二个是当找不到的时候要返回空指针，当这个节点为空时也要返回空指针，我们在递归的过程中一定要保证每一个都有返回值。在这里当我们找到这个节点时为什么要用变量保存呢？因为当我们找到这个节点后我们应该要函数直接返回而不是继续去递归它的左右子树。

通过递归图我们可以看到每次找到节点后返回这个节点必须要有变量去保存这个节点，否则就白找了，并且通过判断变量是否为空的情况就可以知道有没有找到，当任意一个变量不为空时直接返回了找到的这个节点就不会去递归其他的节点。 

第七个：通过前序遍历的数组"ABD##E#H##CF##G##"构建二叉树

这个其实是牛客网的一道题，就是通过前序遍历来让一个字符串被二叉树存储。

BTNode* BinaryTreeCreate(BTDataType* str, int n, int* i)
{
	if (str[*i] == '#')
	{
		(*i)++;
		return NULL;
	}
	BTNode* newnode = (BTNode*)malloc(sizeof(BTNode));
	newnode->data = str[(*i)++];
	newnode->left = BinaryTreeCreate(str, n, i);
	newnode->right = BinaryTreeCreate(str, n, i);
	return newnode;
}

 如图当遇到字符#时，就是空指针，str是传来的字符串，i是记录字符串位置的下标，在这里一定要注意此函数要传下标的地址，因为我们在递归的过程中i会++如果不是传地址的话每次递归后的i++后对上一次函数栈帧不起作用，我们通过递归图来演示。

int main()
{
    char str[100];
	scanf("%s", str);
	int i = 0;
	BTNode* tmp = BinaryTreeCreate(str, 100, &i);
    return 0;
}

 

如图所示当走完全部字符串后返回二叉树的根节点，这样就创建好了一颗二叉树。在这里要注意的是不管遇到空指针还是正常字符都需要让下标I++。在这里我们开辟的空间到最后结束程序都要记得销毁。

第八个：销毁二叉树

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

 销毁二叉树同样需要递归来实现，我们只需要先找到左子树最后一个节点然后依次销毁即可。在这里需要注意的是当这个节点为空时，一定要返回。

第九个：二叉树的层序遍历

void BinaryTreeLevelOrder(BTNode* root)
{
	Queue sl;
	QueueInit(&sl);
	if (root)
	{
		QueuePush(&sl, root);
	}
	while (!QueueEmpty(&sl))
	{
		BTNode* tmp = QueueFront(&sl);
		QueuePop(&sl);
		printf("%d ", tmp->data);
		if (tmp->left)
		{
			QueuePush(&sl, tmp->left);
		}
		if (tmp->right)
		{
			QueuePush(&sl, tmp->right);
		}
	}
	printf("\n");
	QueueDestroy(&sl);
}

层序遍历我们是用队列实现的，先将根节点入队列，每次出队头元素前都需要将这个节点的左右子树入队列。当队列为空说明所有节点都遍历完了，直接销毁队列即可。

 

 当然每次入队列我们是不会入空树的因为层序遍历就是每层从左到右根的遍历。每次用一个变量去保存队列头元素，这样方便出队列和入队列。入节点的子树的时候每次左右子树不为空再入队列。在这里要说明一下，队列里保存的是二叉树结构体的指针而不是节点，如果保存的是节点就会出错。如下面代码要保存树的节点的地址。

typedef BTNode* QueueDate;
typedef struct QueueNode
{
	struct QueueNode* next;
	QueueDate data;
}QueueNode;

第十个：判断是不是完全二叉树

完全二叉树可以在最后一个节点只有左子树，但一定不会在已经有空树的后面还有节点如下图所示：

如图所示，非完全二叉树有空节点后后面还会有节点，而完全二叉树在某一个节点为空时它的右边全是空节点，依据这个特性我们就很容易的判断一棵树是否为完全二叉树。

int BinaryTreeComplete(BTNode* root)
{
	Queue sl;
	QueueInit(&sl);
	if (root)
	{
		QueuePush(&sl, root);
	}
	while (!QueueEmpty(&sl))
	{
		BTNode* tmp = QueueFront(&sl);
		QueuePop(&sl);
		if (tmp==NULL)
		{
			break;
		}
		else
		{
			QueuePush(&sl, tmp->left);
			QueuePush(&sl, tmp->right);
		}
	}
	while (!QueueEmpty(&sl))
	{
		BTNode* tmp = QueueFront(&sl);
		QueuePop(&sl);
		if (tmp)
		{
			QueueDestroy(&sl);
			return 0;
		}
	}
	QueueDestroy(&sl);
	return 1;
}

我们继续用队列实现，这次空节点也要入队列，当队列的头变成空节点时我们出队列并且退出循环，当队列不为空时我们继续拿队头元素，一旦这个元素不是空节点就说明不是完全二叉树，当队列全部出完也没有遇到非空的节点时，那么就说明这棵树为完全二叉树。

---

总结

二叉树最重要的就是递归，要深刻的理解递归过程就必须要多画图，只要理解了递归那么再去写二叉树就手到擒来了。