1. Toy模板网首页
  2. > Toy博客

数据结构：二叉树及相关操作

8月前 作者：卡拉肖克·小黑 分类：Toy博客 阅读(35) 违法举报

这篇具有很好参考价值的文章主要介绍了数据结构：二叉树及相关操作。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

前言

在实现二叉树前，我们要先对树产生一些基本的认识，才可以去实现它。树的用途非常广泛，向文件系统的目录树结构等。

一、树的概念及结构

1.什么是树

树是一种非线性的数据结构，它是由n（n>=0）个有限结点组成一个具有层次关系的集合。有一个特殊的结点，称为根结点，根节点没有前驱结点。除根节点外，其余结点被分成M(M>0)个互不相交的集合T1、T2、……、Tm，其中每一个集合Ti(1<= i <= m)又是一棵结构与树类似的子树。每棵子树的根结点有且只有一个前驱，可以有0个或多个后继。因此，树是递归定义的。
如图所示：
数据结构：二叉树及相关操作,数据结构,数据结构,算法,c语言,链表
注意：树形结构中，子树之间不能有交集，否则就不是树形结构
如图所示：
数据结构：二叉树及相关操作,数据结构,数据结构,算法,c语言,链表
这个就不可以在称为树，这个构成了环形结构，这个是一个图。

2. 树的相关概念

数据结构：二叉树及相关操作,数据结构,数据结构,算法,c语言,链表

节点的度：一个节点含有的子树的个数称为该节点的度。如上图：A的度为3
树的深度：树中节点的最大层次。如上图：树的深度为4
叶子节点：度为0的节点称为叶节点。如上图：K为叶子节点
孩子节点：一个节点含有的子树的根节点称为该节点的子节点。如上图：B是A的孩子节点
兄弟节点：具有相同父节点的节点互称为兄弟节点。 如上图：B、C是兄弟节点
堂兄弟节点：双亲在同一层的节点互为堂兄弟。如上图：F、G是堂兄弟节点

3.树的表示

树结构相对线性表就比较复杂了，要存储表示起来就比较麻烦了，既然保存值域，也要保存结点和结点之间的关系，实际中树有很多种表示方式如：双亲表示法，孩子表示法、孩子双亲表示法以及孩子兄弟表示法等。我们这里就简单的了解其中最常用的孩子兄弟表示法。

typedef int DataType;
struct Node
{
	 struct Node* firstChild1; // 第一个孩子结点
	 struct Node* pNextBrother; // 指向其下一个兄弟结点
	 DataType data; // 结点中的数据域
};

上面树的表示形式如下：
数据结构：二叉树及相关操作,数据结构,数据结构,算法,c语言,链表

二、二叉树概念及结构

1.二叉树概念

二叉树不存在度大于2的结点
如图所示：
数据结构：二叉树及相关操作,数据结构,数据结构,算法,c语言,链表

2.特殊的二叉树

满二叉树：一个二叉树，如果每一个层的结点数都达到最大值，则这个二叉树就是满二叉树。
完全二叉树：对于深度为K的，有n个结点的二叉树，当且仅当其每一个结点都与深度为K的满二叉树中编号从1至n的结点一一对应时称之为完全二叉树。 要注意的是满二叉树是一种特殊的完全二叉树。
数据结构：二叉树及相关操作,数据结构,数据结构,算法,c语言,链表

3.二叉树的性质

1. 若规定根节点的层数为1，则一棵非空二叉树的第i层上最多有2的(i-1)次方个结点。
2. 若规定根节点的层数为1，则深度为h的二叉树的最大结点数是2的h次方减1个。
3. 对任何一棵二叉树，如果度为0其叶结点个数为X个 , 度为2的分支结点个数为Y个,则有X＝Y＋1
4.对于具有n个结点的完全二叉树，如果按照从上至下从左至右的数组顺序对所有节点从0开始编号，则对
于序号为i的结点有：
1.若i>0，i位置节点的双亲序号：(i-1)/2；i=0，i为根节点编号，无双亲节点
2. 若2i+1<n，左孩子序号：2i+1，2i+1>=n否则无左孩子
3. 若2i+2<n，右孩子序号：2i+2，2i+2>=n否则无右孩子

4.二叉树的存储结构

1. 顺序存储顺序结构存储就是使用数组来存储，一般使用数组只适合表示完全二叉树，因为不是完全二叉树会有空间的浪费。而现实中使用中只有堆才会使用数组来存储，二叉树顺序存储在物理上是一个数组，在逻辑上是一颗二叉树。
2. 链式存储二叉树的链式存储结构是指，用链表来表示一棵二叉树，即用链来指示元素的逻辑关系。 通常的方法是链表中每个结点由三个域组成，数据域和左右指针域，左右指针分别用来给出该结点左孩子和右孩子所在的链结点的存储地址 。
数据结构：二叉树及相关操作,数据结构,数据结构,算法,c语言,链表
如上图所示：上面二叉树的储存形式如下：
数据结构：二叉树及相关操作,数据结构,数据结构,算法,c语言,链表
链式存储的结构体如下：

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

三、平衡二叉树实现

1.创建树和树的前中后遍历

1.前中后遍历

所谓二叉树遍历(Traversal)是按照某种特定的规则，依次对二叉树中的节点进行相应的操作，并且每个节点只操作一次。
前序遍历：根，左子树，右子树
中序遍历：左子树，根，右子树
后序遍历：左子树，右子树根，
数据结构：二叉树及相关操作,数据结构,数据结构,算法,c语言,链表
数据结构：二叉树及相关操作,数据结构,数据结构,算法,c语言,链表
中序和后续的遍历同理。

2.创建树且打印前中后遍历

要实现的函数：

//创建二叉树
void TreeCreate(BTDataType* a, int n);
// 二叉树前序遍历 
void BinaryTreePrevOrder(BTNode* root);
// 二叉树中序遍历
void BinaryTreeInOrder(BTNode* root);
// 二叉树后序遍历
void BinaryTreePostOrder(BTNode* root);
// 二叉树销毁
void BinaryTreeDestory(BTNode** root);

实现代码如下：

//创建二叉树
void TreeCreate(BTNode** root ,BTDataType num)
{
	if (*root == NULL)//如果节点为空证明该位置为要插入的位置
	{
		BTNode* pos = (BTNode*)malloc(sizeof(BTNode));//开辟节点
		if (pos == NULL)//判断节点是否开辟成功
		{
			perror("malloc");
			exit(-1);
		}
		pos->data = num;
		pos->left = NULL;
		pos->right = NULL;
		*root = pos;//把该节点连接到树上
		return;
	}
	if (num < (*root)->data)//比根节点小则在左边插入
	{
		TreeCreate(&(*root)->left, num);
	}
	else//比根节点大则在右边插入
	{
		TreeCreate(&(*root)->right, num);
	}
}
// 二叉树前序遍历 
void BinaryTreePrevOrder(BTNode* root)
{
	if (root == NULL)
	{
		return;
	}
	printf("%d ", root->data);
	BinaryTreePrevOrder(root->left);
	BinaryTreePrevOrder(root->right);
}
// 二叉树中序遍历
void BinaryTreeInOrder(BTNode* root)
{
	if (root == NULL)
	{
		return;
	}
	BinaryTreeInOrder(root->left);
	printf("%d ", root->data);
	BinaryTreeInOrder(root->right);
}
// 二叉树后序遍历
void BinaryTreePostOrder(BTNode* root)
{
	if (root == NULL)
	{
		return;
	}
	BinaryTreePostOrder(root->left);
	BinaryTreePostOrder(root->right);
	printf("%d ", root->data);
}
// 二叉树销毁
void BinaryTreeDestory(BTNode** root)
{
	if (*root == NULL)
	{
		return;
	}
	BinaryTreeDestory(&(*root)->left);
	BinaryTreeDestory(&(*root)->right);
	free(*root);
}

测试函数：

void test()
{
	int arr[] = { 2,1,3,7,6,5,9,8,4 };
	int size = sizeof(arr) / sizeof(arr[0]);
	BTNode* root = NULL;
	int i = 0;
	for (i = 0; i < size; i++)
	{
		TreeCreate(&root, arr[i]);//创建二叉树
	}
	BinaryTreePrevOrder(root);//前
	printf("\n");
	BinaryTreeInOrder(root);//中
	printf("\n");
	BinaryTreePostOrder(root);//后
	printf("\n");
	BinaryTreeDestory(&root);//销毁
}
int main()
{
	test();
	return 0;
}

构建的二叉树如下：
数据结构：二叉树及相关操作,数据结构,数据结构,算法,c语言,链表
前序递归部分过程如下：
数据结构：二叉树及相关操作,数据结构,数据结构,算法,c语言,链表
前序要先打印根节点的值在进行递归，中序要先进行左递归，在打印值，最后进行右递归，而后续则是先进行左右递归在打印相应的值。
注意：销毁二叉树要进行后续遍历，只有把根的左右子树都进行释放，才可以释放根节点。根节点先于左右子树释放会找不到相应左右节点，造成内存泄漏。

2.转换为平衡二叉树和相关操作

我们刚才构建的树明显一边节点多，一边节点少，所以我们把上面的树转化为左右子树的节点相差在1以内，进行左右平衡

1.转换为平衡二叉树

// 二叉树节点个数
int BinaryTreeSize(BTNode* root)
{
	if (root == NULL)
	{
		return 0;
	}
	return BinaryTreeSize(root->left) + 1 + BinaryTreeSize(root->right);
}
//左旋
BTNode* get_min(BTNode* root)
{
	if (root->left == NULL)
	{
		return root;
	}
	return get_min(root->left);//返回最左边的节点
}
void turn_left(BTNode** root)
{
	BTNode* pos = *root;
	(*root) = pos->right;//更换头节点
	pos->right = NULL;//避免出现野指针
	get_min(*root)->left = pos;//把最左边的节点链接此接点
}
//右旋
BTNode* get_max(BTNode* root)
{
	if (root->right == NULL)
	{
		return root;
	}
	return get_max(root->right);//返回最右边的节点
}
void turn_right(BTNode** root)
{
	BTNode* pos = *root;
	(*root) = pos->left;
	pos->left = NULL;
	get_max(*root)->right = pos;//把最右边的节点链接此接点
}
//转换为平衡二叉树
void BalanceTree(BTNode** root)
{
	if (*root == NULL)
	{
		return;
	}
	while(1)
	{
		int a = BinaryTreeSize((*root)->left);
		int b = BinaryTreeSize((*root)->right);
		int num = BinaryTreeSize((*root)->left) - BinaryTreeSize((*root)->right);
		if (num < -1)//右边多
		{
			//&（*root）中&和*抵消了，所以传一个root就可以了，但接收要用二级指针
			turn_left(root);//进行左旋
		}
		else if (num > 1)//左边多
		{
			turn_right(root);//进行右旋
		}
		else
		{
			break;
		}
	}
	BalanceTree(&(*root)->left);//开始平衡左子树
	BalanceTree(&(*root)->right);//开始平衡右子树
}

我们需要对树进行判断是否平衡，就需要求出左右节点的个数，我们还要对左边节点数量大于右边节点数量和右边大于左边的情况分别进行左右旋转。
数据结构：二叉树及相关操作,数据结构,数据结构,算法,c语言,链表
这是进行一次循环，当当前根节点的左右平衡时，开始进行左右子树的平衡。
数据结构：二叉树及相关操作,数据结构,数据结构,算法,c语言,链表
这样我们的平衡树就构建好了。
注意：我们进行左右旋转要连接在最后一个节点上，这样可以保障我们旋转后依然有序，左子树的结果比根节点小，右子树节点比根节点大。

2.二叉树的层序遍历

层序遍历就是按照层来访问二叉树的节点

// 层序遍历
void BinaryTreeLevelOrder(BTNode* root)
{
	Queue qu;//创建队列
	QueueInit(&qu);//初始化队列
	QueuePush(&qu, root);//把根节点带入
	while (!QueueEmpty(&qu))//如果不为空则一直进行循环
	{
		BTNode*pos =  QueueFront(&qu);// 获取队列头部元素 
		printf("%d ", pos->data);
		QueuePop(&qu);//头部元素出队列
		if(pos->left != NULL)//如果左孩子不为空则进队列
			QueuePush(&qu, pos->left);
		if (pos->right != NULL)//如果右孩子不为空则进队列
			QueuePush(&qu, pos->right);
	}
	QueueDestroy(&qu);
}

层序遍历需要我们用队列进行辅助操作
数据结构：二叉树及相关操作,数据结构,数据结构,算法,c语言,链表
层序遍历需要我们用队列进行辅助操作，由父节点来带动子节点，当子节点不为空就进入队列。
测试代码：

void test()
{
	int arr[] = { 2,1,3,7,6,5,9,8,4 };
	int size = sizeof(arr) / sizeof(arr[0]);
	BTNode* root = NULL;
	int i = 0;
	for (i = 0; i < size; i++)
	{
		TreeCreate(&root, arr[i]);//创建二叉树
	}
	BalanceTree(&root);//构建
	BinaryTreeLevelOrder(root);//层
	BinaryTreeDestory(&root);//销毁
}
int main()
{
	test();
	return 0;
}

数据结构：二叉树及相关操作,数据结构,数据结构,算法,c语言,链表

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

// 判断二叉树是否是完全二叉树
bool BinaryTreeComplete(BTNode* root)
{
	Queue qu;//创建队列
	QueueInit(&qu);//初始化队列
	QueuePush(&qu, root);//把根节点带入
	while (!QueueEmpty(&qu))//如果不为空则一直进行循环
	{
		BTNode* pos = QueueFront(&qu);// 获取队列头部元素 
		QueuePop(&qu);//头部元素出队列
		if (pos != NULL)
		{
			QueuePush(&qu, pos->left);
			QueuePush(&qu, pos->right);
		}
		else
		{
			while (!QueueEmpty(&qu))//一直出队列，直到队列为空停止循环
			{
				pos = QueueFront(&qu);// 获取队列头部元素 
				if (pos != NULL)//如果头部不为空，则证明不为完全二叉树
				{
					QueueDestroy(&qu);//销毁队列
					return false;
				}
				QueuePop(&qu);//头部元素出队列
			}
		}
	}
	QueueDestroy(&qu);
	return true;
}

数据结构：二叉树及相关操作,数据结构,数据结构,算法,c语言,链表
判断是否为完全二叉树也需要用到队列，当为完全二叉树时，队列不会出现数据和空交替出队列的情况，而非完全二叉树会出现数据和空交替出队列的情况
测试代码如下：

void test()
{
	int arr[] = { 2,1,3,7,6,5,9,8,4 };
	int size = sizeof(arr) / sizeof(arr[0]);
	BTNode* root = NULL;
	int i = 0;
	for (i = 0; i < size; i++)
	{
		TreeCreate(&root, arr[i]);//创建二叉树
	}
	BalanceTree(&root);//构建
	if (BinaryTreeComplete(root))//完全
	{
		printf("YES\n");
	}
	else
	{
		printf("NO\n");
	}
	BinaryTreeDestory(&root);//销毁
}
int main()
{
	test();
	return 0;
}

数据结构：二叉树及相关操作,数据结构,数据结构,算法,c语言,链表

4.平衡二叉树的节点删除

//删除头节点,可以改为按查找节点删除
void DelTree(BTNode** root)//进行左旋
{
	BTNode* del = *root;//保存要删除的元素节点
	*root = del->left;//更换头节点
	get_max(*root)->right = del->right;
	free(del);
	BalanceTree(root);//从新构建平衡树
}

我们选择的是删除头根节点，然后进行左旋，从新构建成树，在进行平衡树的构建。我们也可以选择删除指定的节点，树的节点删除一般没有意义。
过程如下：
数据结构：二叉树及相关操作,数据结构,数据结构,算法,c语言,链表

3.二叉树其他操作

// 二叉树最深节点
int DeepTree(BTNode* root)
{
	if (root == NULL)
	{
		return 0;
	}
	//三目表达式，返回左子树和右子树最大的那个
	return DeepTree(root->left) > DeepTree(root->right) ? DeepTree(root->left) + 1 : DeepTree(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 (k == 1)//从第一层开始，所以递减到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* left = BinaryTreeFind(root->left, x);
//	BTNode* right = BinaryTreeFind(root->right, x);
//	if (left == NULL)//如果左子树没找到该值，则返回右子树的值，右子树树中也没找到返回的空，找到则返回相应的节点
//	{
//		return right;
//	}
//	return left;//要找的节点在左子树上
//}
// 二叉树查找值为x的节点
BTNode* BinaryTreeFind(BTNode* root, BTDataType x)
{
	BTNode* pos = root;
	while (pos != NULL)
	{
		if (pos->data < x)//该节点的值小于查找的值则在树的右边
		{
			pos = pos->right;
		}
		else if(pos->data > x)//该节点的值大于查找的值则在树的左边
		{
			pos = pos->left;
		}
		else
		{
			break;
		}
	}
	return pos;
}

二叉树节点的查找可以用正常方式的查找，也可以针对我们所构建的平衡二叉树设计一个函数，我们所设计的平衡二叉树的节点都满足左孩子的值小于父节点的值，右孩子的值都大于父节点的值，这样设计便于我们进行查找。
测试函数：

void test()
{
	int arr[] = { 2,1,3,7,6,5,9,8,4 };
	int size = sizeof(arr) / sizeof(arr[0]);
	BTNode* root = NULL;
	int i = 0;
	for (i = 0; i < size; i++)
	{
		TreeCreate(&root, arr[i]);//创建二叉树
	}
	BalanceTree(&root);//构建
	printf("%d\n", DeepTree(root));//深度
	printf("%d\n", BinaryTreeLeafSize(root));//节点个数
	printf("%d\n", BinaryTreeLevelKSize(root,3));//k层
	printf("%d\n", BinaryTreeFind(root,3)->data);//查找节点
	BinaryTreeDestory(&root);//销毁
}
int main()
{
	test();
	return 0;
}

数据结构：二叉树及相关操作,数据结构,数据结构,算法,c语言,链表

总结

树的更加高阶的内容我们会在进一步的学习中逐步的解锁
下面是本次的全部代码：
main.c:

#include"main.h"
void test()
{
	int arr[] = { 2,1,3,7,6,5,9,8,4 };
	int size = sizeof(arr) / sizeof(arr[0]);
	BTNode* root = NULL;
	int i = 0;
	for (i = 0; i < size; i++)
	{
		TreeCreate(&root, arr[i]);//创建二叉树
	}
	BinaryTreePrevOrder(root);//前
	printf("\n");
	BinaryTreeInOrder(root);//中
	printf("\n");
	BinaryTreePostOrder(root);//后
	printf("\n");
	printf("%d", BinaryTreeSize(root));//节点个数
	printf("\n");
	BalanceTree(&root);//构建
	BinaryTreeLevelOrder(root);//层
	printf("\n");
	if (BinaryTreeComplete(root))//完全
	{
		printf("YES\n");
	}
	else
	{
		printf("NO\n");
	}
	printf("%d\n", DeepTree(root));//深度
	printf("%d\n", BinaryTreeLeafSize(root));//节点个数
	printf("%d\n", BinaryTreeLevelKSize(root,3));//k层
	printf("%d\n", BinaryTreeFind(root,3)->data);//查找节点
	DelTree(&root);
	BinaryTreeLevelOrder(root);//层
	BinaryTreeDestory(&root);//销毁
}
int main()
{
	test();
	return 0;
}

main.h:

#pragma once
#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>
#include<assert.h>
typedef int BTDataType;
typedef struct BinaryTreeNode
{
	BTDataType data;
	struct BinaryTreeNode* left;
	struct BinaryTreeNode* right;
}BTNode;
// 链式结构：表示队列 
typedef BTNode* QDataType;
typedef struct QListNode
{
	struct QListNode* next;
	QDataType data;
}QNode;
// 队列的结构 
typedef struct Queue
{
	QNode* front;
	QNode* rear;
}Queue;
// 初始化队列 
void QueueInit(Queue* q);
// 队尾入队列 
void QueuePush(Queue* q, QDataType data);
// 队头出队列 
void QueuePop(Queue* q);
// 获取队列头部元素 
QDataType* QueueFront(Queue* q);
// 检测队列是否为空，如果为空返回非零结果，如果非空返回0 
bool QueueEmpty(Queue* q);
// 销毁队列 
void QueueDestroy(Queue* q);
//创建二叉树
void TreeCreate(BTDataType* a, int n);
// 二叉树前序遍历 
void BinaryTreePrevOrder(BTNode* root);
// 二叉树中序遍历
void BinaryTreeInOrder(BTNode* root);
// 二叉树后序遍历
void BinaryTreePostOrder(BTNode* root);
// 二叉树销毁
void BinaryTreeDestory(BTNode** root);
// 二叉树节点个数
int BinaryTreeSize(BTNode* root);
//转换为平衡二叉树
void BalanceTree(BTNode** root);
//删除头节点
void DelTree(BTNode** root);
// 层序遍历
void BinaryTreeLevelOrder(BTNode* root);
// 判断二叉树是否是完全二叉树
bool BinaryTreeComplete(BTNode* root);
// 二叉树最深节点
int DeepTree(BTNode* root);
// 二叉树叶子节点个数
int BinaryTreeLeafSize(BTNode* root);
// 二叉树第k层节点个数
int BinaryTreeLevelKSize(BTNode* root, int k);
// 二叉树查找值为x的节点
BTNode* BinaryTreeFind(BTNode* root, BTDataType x);

test.c:文章来源地址https://www.toymoban.com/news/detail-673495.html

#include"main.h"

// 初始化队列 
void QueueInit(Queue* q)
{
	assert(q);
	q->front = q->rear = NULL;
}
// 队尾入队列 
void QueuePush(Queue* q, QDataType data)
{
	assert(q);
	QNode* pos = (QNode*)malloc(sizeof(QNode));
	if (pos == NULL)
	{
		perror("malloc");
		exit(-1);
	}
	pos->data = data;
	pos->next = NULL;
	if (q->rear == NULL)
	{
		q->front = q->rear = pos;
	}
	else
	{
		q->rear->next = pos;
		q->rear = pos;
	}
}
// 队头出队列 
void QueuePop(Queue* q)
{
	assert(q);
	assert(q->front);
	if (q->front->next == NULL)
	{
		free(q->front);
		q->front = q->rear = NULL;
	}
	else
	{
		QNode* next = q->front->next;
		free(q->front);
		q->front = next;
	}
}
// 获取队列头部元素 
QDataType* QueueFront(Queue* q)
{
	assert(q);
	assert(q->front);
	return q->front->data;
}
// 检测队列是否为空，如果为空返回非零结果，如果非空返回0 
bool QueueEmpty(Queue* q)
{
	assert(q);
	return q->front == NULL;
}
// 销毁队列 
void QueueDestroy(Queue* q)
{
	assert(q);
	QNode* pos = q->front;
	while (pos)
	{
		QNode* next = pos->next;
		free(pos);
		pos = next;
	}
	q->front = q->rear = NULL;
}
//创建二叉树
void TreeCreate(BTNode** root ,BTDataType num)
{
	if (*root == NULL)//如果节点为空证明该位置为要插入的位置
	{
		BTNode* pos = (BTNode*)malloc(sizeof(BTNode));//开辟节点
		if (pos == NULL)//判断节点是否开辟成功
		{
			perror("malloc");
			exit(-1);
		}
		pos->data = num;
		pos->left = NULL;
		pos->right = NULL;
		*root = pos;//把该节点连接到树上
		return;
	}
	if (num < (*root)->data)//比根节点小则在左边插入
	{
		TreeCreate(&(*root)->left, num);
	}
	else//比根节点大则在右边插入
	{
		TreeCreate(&(*root)->right, num);
	}
}
// 二叉树前序遍历 
void BinaryTreePrevOrder(BTNode* root)
{
	if (root == NULL)
	{
		return;
	}
	printf("%d ", root->data);
	BinaryTreePrevOrder(root->left);
	BinaryTreePrevOrder(root->right);
}
// 二叉树中序遍历
void BinaryTreeInOrder(BTNode* root)
{
	if (root == NULL)
	{
		return;
	}
	BinaryTreeInOrder(root->left);
	printf("%d ", root->data);
	BinaryTreeInOrder(root->right);
}
// 二叉树后序遍历
void BinaryTreePostOrder(BTNode* root)
{
	if (root == NULL)
	{
		return;
	}
	BinaryTreePostOrder(root->left);
	BinaryTreePostOrder(root->right);
	printf("%d ", root->data);
}
// 二叉树销毁
void BinaryTreeDestory(BTNode** root)
{
	if (*root == NULL)
	{
		return;
	}
	BinaryTreeDestory(&(*root)->left);
	BinaryTreeDestory(&(*root)->right);
	free(*root);
}
// 二叉树节点个数
int BinaryTreeSize(BTNode* root)
{
	if (root == NULL)
	{
		return 0;
	}
	return BinaryTreeSize(root->left) + 1 + BinaryTreeSize(root->right);
}
//左旋
BTNode* get_min(BTNode* root)
{
	if (root->left == NULL)
	{
		return root;
	}
	return get_min(root->left);//返回最左边的节点
}
void turn_left(BTNode** root)
{
	BTNode* pos = *root;
	(*root) = pos->right;//更换头节点
	pos->right = NULL;//避免出现野指针
	get_min(*root)->left = pos;//把最左边的节点链接此接点
}
//右旋
BTNode* get_max(BTNode* root)
{
	if (root->right == NULL)
	{
		return root;
	}
	return get_max(root->right);//返回最右边的节点
}
void turn_right(BTNode** root)
{
	BTNode* pos = *root;
	(*root) = pos->left;
	pos->left = NULL;
	get_max(*root)->right = pos;//把最右边的节点链接此接点
}
//转换为平衡二叉树
void BalanceTree(BTNode** root)
{
	if (*root == NULL)
	{
		return;
	}
	while(1)
	{
		int a = BinaryTreeSize((*root)->left);
		int b = BinaryTreeSize((*root)->right);
		int num = BinaryTreeSize((*root)->left) - BinaryTreeSize((*root)->right);
		if (num < -1)//右边多
		{
			//&（*root）中&和*抵消了，所以传一个root就可以了，但接收要用二级指针
			turn_left(root);//进行左旋
		}
		else if (num > 1)//左边多
		{
			turn_right(root);//进行右旋
		}
		else
		{
			break;
		}
	}
	BalanceTree(&(*root)->left);//开始平衡左子树
	BalanceTree(&(*root)->right);//开始平衡右子树
}
//删除头节点,可以改为按查找节点删除
void DelTree(BTNode** root)//进行左旋
{
	BTNode* del = *root;//保存要删除的元素节点
	*root = del->left;//更换头节点
	get_max(*root)->right = del->right;
	free(del);
	BalanceTree(root);//从新构建平衡树
}
// 层序遍历
void BinaryTreeLevelOrder(BTNode* root)
{
	Queue qu;//创建队列
	QueueInit(&qu);//初始化队列
	QueuePush(&qu, root);//把根节点带入
	while (!QueueEmpty(&qu))//如果不为空则一直进行循环
	{
		BTNode*pos =  QueueFront(&qu);// 获取队列头部元素 
		printf("%d ", pos->data);
		QueuePop(&qu);//头部元素出队列
		if(pos->left != NULL)//如果左孩子不为空则进队列
			QueuePush(&qu, pos->left);
		if (pos->right != NULL)//如果右孩子不为空则进队列
			QueuePush(&qu, pos->right);
	}
	QueueDestroy(&qu);
}
// 判断二叉树是否是完全二叉树
bool BinaryTreeComplete(BTNode* root)
{
	Queue qu;//创建队列
	QueueInit(&qu);//初始化队列
	QueuePush(&qu, root);//把根节点带入
	while (!QueueEmpty(&qu))//如果不为空则一直进行循环
	{
		BTNode* pos = QueueFront(&qu);// 获取队列头部元素 
		QueuePop(&qu);//头部元素出队列
		if (pos != NULL)
		{
			QueuePush(&qu, pos->left);
			QueuePush(&qu, pos->right);
		}
		else
		{
			while (!QueueEmpty(&qu))//一直出队列，直到队列为空停止循环
			{
				pos = QueueFront(&qu);// 获取队列头部元素 
				if (pos != NULL)//如果头部不为空，则证明不为完全二叉树
				{
					QueueDestroy(&qu);//销毁队列
					return false;
				}
				QueuePop(&qu);//头部元素出队列
			}
		}
	}
	QueueDestroy(&qu);
	return true;
}
// 二叉树最深节点
int DeepTree(BTNode* root)
{
	if (root == NULL)
	{
		return 0;
	}
	//三目表达式，返回左子树和右子树最大的那个
	return DeepTree(root->left) > DeepTree(root->right) ? DeepTree(root->left) + 1 : DeepTree(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 (k == 1)//从第一层开始，所以递减到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* left = BinaryTreeFind(root->left, x);
//	BTNode* right = BinaryTreeFind(root->right, x);
//	if (left == NULL)//如果左子树没找到该值，则返回右子树的值，右子树树中也没找到返回的空，找到则返回相应的节点
//	{
//		return right;
//	}
//	return left;//要找的节点在左子树上
//}
// 二叉树查找值为x的节点
BTNode* BinaryTreeFind(BTNode* root, BTDataType x)
{
	BTNode* pos = root;
	while (pos != NULL)
	{
		if (pos->data < x)//该节点的值小于查找的值则在树的右边
		{
			pos = pos->right;
		}
		else if(pos->data > x)//该节点的值大于查找的值则在树的左边
		{
			pos = pos->left;
		}
		else
		{
			break;
		}
	}
	return pos;
}

到了这里，关于数据结构：二叉树及相关操作的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处： 如若内容造成侵权/违法违规/事实不符，请点击违法举报进行投诉反馈，一经查实，立即删除！

分享到：
领支付宝红包 赞助服务器费用

相关文章

  • 链式二叉树及相关操作(前，中，后，层序遍历)

    链式二叉树及相关操作(前，中，后，层序遍历)

    欢迎来到 Claffic 的博客  💞💞💞 “春来无事，只为花忙。” 前言: 上一期给大家介绍了二叉树的一种顺序结构：堆，这一期承接上一期，给大家继续介绍二叉树的另一种结构：链式结构。 目录 🐽Part1:链式二叉树？  1.前情提要  2.创建一颗二叉树 🐷Part2:相关操作实现 1

    2023年04月16日
    浏览(28)
  • 【数据结构】二叉树 链式结构的相关问题

    【数据结构】二叉树 链式结构的相关问题

     本篇文章来详细介绍一下二叉树链式结构经常使用的相关函数，以及相关的的OJ题。 目录 1.前置说明 2.二叉树的遍历 2.1 前序、中序以及后序遍历 2.2 层次遍历 3.节点个数相关函数实现 3.1 二叉树节点个数 3.2 二叉树叶子节点个数 3.3 二叉树第k层节点个数 3.4 在二叉树中查找值

    2024年02月14日
    浏览(48)
  • 【数据结构】——树和二叉树的相关习题

    【数据结构】——树和二叉树的相关习题

    1、设高度为h的二叉树上只有度为0和度为2的结点，则该二叉树中所包含的结点数至少为（），最多为（）。 A、h ；2 h -1 B、2h-1 ； 2 h -1 C、2h+1； 2 h-1 -1 D、h+1；2 h -1 解析： （B） 最少的情况下，除了根结点该层为1个结点以外，其余h-1层都有2个结点，得2(h-1)，即2(h-1)+1=2h-1。

    2024年02月03日
    浏览(37)
  • 【数据结构】——树和二叉树相关概念（全网超级详解）

    【数据结构】——树和二叉树相关概念（全网超级详解）

       创作不易，家人们来一波三连吧？！ 世界上最大的树--雪曼将军树，这棵参天大树不是最长也不是最宽，是不是很奇怪，大只是他的体积是最大的，看图片肯定是感触不深，大家可以自己去看看  扯远了，这次我们介绍的是一种新的数据结构--树 之前的栈和队列，都是一

    2024年04月08日
    浏览(61)
  • 深入理解数据结构第三弹——二叉树（3）——二叉树的基本结构与操作

    深入理解数据结构第三弹——二叉树（3）——二叉树的基本结构与操作

    二叉树（1）： 深入理解数据结构第一弹——二叉树（1）——堆-CSDN博客 二叉树（2）： 深入理解数据结构第二弹——二叉树（2）——堆排序及其时间复杂度-CSDN博客 前言： 在前面我们讲了堆及其应用，帮助我们初步了解了二叉树的一些原理，但那与真正的二叉树仍有不同，

    2024年04月09日
    浏览(42)
  • 【数据结构】树，二叉树，满二叉树，完全二叉树的定义和二叉树的基本操作

    【数据结构】树，二叉树，满二叉树，完全二叉树的定义和二叉树的基本操作

    🎊专栏【数据结构】 🍔喜欢的诗句：更喜岷山千里雪 三军过后尽开颜。 🎆音乐分享【勋章】 大一同学小吉，欢迎并且感谢大家指出我的问题🥰 目录 ⭐树 🏳️‍🌈定义  🏳️‍🌈注意 🍔树的基本术语 ⭐二叉树 🏳️‍🌈定义 🎆二叉树和树的区别 🏳️‍🌈二叉树

    2024年02月05日
    浏览(59)
  • 【数据结构】二叉树链式结构的实现及其常见操作

    【数据结构】二叉树链式结构的实现及其常见操作

    目录 1.手搓二叉树 2.二叉树的遍历 2.1前序、中序以及后序遍历 2.2二叉树的层序遍历 3.二叉树的常见操作 3.1求二叉树节点数量 3.2求二叉树叶子节点数量 3.3求二叉树第k层节点个数 3.3求二叉树的深度 3.4二叉树查找值为x的节点 4.二叉树的销毁 在学习二叉树的基本操作前，需先要

    2024年02月12日
    浏览(39)
  • DS：树及二叉树的相关概念

    DS：树及二叉树的相关概念

                                                     创作不易，兄弟们来波三连吧！！            树是一种非线性的数据结构，它是由n（n=0）个有限结点组成一个具有层次关系的集合。把它叫做树是因为它看起来像一棵倒挂的树，也就是说它是根朝上，而叶朝下的。

    2024年03月13日
    浏览(58)
  • 数据结构实验4：二叉树的基本操作

    数据结构实验4：二叉树的基本操作

    一、问题描述 运用二叉链表实现二叉树的基本操作，包括：创建二叉树的存储结构、复制已有的二叉树、计算已有的二叉树的深度、先根序序列、中根序序列、后根序序列等。 输入格式：AB#C##D## 二、实验目的 掌握二叉链表及二叉树的基本操作。 三、实验内容及要求 1、构造

    2024年01月23日
    浏览(36)
  • 数据结构：二叉树的基本操作（用递归实现）

    数据结构：二叉树的基本操作（用递归实现）

             本文将通过完成以下内容来展示二叉树的基本操作，代码解释标注全面而且清晰，代码书写也十分规范，适合初学者进行学习，本篇文章算是本人的一些学习记录分享，希望对有需要的小伙伴提供一些帮助~ 本文的内容为： 用递归的方法实现以下算法： 1．以二叉

    2024年02月06日
    浏览(45)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包，优惠每天领

二维码1

领取红包

二维码2

领红包