数据结构-树
学习笔记 数据结构
学习笔记
 发布日期:  2019-03-23
文章字数:   7k
 阅读时长:  24 分

树(Tree)是算法中常用的一种数据结构，为了存储和查找的方便，用各种树结构来存储文件。

简介

定义

树是由 n(n>=0) 个有限节点组成一个具有层次关系的集合，它是一种非线性的数据结构。把它叫做树是因为它看起来像一棵倒挂的树，也就是说它是根朝上，而叶朝下的。

树的数据结构如下图所示：
树的数据结构

单个节点是一棵树，树根就是该节点本身。空集合也是树，称为空树。空树中没有节点。

特点

树具有以下的特点：

  • 有且仅有一个特定的称为根(root)的节点；
  • 每棵树有且只有一个根节点；
  • 每个节点都只有有限个子节点或无子节点；
  • 每一个非根节点有且只有一个父节点；
  • 树里面没有环路；
  • 除了根节点外，其余节点可分为多个互不相交的有限集，其中每一个集合本身又是一棵树，称为原树的子树(SubTree)。

术语

  • 树的度：树内各节点的度的最大值。
  • 节点的度：一个节点含有的子树的个数称为该节点的度。
  • 叶节点或终端节点：度为 0 的节点。
  • 非终端节点或分支节点：度不为 0 的节点，分支节点也称为内部节点。
  • 孩子和双亲：节点的子树的根，该节点称为孩子的双亲。
  • 父亲节点或父节点：若一个节点含有子节点，则这个节点称为其子节点的父节点。
  • 孩子节点或子节点：一个节点含有的子树的根节点称为该节点的子节点。
  • 兄弟节点：具有相同父节点的节点互称为兄弟节点。
  • 节点的层次：从根开始定义起，根为第 1 层，根的子节点为第 2 层，以此类推。
  • 树的深度或高度：树中节点的最大层次。
  • 节点的深度：从根到该节点的唯一路径长，根的深度为 0。
  • 节点的高度：为从该节点到一片树叶的最长路径长，所有树叶的高度为 0。
  • 堂兄弟节点：父节点在同一层的节点互为堂兄弟。
  • 节点的祖先：从根到该节点所经分支上的所有节点。
  • 子孙：以某节点为根的子树中任一节点都称为该节点的子孙。
  • 森林：由 m(m>=0) 棵互不相交的树的集合称为森林。

存储结构

对于存储结构，可能会联想到顺序存储结构和链式存储结构。但是对于数这种可能会有很多孩子的特殊数据结构，只用顺序存储结构或者链式存储结构很难实现，那么可以将这两者结合，产生主要的三种存储结构表示法：双亲表示法、孩子表示法、孩子兄弟表示法。

双亲表示法

双亲表示法是假设以一组连续空间存储树的节点，同时在每个节点中，附设一个指示器指示其双亲节点到链表中的位置。

除了根节点外，其余每个节点，它不一定有孩子，但是有且仅有一个双亲。

节点结构

双亲表示的节点结构：

data(数据域) parent(指针域)
存储节点的数据信息 存储该节点的双亲所在数组中的下标

代码定义

/* 树的双亲表法节点结构定义*/
#define MAX_TREE_SIZE 100
typedef int  ElemeType;

typedef struct PTNode{           // 节点结构
    ElemeType data;              // 节点数据
    int parent;                  // 双亲位置
}PTNode;

typedef struct {                 // 树结构
    PTNode nodes[MAX_TREE_SIZE]; // 节点数组
    int r;                       // 根的位置
    int n;                       // 节点数
}PTree;

特点

由于根节点是没有双亲的，约定根节点的位置域为 -1。
优点：根据节点的 parent 指针很容易找到它的双亲节点。所用时间复杂度为 O(1)，直到 parent 为 -1 时，表示找到了树节点的根。
缺点：查找孩子节点难，想要找到孩子节点，需要遍历整个结构才行。

孩子表示法

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

由于树中每个节点可能有多棵子树，因此可以使用多重链表，即每个节点包含多个指针域，其中每个指针指向一棵子树的根节点，我们把这种方法叫做多重链表表示法。不过，树的每个节点的度(节点的孩子个数)是不同的。

节点结构

孩子表示法有以下两种节点结构：

  • 孩子链表的孩子节点：
child(数据域) next(指针域)
存储某个节点在表头数组中的下标 存储指向某节点的下一个孩子节点的指针
  • 表头数组的表头节点：
data(数据域) firstchild(头指针域)
存储某个节点的数据信息 存储该节点的孩子链表的头指针

代码定义

/* 树的孩子表示法结构定义*/
#define MAX_TREE_SIZE 100
typedef int  ElemeType;

typedef struct CTNode{           // 孩子节点
    int child;                   // 孩子节点的下标
    struct CTNode * next;        // 指向下一节点的指针
}*ChildPtr;

typedef struct {                 // 表头结构
    ElemeType data;              // 节点数据
    ChildPtr firstchild;         // 指向第一个孩子的指针
}CTBox;

typedef struct {                // 树结构
    CTBox nodes[MAX_TREE_SIZE]; // 节点数组
    int r;                      // 根的位置
    int n;                      // 节点树
}CTree;

特点

优点：查找某个节点的孩子或者兄弟，只需要查找这个节点的孩子单链表即可。
缺点：查找双亲难，可以在上面的表头结构中加入节点对应的双亲所在的数组下标。

孩子兄弟表示法

孩子兄弟表示法是指任意一棵树，它的节点的第一个孩子如果存在就是唯一的，它的右兄弟如果存在也是唯一的。因此，设置两个指针，分别指向该节点的第一个孩子和此节点的右兄弟。

节点结构

孩子兄弟表示法的节点结构：

data(数据域) firstchild(指针域) rightsib(指针域)
存储节点的数据信息 存储该节点的第一个孩子的存储地址 存储该节点的右兄弟节点的存储地址

代码定义

/* 树的孩子兄弟表示法结构定义*/
#define MAX_TREE_SIZE 100
typedef int  ElemeType;

typedef struct CSNode{
    ElemeType data;              // 节点数据
    struct CSNode * firstchild;  // 指向第一个孩子的指针
    struct CSNode * rightsib;    // 指向第一个孩子的右兄弟的指针
}CSNode, *CSTree;

树的分类

数据结构中有很多树的结构，其中包括二叉树、二叉搜索树、平衡二叉树、2-3 树、红黑树等等。

二叉树

二叉树是数据结构中一种重要的数据结构，也是树表家族最为基础的结构。

定义

二叉树(Binary Tree)是一个有根树，并且每个节点最多只有2棵子树(即二叉树中不存在度大于2的结点)，并且二叉树的子树有左右之分，其次序不能任意颠倒。

二叉树的数据结构如下图所示：
二叉树的数据结构

二叉树的第 n 层至多有 2n-1 个结点；深度为 k 的二叉树至多有 2k-1 个结点；对任何一棵非空二叉树 T，如果其树叶总数为 n0，度为2的结点数为 n2，则 n0=n2+1。

性质

二叉树的性质：

  • 在非空二叉树中，第 i 层的结点总数不超过 2i-1(i>=1);
  • 深度为 k 的二叉树最多有 2k-1 个结点(k>=1)，最少有 k 个结点;
  • 对于任意一棵二叉树，如果其终端结点数为 n0，而度数为2的结点总数为 n2，则 n0=n2+1;
  • 具有 n 个结点的完全二叉树的深度为 log2(n)+1;
  • 具有 n 个结点的完全二叉树各结点如果用顺序方式存储，则对任一结点 i(1≤i≤n) 之间有如下关系：
    • 如果 i=1，则节点 i 是二叉树的根，无双亲；如果 i>1，则其双亲是节点 i/2；
    • 如果 2i>n，则节点 i 无左孩子，节点 i 是叶子节点；否则其左孩子(即左子树的根结点)是节点 2i；
    • 如果 2i+1>n，则节点 i 无右孩子；否则其其右孩子(即右子树的根结点)是节点 2i+1。
  • 给定n个节点，能构成 h(n) 种不同的二叉树，其中 h(n) 为卡特兰数的第 n 项，h(n)=C(2*n, n)/(n+1)。
  • 设有 i 个枝点，I 为所有枝点的道路长度总和，J 为叶的道路长度总和 J=I+2i。

存储结构

二叉树的顺序存储是用一组地址连续的存储单元依次自上而下、自左至右存储完全二叉树上的结点元素。对于一般二叉树，则应将其每个结点与完全二叉树上的结点相对照，存储在一维数组的相应分量中，以“0”表示不存在的结点。

在二叉树的链式存储结构中，结点至少包含3个域：数据域和左、右指针域。左、右指针分别指向其左右子树的两个分支。有时，为了便于找到结点的双亲，则还可在结点结构中增加一个指向其双亲结点的指针域。

满二叉树

满二叉树(Full Binary Tree)：除最后一层无任何子节点外，每一层上的所有结点都有两个子结点。也可以这样理解，除叶子结点外的所有结点均有两个子结点。节点数达到最大值，所有叶子结点必须在同一层上。

满二叉树的数据结构如下图所示：
满二叉树的数据结构

满二叉树的性质：

  • 一颗树深度为 h，最大层数为 k，深度与最大层数相同，k=h;
  • 叶子数为2n;
  • 第 k 层的结点数是：2k-1;
  • 总结点数是：2k-1，且总节点数一定是奇数。

完全二叉树

完全二叉树(Complete Binary Tree)是指从根结点到倒数第二层满足完美二叉树，最后一层可以不完全填充，其叶子结点都靠左对齐。

完全二叉树的数据结构如下图所示：
完全二叉树的数据结构

满二叉树和：满二叉树必定是完全二叉树，而完全二叉树不一定是满二叉树！

注：完全二叉树是效率很高的数据结构，堆是一种完全二叉树或者近似完全二叉树，所以效率极高，像十分常用的排序算法、Dijkstra算法、Prim算法等都要用堆才能优化，二叉排序树的效率也要借助平衡性来提高，而平衡性基于完全二叉树。

二叉排序树

二叉排序树(Binary Sort Tree)又称为二叉搜索树或二叉查找树(Binary Search Tree)。二叉排序树或者是一棵空树，或者是具有下列性质的二叉树：

  • 若左子树不空，则左子树上所有结点的值均小于它的根结点的值；
  • 若右子树不空，则右子树上所有结点的值均大于或等于它的根结点的值；
  • 左、右子树也分别为二叉排序树；
  • 没有键值相等的节点。

性质

二叉查找树的性质：对二叉查找树进行中序遍历，即可得到有序的数列。

时间复杂度

二叉查找树的时间复杂度：它和二分查找一样，插入和查找的时间复杂度均为 O(logn)，但是在最坏的情况下仍然会有 O(n) 的时间复杂度。原因在于插入和删除元素的时候，树没有保持平衡。我们追求的是在最坏的情况下仍然有较好的时间复杂度，这就是平衡查找树设计的初衷。

查找过程

在二叉排序树中查找给定值的过程如下：

  1. 如果二叉查找树为空，查找失败，返回 null；
  2. 如果二叉查找树的根节点的关键字与给定值相等，则查找出；
  3. 否则，继续在相应的子树中查找。如果要查找的关键字小于根节点的关键字，在左子树中查找；如果要查找的关键字大于根节点的关键字，在右子树中查找。
  4. 重复前面的三个步骤，直至查找成功或查找失败。

二叉查找树的高度决定了二叉查找树的查找效率。

插入过程

在二叉排序树中插入给定值的过程如下：

  1. 若当前二叉查找树为空，则插入的元素为根节点；
  2. 若插入的元素值小于根节点值，则递归从根节点的左子树中找到可插入位置；
  3. 若插入的元素值大于根节点值，则递归从根节点的右子树中找到可插入位置。

新插入的结点一定是一个新添加的叶子结点，并且是查找不成功时查找路径上访问的最后一个节点的左孩子或右孩子节点。

删除过程

在二叉排序树删去一个结点，分三种情况讨论：

  1. 如果删除的结点为叶子结点(即左子树和右子树均为空树)，由于删去叶子结点不破坏整棵树的结构，则可以直接删除此子结点；
  2. 如果删除的结点有一个子节点(只有左子树或右子树)，可以将子节点直接移到被删除元素的位置即可，作此修改也不破坏二叉排序树的特性；
  3. 如果删除的结点有两个子节点(左子树和右子树均不为空)，这时候就采用中序遍历，找到待删除的节点的后继节点，将其与待删除的节点互换，此时待删除节点的位置已经是叶子节点，可以直接删除。

最小值

在二叉排序树中获取最小值的过程如下：

  1. 如果根节点无左子树，则返回根节点。
  2. 依次查询跟节点的左子树节点，返回左子树的最后一个左节点。

最大值

在二叉排序树中获取最大值的过程如下：

  1. 如果根节点无右子树，则返回根节点。
  2. 依次查询根节点的右子树节点，返回右子树的最后一个右节点。

平衡二叉树

平衡二叉树(Balanced Binary Tree)又被称为 AVL 树(有别于 AVL 算法)，平衡二叉树或者是一棵空树，或者是具有下列性质的二叉树：

  • 它的左子树和右子树都是平衡二叉树；
  • 它的左子树和右子树的深度之差的绝对值不超过1。

若将二叉树节点的平衡因子BF定义为该节点的左子树的深度减去它的右子树的深度，则平衡二叉树上所有节点的平衡因子只可能为-1、0和1。只要二叉树上有一个节点的平衡因子的绝对值大于1，那么该二叉树就是不平衡的。

平衡二叉树的常用实现方法有红黑树、AVL、替罪羊树、Treap、伸展树等。在平衡二叉搜索树中，其高度一般都良好地维持在 O(log2n)，大大降低了操作的时间复杂度。

最小二叉平衡树的节点的公式如下：

F(n)=F(n-1)+F(n-2)+1

这个类似于一个递归的数列，可以参考 Fibonacci 数列，公式中 1 是根节点，F(n-1) 是左子树的节点数量，F(n-2) 是右子树的节点数量。

AVL 树

AVL 树是最先发明的自平衡二叉查找树算法。在 AVL 中任何节点的左右子树的高度最大差别为一，所以它也被称为高度平衡树，n 个结点的 AVL 树最大深度约 1.44log2n。查找、插入和删除在平均和最坏情况下都是 O(logn)。增加和删除可能需要通过一次或多次树旋转来重新平衡这个树。这个方案很好的解决了二叉查找树退化成链表的问题，把插入，查找，删除的时间复杂度最好情况和最坏情况都维持在O(logN)。但是频繁旋转会使插入和删除牺牲掉O(logN)左右的时间，不过相对二叉查找树来说，时间上稳定了很多。

AVL 树最关键的也是最难的一步操作就是旋转。旋转主要是为了实现 AVL 树在实施了插入和删除操作以后，树重新回到平衡的方法。

红黑树

红黑树是一种自平衡二叉查找树，是在计算机科学中用到的一种数据结构，典型的用途是实现关联数组。它是在1972年由 Rudolf Bayer 发明的，他称之为对称二叉B树，它现代的名字是在 Leo J. Guibas 和 Robert Sedgewick 于1978年写的一篇论文中获得的。它是复杂的，但它的操作有着良好的最坏情况运行时间，并且在实践中是高效的: 它可以在 O(logn) 时间内做查找，插入和删除，这里的 n 是树中元素的数目。

红黑树和 AVL 树一样都对插入时间、删除时间和查找时间提供了最好可能的最坏情况担保。这不只是使它们在时间敏感的应用如实时应用（real time application）中有价值，而且使它们有在提供最坏情况担保的其他数据结构中作为建造板块的价值；例如，在计算几何中使用的很多数据结构都可以基于红黑树。此外，红黑树还是2-3-4树的一种等同，它们的思想是一样的，只不过红黑树是2-3-4树用二叉树的形式表示的。

红黑树是每个节点都带有颜色属性的二叉查找树，颜色为红色或黑色。在二叉查找树强制的一般要求以外，对于任何有效的红黑树增加了如下的额外要求：

  1. 节点是红色或黑色。
  2. 根是黑色。
  3. 所有叶子都是黑色(叶子是 NIL 节点)。
  4. 每个红色节点必须有两个黑色的子节点(从每个叶子到根的所有路径上不能有两个连续的红色节点)。
  5. 从任一节点到其每个叶子的所有简单路径都包含相同数目的黑色节点。

Treap

Treap是一棵二叉排序树，它的左子树和右子树分别是一个 Treap，和一般的二叉排序树不同的是，Treap 纪录一个额外的数据，就是优先级。Treap 在以关键码构成二叉排序树的同时，还满足堆的性质(在这里假设节点的优先级大于该节点的孩子的优先级)。但是这里要注意的是 Treap 和二叉堆有一点不同，就是二叉堆必须是完全二叉树，而 Treap 并不一定是。

伸展树

伸展树(Splay Tree)是一种二叉排序树，它能在 O(logn) 内完成插入、查找和删除操作。它由 Daniel Sleator 和 Robert Tarjan 创造。它的优势在于不需要记录用于平衡树的冗余信息。在伸展树上的一般操作都基于伸展操作。

B 树

B 树(B-tree)是一种树状数据结构，能够用来存储排序后的数据。这种数据结构能够让查找数据、循序存取、插入数据及删除的动作，都在对数时间内完成。B 树，概括来说是一个一般化的二叉查找树，可以拥有多于2个子节点。与自平衡二叉查找树不同，B 树为系统最优化大块数据的读和写操作。B 树算法减少定位记录时所经历的中间过程，从而加快存取速度。这种数据结构常被应用在数据库和文件系统的实作上。

在 B 树中查找给定关键字的方法是，首先把根结点取来，在根结点所包含的关键字 K1,…,Kn 查找给定的关键字(可用顺序查找或二分查找法)，若找到等于给定值的关键字，则查找成功；否则，一定可以确定要查找的关键字在 Ki 与 Ki+1 之间，Pi 为指向子树根节点的指针，此时取指针 Pi 所指的结点继续查找，直至找到，或指针 Pi 为空时查找失败。

B树也是一种用于查找的平衡树，但是它不是二叉树。B 树作为一种多路搜索树，它或者是空树，或者是满足下列性质的树：

  • 定义任意非叶子结点最多只有 m 个儿子；且 m>2；
  • 根结点的儿子数为[2, m]；
  • 除根结点以外的非叶子结点的儿子数为[M/2, M]；
  • 每个结点存放至少m/2-1（取上整）和至多m-1个关键字；（至少2个关键字）
  • 非叶子结点的关键字个数等于指向儿子的指针个数-1；
  • 非叶子结点的关键字：K[1], K[2], …, K[M-1]；且K[i] < K[i+1]；
  • 非叶子结点的指针：P[1], P[2], …, P[M]；其中P[1]指向关键字小于K[1]的子树，P[m]指向关键字大于K[m-1]的子树，其它P[i]指向关键字属于(K[i-1], K[i])的子树；
  • 所有叶子结点位于同一层。

B+ 树

B+ 树是 B 树的变体，也是一种多路搜索树：

  • 其定义基本与 B 树相同；
  • 非叶子结点的子树指针与关键字个数相同；
  • 非叶子结点的子树指针 P[i]，指向关键字值属于 [K[i], K[i+1]) 的子树(B 树是开区间)；
  • 为所有叶子结点增加一个链指针；
  • 所有关键字都在叶子结点出现。

B+ 树的搜索与 B 树也基本相同，区别是 B+ 树只有达到叶子结点才命中(B 树可以在非叶子结点命中)，其性能也等价于在关键字全集做一次二分查找；

B+ 树的性质：

  • 所有关键字都出现在叶子结点的链表中(稠密索引)，且链表中的关键字恰好是有序的；
  • 不可能在非叶子结点命中；
  • 非叶子结点相当于是叶子结点的索引(稀疏索引)，叶子结点相当于是存储(关键字)数据的数据层；
  • 更适合文件索引系统。

B* 树

B* 树是 B+ 树的变体，在 B+ 树的非根和非叶子结点再增加指向兄弟的指针，将结点的最低利用率从1/2提高到2/3。

B 树定义了非叶子结点关键字个数至少为(2/3)m，即块的最低使用率为2/3(代替 B+ 树的1/2)；

  • B+ 树的分裂：当一个结点满时，分配一个新的结点，并将原结点中1/2的数据复制到新结点，最后在父结点中增加新结点的指针；B+ 树的分裂只影响原结点和父结点，而不会影响兄弟结点，所以它不需要指向兄弟的指针；
  • B* 树的分裂：当一个结点满时，如果它的下一个兄弟结点未满，那么将一部分数据移到兄弟结点中，再在原结点插入关键字，最后修改父结点中兄弟结点的关键字(因为兄弟结点的关键字范围改变了)；如果兄弟也满了，则在原结点与兄弟结点之间增加新结点，并各复制1/3的数据到新结点，最后在父结点增加新结点的指针。

所以，B* 树分配新结点的概率比 B+ 树要低，空间使用率更高。

Trie 树

Tire 树称为字典树，又称单词查找树。Trie 树，是一种树形结构，是一种哈希树的变种。典型应用是用于统计，排序和保存大量的字符串(但不仅限于字符串)，所以经常被搜索引擎系统用于文本词频统计。它的优点是：利用字符串的公共前缀来减少查询时间，最大限度地减少无谓的字符串比较，查询效率比哈希树高。　

Trie 树的性质：

  • 根节点不包含字符，除根节点外每一个节点都只包含一个字符；
  • 从根节点到某一节点，路径上经过的字符连接起来，为该节点对应的字符串；
  • 每个节点的所有子节点包含的字符都不相同。

Tire 树的应用：

  • 串的快速检索：给出 N 个单词组成的熟词表，以及一篇全用小写英文书写的文章，请按最早出现的顺序写出所有不在熟词表中的生词。在这道题中，可以用数组枚举，用哈希，用字典树，先把熟词建一棵树，然后读入文章进行比较，这种方法效率是比较高的。
  • “串”排序：给定 N 个互不相同的仅由一个单词构成的英文名，将他们按字典序从小到大输出。用字典树进行排序，采用数组的方式创建字典树，这棵树的每个结点的所有儿子很显然地按照其字母大小排序。对这棵树进行先序遍历即可。
  • 最长公共前缀：对所有串建立字典树，对于两个串的最长公共前缀的长度即他们所在的结点的公共祖先个数，于是，问题就转化为求公共祖先的问题。

树的遍历

树的遍历是树的一种重要的运算。所谓遍历是指按某条搜索路径巡访树中每个结点，使得每个结点均被访问一次，而且仅被访问一次。

二叉树的遍历是指从根结点出发，按照某种次序依次访问二叉树中所有的结点，使得每个结点被访问依次且仅被访问一次。二叉树的遍历方式分为3种：

  • 前序遍历：先根节点，后左孩子节点，再右孩子结点。

    若树为空，则空操作返回。否则，先访问根节点，然后前序遍历左子树，再前序遍历右子树。

  • 中序遍历：先左孩子结点，后根节点，再右孩子结点。

    若树为空，则空操作返回。否则，从根节点开始(注意并不是先访问根节点)，中序遍历根节点的左子树，然后是访问根节点，最后中序遍历根节点的右子树。

  • 后序遍历：先左孩子节点，后右孩子结点，再根节点。

    若树为空，则空操作返回。否则，先后序遍历左子树，然后后序遍历右子树，最后访问根节点。

注意：这里的序为根节点的遍历顺序。

二叉树的3中遍历方式的结果如下图所示：
二叉树的遍历方式

学习笔记 数据结构
赏
评论
 上一篇
数据结构-散列表 数据结构-散列表
散列表(Hash table)是实现字典操作的一种有效的数据结构。 简介定义散列表也叫哈希表，是根据键和值(key 和 value)直接进行访问的数据结构。也就是说，它通过把 key 和 value 映射到表中的一个位置来访问记录，以加快查
2019-03-25 学习笔记
学习笔记 数据结构
下一篇 
数据结构-链表 数据结构-链表
链表(Linked list)是算法中常用的一种基础数据结构，是一种链式存储结构的线性表。 简介定义链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。 链表由一系列节点(链表中每一个元素称
2019-03-19 学习笔记
学习笔记 数据结构
  目录