你好赵伟

这个屌丝很懒，什么也没留下！

热门标签

数据结构——二叉树_二叉树csdn

作者：你好赵伟 | 2024-08-19 22:00:17

踩

二叉树csdn

树

树的概念

树是一种非线性的数据结构，它是由n个有限节点组成的具有层次关系的集合。每一个节点代表一个元素，由父节点和子节点的层次关系连接。它被叫做树的原因是因为看起来像一颗倒挂的树（根朝上，叶子朝下）。

树的顶部节点就是根节点，他没有父节点。
除根节点外，其余结点被分为M(M>0)个不相关的集合T1，T2，T3…Tm，其中每一个集合Ti(1<=i<=m)又是一个与树类似的子树，每棵子树的根节点有且只有一个父节点，可以有0个或多个子节点。

所以树都是递归定义的。

在树形结构中，子树之间不能有交集，否则就不是树形结构。

有关树的基本概念

节点（Node）：树中的每个元素都被视为一个节点。
根节点（Root）：树的顶部节点，没有父节点。
子节点（Child）：与另一节点通过有向边相连的节点，称为子节点。
父节点（Parent）：如果一个节点指向另一个节点，那么这个节点是子节点的父节点。
叶节点（Leaf）：没有子节点的节点。
边（Edge）：连接两个节点的有向连接，一棵树有N个节点，就有N-1条边
路径（Path）：从树中一个节点到另一个节点的一系列边。
深度（Depth）：从根节点到特定节点的路径长度。
高度（Height）：从特定节点到最远叶节点的路径长度。

节点的度：一个节点含有的子树或者节点的个数，如上图：A的度为6。
兄弟节点：具有相同的父节点的节点，如上图：B、D是兄弟节点。
树的度：一棵树中，具有最多子节点的节点的度，如上图：树的度为6。
节点的层次：从根节点开始，根为第一层，根的子节点为第二层，以此类推。
树的高度：树中节点的最大层次，如上图：树的高度为4.
森林：由m个互不相交的树的集合。

树的表示

树结构的表示相较于线性表就比较麻烦，因为既要保存值域，也要保存节点和节点的关系。

树常用的表示方法有：

节点链接表示
数组表示
双亲表示
孩子-兄弟表示

我们了解下最常用的孩子兄弟表示法。


typedef int DataType;
 struct Node
 {
 struct Node* firstChild1;    
struct Node* pNextBrother;   
DataType data;               
};

这种表示法的优势在于便于插入删除节点（修改指针即可）、方便遍历所有节点、适用于表示有多个孩子或需要频繁变更结构的树

树的实际应用

除此之外，树还可以用于文件系统、组织结构图、数据库索引和优先队列和堆等等。

二叉树

概念

在一棵树中，每个节点最多只有两个子节点（通常称为左节点和右节点），就是叫做二叉树。

二叉树没有度为2的节点。
二叉树的子树有左右之分，次序不能颠倒。

任意二叉树都是有以下几种情况复合而成的。

常见类型

满二叉树：所有层都是满的，即除了叶节点外，每个节点都有两个子节点。
完全二叉树：除去最后一层外，其他层的节点都是满的。（叶子节点那层可满可不满）满二叉树是一种特殊的完全二叉树。在最后一层，所有的节点都尽可能地集中在左侧连续排列。也就是说，如果最后一层不是满的，那么这些未填充的空位（如果存在）只能出现在右侧。

二叉树的性质

1.规定根节点的层数为1，一棵非空二叉树的第i层最多有2 ^ (i - 1)个节点。

最多是因为该层可能是最最后一层，不是满节点。

2.深度为h的二叉树的最大节点个数是2 ^ h - 1。

3.一棵二叉树，度为0的节点个数为n0，度为2的节点个数为n2，则n0 = n2 + 1。（度为0的节点比度为2节点多一个）

4.n个节点的满二叉树的深度h = log(n + 1)（以2为底）

二叉树的存储结构

1.顺序存储

顺序存储就是使用数组来存储，一般适合完全二叉树，如果不是的话会浪费空间，真正用数组存储的是堆（一种特殊的完全二叉树）。

二叉树顺序存储在物理上是一个数组，在逻辑上是一颗二叉树。

若父节点的索引为i，则左孩子为2 * i + 1，右孩子为2 * i + 2。
若孩子的索引为i，则父亲为 (i - 1) / 2。（因为除法是整除的，即使是右孩子 2 * i + 2，在减一除2后得到的也是i）

2.链式存储

链式存储就是用链表来表示一棵二叉树，每个节点由数据和左右指针构成。


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

链式结构又分为二叉链和三叉链，我们先来学习用二叉链实现的树。

二叉树链式结构的实现

前置

我们先要创建一棵二叉树，这样是为了便于后后序操作的进行。

注意：这不是真正的创建操作，这只是暴力创建一棵二叉树，是为了方便后续的学习与操作。


typedef int BTDataType;
 
typedef struct BinarytreeNode
{
	BTDataType data;
	struct BinaryTreeNode* left;
	struct BinaryTreeNode* right;
}BTNode;
 
BTNode* BuyBTNode(BTDataType x)
{
	BTNode* newnode = (BTNode*)malloc(sizeof(BTNode));
	if (newnode == NULL)
	{
		perror("malloc fail");
		return;
	}
	newnode->data = x;
	newnode->left = NULL;
	newnode->right = NULL;
}
 
BTNode* CreatBTNode()
{
	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;
}

二叉树的遍历

二叉树的遍历是按照某种顺序访问树中的所有节点，而不需要改变树的结构。

二叉树的遍历方法有

前序遍历（Preorder Traversal）
中序遍历（Inorder Traversal）
后序遍历（Postorder Traversal）
层序遍历（Levelorder Traversal）

前序遍历

访问顺序：根节点 -> 左子树 -> 右子树

首先访问根节点，然后递归前序遍历左子树，接着是右子树。

递归实现


// 二叉树前序遍历 
void PrevOrder(BTNode* root)
{
	if (root == NULL)
	{
		printf("N ");
		return;
	}
 
	printf("%d ", root->data);
	PrevOrder(root->left);
	PrevOrder(root->right);
}

中序遍历

访问顺序：左子树 -> 右子树 -> 根节点。

首先递归进行中序遍历左子树，然后访问根节点，最后递归地进行中序遍历右子树。

递归实现


// 二叉树中序遍历
void InOrder(BTNode* root)
{
	if (root == NULL)
	{
		printf("N ");
		return;
	}
	InOrder(root->left);
	printf("%d ", root->data);
	InOrder(root->right);
}

后序遍历

访问顺序：左子树 -> 右子树 -> 根节点。

递归地进行后序遍历左子树，接着右子树，最后访问根节点。

递归实现


//二叉树后序遍历
void PostOrder(BTNode* root)
{
	if (root == NULL)
	{
		printf("N ");
		return;
	}
	PostOrder(root->left);
	PostOrder(root->right);
	printf("%d ", root->data);
}

层序遍历

二叉树的层序遍历，也称为广度优先遍历，按照从上到下、从左往右地顺序访问二叉树的节点。

这种遍历通常使用队列实现。

基本步骤：

初始化：创建一个队列，将根节点（如果存在）入队列。
遍历循环：队列非空时，弹出队列前端节点，访问该节点（如：打印节点的值），将该节点的左子节点和右子节点入队列。
继续：重复步骤2，直到队列为空。


// 层序遍历
void BinaryTreeLevelOrder(BTNode* root)
{
	Queue q;
	QueueInit(&q);
	if (root)
		QueuePush(&q, root);
	while (!QueueEmpty(&q))
	{
		BTNode* front = QueueFront(&q);
		QueuePop(&q);
		printf("%d ", front->data);
 
		if (front->left)
			QueuePush(&q, front->left);
 
		if (front->right)
			QueuePush(&q, front->right);
	}
	QueueDestroy(&q);
}

二叉树的相关接口

节点的个数

终止情况 节点为空则返回0。

单层递归处理逻辑 返回1 + 左子树节点的个数 + 右子树节点的个数


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

这里把终止情况和在一起了。

叶子节点的个数

终止情况 节点为空返回0；节点的左右子树为空返回1。

单层递归处理逻辑 返回左子树的叶子节点个数和右子树节点个数。


// 二叉树叶子节点个数
int BinaryTreeLeafSize(BTNode* root)
{
	if (root == NULL) return 0;
	
	if (root && root->left == NULL && root->right == NULL) return 1;
	
	return BinaryTreeLeafSize(root->left) + BinaryTreeLeafSize(root->right);
}

二叉树高度

终止情况 节点为空返回0；节点的左右子树为空返回1。

单层递归处理逻辑 求出左子树和右子树的高度，比较一下，返回较大高度 + 1（加1是为了算上根节点）


//二叉树高度
int  BinaryTreeHight(BTNode* root)
{
	if (root == NULL) return 0;
 
	if (root && root->left == NULL && root->right == NULL) return 1;
 
	int lefthight = BinaryTreeHight(root->left);
	int righthight = BinaryTreeHight(root->right);
 
	return (lefthight > righthight ? lefthight : righthight) + 1;
}

注意：这里左子树高度和右子树高度一定要存起来，不能直接放在return里，不然的话递归次数会指数级增加的


(BinaryTreeHight(root->left) > BinaryTreeHight(root->right) ?
BinaryTreeHight(root->left) : BinaryTreeHight(root->right)) + 1

上面这种写法是完全错误的写法，一定要避免。

第k层节点个数

终止情况 节点为空返回0；k == 1返回1。

单层递归处理逻辑 返回左子树k-1层节点的个数和右子树k-1层节点的个数。


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

查找值为x的节点

终止情况 节点为空返回空指针；找到值相等的节点，返回该节点。

单层递归处理逻辑 递归地去左子树找，找到了返回，找不到就去右子树找，找到了返回，两棵子树都没找到返回空指针。


// 二叉树查找值为x的节点
BTNode* BinaryTreeFind(BTNode* root, BTDataType x)
{
	if (root == NULL)
		return NULL;
	if (root->data == x)
		return root;
 
	BTNode* ret1 = BinaryTreeFind(root->left,x);
	if (ret1)
		return ret1;
	BTNode* ret2 = BinaryTreeFind(root->right, x);
	if (ret2)
		return ret2;
	return NULL;
}

销毁二叉树

后序遍历的一个应用，递归访问左子树，然后右子树，销毁根节点。


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

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

基本思想

将这棵树当成完全二叉树，将其节点（包括空节点）入队列，出队列时带入左右节点，当出队列访问到的节点为空时，不再入队列，然后遍历队列，发现有非空节点，说明不是完全二叉树，返回false，遍历完就返回true。


bool BinaryTreeComplete(BTNode* root)
{
	Queue q;
	QueueInit(&q);
	QueuePush(&q, root);
 
	while (!QueueEmpty(&q))
	{
		BTNode* front = QueueFront(&q);
		if (front == NULL)
			break;
		QueuePop(&q);
		
		QueuePush(&q, front->left);
 
		QueuePush(&q, front->right);
	}
 
	while (!QueueEmpty(&q))
	{
		BTNode* front = QueueFront(&q);
		if (front)
			return false;
		QueuePop(&q);
	}
	return true;
 
}

通过前序遍历创建二叉树

给定一个前序遍历的数组，创建二叉树。


// 通过前序遍历的数组"ABD##E#H##CF##G##"构建二叉树
BTNode* BinaryTreeCreate(BTDataType* a, int n, int* pi)
{
	if (a[*pi] == '#')
	{
		(*pi)++;
		return NULL;
	}
 
	BTNode* root = (BTNode*)malloc(sizeof(BTNode));
	if (root == NULL)
	{
		perror("malloc fail!");
		return NULL;
	}
	root->data = a[(*pi)++];
 
	root->left = BinaryTreeCreate(a, n, pi);
	root->right = BinaryTreeCreate(a, n, pi);
 
	return root;
}

拜拜，下期再见

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/你好赵伟/article/detail/1003860

推荐阅读

相关标签