数据结构(十一)之树结构

如需转载, 请咨询作者, 并且注明出处.
有任何问题, 可以关注我的微博: coderwhy, 或者添加我的微信: 372623326

树也是一种非常常用的数据结构, 特别是二叉树.

二叉树是程序中一种非常重要的数据结构, 它的优势是前面介绍的数据结构所没有的.

一. 树的概念

我们先来简单的认识一些关于树的概念, 再来认识特殊的二叉树以及它的相关编码工作.

树是什么?

• 真实的树:

  • 相信每个人对现实生活中的树都会非常熟悉

    img

  • 我们来看一下树有什么特点?

    • 树通常有一个根. 连接着根的是树干.
    • 树干到上面之后会进行分叉成树枝, 树枝还会分叉成更小的树枝.
    • 在树枝的最后是叶子.

  • 树的抽象:

    • 专家们对树的结构进行了抽象, 发现树可以模拟生活中的很多场景.

• 模拟树结构

  • 公司组织架构:

    img

  • 红楼梦家谱

    img

• 我们再将里面的数据移除, 仅仅抽象出来结构, 那么就是我们要学习的树结构

  img

树的优点

• 我们之前已经学习了多种数据结构来保存数据, 为什么要使用树结构来保存数据呢?
  • 树结构和数组/链表/哈希表的对比有什么优点呢?
• 数组:
  • 优点:
    • 数组的主要优点是根据下标值访问效率会很高.
    • 但是如果我们希望根据元素来查找对应的位置呢?
    • 比较好的方式是先对数组进行排序, 再进行二分查找.
  • 缺点:
    • 需要先对数组进行排序, 生成有序数组, 才能提高查找效率.
    • 另外数组在插入和删除数据时, 需要有大量的位移操作(插入到首位或者中间位置的时候), 效率很低.
• 链表:
  • 优点:
    • 链表的插入和删除操作效率都很高.
  • 缺点:
    • 查找效率很低, 需要从头开始依次访问链表中的每个数据项, 直到找到.
    • 而且即使插入和删除操作效率很高, 但是如果要插入和删除中间位置的数据, 还是需要重头先找到对应的数据.
• 哈希表:
  • 优点:
    • 我们学过哈希表后, 已经发现了哈希表的插入/查询/删除效率都是非常高的
    • 但是哈希表也有很多缺点.
  • 缺点:
    • 空间利用率不高, 底层使用的是数组, 并且某些单元是没有被利用的.
    • 哈希表中的元素是无序的, 不能按照固定的顺序来遍历哈希表中的元素.
    • 不能快速的找出哈希表中的最大值或者最小值这些特殊的值.
• 树结构:
  • 我们不能说树结构比其他结构都要好, 因为每种数据结构都有自己特定的应用场景.
  • 但是树确实也综合了上面的数据结构的优点(当然优点不足于盖过其他数据结构, 比如效率一般情况下没有哈希表高), 并且也弥补了上面数据结构的缺点.
  • 而且为了模拟某些场景, 我们使用树结构会更加方便. 比如文件的目录结构.

树的术语

• 在描述树的各个部分的时候有很多术语.

  • 为了让介绍的内容更容易理解, 需要知道一些树的术语.
  • 不过大部分术语都与真实世界的树相关, 或者和家庭关系相关(如父节点和子节点), 所以它们比较容易理解.

• 我们先来看一下树的结构

  img

• 树的定义:

  • 树（Tree）: n（n≥0）个结点构成的有限集合。
    • 当n=0时，称为空树；
    • 对于任一棵非空树（n> 0），它具备以下性质：
    • 树中有一个称为“根（Root）”的特殊结点，用 r 表示；
    • 其余结点可分为m(m>0)个互不相交的有限集T1，T2，... ，Tm，其中每个集合本身又是一棵树，称为原来树的“子树（SubTree）”
  • 注意:
    • 子树之间不可以相交
    • 除了根结点外，每个结点有且仅有一个父结点；
    • 一棵N个结点的树有N-1条边。

• 树的术语:

  • 1.结点的度（Degree）：结点的子树个数.
  • 2.树的度：树的所有结点中最大的度数. (树的度通常为结点的个数N-1)
  • 3.叶结点（Leaf）：度为0的结点. (也称为叶子结点)
  • 4.父结点（Parent）：有子树的结点是其子树的根结点的父结点
  • 5.子结点（Child）：若A结点是B结点的父结点，则称B结点是A结点的子结点；子结点也称孩子结点。
  • 6.兄弟结点（Sibling）：具有同一父结点的各结点彼此是兄弟结点。
  • 7.路径和路径长度：从结点n1到nk的路径为一个结点序列n1 , n2,… , nk, ni是 ni+1的父结点。路径所包含边的个数为路径的长度。
  • 8.结点的层次（Level）：规定根结点在1层，其它任一结点的层数是其父结点的层数加1。
  • 9.树的深度（Depth）：树中所有结点中的最大层次是这棵树的深度。

树的表示

• 树可以有多种表示的方式.

• 最普通的表示方式:

  img

• 儿子-兄弟表示法

  img

• 儿子-兄弟表示法旋转

  img

• 你发现上面规律了吗?

  • 其实所有的树本质上都可以使用二叉树模拟出来.
  • 所以在学习树的过程中, 二叉树非常重要.

二. 二叉树

如果树中每个节点最多只能有两个子节点, 这样的树就成为"二叉树".

前面, 我们已经提过二叉树的重要性, 不仅仅是因为简单, 也因为几乎上所有的树都可以表示成二叉树的形式.

二叉树的概念

• 二叉树的定义

  • 二叉树可以为空, 也就是没有结点.
  • 若不为空，则它是由根结点和称为其左子树TL和右子树TR的两个不相交的二叉树组成。

• 二叉树有五种形态:

  • 注意c和d是不同的二叉树, 因为二叉树是有左右之分的.
  img

二叉树的特性

• 二叉树有几个比较重要的特性, 在笔试题中比较常见:

  • 一个二叉树第 i 层的最大结点数为：2^(i-1), i >= 1;

  • 深度为k的二叉树有最大结点总数为： 2^k - 1, k >= 1;

  • 对任何非空二叉树 T，若n0表示叶结点的个数、n2是度为2的非叶结点个数，那么两者满足关系n0 = n2 + 1。

    img

特殊的二叉树

• 完美二叉树(Perfect Binary Tree) , 也称为满二叉树(Full Binary Tree）

  • 在二叉树中, 除了最下一层的叶结点外, 每层节点都有2个子结点, 就构成了满二叉树.
  img

• 完全二叉树(Complete Binary Tree)

  • 除二叉树最后一层外, 其他各层的节点数都达到最大个数.
  • 且最后一层从左向右的叶结点连续存在, 只缺右侧若干节点.
  • 完美二叉树是特殊的完全二叉树.

• 下面不是完全二叉树, 因为D节点还没有右结点, 但是E节点就有了左右节点.

  img

二叉树的存储

• 二叉树的存储常见的方式是数组和链表.

• 使用数组存储:

  • 完全二叉树: 按从上至下、从左到右顺序存储

    img

  • 非完全二叉树:

    • 非完全二叉树要转成完全二叉树才可以按照上面的方案存储.
    • 但是会造成很大的空间浪费
    img

• 链表存储:

  • 二叉树最常见的方式还是使用链表存储.
  • 每个结点封装成一个Node, Node中包含存储的数据, 左结点的引用, 右结点的引用.
  img