[What]数据结构与算法 -> 二叉树

课程:王争 –> <数据结构与算法之美>

理解树与二叉树。

概念

tree.jpg

上面便是一个树,与现实的树很类似:

  • 每个元素称为一个 节点 ,节点之间的连线组成 父子关系
    • 比如A是B的父节点,是E的子节点
  • 没有父节点的节点就是 根节点 , 没有子节点的节点就是 叶子节点
  • 节点的高度 : 节点到叶子节点的 最长路径(边数)
    • 比如A节点的高度就是2
  • 节点的深度 : 根节点 到此节点的 边数
    • 比如C节点的深度就是2
  • 节点的层数 : 根节点 到此节点的 节点个数 (节点深度 + 1)
    • 比如C节点的层数就是3
  • 树的高度 : 根节点 到叶子节点的 最长边数
    • 比如此树高度为3

二叉树

binary_tree_overview.jpg

二叉树是相对上图的一个特例:

  • 每个节点 最多 有两个叶子节点,称为 左子节点右子节点
  • 当二叉树中除了叶子节点之外的所有节点都有两个节点且左右层数相等时,就是 满二叉树
  • 当满二叉树的最后一层叶子节点靠左排列,且左边不要求子节点完整,就是 完全二叉树
    • 最后一层左边的节点要集中向左排列

二叉树的存储

链式存储

binary_tree_link_save.jpg

链式存储在逻辑上更易理解和扩展,但由于其内存的分散性而无法很好的利用cache line.

数组存储

binary_tree_array_save.jpg

存储规则为:

  • 将根节点放在下标为1的位置
  • 左子节点的位置 = 父节点下标 * 2
    • 比如 B = 2 * 1
  • 右子节点的位置 = 父节点下标 * 2 + 1
    • 比如 C = 2 * 1 + 1
  • 当前节点求父节点 = 当前节点下标 / 2

只要有上述规则,那么通过父节点找到其左右子节点或者是通过子节点找到父节点通过数组索引换算即可。

数组存储的方式其查找效率很高能很好的利用cache line,但也有下述不足:

  • 当为 非完全二叉树 时,会浪费一些内存空间。
  • 当需要增加或删除节点时,数组需要动态扩容或缩容

完全二叉树和满二叉树,都只浪费下表为0的位置,这也是完全二叉树名字的由来

如下为完全二叉树存储:

binary_tree_array_complete.jpg

如下为非完全二叉树,可以看到浪费了不少的组数空间,其实这种情况下,cache line的效果也不强了。

binary_tree_array_uncomplete.jpg

二叉树的遍历

二叉树的遍历,指的是遍历节点本身与其左右子树的先后顺序。

一般有以下3种方式:

  • 前序遍历 : 节点 -> 左子树 -> 右子树
  • 中序遍历 : 左子树 -> 节点 -> 右子树
  • 后序遍历 : 左子树 -> 右子树 -> 节点
binary_tree_scan.jpg

如上图的满二叉树几种遍历方式为:

  • 前序遍历 : A -> B -> D -> E -> C -> F -> G
  • 中序遍历 : D -> B -> E -> A -> F -> C -> G
  • 后序遍历 : D -> E -> B -> F -> G -> C -> A

可以看到,这其实是一个递归的遍历方式,其递推公式如下:

  前序 : preOrder(r) = print(r) + preOrder(r->left) + preOrder(r->right) 
  中序 : inOrder(r) = preOrder(r->left) + print(r) + preOrder(r->right) 
  前序 : postOrder(r) = preOrder(r->left) + preOrder(r->right) + print(r)

时间复杂度:因为需要遍历所有节点,其时间复杂度就是O(n)

二叉查找树(Binary Search Tree)

二叉查找树的特点: 在树中的任意一个节点,其 左子树 中的每个节点的值都要小于这个节点的值,而 右子树 节点的值都要大于这个节点的值。

查找

先从根节点开始查找,如果要查找的值小于根节点就递归查找左树,如果要查找的值大于根节点就递归查找右树。

插入

从根节点开始,如果要插入的数据比节点大则将数据插到右子节点的位置,如果不为空则需要递归的判断查找位置 ,如果要插入的数据比节点小则将数据插到左子节点的位置,如果不为空则需要递归的判断查找位置

删除

  • 如果要删除的节点没有子节点,只需要将父节点中指向该节点的指针置空,并释放该节点的内存
  • 如果要删除的节点仅有一个子节点,只需要将父节点中指向该节点的指针指向子节点,并释放该节点的内存
  • 如果要删除的节点有两个子节点,需要:
    • 找到这个节点的右子树中的最小节点,替换到要删除的节点上。
    • 删除原来最小节点的位置,并释放节点内存

排序

利用 中序遍历 的方法,将此二叉树上的数据由小到大的排列起来。

当节点的 key 值相同时

这种情况下有以下两种通常的方法:

  1. 借助哈希表的思想,节点扩展为一个链表或可动态扩容的数组,相同Key值的数据放在同一链表或数组中。
  2. 将key值相同的数据当做新节点来处理:
    • 插入节点时,如果碰到key值相同的节点,将此数据插入在该节点的右树中
    • 查找节点时,如果碰到key值相同的节点,继续在右子树中查找,直到遇到叶子节点
    • 删除节点时,查到所有节点后依次删除

简易示例

位于此处

Last Updated 2019-04-15 一 20:41.
Render by hexo-renderer-org with Emacs 26.1 (Org mode 9.1.14)