树

• n个节点组成的有限集合
• 树中有一个称为根的特殊节点
• 其余节点可分为m个互不相交的有限集,每个集合又是一棵树,称为"子树"

二叉搜索树 二叉排序树 二叉查找树

二叉搜索树（BST，Binary Search Tree）
一棵二叉树，可以为空；如果不为空，满足以下性质：

• 非空左子树的所有键值小于其根结点的键值
• 非空右子树的所有键值大于其根结点的键值。
• 左、右子树都是二叉搜索树。

平衡二叉树

平衡二叉树（Balanced Binary Tree）（AVL树）

• 全称 平衡二叉搜索树
• 平衡因子（Balance Factor，简称BF: BF(T) = hL-hR， 其中hL和hR分别为T的左、右子树的高度
• 空树，或者任一结点左、右子树高度差的绝对值不超过1，即|BF(T) |≤ 1

堆

• 结构性:用数组表示的完全二叉树
• 有序性:任一结点的关键字是其子树所有结点的最大值,最大堆,反过来是最小堆
• 创建:使用数组存储,第一个元素使用最大值做哨兵(其实只是创建了一个堆顶元素)
• 插入:从数组最后,每次比i/2元素大就继续相上替换
• 删除:删除最大堆顶元素,把最后一个节点放到堆顶,开始向下比较,每次把较大的移上来(删除的堆顶)

• 建立(把已经存在的N个元素放在一个"堆数组"中,形成堆)
  https://www.jianshu.com/p/21bef3fc3030

  1. O(N*logN) 方法1:把N个元素逐个插入到最大堆
  2. O(N) 方法2: 先把序列按完全二叉树存放,然后从该完全二叉树中的最后一个非叶子节点为根节点的子树进行调整，然后依次去找倒数第二个倒数第三个非叶子节点,每次都是调整根节点,就像删除操作时候,把最后元素放在堆顶,然后进行下沉,当把所有元素调整完

哈夫曼树

• 也称为 最优二叉树
• WPL(带权路径长度),每个节点带有权值W,从根节点到叶子节点长度I,则带权路径长度和就是从根节点到叶子,所有的W*I之和
• 没有度为1的节点
• n个叶子的哈夫曼树共有2n-1节点
• 哈夫曼树的任意叶子节点的左右子树交换后仍然是哈夫曼树
• 对一组权重 1 2 3 3 序列,存在不同构的多个哈夫曼树
• 初始化:O(n*logn)
• 初始化一个最小堆
• 创建一个"根节点"
• 从最小堆取出两次最小值作为这个节点的左右
• 这个"根节点"的权重是两个叶子节点权重之和
• 把这个"根节点"重新放回到最小堆中
• 重复上述过程

前驱节点

这个节点在中序遍历序列中的上一个节点

后继节点

这个节点在中序遍历序列中的下一个节点

删除算法

• 要删除的是叶结点：直接删除，并再修改其父结点指针---置为NULL
• 要删除的结点只有一个孩子结点:将其父结点的指针指向要删除结点的孩子结点
• 要删除的结点有左、右两棵子树：1. 用另一结点替代被删除结点：右子树的最小元素 或 左子树的最大元素 2. 重新使用删除算法删除 刚刚那个 右子树的最小元素 或 左子树的最大元素 节点

前缀树 字典树

https://www.cnblogs.com/weiyalin/p/10818207.html

二叉判定树 二叉排序树

https://www.cnblogs.com/Littlejiajia/p/13306961.html#_label6
二叉判定树是用于描述解决问题的思路,应该标明是哪种算法的判定树,例如:二分查找判定树,可以展示出查找的路径

完美二叉树 满二叉树

除最后一层无任何子节点外，每一层上的所有结点都有两个子结点的二叉树。

完全二叉树

有n个结点的二叉树，对树中结点按从上至下、从左到右顺序进行编号，编号为i（1 ≤ i ≤ n）结点与满二叉树中编号为 i 结点在二叉树中位置相同

二叉树的存储

顺序存储(例如,数组)

1. 满二叉树

   • 非根节点的父节点序号是i/2
   • 序号为i节点左孩子序号为i*2
   • 序号为i节点右孩子序号为i*2+1
2. 一般二叉树
   会造成空间浪费

链表存储

树的表示

• 儿子-兄弟表示法
  普通的树结构也可以通过这个方法转为二叉树

最后更新于 2021-07-30 11:04:38 并被添加「」标签，已有 727 位童鞋阅读过。