【算法与数据结构】深入二叉树实现超详解（全源码优化）

04-10 1787阅读

【算法与数据结构】深入二叉树实现超详解（全源码优化）

文章目录

  • 📝前言
  • 🌠 接口函数
    • ✏️ 实现函数
      • 🌉创建树的新节点
      • 🌠通过前序遍历的数组构建二叉树
      • 🌉包装通过前序遍历的数组构建二叉树
          • 🌉前序构建二叉树
          • 🌉中序构建二叉树
          • 🌉后序构建二叉树
          • 🌠二叉树的销毁
          • 🌠层次遍历
            • 🌠第一种实现：不用数组模拟队列
            • 🌠第二种实现：不用数组模拟队列，创建队列实现
            • 🌉判断二叉树是否是完全二叉树
            • 🌠二叉树节点个数
            • 🌉二叉树叶子节点个数
            • 🌉二叉树第k层节点个数
            • 🌠二叉树查找值为x的节点
            • 🌉 完整代码实现
                • 🌉 BinaryTree.h文件
                • 🌉 Queue.h文件
                • 🌉 Queue.c文件
                • 🌉 BinaryTreeTest.c文件
                • 🌉测试一下效果（BinaryTreeTest.c）文件
                • 🚩总结

                  📝前言

                  上节我们学习了二叉树（前中后）序遍历

                  这节将实现二叉树。

                  让我们复习一下二叉树，接着就是二叉树的实现了😊，学习起来吧！

                  1. 满二叉树：一个二叉树，如果每一个层的结点数都达到最大值，则这个二叉树就是满二叉树。也就是说，如果一个二叉树的层数为K，且结点总数是 ，则它就是满二叉树。
                  2. 完全二叉树：完全二叉树是效率很高的数据结构，完全二叉树是由满二叉树而引出来的。对于深度为K的，有n个结点的二叉树，当且仅当其每一个结点都与深度为K的满二叉树中编号从1至n的结点一一对应时称之为完全二叉树。 要注意的是满二叉树是一种特殊的完全二叉树。

                    【算法与数据结构】深入二叉树实现超详解（全源码优化）

                    本节代码举例图

                    【算法与数据结构】深入二叉树实现超详解（全源码优化）

                    好了，差不多了，启动！—》

                  🌠 接口函数

                  头文件Tree.h，这里封装了树的接口，需要时直接#include"Tree.h"。

                  # define _CRT_SECURE_NO_WARNINGS 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);
//二叉树销毁
BTNode* BinaryTreeDestory(BTNode** root);
//二叉树节点个数
int BTNodeTreeSize(BTNode* root);
//二叉树叶子节点个数
int BTNodeTreeLeafSize(BTNode* root);
//二叉树第k层节点个数
int BinaryTreeLevelKSize(BTNode* root, int k);
//二叉树查找值为x的节点
BTNode* BinaryTreeFind(BTNode* root, BTDataType x);
//二叉树前序遍历
void BinaryTreePrevOreder(BTNode* root);
//二叉树中序遍历
void BinaryTreeInOrder(BTNode* root);
//二叉树后序遍历
void BinaryTreePostOrder(BTNode* root);
//层序遍历
void BinaryTreeLevelOrder(BTNode* root);
//求树的高度
int BinaryHeight(BTNode* root);
//判断二叉树是否是完全二叉树
bool BinaryTreeCompelete(BTNode* root);
//前序遍历
void BTreePrever(BTNode* root);
//中序遍历
void BTreeQrder(BTNode* root);
//后序遍历
void BTreeBack(BTNode* root);

                  ✏️ 实现函数

                  🌉创建树的新节点

                  //创建新节点
BTNode* BuyBTNode(int val)
{
	//使用malloc动态申请内存,分配一个BTNode类型的结构体。
	BTNode* newNode = (BTNode*)malloc(sizeof(BTNode));
	if (newNode == NULL)//
	{
		perror("malloc fail");//检查malloc是否成功
		return ;
	}
	newNode->data = val;//将新节点的data字段设置为传入的val值。
	newNode->left = NULL;//将新节点的left和right子节点指针设置为NULL。
	newNode->right = NULL;
	return newNode;//返回新创建的节点指针。
}

                  动态创建一个新的二叉树节点,并初始化其data和子节点指针字段。这样就可以在构建二叉树的过程中不断调用这个函数来创建新的节点,然后连接起来形成树形结构。

                  🌠通过前序遍历的数组构建二叉树

                  BTNode* BinaryTreeCreateHelper(BTDataType* a, int n, int* pi)
{									//n是数组a的长度
									//pi是索引指针,用于遍历a数组
	if (*pi >= n || a[*pi] == 'N')//检查*pi是否越界或当前元素为'N',如果是则跳过该节点,					(*pi)++向后移动。这里的N意思是空
	{
		(*pi)++;//
		return NULL;
	}
	//否则,调用BuyBTNode函数创建新的节点,并将a[*pi]的值赋给节点。(*pi)++后移。
	BTNode* newNode = BuyBTNode(a[(*pi)++]);
	if (newNode != NULL)
	{
		newNode->left = BinaryTreeCreateHelper(a, n, pi);//递归创建左子节点
		newNode->right = BinaryTreeCreateHelper(a, n, pi);//递归创建右子节点
	}
	return newNode;//每次递归都返回创建好的节点。
}

                  通过递归和索引下标的递增,就可以按先序遍历顺序依次创建二叉树的每个节点,并建立节点之间的父子关系，最终返回根节点,就完成了整个二叉树的创建。利用了递归的思想,通过不断调用自身函数来实现结构的生成。

                  BTNode* BinaryTreeCreate(BTDataType* a, int n, int* pi)
{
	return BinaryTreeCreateHelper(a, n, pi);
}

                  🌉包装通过前序遍历的数组构建二叉树

                  BinaryTreeCreate函数是对BinaryTreeCreateHelper的一个包装。BinaryTreeCreateHelper负责具体创建二叉树的递归操作，BinaryTreeCreate作为入口函数,接收参数,调用辅助函数创建树,并返回根节点指针。

                  BTNode* BinaryTreeCreate(BTDataType* a, int n, int* pi)
{
	return BinaryTreeCreateHelper(a, n, pi);
}

                  这样设计有利于函数单一职责原则,明确划分主函数和辅助函数的职责,更好地实现二叉树从先序序列的创建。

                  这里的三种方法构建，其实是我们通过前面我们将用前序构建出来一个二叉树，这个三种呢，其实是基于前面一盹乱来，将前面的已经构建好的，遍历打印刷一遍出来！哈哈哈，以下是代码遍历来刷一遍：

                  🌉前序构建二叉树
                  void BTreePrever(BTNode* root)
{
	if (root == NULL)
		return;
	printf("%c ", root->_data);
	BTreeQrder(root->_left);
	BTreeQrder(root->_right);
}
                  🌉中序构建二叉树
                  void BTreeQrder(BTNode* root)
{
	if (root == NULL)
		return;
	BTreeQrder(root->_left);
	printf("%c ", root->_data);
	BTreeQrder(root->_right);
}
                  🌉后序构建二叉树
                  void BTreeBack(BTNode* root)
{
	if (root == NULL)
		return;
	BTreeQrder(root->_left);
	BTreeQrder(root->_right);
	printf("%c ", root->_data);
}

                  🌠二叉树的销毁

                  BinaryTreeDestory函数是用于释放二叉树占用的内存的。

                  void BinaryTreeDestory(BTNode** root)
{
	if (*root != NULL)
	{
		BinaryTreeDestory(&((*root)->left)); //释放左子树
		BinaryTreeDestory(&((*root)->right)); //释放右子树
		free(*root);//
		*root = NULL;
	}
}

                  🌠层次遍历

                  什么是层次遍历呢？

                  【算法与数据结构】深入二叉树实现超详解（全源码优化）

                  什么是层次遍历呢？我们先了解下层序遍历：除了先序遍历、中序遍历、后序遍历外，还可以对二叉树进行层序遍历。设二叉树的根节点所在层数为1，层序遍历就是从所在二叉树的根节点出发，首先访问第一层的树根节点，然后从左到右访问第2层上的节点，接着是第三层的节点，以此类推，自上而下，自左至右逐层访问树的结点的过程就是层序遍历。

                  So->

                  因此我们可以用队列控制，出队入队遍历二叉树

                  🌠第一种实现：不用数组模拟队列

                  使用队列queue来模拟层序遍历,front和rear指针分别表示队头和队尾，front指针控制出队,rear指针控制入队,两个指针同时移动,就可以模拟出层序的遍历顺序。

                  void LevelOrder(BTNode* root) 
{
	if (root == NULL)//首先判断如果根节点为空,直接返回
		return;
	BTNode* queue[1000]; //使用队列queue来模拟层序遍历,front和rear指针分别表示队头和队尾
	int front = 0, rear = 0;
	queue[rear++] = root;//根节点入队
	while (front data); 
		if (current->left != NULL)//如果当前节点有左子节点,将左子节点加入队尾
			queue[rear++] = current->left;
		if (current->right != NULL)//如果当前节点有右子节点,将右子节点加入队尾
			queue[rear++] = current->right;//rear指针每次递增1,实现节点入队
	}
}

                  【算法与数据结构】深入二叉树实现超详解（全源码优化）

                  【算法与数据结构】深入二叉树实现超详解（全源码优化）

                  🌠第二种实现：不用数组模拟队列，创建队列实现

                  特别注意当我们在这里的取头元素记得要要用数的结构体类型，否则就会崩溃找很久错误，对当然，也可以换取队列的头文件的类型换成BTNode*,而不是int和其他类型

                  void LevelOrder(BTNode* root)
{
	Queue q;
	QueueInit(&q);//初始化队列
	if (root)
		QueuePush(&q, root);//入队
	while (!QueueEmpty(&q))//判断是否为空
	{
		//特别注意当我们在这里的取头元素记得要要用数的结构体类型，否则就会崩溃找很久错误，对当然，也可以换取队列的头文件的类型换成BTNode*,当然文章后面有完整代码，经过优化的，这个是阿森太笨错的，记录下哈哈哈
		BTNode* front = QueueFront(&q);//取队头
		QueuePop(&q);//出队
		if (front)
		{
			printf("%d ", front->data);
			//带入下一层
			QueuePush(&q, front->left);
			QueuePush(&q, front->right);
		}
		else
		{
			printf("N ");
		}
	}
	printf("\n");
	QueueDestroy(&q);//销毁队列
}

                  【算法与数据结构】深入二叉树实现超详解（全源码优化）

                  while循环条件是判断队列是否为空,不是front和rear指针比较。每次从队列取出节点front后,直接打印数据,然后入队其子节点。如果front为空,打印一个标识符"N"。

                  🌉判断二叉树是否是完全二叉树

                  【算法与数据结构】深入二叉树实现超详解（全源码优化）

                  1. 数组模拟队列实现：
                  //辅助函数：判断队列是否为空
int QueueIsEmpty(int front, int rear)
{
	return front == rear;
}
//判断二叉树是否是完全二叉树
int BinaryTreeComplete(BTNode* root)
{
	if (root == NULL)
		return 1; //空树是完全二叉树
	BTNode* queue[1000];//用于存放节点的队列
	int front = 0, rear = 0;
	int flag = 0;//用于标记是否遇到空节点
	//根节点入队
	queue[rear++] = root;
	while (!QueueIsEmpty(front, rear))
	{
		BTNode* current = queue[front++];
		//如果遇到空节点后面还有非空节点，说明不是完全二叉树
		if (current == NULL)
			flag = 1;
		else
		{
			//左右孩子入队
			queue[rear++] = current->left;
			queue[rear++] = current->right;
			//如果遇到空节点后面还有非空节点，说明不是完全二叉树
			if (flag)
				return 0;
		}
	}
	//遍历结束，说明是完全二叉树
	return 1;
}

                  首先使用队列来层序遍历二叉树根节点入队，循环取出队首节点current，如果current为空,设置flag标记为1,表示遇到了空节点，如果current非空,将其左右孩子入队，如果flag已经被设置为1,说明之前遇到了空节点,现在又有非空节点,必然不是完全二叉树,直接返回0，遍历结束,说明没有发现flag为1后还有非空节点的情况,即树节点是从左到右依次完整填充每一层的,就是完全二叉树,返回1

                  1. 用队列实现：
                  //判断二叉树是否是完全二叉树
bool BinaryTreeComplete(BTNode* root)
{
	Queue queue;
	QueueInit(&queue);
	if (root)
		QueuePush(&queue, root);
	while (!QueueEmpty(&queue))
	{
		QDataType front = QueueFront(&queue);
		QueuePop(&queue);
		if (front == NULL)
			break;
		QueuePush(&queue, front->_left);
		QueuePush(&queue, front->_right);
	}
	//break跳出后
	//判断这后的元素是否有非空值
	//有非控制则不是完全二叉树
	while (!QueueEmpty(&queue))
	{
		QDataType front = QueueFront(&queue);
		QueuePop(&queue);
		if (front != NULL)
		{
			QueueDestroy(&queue);
			return false;
		}
	}
	//如果没有非空值返回true
	QueueDestroy(&queue);
	return true;
}

                  这里的逻辑没什么大变化，当然也有一些小细节：

                  这是队列的销毁，和平常一样：

                  void QueueDestroy(Queue* pq)
{
	assert(pq); // 断言队列指针是否为空
	QNode* cur = pq->phead; // cur指向队列头节点
	while (cur)
	{					//切莫将cur->next写成pq->phead->next
		QNode* next = cur->next; // 保存cur下一个节点的指针
		free(cur); // 释放cur节点内存
		cur = next; // cur指针移到下一个节点
	}
	pq->phead = pq->ptail = NULL; // 重置头尾节点指针为空
	pq->size = 0; // 重置队列大小为0
}

                  🌠二叉树节点个数

                  【算法与数据结构】深入二叉树实现超详解（全源码优化）

                  //二叉树节点个数
int BinaryTreeSize(BTNode* root)
{
	if (root == NULL)
		return 0;//递归终止条件是空节点,返回0
	return 1 + BinaryTreeSize(root->left) + BinaryTreeSize(root->right);
	//非空节点返回它本身+左子树+右子树节点个数的和
}

                  这个函数BinaryTreeSize用来计算一棵二叉树的节点总个数。，如果传入的根节点root为空,说明这棵二叉树没有节点,返回0，如果不是空节点,则:这个节点本身就是1个节点，加上它左子树的节点个数BinaryTreeSize(root->left)，加上它右子树的节点个数BinaryTreeSize(root->right)，递归计算左右子树节点个数,然后汇总返回。时间复杂度为O(N),只需要一次遍历二叉树。

                  🌉二叉树叶子节点个数

                  //二叉树叶子节点个数
int BinaryTreeLeafSize(BTNode* root)
{
	if (root == NULL)
		return 0;
	if (root->left == NULL && root->right == NULL)
		return 1;//如果root节点的左右子节点都为空,则root就是叶子节点,返回1
	return BinaryTreeLeafSize(root->left) + BinaryTreeLeafSize(root->right);
}

                  如果传入的根节点root为空,说明这棵二叉树没有节点,返回0如果root节点的左右子节点都为空,则root就是叶子节点,返回1，否则:计算root的左子树叶子节点个数BinaryTreeLeafSize(root->left)，计算root的右子树叶子节点个数BinaryTreeLeafSize(root->right)

                  汇总返回左右子树叶子节点个数之和

                  🌉二叉树第k层节点个数

                  //二叉树滴k层节点个数
int BinaryTreeLevelKSize(BTNode* root, int k)
{
	if (root == NULL)
		return 0;
	if (k == 1)
		return 1;
		//计算root的左子树第k-1层节点个数          //计算root的右子树第k-1层节点个数
	return BinaryTreeLevelKSize(root->left, k - 1) + BinaryTreeLevelKSize(root->right, k - 1);
}

                  递归基线是查询第一层或空树时返回值，每次递归都将层数k减1,向下查询下一层，从下至上不断累加各层节点个数，时间复杂度为O(N),只需要一次遍历。利用层序遍历思想实现对指定层的统计。

                  🌠二叉树查找值为x的节点

                  //二叉树查找值为x的节点
BTNode* BinaryTreeFind(BTNode* root, BTDataType x)
{
	if (root == NULL)//根节点root为空,直接返回NULL
		return NULL;
	if (root->data == x)//root节点的数据等于查找值x,返回root
		return root;
	BTNode* leftResult = BinaryTreeFind(root->left, x);//在root的左子树中查找
	if (leftResult != NULL)//如果左子树找到返回结果,直接返回
		return leftResult;
	return BinaryTreeFind(root->right, x);//如果左子树没有找到,继续在root的右子树
}

                  递归终止条件是找到节点或者子树为空，先在左子树查找,如果找到直接返回，如果左子树没有找到,再在右子树查找，采用深度优先搜索的递归方式遍历整棵二叉树，时间复杂度为O(N),最坏情况需要遍历整棵二叉树。利用递归实现二叉树的深度优先搜索。

                  当然你也可以查找–>

                  // 查找x所在的节点
BTNode* TreeFind(BTNode* root, int x)
{
	if (root == NULL)//根节点root为空,直接返回NULL
		return NULL;
	if (root->val == x)//root节点的值等于x,返回root节点
		return root;
	BTNode* ret1 = TreeFind(root->left, x);
	//在root的左子树中查找TreeFind(root->left, x)
	if (ret1)//如果左子树找到节点,直接返回
		return ret1;
		
	//如果左子树没有找到,在root的右子树中查找TreeFind(root->right, x)/
	BTNode* ret2 = TreeFind(root->right, x);
	if (ret2)
		return ret2;
	return NULL;如果左右子树均没有找到,返回NULL
}

                  用深度优先搜索的递归方式遍历二叉树先在左子树查找，找到则返回,否则查右子树,递归终止条件是找到节点或者子树为空，时间复杂度为O(N),最坏情况需要遍历整棵树。

                  🌉 完整代码实现

                  🌉 BinaryTree.h文件
                  # define _CRT_SECURE_NO_WARNINGS 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);
//二叉树销毁
BTNode* BinaryTreeDestory(BTNode** root);
//二叉树节点个数
int BTNodeTreeSize(BTNode* root);
//二叉树叶子节点个数
int BTNodeTreeLeafSize(BTNode* root);
//二叉树第k层节点个数
int BinaryTreeLevelKSize(BTNode* root, int k);
//二叉树查找值为x的节点
BTNode* BinaryTreeFind(BTNode* root, BTDataType x);
//二叉树前序遍历
void BinaryTreePrevOreder(BTNode* root);
//二叉树中序遍历
void BinaryTreeInOrder(BTNode* root);
//二叉树后序遍历
void BinaryTreePostOrder(BTNode* root);
//层序遍历
void BinaryTreeLevelOrder(BTNode* root);
//求树的高度
int BinaryHeight(BTNode* root);
//判断二叉树是否是完全二叉树
bool BinaryTreeCompelete(BTNode* root);
//前序遍历
void BTreePrever(BTNode* root);
//中序遍历
void BTreeQrder(BTNode* root);
//后序遍历
void BTreeBack(BTNode* root);
                  🌉 Queue.h文件
                  # define _CRT_SECURE_NO_WARNINGS 1
#include 
#include 
#include 
#include 
#include "BinaryTree.h"
typedef BTNode* QDataType;
typedef struct QueueNode
{
	QDataType data;
	struct QueueNode* next;
}QNode;
//二级指针
入队列
//void QueuePush(QNode** pphead, QNode** pptail);
出队列
//void QueuePop(QNode** pphead, QNode** pptail);
typedef struct Queue
{
	QNode* phead;
	QNode* ptail;
	int size;
}Queue;
void QueueInit(Queue* pq);
void QueueDestroy(Queue* pq);
void QueuePush(Queue* pq, QDataType x);
void QueuePop(Queue* pq);
QDataType QueueFront(Queue* pq);
QDataType QueueBack(Queue* pq);
bool QueueEmpty(Queue* pq);
int QueueSize(Queue* pq);
                  🌉 Queue.c文件
                  #include "Queue.h"
void QueueInit(Queue* pq)
{
	assert(pq); // 断言队列指针是否为空
	pq->phead = NULL; // 初始化头节点指针为空
	pq->ptail = NULL; // 初始化尾节点指针为空  
	pq->size = 0; // 初始化队列大小为0
}
void QueueDestroy(Queue* pq)
{
	assert(pq); // 断言队列指针是否为空
	QNode* cur = pq->phead; // cur指向队列头节点
	while (cur)
	{
		QNode* next = cur->next; // 保存cur下一个节点的指针
		free(cur); // 释放cur节点内存
		cur = next; // cur指针移到下一个节点
	}
	pq->phead = pq->ptail = NULL; // 重置头尾节点指针为空
	pq->size = 0; // 重置队列大小为0
}
void QueuePush(Queue* pq, QDataType* x)
{
	assert(pq); // 断言队列指针是否为空
	QNode* newnode = (QNode*)malloc(sizeof(QNode)); // 申请新节点内存
	if (newnode == NULL)
	{ // 申请失败
		perror("malloc fail");
		return;
	}
	newnode->data = x; // 设置新节点数据
	newnode->next = NULL; // 设置新节点next指针为空
	if (pq->ptail)
	{ // 如果队列不为空
		pq->ptail->next = newnode; // 尾节点指向新节点
		pq->ptail = newnode; // 更新尾节点指针
	}
	else
	{ // 队列为空
		pq->phead = pq->ptail = newnode; // 头尾节点同时指向新节点
	}
	pq->size++; // 队列大小增加1
}
//出队列
void QueuePop(Queue* pq)
{
	assert(pq); // 断言队列指针是否为空
	if (pq->phead == NULL)
		return; // 队列为空直接返回
	assert(pq->phead != NULL); // 断言头节点不为空
	if (pq->phead->next == NULL)
	{ // 队列只有一个节点
		free(pq->phead); // 释放头节点
		pq->phead = pq->ptail = NULL; // 头尾节点同时置空
	}
	else
	{ // 队列有多个节点
		QNode* next = pq->phead->next; // 保存头节点的下一个节点
		free(pq->phead); // 释放头节点
		pq->phead = next; // 头节点指向下一个节点
	}
	pq->size--; // 队列大小减1
}
QDataType QueueFront(Queue* pq)
{
	assert(pq);
	assert(pq->phead != NULL);
	return pq->phead->data;
}
QDataType QueueBack(Queue* pq)
{
	assert(pq);
	//暴力检查
	assert(pq->ptail != NULL);
	return pq->ptail->data;
}
bool QueueEmpty(Queue* pq)
{
	assert(pq);
	
	return pq->size == 0;
}
int QueueSize(Queue* pq)
{
	assert(pq);
	return pq->size;
}
                  🌉 BinaryTreeTest.c文件
                  # define _CRT_SECURE_NO_WARNINGS 1
#include "Queue.h"
BTNode* BuyBTNode(int val)
{
	BTNode* newNode = (BTNode*)malloc(sizeof(BTNode));
	if (newNode != NULL)
	{
		newNode->_data = val;
		newNode->_left = NULL;
		newNode->_right = NULL;
	}
	return newNode;
}
//通过前序遍历的数组构建二叉树
BTNode* PreBinaryTreeCreateHelper(BTDataType* a, int n, int* pi)
{
	if (*pi >= n || a[*pi] == 'N')
	{
		(*pi)++;
		return NULL;
	}
	BTNode* newNode = BuyBTNode(a[(*pi)++]);
	if (newNode != NULL)
	{
		newNode->_left = PreBinaryTreeCreateHelper(a, n, pi);
		newNode->_right = PreBinaryTreeCreateHelper(a, n, pi);
	}
	return newNode;
}
//辅助函数构建二叉树
BTNode* BinaryTreeCreate(BTDataType* a, int n, int* pi)
{
	return PreBinaryTreeCreateHelper(a, n, pi);
}
//通过前序遍历的数组打印
void BTreePrever(BTNode* root)
{
	if (root == NULL)
		return;
	printf("%c ", root->_data);
	BTreeQrder(root->_left);
	BTreeQrder(root->_right);
}
//通过中序遍历的数组构建二叉树
void BTreeQrder(BTNode* root)
{
	if (root == NULL)
		return;
	BTreeQrder(root->_left);
	printf("%c ", root->_data);
	BTreeQrder(root->_right);
}
//通过后序遍历的数组构建二叉树
void BTreeBack(BTNode* root)
{
	if (root == NULL)
		return;
	BTreeQrder(root->_left);
	BTreeQrder(root->_right);
	printf("%c ", root->_data);
}
//二叉树的销毁
BTNode* BinaryTreeDestory(BTNode** root)
{
	if (*root != NULL)
	{
		BinaryTreeDestory(&(*root)->_left);
		BinaryTreeDestory(&(*root)->_right);
		free(*root);
		*root = NULL;
	}
}
//二叉树节点个数
int BinaryTreeSize(BTNode* root)
{
	if (root == NULL)
		return 0;
	return 1 + BinaryTreeSize(root->_left) + BinaryTreeSize(root->_right);
	//return root == NULL ? 0 : 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);
	
}
//二叉树第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);
}
//二叉树查找值为x的节点
BTNode* BinaryTreeFind(BTNode* root, BTDataType x)
{
	if (root == NULL)
		return NULL;
	if (root->_data == x)
		return root;
	BTNode* leftResult = BinaryTreeFind(root->_left, x);
	if (leftResult != NULL)
		return leftResult;
	return BinaryTreeFind(root->_right, x);
	
	//也可以这种方法
	//if (root == NULL)
	//	return NULL;
	//if (root->_data == x)
	//{
	//	return root;
	//}
	//BTNode* res1 = BinaryTreeFind(root->_left, x);
	//if (res1)
	//	return res1;
	//BTNode* res2 = BinaryTreeFind(root->_right, x);
	//if (res2)
	//	return res2;
	//retrun NULL;
}
//层序遍历
void LevelOrder(BTNode* root)
{
	if (root == NULL)
		return;
	Queue queue;
	QueueInit(&queue);
	if (root)
		QueuePush(&queue, root);
	while (!QueueEmpty(&queue))
	{
		QDataType front = QueueFront(&queue);
		printf("%c ", front->_data);
		QueuePop(&queue);
		
		if (front->_left)
			QueuePush(&queue, front->_left);
		if (front->_right)
			QueuePush(&queue, front->_right);
	}
	QueueDestroy(&queue);
}
//求树的高度
int BinaryHeight(BTNode* root)
{
	if (root == NULL)
		return 0;
	int leftHeight = BinaryHeight(root->_left);
	int rightHeight = BinaryHeight(root->_right);
	return leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;
}
//判断二叉树是否是完全二叉树
bool BinaryTreeComplete(BTNode* root)
{
	Queue queue;
	QueueInit(&queue);
	if (root)
		QueuePush(&queue, root);
	while (!QueueEmpty(&queue))
	{
		QDataType front = QueueFront(&queue);
		QueuePop(&queue);
		if (front == NULL)
			break;
		QueuePush(&queue, front->_left);
		QueuePush(&queue, front->_right);
	}
	//break跳出后
	//判断这后的元素是否有非空值
	//有非控制则不是完全二叉树
	while (!QueueEmpty(&queue))
	{
		QDataType front = QueueFront(&queue);
		QueuePop(&queue);
		if (front != NULL)
		{
			QueueDestroy(&queue);
			return false;
		}
	}
	//如果没有非空值返回true
	QueueDestroy(&queue);
	return true;
}

                  🌉测试一下效果（BinaryTreeTest.c）文件

                  int main() 
{
    BTDataType preOrder[] = { '1','2','3','N','N','N','4','5','N','N','6','N','N' };
    int index = 0;
    BTNode* root = BinaryTreeCreate(preOrder, sizeof(preOrder) / sizeof(preOrder[0]), &index);
    //前序遍历
    printf("前序遍历:\n");
    BTreePrever(root);
    printf("\n");
    //中序遍历
    printf("中序遍历:\n");
    BTreeQrder(root);
    printf("\n");
    //后序遍历
    printf("后序遍历:\n");
    BTreeBack(root);
    printf("\n");
    printf("二叉树层序遍历结果为：");
    LevelOrder(root);
    printf("\n");
     
    printf("二叉树节点个数为：%d\n", BinaryTreeSize(root));
    printf("二叉树叶子节点个数为：%d\n", BinaryTreeLeafSize(root));
    printf("二叉树第3层节点个数为：%d\n", BinaryTreeLevelKSize(root, 3));
    printf("二叉树是否是完全二叉树：%s\n", BinaryTreeComplete(root) ? "是" : "不是");
    BTNode* findNode = BinaryTreeFind(root, 'H');
    if (findNode != NULL)
        printf("查找值为'H'的节点成功。\n");
    else
        printf("未找到该节点的值为'H'。\n");
 
    BinaryTreeDestory(&root);
    return 0;
}

                  代码前序构建图：

                  【算法与数据结构】深入二叉树实现超详解（全源码优化）

                  运行代码图

                  如果数组的N改为#，或者任意符号，只需将以下代码修改

                  //通过前序遍历的数组构建二叉树
BTNode* PreBinaryTreeCreateHelper(BTDataType* a, int n, int* pi)
{
	if (*pi >= n || a[*pi] == '#')//这里替换修改即可
	{
		(*pi)++;
		return NULL;
	}
	BTNode* newNode = BuyBTNode(a[(*pi)++]);
	if (newNode != NULL)
	{
		newNode->_left = PreBinaryTreeCreateHelper(a, n, pi);
		newNode->_right = PreBinaryTreeCreateHelper(a, n, pi);
	}
	return newNode;
}

                  【算法与数据结构】深入二叉树实现超详解（全源码优化）

                  🚩总结

                  感谢你的收看，如果文章有错误，可以指出，我不胜感激，让我们一起学习交流，如果文章可以给你一个小小帮助，可以给博主点一个小小的赞😘，可以点点关注和赞哦 💓 💗 💕 💞

                  【算法与数据结构】深入二叉树实现超详解（全源码优化）

VPS购买请点击我

文章版权声明：除非注明，否则均为主机测评原创文章，转载或复制请以超链接形式并注明出处。

相关阅读

目录[+]