PHPor 的Blog

概述

树的章节一般分两大部分： 一部分将树，一部分将二叉树；虽然二叉树也是树，但是二叉树足够特殊，足够有用，所以重点来讲；或者说，如果不是二叉树，树的家族也不会如此的德高望重。

在二叉树中，又有一些特殊性质的二叉树，可能没法用树的结构来描述他们之间的关系；比如： 满二叉树一定是完全二叉树；完全二叉树和二叉排序树直接却没有从属关系；完全二叉树和二叉排序树是从不同的维度定义出来的特殊的二叉树。

二叉排序树（也叫二叉查找树）在树的家族中是一颗耀眼的明星，但是在树的章节中没有被介绍，大概因为这是二叉树的实际应用，而和树本身的形态没有直接关系；还有一些特殊的树，如：红黑树、B+、B-树，稍后再研究，有些数据结构的书是没有提及的，大概因为这些东西可以自学，不需要教吧。

树

树的逻辑结构

树的定义

树是n（n>=0)个结点的有限集合。当 n= 0 时，称为空树；任意一颗非空树满足一下两个条件：

1. 有且只有一个特定的称为根的结点
2. 当 n > 1 时，除根结点之外的其余结点被分成m(m>0)个互不相交的有限集合T1, T2, …, Tm，其中每个集合又是一棵树，并称为这个根结点的子树

树的基本术语

1. 结点的度，树的度
2. 叶子结点，分支结点
3. 孩子结点，双亲结点，兄弟结点
4. 路径、路径长度
5. 祖先、子孙
6. 结点的层数、树的深度（高度）
7. 层序编号
8. 有序树、无序树
9. 森林
10. 同构

树的表示形式

一般有四种表示形式：

1. 树形图
2. 嵌套图
3. 凹凸表
4. 广义表

树的遍历

1. 前（根）序遍历
2. 后（根）序遍历
3. 层序遍历
   注： 这里说的是树，不是二叉树，所以没有中序遍历（如果有的话，三个子树的树根应该放哪里？）

树的存储结构

1. 双亲表示法
   1. 思想： 每个结点都记住自己双亲结点的位置（即可保证该树是唯一的）
   2. 缺点： 要找到一个结点的所有孩子是比较麻烦的
   3. 使用数组存储还是比较方便的
2. 孩子表示法
   1. 思想： 每个结点都记住自己孩子的位置（即可保证该树是唯一的）
   2. 缺点： 要找到结点的双亲结点比较麻烦
   3.  两种形式：
      1.  多重链表标识
         1. 思想： 父亲那N个绳拉住自己的N个孩子
         2. 关于拿几根绳？两种办法：
            1. 有几个孩子拿几根绳
               1. 需要有一个地方记录自己的绳子数目（就是该结点的度）
            2. 孩子最多的父亲拿几根绳子大家就都拿几根绳子
               1. 没人的绳子数目是一样的，不需要各自记录
      2. 孩子链表
         1. 思想：所有节点维护在一个数组中；然后，父亲拿一根绳子牵着老大，然后老大牵着老二；依次类推
3. 孩子双亲表示法
   1. 思想：孩子表示法中，添加一个双亲节点的指针
4. 孩子兄弟表示法
   1. 思想： 每个节点都左手拉着自己孩子，右手拉着自己的弟弟妹妹

二叉树

概述

二叉树是一种最简单的树结构，其存储结构更具有规范性和确定性，在一系列条件的约束下，使得二叉树具有很多的性质，方便我们研究和使用二叉树。

二叉树的定义

二叉树的5种基本形态

1. 空二叉树
2. 只有一个根结点
3. 根结点只有左子树
4. 根结点只有右子树
5. 根结点既有左子树又有右子树

特殊二叉树

1. 斜树
   1. 左斜树
   2. 右斜树
2. 满二叉树
3. 完全二叉树
   1. 从满二叉树的最后面的结点去掉n (n >= 0)个结点都是完全二叉树
   2. 满二叉树是一种特殊的完全二叉树

二叉树的性质

二叉树有5个重要的性质，他们主要讨论了树的深度、结点数等之间的关系

1. 在二叉树的第i层上至多有2^i-1个结点 (i >= 1)
2. 深度为k的二叉树至多有2^k-1个结点 (k >=1)
3. 对任何一颗二叉树T，如果其叶子结点数为n0，度为2的结点数为n2，则：n₀=n₂+1
4. 具有n个结点的完全二叉树的深度为log₂ⁿ+1
5. 如果有一颗有n个节点的完全二叉树的节点按层次序编号，对任一层的节点i（1<=i<=n）有1.如果i=1，则节点是二叉树的根，无双亲，如果i>1，则其双亲节点为[i/2]，向下取整

   2.如果2i>n那么节点i没有左孩子，否则其左孩子为2i

   3.如果2i+1>n那么节点没有右孩子，否则右孩子为2i+1

二叉树的遍历

1. 前序遍历
2. 中序遍历
3. 后序遍历

二叉树的存储

顺序表

思想： 将一棵树通过添加“虚节点”的方式完善成完全二叉树，然后存储

缺点： 空间浪费严重，只适合存储完全二叉树的情况

链式存储

1. 二叉链表
   1. 思想： 每个结点包含数据域和左右孩子两个指针域
   2. 缺点： 寻找双亲结点不方便
2. 三叉链表
   1. 思想： 在二叉链表的基础上添加双亲结点指针域

线索链表

实际问题： select * from tb where id < N limit 2; 在这种情况下，我们不仅要查到id=2的结点，还要找到他附近的一些结点；即： 需要访问二叉树中的结点在某种遍历序列中的前驱和后继；

于是： 在存储结构中应该保存结点在某种遍历序列中前驱和后继的信息。

思想： 根据二叉树的性质可知，二叉树中有n+1个指针域为空，可以想办法利用起来；通过添加标记来区分是孩子指针还是前驱（或后继）指针；注意： 挨着自己的孩子在线索化中未必就挨着自己，但是要找到挨着自己的那个结点并不难，对于中序线索链表，如果自己子树的深度为k，则，找到自己的前驱或后继的时间复杂度为log₂^k

由于二叉树的遍历次序有三种，因此有三种意义上的前驱和后继，相应的也有三种线索链表：前序线索链表、中序线索链表、后序线索链表。中序线索链表看起来更加直观一些

中序线索链表上求结点前驱

中序线索链表上求结点后继

中序线索链表上遍历

 

首先，数据结构分为逻辑结构和存储结构，这里我们也要把树的逻辑结构和存储结构分开来讲。

树的最基本的定义：
树是n（n>=0）个结点的有限集合。当n==0时，称为空树；任意一棵非空树满足以下两个条件：

1. 有且只有一个特定的称为根（root）的结点；
2. 当n>1时，除根结点之外的其余结点被分成m(m>0)个互不相交的有限集合T1,T2,…,Tm，其中每个集合又是一棵树，并称为这个根结点的子树（Subtree）。

显然，树的定义是递归的。

其它所有的树都是在树的基本定义的基础上添加限制条件而得到的，他们都具有不同的特点，也因此有不同的用途；

树的表示形式：

1. 树形图
2. 嵌套图
3. 凹凸表
4. 广义表

树的几种基本存储方法：

1. 双亲表示法
2. 孩子表示法
3. 双亲孩子表示法
4. 孩子兄弟表示法

二叉树：

1. 二叉树区分左子树、右子树，但是左右不分大小

二叉排序树：
它或者是一个空树，或者是具有如下性质的二叉树：

1. 如果它的左子树不为空，则它的左子树的所有结点的值均小于其根结点的值
2. 如果它的右子树不为空，则它的左子树的所有结点的值均大于其根结点的值
3. 它的左右子树也分别为二叉排序树

用途： 二叉排序树的中序遍历是一个有序序列

二叉搜索树（也叫二叉查找树）：
很多地方把二叉搜索树与二叉排序树当成一个概念； 我觉得二叉搜索树应该是一个平衡二叉树，因为只有平衡才能保证搜索的最大时间复杂度为O(logⁿ);
对于二叉排序树，在极端情况下（如斜树），查找的最坏的时间复杂度为O(n);

B-树：
B-树是一种平衡的多路查找树； 一棵m阶的B-树或为空树，或为满足下列特性的m叉树：

1. 树中每个节点至多有m棵子树
2. 若根结点不是叶子结点，则至少有两棵子树
3. 除根结点之外的所有非终端结点至少有[m/2]棵子树
4. 所有的非终端结点中包含下列信息数据(n,A0,K1,A1,K2,A2,…,Kn,An)其中Ki(i=1,…,n)为关键字，且Ki<Ki+1,(i=1,…,n-1); Ai(i=0,…,n)为指向子树根节点的指针，且指针Ai-1所指子树中所有节点的关键字均小于Ki(i=1,…,n),An所指子树中所有节点的关键字均大于Kn,n([m/2]-1)≤n≤m-1)为关键字的个数（或n+1为子树个数）。
5. 所有的叶子结点都出现在同一层次上，并且不带信息（空指针）。

B+ 树：
B+树是B-树的变型，m阶的B+树和m阶的B-树的区别是：

1. 关键字个数和子树个数一样多
2. 所有叶子结点中包含全部关键字信息及指向含这些关键字记录的指针，且叶子节点本身依关键字的大小自小而大顺序链接。
3. 所有非终端结点可看成索引，节点中仅含有其子树中的最大（或最小）关键字

键树：
键树（数字查找树）：是一棵度≥2的树，树中每个结点不是包含一个或几个关键字，而是只含有组成关键字的符号。如数值中的每一位，单词中的每个字母。

还需要了解的：
    红黑树、AVL(平衡二叉树）、Treap、伸展树 等。

本次学习从百度百科、百度文库中学到不少东西。

参考资料：
http://baike.baidu.com/view/593144.htm