Python3数据结构07 - 树、3种存储结构、二叉树

  • 原创
  • Madman
  • /
  • 2018-09-08 13:52
  • /
  • 0
  • 146 次阅读

Synopsis: 本文主要讲述了树这种数据结构是如何构成的,它的一些术语,比如根节点、父节点、子节点等。树的用途很广,比如HTML、文件系统的目录结构都是树的数据结构。重点讲述了,如何存储和表示一个普通的树、二叉树

代码已上传到 https://github.com/wangy8961/python3-algorithms ,欢迎star

1. 树

树(tree)是一种抽象数据类型(ADT),用来模拟具有树状结构性质的数据集合。它是由n(n>0)个有限节点组成一个具有层次关系的集合,把它叫做 "树" 是因为它看起来像一棵倒挂的树,也就是说它是根朝上,而叶朝下的。它具有以下的特点:

  • 每个节点有零个或多个子节点
  • 没有父节点的节点称为根节点
  • 每一个非根节点有且只有一个父节点
  • 除了根节点外,每个子节点可以分为多个不相交的子树

1.1 术语

参考 https://en.wikipedia.org/wiki/Tree_(data_structure)

  • 子节点(Child): 一个节点含有的子树根节点称为该节点的子节点。比如上图中,节点B往下也是一棵树,这个子树的根节点就是B,所以节点B是节点A的子节点(该子树是节点A的左子树);同理,节点C也是节点A的子节点
  • 父节点或双亲(Parent): 若一个节点含有子节点,则这个节点被称为其子节点的父节点。比如上图中,节点A就是节点B或节点C的父节点
  • 兄弟节点(Siblings): 具有相同父节点的节点互称为兄弟节点。比如上图中,节点B和节点C的父节点都是A,所以他俩是兄弟节点
  • 节点的层次(Level): 从根节点开始算起,根为第1层,根的子节点为第2层,以此类推
  • 堂兄弟节点父节点在同一层的节点互为堂兄弟。比如上图中,节点F的父节点是B,节点G的父节点是C,他俩的父节点在同一层,所以节点F和G是堂兄弟
  • 节点的祖先(Ancestor): 从根到该节点所经分支上的所有节点。比如上图中,节点K的祖先是A、B、D、I
  • 节点的子孙(Descendant): 以该节点为根的子树中任一节点都称为该节点的子孙。比如上图中,节点B的子孙是D、E、F、I、J、K
  • 节点的度(Degree): 一个节点含有的子树的个数称为该节点的度。比如上图中,节点A的度是2,节点B的度是3,节点K的度是0
  • 叶节点(Leaf node): 度为零的节点。比如上图中,节点K、J、F、L、O、P都是叶节点
  • 分支节点(Branch node): 度不为零的节点
  • 树的度: 一棵树中,最大的节点的度称为树的度。比如上图中,节点B的度为3,它是所有节点中度最大的,所以树的度是3
  • 节点的深度(Depth of node): 对于任意节点,它的深度为从根节点到它的唯一路径长。比如上图中,节点B的深度为1,节点K的深度为4,节点A的深度为0(根节点深度为0
  • 节点的高度(Height of node): 对于任意节点,它的高度为从它到叶节点最长路径长。比如上图中,节点B到叶节点K的路径长为3,到叶节点J的路径长为2,到叶节点F的路径长为1,所以节点B的高度为3; 叶节点高度都为0
  • 树的高度(Height of tree): 树的高度是其根节点的高度
  • 森林(Forest): 由m(m>=0)棵互不相交的的组成的集合,称为森林

1.2 树的种类

  • 无序树: 树中任意节点的子节点之间没有顺序关系,这种树称为无序树,也称为自由树
  • 有序树: 树中任意节点的子节点之间有顺序关系,这种树称为有序树
    • 二叉树: 每个节点最多含有两个子树的树称为二叉树
      • 完全二叉树: 对于一颗二叉树,假设其深度为d(d>1)。除了第d层外,其它各层的节点数目均已达最大值,且第d层所有节点从左向右连续地紧密排列,这样的二叉树被称为完全二叉树
        • 满二叉树: 所有叶节点都在最底层的完全二叉树
      • 平衡二叉树(AVL树): 当且仅当任何节点的两棵子树的高度差不大于1的二叉树
      • 排序二叉树(Binary Search Tree): 也称二叉查找树、二叉搜索树、有序二叉树
    • 霍夫曼树: 带权路径最短的二叉树称为哈夫曼树或最优二叉树
    • B树: 一种对读写操作进行优化的自平衡的二叉查找树,能够保持数据有序,拥有多于两个子树

1.3 树的应用场景

  • 文件系统的目录结构、网站的多级菜单
  • XML、HTML
  • 路由协议
  • MySQL数据库索引
  • 很多经典的AI算法其实都是树搜索,此外机器学习中的decision tree也是树结构

1.4 树的存储与表示

前几篇博客我们讲了顺序表链表存储结构,对于这种可能有多个孩子节点的数据结构时,很难只单独用顺序表或链表来表示树中节点的关系。但是,我们可以将二者结合,就产生了三种树的存储结构表示法:双亲表示法孩子表示法孩子兄弟表示法

(1) 双亲表示法

因为中除了根节点以外,其余每个节点,它不一定有子节点,但是一定有且仅有一个双亲节点,所以我们可以使用指向双亲节点的指针(parent)来表示树中节点的关系

双亲表示法是以一组连续空间存储树的节点,同时在每个节点中,设置一个指针,指向其双亲节点(即父节点)在数组中的位置(即下标)。注意: 由于根节点没有双亲节点,所以我们约定根节点的parent值为-1

优缺点分析:

  • 优点: 根据节点的parent指针可以快速找到它的双亲节点,时间复杂度为O(1)
  • 缺点: 要查找某个节点的所有子节点,需要遍历整棵树,时间复杂度为O(n)

(2) 孩子表示法

一个节点可能有多个子节点,如果在每个节点中,为它的每个孩子设置一个指针的话,也可以表示树中节点的关系

孩子表示法 01

子节点的个数是节点的度,而树的度是各个节点的度的最大值,所以我们可以让每个节点的指针域的个数等于树的度。比如下图中,树的度是3,则每个节点的指针域个数也为3,没有子节点需要指向的话,就设置该指针域为null

孩子表示法 02

这种方法对于树中各节点的度相差很大时,显然是很浪费空间的,因为有很多的节点,它的指针域都是空的。不过如果树的各节点度相差很小时,那就意味着开辟的空间被充分利用了,这时存储结构的缺点反而变成了优点

既然很多指针域都可能为空,为什么不按需分配空间呢?所以,我们可以专门取一个位置来存储节点指针域的个数,每个节点的指针域的个数等于该节点的度

孩子表示法 03

这种方法克服了浪费空间的缺点,对空间利用率是很高了,但是由于各个节点的链表是不相同的结构,加上要维护节点的度的数值,在运算上就会带来时间上的损耗

能否有更好的方法,既可以减少空指针的浪费又能使节点结构相同?仔细观察,我们为了要遍历整棵树,把每个节点放到一个顺序存储结构的数组中是合理的,但每个节点的孩子有多少是不确定的,所以我们再对每个节点的孩子建立一个单链表体现它们的关系

孩子表示法是把每个节点的孩子节点排列起来,以单链表作存储结构,则n个节点有n个孩子链表,如果是叶子节点则此单链表为空。然后n个头指针又组成一个线性表,采用顺序存储结构,存放进一个一维数组中

孩子表示法 04

优缺点分析:

  • 优点: 要查找某个节点的所有子节点,或者找它的兄弟节点,只需要查找这个节点的孩子单链表即可
  • 缺点: 要查找某个节点的父节点,需要遍历整棵树

(3) 孩子兄弟表示法

除了从双亲和孩子的角度研究树的存储结构外,我们还可以从孩子和兄弟的角度来确定节点间的关系。任意一个节点,如果它的第一个孩子节点存在的话,肯定是唯一的;同时,如果节点的右兄弟如果存在的话,也肯定是唯一的。因此,我们设置两个指针,分别指向该节点的第一个孩子和此节点的右兄弟

孩子兄弟表示法 01

优缺点分析:

  • 优点: 要查找节点的某个子节点,只需要通过firstchild找到此节点的长子,然后再通过长子节点的rightsib找到它的二弟,接着一直下去,直到找到具体的孩子
  • 缺点: 要查找某个节点的父节点,可能需要遍历整棵树

另外,这个表示法的最大好处是它把一棵复杂的树变成了一棵二叉树:

孩子兄弟表示法 02

这样就可以充分利用二叉树的特性和算法来处理这棵树了

2. 二叉树

二叉树(Binary tree)是每个节点最多只有两个分支(即不存在分支大于2的节点)的树结构。通常分支被称作左子树右子树二叉树的分支具有左右次序,不能随意颠倒

2.1 二叉树的性质

  1. 在二叉树的第 i 层上最多有 2i 个节点(i >= 1)
  2. 深度为 k 的二叉树最多有 2k - 1 个节点(k >= 1)
  3. 对任意一棵二叉树,如果它的叶节点(度为0)数量为 n0,度为2的节点数量为 n2,则 n0 = n2 + 1
  4. 具有 n 个节点的完全二叉树的深度 k <= log2n + 1
  5. 具有 n 个节点的完全二叉树,节点按从上至下、从左至右编号,则编号为 i 的节点,其左孩子的编号必为 2i,其右孩子的编号必为 2i+1;其双亲节点的编号必为小于或等于 i/2 的最大整数 (i = 1除外,因为根节点没有双亲节点)

2.2 特殊二叉树

(1) 斜树

斜树

所有的节点都只有左子树的二叉树叫左斜树,所有的节点都只有右子树的二叉树叫右斜树,这两者统称斜树

(2) 满二叉树

满二叉树

除了叶节点以外,其它节点都存在左子树和右子树;并且所有叶节点都在最后一层上,这样的二叉树称为满二叉树

(3) 完全二叉树

完全二叉树

除了最后一层以外,其它各层的节点数都达到最大数目;并且,如果最后一层有叶节点,则叶节点必须从左至右依次排列(不能有空档),这样的二叉树称为完全二叉树

2.3 二叉树的存储结构

(1) 顺序存储

顺序存储结构非常适合完全二叉树

用一维数组存储完全二叉树中的节点,并且节点的存储位置(下标)可以体现节点之间的逻辑关系,假设某个节点的下标为i,则它的左孩子下标为2i + 1,它的右孩子下标为2i + 2,它的双亲节点的下标为小于或等于 i - 1 / 2 的最大整数

顺序存储 01

那么对于一般的二叉树呢?我们可以用虚拟的空节点补齐,将它当作完全二叉树一样存储,只是把不存在的节点设置为null即可:

顺序存储 02

但是,对于普通的二叉树,有一个极端的情形,假设深度为 k 的右斜树,它只有 k 个节点,但按照上面的存储方式的话,则要分配 2k - 1 个连续存储单元空间,绝大部分空间是空的,极大的浪费内存。所以,顺序存储结构一般只用于完全二叉树

(2) 二叉链表

二叉树的每个节点最多只有两个孩子,所以可以为它设计一个数据域和两个指针域(分别指向左、右孩子节点),我们称这样的链表为二叉链表

二叉链表

2.4 遍历二叉树

  • 前序遍历: 根节点、左子树、右子树
  • 中序遍历: 左子树、根节点、右子树
  • 后序遍历: 左子树、右子树、根节点

2.5 从遍历序列反推二叉树

二叉树遍历的性质:

  • 已知中序遍历序列和前序遍历序列,可以唯一确定一棵二叉树
  • 已知中序遍历序列和后序遍历序列,可以唯一确定一棵二叉树

必须给出中序遍历和前序或者后序,先通过前序或者后序确定根节点是哪个,再通过中序遍历确定根节点的左子树、右子树。依次类推,每次通过前序或者后序来确定左(右)子树的根节点,再通过中序来确定这个节点的左子树和右子树

比如,已知一棵二叉树的前序遍历序列为 ABCDEF,中序遍历序列为 CBAEDF,请问这棵二叉树的后序遍历序列是多少?

  1. 根据前序遍历序列,知道 A 是根节点
  2. 根据中序遍历序列,以 A 划分左、右,则 CB 在 A 的左子树中(目前顺序未知),EDF 在 A 的右子树中(目前顺序未知)
  3. 根据前序遍历序列中的 BC,知道该子树中 B 是根节点,C 到底是左孩子还是右孩子暂时未知
  4. 根据中序遍历序列中的 CB,知道 C 是 B 的左孩子
  5. 同理,处理 EDF,根据前序遍历序列中的 DEF,知道该子树中 D 是根节点
  6. 根据中序遍历序列中的 EDF,知道 E 是 D 的左孩子,F 是 D的右孩子

反推二叉树

所以,最终得到的二叉树如上图所示,为了避免推导失误,需要再根据图示推导出它的前序和中序,如果与题目一致,则说明我们画的二叉树是正确的。复原了二叉树,那它的后序遍历为: CBEFDA

代码已上传到 https://github.com/wangy8961/python3-algorithms ,欢迎star

未经允许不得转载: LIFE & SHARE - 王颜公子 » Python3数据结构07 - 树、3种存储结构、二叉树

分享

作者

作者头像

Madman

如果博文内容有误或其它任何问题,欢迎留言评论,我会尽快回复; 或者通过QQ、微信等联系我

0 条评论

暂时还没有评论.

发表评论前请先登录