首页  思维导图  详情



 



数据结构—树

2024-04-10 10:15:47   9  举报





AI智能生成

数据结构—树

数据结构

二叉树

B+树

树结构

模板推荐

作者其他创作

大纲/内容

什么是树

一种抽象的数据类型，具有树状结构性质的数据集合

树的重要概念

结点

树里面的元素

父子关系

结点之间相连的边

子树

结点大于一，其余互不相交节点的集合

度

一个结点拥有的字树的数量就是结点的度

叶子节点

度为0的节点

孩子

结点的子树的根称为孩子节点

双亲

和孩子结点对应

兄弟

同一个双亲的结点

深林

有多个互不相交的树组成深林

树形数据结构特性

结点高度

结点到叶子节点的最长路径

结点的深度

根节点到该结点的边的个数

结点的层数

结点的深度+1

树的高度

树的根结点的高度

二叉树

 概念

二叉树是一种特殊的树形结构，每个结点最多只有两颗子树

二叉树的第N层最多有2^(N-1)次方个结点

满二叉树

除叶子结点外，其他结点都拥有左右两个结点

完全二叉树

除最后一层结点外，其他层结点个数必须达到最大，且最后一层的结点必须连续靠左排列

数组存储(数组下标i)

左结点=2*i

右结点=2*i+1

二叉树遍历(根节点输出)

前序遍历

根左右

中序遍历

左根右

后序遍历

左右根

层次遍历

队列实现

二叉搜索树

二叉搜索树定义

如果它的左子树不为空，则左子树上结点小于根结点

如果它的右子树不为空，则右子树结点大于根结点

特性

二叉搜索树的中序遍历是单调递增的

二叉搜索树的crud

插入：每次插入结点时要从根结点开始比较，小的放左结点，大的放右结点

查找：和插入的逻辑一致

二叉搜索树的删除 

如果要删除的数是叶子结点，直接将叶子结点删除

如果要删除的结点只有一个子树，子树替换删除结点的位置

如果要删除的结点有左右两颗子树，找后继结点，而且后继结点的左子树一定为空

修改：查找到值修改

红黑树

什么是红黑树

红黑树是一颗自平衡二叉树，通过对红黑树插入、删除做特殊操作，保证红黑树的平衡特性。提高红黑树的查找性能（logn）

红黑树特性

红黑树有两种节点颜色：红色和黑色

根节点必须是黑色

红黑树的叶子结点是空的黑色结点，不存储任何数据

红黑树的结点不能是两个红色结点相连，且任意结点到达叶子结点的路径中，黑色结点的数量必须相等

红黑树新加入的点必须是红色

旋转和变色

变色

当前结点的父结点是红色，且它的祖父结点是的另一个子结点（叔叔结点）也是红色： 1. 把父结点设置为黑色 2. 把叔叔结点设置为黑色 3. 把祖父结点设置为红色 4. 把指针指向祖父结点

左旋

当前父结点是红色，叔叔结点是黑色，且当前结点是右子树。进行左旋操作（以父结点进行左旋）

右旋

当前父结点是红色，叔叔结点是黑色，且当前结点是左子树。变色+右旋 1. 把父结点变为黑色 2. 把祖父结点变为红色 3. 以祖父结点进行右旋

赫夫曼树（哈夫曼树）

什么是赫夫曼树

给定N个权值作为N个叶子结点的权重，构造一颗二叉树，如果该树所有带权路径长度之和最小，称这样的二叉树为最优二叉树，也称为赫夫曼树。注：权值越大离根结点越近

赫夫曼树与赫夫曼编码

赫夫曼树左子树所在边为二进制 0 ，右子树所在边为 1。从根结点到叶子结点的边组合起来就是该叶子结点的编码，称为赫夫曼编码。

赫夫曼树的构建

构建赫夫曼树就是构建最优二叉树，使用贪心算法实现。 1. 将叶子结点集合按照权重从小到大排序 2. 取出两个最小的叶子结点，将两个叶子结点的权重相加，生成新的结点 3. 以新的结点为根，最小的两个结点为左右结点，建立新的子树 4. 将新结点放入排序集合中。 5. 重复上面4步，直到排序集合中只剩最后一个结点，哈夫曼树构建完成。

堆树

什么是堆树

堆树是一颗特殊的二叉树。 1. 首先它是一颗完全二叉树 2. 其每一个结点的值都大小等于左右子节点（大顶堆）或者小于等于左右子结点（小顶堆）

堆树示意图

堆树的插入删除(以数组A存储大顶堆为例)

插入

从下到上

1. 将期望结点插入到堆树的末尾，数组扩展一个位置。A[len] = 50

2. 插入结点和其父结点比较，如果比父结点大交互位置，否则不用变

len = 2*i + 1 父结点位置pos = (len - 1) / 2 比较交换位置： A[pos] > A[len] ? 不动：交换位置 A[pos] = 50; A[len] = 20; len = pos;

3. 交换后再与交换后的父结点比较，直到不能交换为止。

继续与父节点比较 len = 2*i + 1 父结点位置pos = (len - 1) / 2 比较交换位置： A[pos] > A[len] ? 不动：交换位置 A[pos] = 50; A[len] = 40; len = pos;