二叉树

文章目录

• 1.树的概念及结构
• • 1.1数的概念
  • 1.2树的概念术语
  • 1.3树的表示
  • 1.4树在实际中的运用
• 2.二叉树的概念及结构
• • 2.1二叉树的概念
  • 2.2特殊的二叉树
  • 2.3二叉树的性质
  • 2.4二叉树的存储结构
• 3.二叉树的顺序结构及实现
• • 3.1二叉树的顺序结构
  • 3.2堆的概念及其结构
  • 3.3堆的实现(数组)
  • • 堆存储结构体创建
    • 堆的初始化（创建）
    • 堆的摧毁
    • 堆的插入
    • 堆的删除
    • 取堆顶的数据
    • 堆的数据个数
    • 堆的判空
  • 3.4堆的应用
  • • 堆排序
    • 建堆的时间复杂度
    • TOP-K问题
• 4.二叉树链式结构
• • 4.1二叉树的简易创建（非真正二叉树创建）
  • 4.2二叉树的遍历
  • • 4.2.1前序、中序、后序遍历
    • • 二叉树前序遍历
      • 二叉树中序遍历
      • 二叉树后序遍历
    • 4.2.2二叉树层序遍历
  • 4.3 二叉树节点个数及高度
  • • 二叉树节点个数
    • 二叉树叶子节点个数
    • 二叉树第k层节点个数
    • 二叉树的深度
    • 二叉树查找值为x的节点
    • 二叉树销毁

1.树的概念及结构 1.1数的概念

树是一种非线性的数据结构，它是由n（n>=0）个有限结点组成一个具有层次关系的集合。把它叫做树是因为它看起来像一棵倒挂的树，也就是说它是根朝上，叶朝下的。
1.有一个特殊结点，称为根结点，根结点没有前驱结点。
2.除根结点外，其余结点被分成M(M>0)个互不相交的集合T1、T2、…、Tm,其中每一个集合Ti（1<=i<=m）又是一颗结构与树类似的子树。每棵子数的根结点有且只有一个前驱，可以有0个或多个后继结点。
3.树是递归定义的。
" />

注意： 树形结构中，子树之间不能有交集(即不能够在树里面出现回路)，否则就不是树形结构。

1.2树的概念术语

1.3树的表示

树的结构相对于线性表更复杂，想要存储起来就比较麻烦，既要保存值域，也要保存节点与节点之间的关系。
实际中的树的表示：双亲表示法、孩子表示法，孩子双亲表示法、孩子兄弟表示法等。
比较常用的就是孩子兄弟表示法。

孩子兄弟表示法：

typedef int DataType;

typedef struct Node
{
	struct Node* _firstChild;    //第一个孩子结点
 	struct Node* _pNextBrother;  //指向其下一个兄弟结点
	DataType _data;              //结点中的数据域
}Node;

1.4树在实际中的运用

相当于磁盘里面的文件及其展开。

2.二叉树的概念及结构 2.1二叉树的概念

一颗二叉树是结点的一个有限集合，该集合：
1.或者为空。
2.或者由一个根结点加上两棵称为左子树和右子树的二叉树组成。

1.二叉树不存在度大于2的结点。
2.二叉树有左右之分，次序不能颠倒，因此二叉树是有序树。

对于任意的二叉树都是由以下几种情况复合而成的：

2.2特殊的二叉树

满二叉树（Full Binary Tree）:除最后一层无任何子节点外，每一层上的所有结点都有两个子结点二叉树。如果一个二叉树的层次为k，且总结点总数是2^k-1，则它就是满二叉树。

完全二叉树（Complete Binary Tree） :叶节点只能出现在最下层和次下层，并且最下面一层的结点都集中在该层最左边的若干位置的二叉树。完全二叉树是效率很高的数据结构，完全二叉树由满二叉树引出来。且满二叉树是一种特殊的完全二叉树。

2.3二叉树的性质

1.若规定根节点的层数为1，则一棵非空二叉树的第k层上最多有2^(k-1)个结点。
2.若规定根节点的层数为1，则深度为h的二叉树的最大结点数是2^h - 1。
3.对任何一棵二叉树，如果度为0其叶结点个数为n0，度为2的分支结点个数为n2，则有
n0=n2+1。
4.若规定根节点的层数为1，具有n个结点的满二叉树的深度，h= log ⁡ 2 ( n + 1 ) \log_2{(n+1)} log2​(n+1)。
5.对于具有n个结点的完全二叉树，如果按照从上至下从左至右的数组顺序对所有结点从0开始编号，则对于序号为i的结点有：

1. 若i>0，i位置节点的双亲序号：(i-1)/2；i=0，i为根节点编号，无双亲节点
2. 若2i+1=n否则无左孩子
3. 若2i+2=n否则无右孩子

2.4二叉树的存储结构

二叉树一般可以使用两种结构存储，一种顺序结构，一种链式结构。
1.顺序存储
顺序结构存储就是使用数组来存储，一般使用数组只适合表示完全二叉树，因为不是完全二叉树会有空间的浪费。而现实使用中只有堆才会使用数组来存储。二叉树顺序存储在物理上是一个数组，在逻辑上是一颗二叉树。

2.链式存储
二叉树的链式存储结构是指，用链表来表示一颗二叉树，即用链表来指示元素间的逻辑关系。通常的方法是链表中每个结点由三个域组成，，数据域和左右指针域，左右指针分别用来给出该结点左孩子和右孩子所在的链结点的存储地址。链式结构又分为二叉链和三叉链，一般我们学习都是二叉链。红黑树等会用到三叉链。

二叉链：

typedef int BTDataType;
//二叉链
typedef struct BinaryTreeNode
{
	struct BTreeNode* pleft;   //指向当前节点左孩子
	struct BTreeNode* right;   //指向当前节点右孩子
	BTDataType data;           //当前节点值域
}TreeNode;

三叉链：

typedef int BTDataType;
//三叉链
typedef struct BinaryTreeNode
{
	struct BTreeNode* pparent;   //指向当前节点的双亲
	struct BTreeNode* pleft;     //指向当前节点的左孩子
	struct BTreeNode* pright;    //指向当前节点的右孩子
	BTDataType data;             //当前节点值域
}TreeNode;

3.二叉树的顺序结构及实现 3.1二叉树的顺序结构

普通的二叉树是不适合用数组来存储的，因为可能会存在大量的空间浪费。完全二叉树更适合使用顺序结构存储。我们通常把堆（一种二叉树）使用顺序结构的数组来存储，这里的堆和 *** 作系统虚拟进程地址空间中的堆是两回事，一个是数据结构，一个是 *** 作系统中管理内存的一块区域分段。

3.2堆的概念及其结构

" />

3.3堆的实现(数组)

堆的底层结构我们将采用数组来实现。接下来我们实现一个小堆。

堆存储结构体创建

typedef int HPDataType;
typedef struct Heap
{
	HPDataType* a;     //指向int类型的指针
	size_t size;       //记录数组中的元素个数
	size_t capacity;   //数组的容量
}HP;//对结构体重命名

堆的初始化（创建）

//堆的初始化（构建）
void HeapInit(HP* php)
{
	assert(php);
	php->a = NULL;
	php->size = php->capacity = 0;
}

堆的摧毁

因为堆的底层结构使用了动态申请空间，所以使用完，程序结束时需要把申请的空间释放掉（还给 *** 作系统），也可以避免内存泄漏而带来的损失。

//堆的销毁
void HeapDestroy(HP* php)
{
	assert(php);
	free(php->a);//将a指向的空间释放掉
	php->a = NULL;//置为空
	php->size = php->capacity = 0;
}

堆的插入

例如：先插入一个10到数组的尾上，再进行向上调整算法，知道满足指定的堆。
1.先将元素插入到堆的末尾，即最后一个孩子之后。
2.插入之后如果堆的性质遭到破坏，将新插入的节点顺着其双亲往上调整到合适的位置即可。

//交换数据
void Swap(HPDataType* pa, HPDataType* pb)
{
	HPDataType tmp = *pa;
	*pa = *pb;
	*pb = tmp;
}

//向上调整算法
void AdjustUp(HPDataType* a, size_t child)
{
	size_t parent = (child - 1) / 2;//算出child父亲的下标
	while (child > 0 && a[parent] > a[child])//如果父亲大于孩子，孩子的下标大于0.那么就继续调整
	{
		Swap(&a[child], &a[parent]);//交换
		child = parent;
		parent = (child - 1) / 2;
	}
}

//堆的插入
void HeapPush(HP* php, HPDataType x)
{
	assert(php);//检测指针的有效性

	//如果空间满了，就增容
	if (php->size == php->capacity)
	{
		size_t newCapacity = php->capacity == 0 ? 4 : php->capacity * 2;//新的空间的大小
		HPDataType* tmp = (HPDataType*)realloc(php->a, sizeof(HPDataType) * newCapacity);//动态开辟一块空间
		if (tmp == NULL)
		{
			printf("realloc fail\n");
			exit(-1);//空间开辟失败，退出程序
		}
		php->a = tmp;//将开辟成功的空间让它指向a的空间
		php->capacity = newCapacity;//更新容量
	}
	php->a[php->size] = x;//将数据放入指定位置
	php->size++;//下标向下走一位

	//向上调整,控制保持是一个小堆
	AdjustUp(php->a, php->size - 1);
}

堆的删除

堆的删除是删除堆顶的数据，将堆顶的数据根最后一个数据换一下，然后删除数组的最后一个数据，再进行向下调整算法。
1.将堆顶元素与堆中最后一个元素进行交换。
2.删除堆中最后一个元素。
3.将堆顶元素向下调整到满足维持特性为止。

//交换数据
void Swap(HPDataType* pa, HPDataType* pb)
{
	HPDataType tmp = *pa;
	*pa = *pb;
	*pb = tmp;
}

void AdjustDown(HPDataType* a, size_t size, size_t root)
{
	size_t parent = root ;//让父亲指定堆顶
	size_t child = parent * 2 + 1;//算出左孩子的下标
	while (child < size)
	{
		//选出左右孩子中较小的那个孩子
		if (a[child] > a[child + 1] && child + 1 < size)
		{
			child++;
		}
		//如果孩子小于父亲，则进行调整
		if (a[child] < a[parent])
		{
			Swap(&a[child], &a[parent]);
			parent = child;
			child = parent * 2 + 1;
		}
		//如果孩子不小于父亲，调整完毕，跳出循环
		else
		{
			break;
		}
	}

}

//堆的删除(删除堆顶的数据（最大/最小）)
void HeapPop(HP* php)
{
	assert(php);//检测指针的有效性
	assert(php->size > 0);//保证堆里面有数据
	Swap(&php->a[php->size-1], &php->a[0]);//交换堆顶和尾部的数据
	--php->size;//size向下减小一位

	//向下调整数据，保持为小堆
	AdjustDown(php->a, php->size, 0);
}

取堆顶的数据

在保证堆里面有数据的情况下，直接返回堆顶数据。

//取堆顶的数据
HPDataType HeapTop(HP* php)
{
	assert(php);//检测指针的有效性
	assert(php->size > 0);//保证堆里面有数据可以取
	return php->a[0];//返回堆顶数据
}

堆的数据个数

//堆的数据个数
int HeapSize(HP* php)
{
	assert(php);//检测指针有效性
	return php->size;//返回数据个数
}

堆的判空

//堆的判空
bool HeapEmpty(HP* php)
{
	assert(php);
	return php->size == 0;
}

3.4堆的应用 堆排序

我们先用我们之前写的堆来排一个数组的升序。但是每次堆排序都要这样写一个堆那简直太麻烦了，而且空间复杂度为O（N）。所以我们一般情况下不这样来写堆排序。

堆排序即利用堆的思想来进行排序，总共分为两个步骤：
1.建堆
升序：建大堆
降序：建小堆
2.利用堆删除思想来进行排序
建堆和堆删除中都用到了向下调整，因此掌握了向下调整，就可以完成堆排序。

对数组建堆有两种方式：
1.使用向上调整，插入数据的思想建堆

//向上调整建堆
	for (int i = 1;i < n;i++)
	{
		AdjustUp(a, i);
	}

2.使用向下调整，插入数据的思想建堆

//向下调整建堆
	for (int i = (n - 1 - 1) / 2;i >= 0;--i)//从倒数第一个非叶子节点开始
	{
		AdjustDown(a, n, i);
	}

建堆的时间复杂度

TOP-K问题

TOP-K问题：即求数据集合中前K个最大的元素或者最小的元素，一般情况下数据量都比较大。
比如：专业前10名、世界500强、游戏中前10的活跃玩家等。
对于Top-K问题，能想到的最简单直接的方式就是排序，但是：如果数据量非常大，排序就不太可取了(可能数据都不能一下子全部加载到内存中)。最佳的方式就是用堆来解决，基本思路如下：
1.用数据集合中前K个元素来建堆
前K个最大的元素 – 建小堆
前K个最小的元素 – 建大堆
2.用剩余的N-K个元素依次与堆顶元素进行比较，不满足则替换堆顶的元素。
将剩余N-K个元素依次与堆顶元素比完之后，堆中剩余的K个元素就是所求的前K个最小或者最大的元素。
时间复杂度：O(K+logK*(N-K))
空间复杂度：O(K)

举一个例子：

void AdjustDown(HPDataType* a, size_t size, size_t root)
{
	size_t parent = root;//让父亲指定堆顶
	size_t child = parent * 2 + 1;//算出左孩子的下标
	while (child < size)
	{
		//选出左右孩子中较小的那个孩子
		if (a[child] > a[child + 1] && child + 1 < size)
		{
			child++;
		}
		//如果孩子小于父亲，则进行调整
		if (a[child] < a[parent])
		{
			Swap(&a[child], &a[parent]);
			parent = child;
			child = parent * 2 + 1;
		}
		//如果孩子不小于父亲，调整完毕，跳出循环
		else
		{
			break;
		}
	}

}

void PrintTopK(int* a, int n, int k)
{
	// 1. 建堆--用a中前k个元素建堆
	int* KminHeap = (int*)malloc(sizeof(int) * k);//开辟可以存放k个元素的整形空间
	if (KminHeap == NULL)//开辟失败的情况
	{
		printf("malloc fail\n");
		exit(-1);//开辟失败，退出程序
	}
	for (int i = 0;i < k;i++)//把前k个元素放入堆中
	{
		KminHeap[i] = a[i];
	}
	
	//建堆 - 从倒数第一个非叶子节点开始建
	for (int j = (k - 1 - 1) / 2;j >= 0;--j)
	{
		AdjustDown(KminHeap, k, j);
	}
	// 2. 将剩余n-k个元素依次与堆顶元素交换，不满足则替换
	for (int i = k;i < n;++i)//遍历剩余的元素
	{
	    //如果比堆顶元素大，则进行交换
		if (a[i] > KminHeap[0])
		{
			KminHeap[0] = a[i];
			AdjustDown(KminHeap, k, 0);//向下调整，使大的元素向下沉
		}
	}
	for (int i = 0;i < k;++i)
	{
		printf("%d ", KminHeap[i]);
	}
}

void TestTopK()
{
	int n = 10000;
	int* a = (int*)malloc(sizeof(int) * n);//开n个整形空间
	srand(time(0));//随机产生一些数
	for (size_t i = 0;i < n;i++)//遍历随机产生的n个数
	{
		a[i] = rand() % 1000000;//让随机产生的n个数的大小范围在0-1000000以内
	}
	//因为数是随机产生的所以我们不知道最大的前k个数据是多少，所以我们随机更改里面的10个数，让它们均大于随机产生的数，这样最后排序筛选出的最大的10个数就是给的这10个。
	a[5] = 1000000 + 2;
	a[1024] = 1000000 + 1;
	a[1551] = 1000000 + 3;
	a[55] = 1000000 + 6;
	a[7] = 1000000 + 5;
	a[2565] = 1000000 + 8;
	a[5445] = 1000000 + 7;
	a[7854] = 1000000 + 4;
	a[1] = 1000000 + 10;
	a[3254] = 1000000 + 9;
	
	//调用排序函数
	PrintTopK(a, n, 10);
}

int main()
{
	TestTopK();
	return 0;
}

运行结果如下：这样就选出了最大的k个数

4.二叉树链式结构 4.1二叉树的简易创建（非真正二叉树创建）

二叉树是：
1.空树
2.非空：根节点，根节点的左子树、根节点的右子树组成。

我们根据上诉图来创建一棵二叉树。需要注意的是这里并不是创建二叉树的方式，真正创建二叉树的方式后续在说。

typedef int BTDataType;

typedef struct BinaryTreeNode
{
	struct BinaryTreeNode* left;//指向左子树的指针
	struct BinaryTreeNode* right;//指向右子树的指针
	BTDataType data;//存放数据
}BTNode;

BTNode* BuyBTNode(BTDataType x)
{
	BTNode* newnode = (BTNode*)malloc(sizeof(BTNode));//开辟一个新的节点空间
	if (newnode == NULL)
	{
		printf("malloc fail\n");
		exit(-1);//节点空间开辟失败，终止程序
	}
	newnode->data = x;//将数据放入节点数据域
	newnode->left = newnode->right = NULL;//将左右指针指向均置为空
	return newnode;//返回新的节点
}

BTNode* CreatBinaryTree()
{
	BTNode* node1 = BuyBTNode(1);
	BTNode* node2 = BuyBTNode(2);
	BTNode* node3 = BuyBTNode(3);
	BTNode* node4 = BuyBTNode(4);
	BTNode* node5 = BuyBTNode(5);
	BTNode* node6 = BuyBTNode(6);

	node1->left = node2;
	node1->right = node4;
	node2->left = node3;
	node4->left = node5;
	node4->right = node6;

	return node1;
}

4.2二叉树的遍历 4.2.1前序、中序、后序遍历

二叉树遍历(Traversal)是按照某种特定的规则，依次对二叉树中的节点进行相应的 *** 作，并且每一个节点只 *** 作一次。 遍历二叉树是最重要的运算之一，也是二叉树上进行其它运算的基础。

二叉树的遍历有：前序/中序/后序的递归结构遍历：
1.前序遍历（Preorder Traversal)—— 访问根节点的 *** 作发生在遍历其左右子树之前。
2. 中序遍历(Inorder Traversal)——访问根结点的 *** 作发生在遍历其左右子树之中（间）。
3. 后序遍历(Postorder Traversal)——访问根结点的 *** 作发生在遍历其左右子树之后。

由于被访问的结点必是某子树的根，所以N(Node）、L(Left subtree）和R(Right subtree）又可解释为根、根的左子树和根的右子树。NLR、LNR和LRN分别又称为先根遍历、中根遍历和后根遍历。

二叉树前序遍历

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

二叉树中序遍历

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

二叉树后序遍历

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

4.2.2二叉树层序遍历

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

4.3 二叉树节点个数及高度 二叉树节点个数

✈️这里我们用分治的思想来解决问题：分治，即分而治之，它的基本思想是将一个规模为N的问题分解为K个规模较小的问题，这些子问题相互独立且与原问题性质相同。那么只要解决子问题，那么原问题也可以得到解决。

🚀思路：子问题
1.空树，为最小规模子问题，节点个数返回0
2.非空树，左子树个数+右子树个数+1

//二叉树节点个数
int BinaryTreeSize(BTNode* root)
{
	return root == NULL ? 0 : BinaryTreeSize(root->left) + BinaryTreeSize(root->right) + 1;
}

二叉树叶子节点个数

我们依旧使用分治的思想来解决题目。

//二叉树叶子节点个数
int BinaryTreeLeafSize(BTNode* root)
{
	if (root == NULL)//为空树的情况
		return NULL;
	if (root->left == NULL && root->right == NULL)//左右孩子均为空即为叶子节点
		return 1;
	return BinaryTreeLeafSize(root->left) + BinaryTreeLeafSize(root->right);
}

二叉树第k层节点个数

//二叉树第k层节点个数
int BinaryTreeLevelSize(BTNode* root, int k)
{
	assert(k >= 1);//保证传入的层数大于等于1
	if (root == NULL)//空树
		return 0;
	if (k == 1)//第一层节点数
		return 1;
	return BinaryTreeLevelSize(root->left, k - 1) + BinaryTreeLevelSize(root->right, k - 1);
}

二叉树的深度

🚀输入一棵二叉树的根节点，求该树的深度。从根节点到叶节点依次经过的节点（含根、叶节点）形成树的一条路径，最长路径的长度为树的深度。

//二叉树的深度
int BinaryTreeDepth(BTNode* root)
{
	if (root == NULL)
		return 0;
	int leftDepth = BinaryTreeDepth(root->left);//向左子树递归
	int rightDepth = BinaryTreeDepth(root->right);//向右子树递归

	return leftDepth > rightDepth ? leftDepth + 1 : rightDepth + 1;//找出左右深度中较大的那一个，让后加上根节点的高度
}

二叉树查找值为x的节点

思路：单边递归查找
🚀具体方法：先对左子树递归查找。如果没有找到x，则返回NULL，如果找到了x，便返回x所在的节点。然后在根据返回的值判断是否需要进行右递归查找。如果左右都没有找到，那么二叉树中不存在此值，返回NULL指针。

//二叉树查找值为x的节点
BTNode* BinaryTreeFind(BTNode* root, BTDataType x)
{
	if (root == NULL)//空树
		return NULL;
	if (root->data == x)//根节点即为x
		return root;
	BTNode* ret1 = BinaryTreeFind(root->left, x);//向左子树递归
	if (ret1)//若返回的不为空，则找到x了，那么返回x节点的地址
		return ret1;
	BTNode* ret2 = BinaryTreeFind(root->right, x);//向右子树递归
	if (ret2)//若返回的不为空，则找到x了，那么返回x节点的地址
		return ret2;

	return NULL;//找不到则返回空
}

二叉树销毁

🚀二叉树的节点是我们动态申请的空间，在使用完二叉树之后，我们需要对其进行销毁。若没有销毁或处理不当，那么有可能会造成内存泄漏，所以我们一定要注意动态开辟空间的销毁。

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