数据结构：二叉树与树

一 树的基本概念：

1.树的形状：

2.树的定义：

树是一种非线性的数据结构，它是n(n >= 0)个结点的有限集。当n = 0时，称为空树。在任意一棵非空树中应满足：

2.1 有且仅有一个特定的称为根的结点。
2.2 当n > 1时，其余结点可分为m(m > 0)个互不相交的有限集T1 ……Tm，其中每个集合本身又是一棵树，并且称为根的子树。
显然，树的定义是递归的，即在树的定义中又用到其自身，树是一种递归的数据结构。树作为一种逻辑结构，同时也是一种分层结构，具有以下两点特点：

2.3 树的根结点没有前驱，除根结点外的所有结点有且只有一个前驱。
2.4 树中所有结点可以有零个或多个后继。

3.树中相关的关键词概念：

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

3.2 路径：树的路径是指从根节点到树内特定节点遍历的节点序列

3.3 根：树顶端的节点称为根。一棵树只有一个根，如果要把一个节点和边的集合称为树，那么从根到其他任何一个节点都必须有且只有一条路径。A是根节点

3.4 父节点：若一个节点含有子节点，则这个节点称为其子节点的父节点；如上图：A是B的父节点

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

3.6 兄弟节点：具有相同父节点的节点互称为兄弟节点 如上图：I与J就是兄弟

3.7 堂兄弟节点：不是相同父亲的节点且在同一层而和相邻的称堂兄弟节点 如上图：H与I就是堂兄弟

3.8 叶节点：度为0的节点就是叶节点或者说没有孩子的节点 如上图：P和Q

3.9 分支节点：度不为0的点。列如：B、C、D、都是分支节点。

3.10 子树：每个节点都可以作为子树的根，它和它所有的子节点、子节点的子节点等都包含在子树中。

3.11 节点的层次：从根开始定义，根为第一层，根的子节点为第二层，以此类推。

3.12 深度 \ 高度：树中节点的最大层。如图就是4。

3.13 节点的祖先：从根到该节点的所经过分支上的所有节点，A就是所有节点的祖先。

3.14 深林：互不相交的树的集合被称为深林。

3.15 子孙：以某节点为根的子树的子树中任一节点都被称为该节点的子孙。列如所有节点都是A的子孙

4.树的性质：

4.1 树中的结点数等于所有结点的度数之和加1
4.2 度为m的树中第i层上至多有m^(i-1)个结点(i >= 1)
4.3 高度为h的m叉树至多有(m^h - 1)/(m - 1)个结点
4.4 具有n个结点的m二叉的最小高度为[logm(n(m - 1) + 1)]

二 二叉树的基本概念：

1.二叉树的形状：

2.二叉树的定义：

二叉树是另一种树形结构，其特点时每个结点至多只能有两棵树(即二叉树中不存在度大于2的结点)，并且二叉树的子树也有左右之分，其次序不能任意颠倒。

与树相似，二叉树也有递归的形式定义。二叉树是n(n >= 0)个结点的有限集合：

2.1 或者为空二叉树，即n = 0.
2.2 或者由一个根结点和两个互不相交的被称为根的左子树和右子树组合。左子树和右子树又是分别  是一棵二叉树
二叉树是有序树，若将其左右子树颠倒，则成为另一颗不同的二叉树。即使树中结点只有一颗子树，也要区分它是左子树还是右子树。

3.二叉树的性质：

3.1 非空二叉树上的叶子节点数等于度为2的结点数加1，n0 = n1 + 1
3.2 非空二叉树上第k层上至多有2^(k-1)个结点(k >= 1)
3.3 高度为h二叉树至多有2^(h - 1)个结点(h >= 1)
3.4 对完全二叉树按从上到下、左到右的顺序依次编号1，2……n
3.5 具有n个(n > 0)结点的完全二叉树的高度为[log2(n + 1)]或[log2n] + 1

三 特殊的二叉树：

1.满二叉树(FBT)：

1.1 所有非叶节点都拥有两个子节点。

1.2 最深层的叶子节点从左到右依次排列，没有空缺。

1.3 深度为 h 的完全二叉树，具有 2^h - 1 个节点。

2.完全二叉树(CBT)：

2.1 每一层都拥有最大数量的节点。

2.2 深度为 k 的满二叉树，具有 2^k - 1 个节点。

2.3 非叶节点都拥有两个子节点，最底层可能存在一些空缺。

3.满二叉树和完全二叉树的形状：

四 二叉树的存储结构：

1.顺序存储结构：

二叉树的顺序存储是指使用一维数组来存储二叉树中的节点，并将节点的逻辑结构映射到数组的物理结构中。这种存储方式通常用于空间受限的场景，因为只需要一个数组即可存储整个二叉树。

 2.为什么二叉树的顺序存储只能应用于完全二叉树？

2.1 节点索引与子节点关系： 在顺序存储中，节点的索引与它的子节点之间存在着固定的关系。例如，对于一个节点 i，它的左子节点的索引为 2i，右子节点的索引为 2i + 1。这种关系依赖于完全二叉树的结构特点，即每个非叶节点都拥有两个子节点。

2.2 空间利用率： 顺序存储旨在节省空间，因此需要尽可能地利用数组空间。在完全二叉树中，所有非叶节点都拥有两个子节点，因此数组空间可以得到充分利用。而对于非完全二叉树，可能存在一些节点只有一个子节点或没有子节点，导致数组空间浪费。

2.3 空缺节点处理： 在非完全二叉树中，可能存在空缺节点，即没有实际内容的节点。顺序存储难以有效地处理这些空缺节点，因为它们会破坏节点索引与子节点关系的约定。

2.4 算法复杂度： 对于非完全二叉树，顺序存储需要额外的机制来处理空缺节点，这会导致算法复杂度的增加，降低效率。

3.完全二叉树的顺序存储与非完全二叉树存储形状的区别：

2.堆(Heap)：

堆的定义：

堆（Heap）是一种特殊的树形数据结构，它满足堆性质：允许高效地检索和删除最大/最小元素。堆通常用于实现优先队列。

堆的性质：

在堆中，每个非叶节点的值都应该大于或等于其子节点的值（最大堆）或者小于或等于其子节点的值（最小堆）。

堆通常使用完全二叉树来实现，因为完全二叉树结构可以保证堆性质的有效性和空间利用率。

在最大堆中，根节点是堆中最大的元素；在最小堆中，根节点是堆中最小的元素。

堆的种类:

根据堆性质的不同，堆可以分为两种类型：

最大堆： 在最大堆中，每个非叶节点的值都大于或等于其子节点的值。根节点是堆中最大的元素。

最小堆： 在最小堆中，每个非叶节点的值都小于或等于其子节点的值。根节点是堆中最小的元素。

最大堆与最小堆的形状：

3.顺序存储代码实现：

堆的存储结构：

typedef int HPDataType;
typedef struct Heap
{
	HPDataType* a;
	int size;
	int capacity;
}HP;

堆的所有接口：

//初始化、销毁
void HPInit(HP* php);
void HPDestroy(HP* php);
 
// 插入
void HPPush(HP* php, HPDataType x);
 
//获取堆顶元素、堆的有效数据个数
HPDataType HPTop(HP* php);
HPDataType HPsize(HP* php);
 
// 删除堆顶的数据
void HPPop(HP* php);
 
//判断堆是否为空
bool HPEmpty(HP* php);

堆的初始化：

void HPInit(HP* php)
{
	assert(php);
	php->a = NULL;
	php->capacity = php->size = 0;
}

输出：

堆的销毁：

void HPDestroy(HP* php)
{
	assert(php);
	free(php->a);
	php->a = NULL;
	php->capacity = php->size = 0;
}

输出：

插入：

void HPPush(HP* php, HPDataType x)
{
	assert(php);
	//扩容数组
	if (php->capacity == php->size)
	{
		HPDataType Newcapacity = php->capacity == 0 ? 4 : php->capacity * 2;
		HPDataType* Ptmp = (HPDataType*)realloc(php->a , sizeof(HPDataType) * Newcapacity);
		if (Ptmp == NULL)
		{
			perror("calloc error");
			exit(-1);
		}
		php->a = Ptmp;
		php->capacity = Newcapacity;	
	}
	php->a[php->size] = x;
	php->size++;
	//向上调整
	AdjustUp(php->a, php->size - 1); //因为php->size最后是指向最后数据的后面一个所以传要减一
}

输出：

向上调整(建小堆)：

void AdjustUp(HPDataType* a , HPDataType child)
{
	HPDataType parents = (child - 1) / 2;//找父节点
	while (child > 0)//当child走到首节点时就会停止循环
	{
		if (a[child] < a[parents])
		{
			Swap(&a[child] , &a[parents]);//交换数据
			child = parents;
			parents = (parents - 1) / 2;//改变父亲指针的指向，让父亲指针往上指
		}
		else
		{
			break;
		}
	}
}

交换父子数据：

void Swap(HPDataType* x , HPDataType* y)
{
	int tmp = *x;
	*x = *y;
	*y = tmp;
}

当堆(小堆)要插入新数据时在逻辑层面上是在堆的最右下方插入一个值而在物理层面上是直接在添加在数组的后面，而我们插入一个值必然会改变小堆(大堆)的性质所以需要向上调整以此来保持，所以当插入32时首先需要找到父亲节点然后再跟它比下大小如果新插入的节点比它小那就需要调整，把数据互相交换然后让孩子指向父亲然后再让父亲指向父亲同时要查看数据的大小，当child小于0时就可以退出了

获取堆顶(最大或最小)的元素：

HPDataType HPTop(HP* php)
{
	assert(php);
	return php->a[0];
}

输出：

获取堆的数据个数：

HPDataType HPsize(HP* php)
{
	assert(php);
	return php->size;
}

输出：

删除堆顶的数据：

void HPPop(HP* php)
{
	assert(php);
	assert(php->size > 0);
	Swap(&php->a[0] , &php->a[php->size-1]);//先首尾交换
	php->size--;//删除尾部数据(实际上是隐藏交换之后的尾部数据)
	AdjustDown(php->a , php->size ,0);//向下调整
}

输出：

虽然50 32还是显示但是我们靠自减已经将他们在逻辑层面给删除了但是再物理层面上还是带显示的

向下调整(逐个删除每个数据)：

void AdjustDown(HPDataType* a , HPDataType n , HPDataType parents)
{
	
	HPDataType child = (parents * 2) + 1;
	while (child < n)
	{
		//假设child指向左孩子
		if (child + 1 < n && a[child] > a[child + 1])//选出左右孩子谁大谁小
		{
			
			child++;//如果右孩子小那就让child指针自增指向右孩指就行
		}
		if (a[child] < a[parents])
		{
			Swap(&a[child], &a[parents]);
			child = parents;
			child = (parents * 2) + 1;
		}
		else
		{
			break;
		}
	}
 
}

判断堆是否为空：

bool HPEmpty(HP* php)
{
	assert(php);
	if (php->size == 0)
	{
		return false;
	}
	return true;
	//return php->size == 0;
}

输出：

打印堆：

4.链表存储结构：

链式二叉树是一种非线性数据结构，它使用链接而不是连续的内存布局来表示元素之间的层次关系。与将节点存储在数组中的传统二叉树不同，链式二叉树使用指针来连接节点，从而为节点分配和动态内存管理提供了灵活性。

二叉树的前序，中序，后序遍历:

二叉树遍历是指对二叉树中的每个节点恰好访问一次的系统过程。它是探索和操作二叉树的基本技术。三种常见的遍历方法是前序、中序、后序。

前序遍历：

在前序遍历中，首先访问根结点，然后访问左子树，最后访问右子树 如上图：

遍历顺序：

首先访问根节点 1 ，然后再访问根节点 1 的左子树 2 最后再访问以 2 为根节点的左子树 4，接下来就是访问以 4 为根节点的左子树 NULL 与 右子树 NULL 

1 2 4 NULL NULL

当右子树是NULL那就需要向上返回 ，先是返回到 4 但因 4 已经遍历过了所以需要再次向上返回，返回到 2 但因 2 已经遍历过了但以它为根节点的右子树并没有被遍历过所以就先访问 以 2 为根节点的右子树 5 ，最后访问以5为根的左子树 NULL 和右子树 NULL

5 NULL NULL

这里需要直接返回到 1 这里就不过多解释了思想和上面一样，遍历以 1 为根节点的右子树 3 然后再遍历以 3 为根节点的左子树 6 然后再访问以 3 为根节点的左子树 NULL 和 右子树 NULL，接下来需要返回到 以 3 为根节点的右子树 7最后访问以 7 为根节点的左子树 NULL 和 右子树 NULL

3 6 NULL NULL 7 NULL NULL

它的完整顺序就是 1 2 4 NULL NULL  5 NULL NULL 3 6 NULL NULL 7 NULL NULL

中序遍历：

在中序遍历中，首先访问左子树，然后访问根结点，最后访问右子树 如上图：

遍历顺序：

首先是访问 根节点的左子树 2 然后再访问以 2 为根节点的左子树 4最后再访问以 4 为根节点的左子树 NULL当碰到NULL就可以返回到根节点 4 最后再访问以 4 为根节点的右子树 NULL

 NULL 4 NULL

访问完以 4 为根节点的左树右树那就需要继续向上返回到根节点 2 因只遍历过以根节点的 2 的左子树但右子树并没有遍历所以现在需要遍历右子树 ，先遍历以根节点 5 的左子树 NULL然后再遍历根节点 5 最后需遍历以根节点 5 的右子树 NULL

2 NULL 5 NULL

当以根节点 1 的左子树全部遍历完所以就需要遍历根节点 1 了  那么遍历完左子树 根节点那就需要遍历右子树了。先访问以根节点 1 的右子树 3然后再访问以根节点 3 的左子树 6 然后再遍历以根节点 6 的左子树 NULL当碰到 NULL 那这个程序就需要返回到根节点 6 然后向右访问 NULL碰到NULL那就需要再次返回到根节点 3 ，以3的左子树已经全部访问完所以就需要向右访问以此循环

1 NULL 6 NULL 3 NULL 7 NULL

它的完整顺序就是 NULL 4 NULL 2 NULL 5 NULL 1 NULL 6 NULL 3 NULL 7 NULL

后序遍历：

在后序遍历中，首先访问左子树，然后访问右子树，最后访问根结点 如上图：

遍历顺序：

首先是访问 根节点的左子树 2 然后再访问以 2 为根节点的左子树 4最后再访问以 4 为根节点的左子树 NULL当碰到NULL就可以返回到根节点 4 但是根节点是最后才访问的所以现在不能访问 4 而是先访问以 4 为根节点的右子树 NULL最后再访问以 4 为根节点

NULL NULL 4

访问完根节点 4 之后就需要向上返回到以 2 为根节点但是后序的访问顺序是先访问左 右最后再访问根节点的 所以我们需要向以 2 为根节点的右遍历左子树与右子树 NULL最后再访问根节点 5。

NULL NULL 5

访问完以 2 为根节点的左子树与右子树那么就可以访问根节点了但是根节点 2 也是也是以 1 为根节点的左子树，现在以 1 为左子树已经访问完那就可以访问以 1 为根节点的右子树了所以我们现在向右遍历 直到遍历到以 6 为根节点的左子树 NULL 然后就需开始返回到 根节点 6 然后再向右子树 NULL 最后再访问 根节点 6

NULL NULL 6

访问根节点 6 之后就和以 根节点 1 为左子树的 2 一样这里我就不重新赘述了 最后访问完以 1 为右子树就需要访问 根节点 1 了

NULL NULL 7 3 1

它的完整顺序就是 NULL NULL 4 NULL NULL 5 2 NULL NULL 6 NULL NULL 7 3 1

4.链式存储代码实现：

链式存储结构：

typedef int BTDataType;
typedef struct BinaryTree
{
	struct BinaryTree* left;//左子树
	struct BinaryTree* right;//右子树
	BTDataType data;
}BT;

链式存储所有接口：

//二叉树的初始化
BT* CreatTreeNode(int x);
 
//二叉树的销毁
void DestroyBinaryTree(BT* root);
 
//前序遍历、中序遍历、后序遍历
void PrevOrder(BT* root);
void InOrder(BT* root);
void PostOrder(BT* root);
 
//获取二叉树相关个数
int BinaryTreeSize(BT* root);
 
//获取叶子节点相关个数
int BinaryTreeleafSize(BT* root);
 
//获取树的高度
int  BinaryTreeHeight(BT* root);
 
//计算第K层节点个数
int  BinaryTreeKcount(BT* root, BTDataType k);
 

链式存储初始化：

BT* CreatTreeNode(int x)
{
	BT* Newnode = (BT*)malloc(sizeof(BT));
	if (Newnode == NULL)
	{
		perror("malloc error");
		return NULL;
	}
	Newnode->data = x;
	Newnode->left = NULL;
	Newnode->right = NULL;
	return Newnode;
}

输出：

链式存储销毁：

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

输出：

前序遍历：

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

输出：

中续遍历：

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

输出：

后续遍历：

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

输出：

获取二叉树相关个数：

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

输出：

获取叶子节点相关个数：

int BinaryTreeleafSize(BT* root)
{
	if (root->left == NULL && root->right == NULL)
	{
		return 1;
	}
	if (root == NULL)
	{
		return 0;
	}
	else
	{
		return BinaryTreeleafSize(root->left) + BinaryTreeleafSize(root->right);
	}
}

输出：

获取树的高度：

int  BinaryTreeHeight(BT* root)
{
	if (root == NULL)
	{
		return 0;
	}
	BTDataType Tleft = BinaryTreeHeight(root->left);
	BTDataType Tright = BinaryTreeHeight(root->right);
	return Tleft > Tright ? Tleft + 1 : Tright + 1;
 
}

输出：

计算第K层节点个数：

int  BinaryTreeKcount(BT* root, BTDataType k)
{
	if (root == NULL || k < 1)
	{
		return 0;
	}
	if (k == 1)
	{
		return 1;
	}
	return BinaryTreeKcount(root->left, k - 1) + BinaryTreeKcount(root->right, k - 1);
}

输出：

五 树与二叉树的区别：

1. 子节点数量

• 树：一个节点可以拥有任意多个子节点。
• 二叉树：一个节点最多只能拥有两个子节点，通常称为左子节点和右子节点。

2. 子节点的顺序

• 树：树的子节点可以任意排列，没有左右之分。
• 二叉树：二叉树的子节点必须严格按照左右顺序排列。

3. 应用场景

• 树：树常用于表示具有层次关系的数据结构，例如文件目录树、组织机构图等。
• 二叉树：二叉树由于其结构简单、易于实现，在计算机科学中有着广泛的应用，例如二叉查找树、二叉堆、表达式树等。

4.形象比喻

• 树可以想象成一棵树木，每个节点代表一个树枝，子节点代表树枝的分叉。树枝可以任意分叉，没有左右之分。
• 二叉树可以想象成一棵只有左右两个分支的树，每个节点代表一个树枝，左子节点代表树枝的左边分支，右子节点代表树枝的右边分支。

六 总结：

树和二叉树都是重要的数据结构，但它们在子节点数量、子节点顺序和应用场景等方面存在着差异。选择哪种数据结构取决于具体的应用需求。