树的基础概念
- 树的基本概念 由N个节点（N>=0）构成的集合
- 有一个特殊的节点，称为根节点，根节点没有前驱节点
- 除过根节点外，其余节点别分成M个（M>0）个互不相交 的集合T1、T2…Tn,其中每一个集合又是一棵与树结构类 似的子树
- 树是递归定义的
- 名词解释 | 名称 | 含义 | | :—- | :—- | | 结点 | 结点包括一个数据元素及若干指向其他子树的分支（指 针（索引）） | | 结点的度 | 结点所拥有的的子树的个数 | | 度为0的结点 | 又称终端节点 | | 分支结点 | 度不为零的结点 非终端结点 | | 祖先结点 | 从根结点到该结点所经分支上的所有结点 | | 子孙结点 | 以某结点为根结点的子树中的所有结点 | | 双亲结点 | 树中某结点有孩子节点，该结点称为它孩子节点的双亲结 点 | | 孩子结点 | 树中一个结点的子树的根结点称为该结点的孩子结点 | | 兄弟结点 | 具有相同双亲结点的结点 | | 树的度 | 树中所有结点的度的最大值 | | 结点的层次 | 从根结点到树中某结点所经路径上的分支数 | | 树的深度 | 树中所有结点的层次的最大值 | | 有序树 | 树中结点的各棵子树T0,T1…是有序的 | | 无序树 | 树中结点的各棵子树之间的次序不重要，可以相互交换位 置 | | 森林 | 树m棵树的集合 |
- 树的存储结构
- 双亲表示法 用指针表示出每个结点的双亲结点
- 优点 寻找一个结点的双亲结点操作实现很方便
- 缺点 寻找一个结点的孩子结点很不方便
- 孩子表示法 用指针指出每个结点的孩子结点
- 优点 寻找一个结点的孩子结点比较方便
- 缺点 寻找一个结点的双亲结点很不方便
- 双亲表示法 用指针表示出每个结点的双亲结点
- 双亲孩子表示法
用指针既表示出每个结点的双亲结点，也表示出每个结点 的孩子结点
- 孩子兄弟表示法
表示出第一个结点的第一个孩子结点，也表示出每个结点 的下一个兄弟结点
- 树的应用 电脑的目录
二叉树
- 概念 一棵二叉树是结点的一个有限集合，该集合或者为空，或 者是由一个根节点加上两棵分别称为左子树和右子树的二 叉树组成
特点
每个结点最多有两棵子树
二叉树的子树有左右之分，其次序不能颠倒
满二叉树 所有分支结点都存在左子树和右子树，并且所有叶子结点 都在同一层上
- 完全二叉树
如果一棵具有N个结点的二叉树的结构与满二叉树的前N 个节点的结构相同，称为完全二叉树
- 二叉树的性质、
- 若规定根节点的层次为1，则一棵非空二叉树第i层上最多 有2^（i-1）（i>=1）个结点
- 若规定只有根节点的二叉树的深度为1，则深度为K的二 叉树的最大结点数是2^k-1(k>=0)
- 对任何一棵二叉树，如果其叶结点个数为n0，度为2的非 叶结点个数为n2,则有n0=n2+1
- 具有n个结点的完全二叉树，如果按照从上至下从左到右 的顺序对所有结点从0开始编号，则对于序号为i的结点 有：
- 如果i>0,则序号为i的结点的双亲结点的序号为（i-1）/2, 如果i==0，则序号为i的结点为根节点，无双亲结点
- 如果2i+1
- 如果2i+2
- 二叉树的存储结构
- 顺序存储
- 优点、 存储完全二叉树，简单省空间
- 缺点 对一般二叉树尤其单支树，存储空间利用不理想
- 链式存储
- 顺序存储
- 二叉树的基本操作
- 二叉树的创建
- 二叉树的遍历
- 前序
- 中序
- 后序
- 层序
- 初始化一个队列
- 把根节点的指针入队列
- 当队列非空时循环执行
- 出队列取一个节点
- 若该结点的左子树非空，将该节点的左子树指针入队列
- 若该节点的右子树非空将该节点的右子树入队列
- 结束
二叉搜索树
- 性质
- 如果左子树不为空，则左子树上所有节点的值都小于根结 点的值
- 它的右子树不为空，则右子树上所有节点的值都大于根结 点的值
- 它的左右子树也分别为二叉搜索树
- 操作
- 搜索 若根结点不为空
- 根结点key==要查找的key，返回true
- 根结点key>查找key，在其左子树查找
- 根结点key<查找key，在其右子树查找
- 否则返回false
- 插入
- 首先检测这个节点是不是已经存在，要是存在不插入
- 否则将元素插入到找到的位置
- 删除
- 首先判断是否在树中，没有直接返回
- 有的情况v
- 要删除的节点没有孩子节点 直接删除该结点
- 要删除的节点只有左孩子
删除该结点并使被删除结点的双亲结点指向被删除结点的 左孩子结点 - 要删除的节点只有右孩子
删除该结点并使被删除结点的双亲结点指向被删除结点的 右孩子结点 - 要删除的节点有左、右孩子结点
在它的右子树中寻找中序下的第一个结点（关键码最
小），用它的值填补到被删除节点中，再来处理该结点的 删除问题
- 二叉搜索树性能分析
最坏情况下，平均查找长度为O(n)一般情况下平均长度 为O(lgn)
AVL树
- AVL树性质
- 它的左右子树都是AVL树
- 左子树和右子树高度之差（简称平衡因子）的绝对值不超 过1（-1、0、1）
- 如果一棵树是高度平衡的，它就是AVL树。如果它有n个 节点，其高度可保持在0(lgn)，平均搜索复杂度O(lgn)
- 平衡化旋转
- 左单旋
- 右单旋
- 左右双旋
- 右左双旋
- AVL树的插入
- 如果是空树，插入后即为根结点，插入后直接返回true
- 如果树不空，寻找插入位置，若在查找过程中找到key， 则插入失败直接返回false
- 插入节点
- 更新平衡因子，对树进行调整
- AVL树的删除
- 被删除结点只有左孩子
parent的平衡因子为1或者-1，parent高度不变，则从 parent到根所有结点高度均不变，不用调整 - 被删除结点只有右孩子
parent的平衡因子变成0，虽然以parent为根的子树平
衡，其高度减1，但需要检查parent的双亲结点的平衡性 - 被删除结点左右孩子都有 变为删除中序遍历下的第一个结点q
结点parent的平衡因子为2或者-2，则较矮子数缩短， parent发生不平衡，需要进行平衡化旋转 - parent较高子树的根为q
- 如果q的平衡因子为0，执行单循环恢复parent
- 如果q的平衡因子与parent平衡因子（正负）号相同，则 执行一个单循环恢复parent
- 如果q的平衡因子与parent平衡因子（正负）号相反，则 执行一个双旋转恢复parent
- 被删除结点只有左孩子
红黑树
- 概念
红黑树是一棵二叉搜索树，它在每个节点上增加了一个存 储位来表示结点的颜色，保证最长路径不超过最短路径的 两倍，近似平衡 - 性质
- 每个结点不是红色就是黑色
- 树的根结点是黑色
- 如果一个结点是红色的，则它的两个孩子结点是黑色的（没有连续的两个红色结点）
- 对于每个节点，从该结点到其所有后代叶节点的简单路径上，均包含相同数目的黑色结点（每条路径上黑色结点的 数量相等）
- 每个叶子节点都是黑色的（此处的叶子结点指的是空节点）
- 插入实现
- 若树为空，插入后需将新节点改成黑色
- 插入结点的父节点为黑色，不违反任何性质，直接插入
- 红黑树和AVL树的比较
- 二叉搜索树没有自平衡的机制:
向二叉搜索树中依次插入（1，2，3，4，5，6）,二叉搜索树退化成了链表.
- 二叉搜索树没有自平衡的机制:
- 平衡二叉树的定义过于严格
平衡二叉树的定义过于严格，导致每次插入或者删除一个元素之后，都要去维护二叉树整体的平衡，这样产生额外的代价又太大了 - 红黑树保证最长路径不超过最短路径的二倍，因而近似平衡。
B树
- 平衡的多叉树
- 性质
- 根结点至少有两个孩子
- 每个非根结点至少有M/2（上取整）个孩子，至多有M个 孩子
- 每个非根结点至少有M/2-1（上取整）个关键字，并且以 升序排列
- key[i]和key[i+1]之间的孩子结点的值介于key[i]、key[i+1] 之间
- 所有的叶子结点都在同一层
- B+树
- 性质
- 其定义基本与B树相同
- 非叶子节点的子树指针与关键字个数相同
- 非叶子结点的子树指针P[i]，指向关键字值属于[k[i],k[i+ 1])的子树
- 为所有叶子节点增加一个链指针
- 所有关键字都在叶子节点出现
- 搜索 和B树基本相同
- 特性
- 所有关键字都出现在叶子节点的链表中（稠密索引），且 链表中的关键字恰好是有序的
- 不可能在叶子结点命中
- 非叶子节点相当于是叶子结点的索引（稀疏索引），叶子 结点相当于是存储（关键字）数据的数据层
- 更适合文件索引系统
- 性质
- B*树
- 在B+树的非根和非叶子结点之间再增加指向兄弟的指针
Huffman树（最优二叉树）
- 概念
- 路径
- 路径长度
- 把带权路径长度最小的树叫做Huffman树
- 构造huffman树
- 构造n棵只有根结点的二叉树森林，每棵二叉树都只有一 个带有权值的根结点
- 重复以下步骤，直到F中只剩下一棵树
- 在二叉树森林中选最小的两个，作为左右子树构建一棵新 的二叉树，新二叉树的根结点的权值为左右子树根结点的 权值之和
- 在原来二叉树森林里删除这两棵二叉树
- 把新的二叉树加入二叉树森林
- huffman编码 编码
- 在数据通信中经常把传输的文字转换成二进制字符0和1组 成的二进制串，这叫做编码
- 等长编码
- 不等长编码
- 文件压缩
若有收获，就点个赞吧
0 人点赞
