树

树是n（n>=0）个结点的有限集；n=0的时候称为空树；在任意的一颗非空树中：

• 有且仅有一个特定的称为根的结点
• 当n>1的时候，其余结点可分为m(m>0)个互不相交的有限集T1、T2.....Tm，其中每个集合本身又是一棵树，并且称为根的子树
• 子树的个数没有限制，但是他们一定是互不相交

树的一些基本概念

• 结点拥有的子树个数称为结点的度
• 度为0的结点称为叶节点或者终端结点；度不为0的节点称为非终端结点或者分支结点，除根节点外，分支结点也被称为内部结点
• 树的度是各结点的度的最大值
• 结点的子树的根成为该结点的孩子，相应的，该结点称为该孩子的双亲；同一个双亲的孩子互称兄弟，结点的祖先是从根到该节点所经分支的所有结点
• 结点的层次从根开始定义，根为第一层，根的孩子为第二层；树中结点的最大层次称为树的深度或高度
• 如果将树中结点的各子树看成从左至右是有次序的，不能互换的，则称该树为有序树，否则为无序树
• 森林是m(m>=0)颗互不相交的树的集合

树的抽象数据类型

树的存储结构

和之前介绍的线性表不同，树是一对多的关系，并不是只有唯一的前驱和后继；也就是说之前的顺序存储和链式存储都不适合树的存储结构；这里介绍三种不同的表示法：

双亲表示法

设计思路：我们在每个结点中，增加一个或者多个指针域，里面放着我们所关注的结点的位置

比如说，如果我们想知道每个结点的双亲，那么我们就可以这样设计存储结构：

这样的话如果我们想知道某个结点的双亲，时间复杂度为O(1)，但是如果我们想知道结点的孩子是什么，就得需要遍历整个树结构，当然我们还可以多加上一个指针域

存储结构的设计是一个非常灵活的过程，一个存储结构设计的是否合理，取决于基于该存储结构的运算是否合适、是否方便、时间复杂度好不好，当然，这个也不是越多越好

孩子表示法

换一种思考方式，由于树中每个结点可能有多颗子树，可以考虑用多重链表，即每个结点有多个指针域，其中每个指针指向一个数的根结点，我们把这种方法叫做多重链表表示法

方案一：

这种方法对于树中结点的度相差很大，显然很浪费空间，因为有很多结点的指针域都是空的

方案二：

我们专门取一个位置来存储结点指针域的个数，这样的话可以节省空间

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

孩子表示法：

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

孩子兄弟表示法

任意一颗树，它的结点的第一个孩子如果存在就是唯一的，它的右兄弟如果存在也是唯一的，因此我们设置两个指针，分别指向该结点的第一个孩子和此结点的右兄弟

 

但是这种方法有缺陷；如果某一结点的兄弟非常多，那么这个指针域需要增加很多，那么无疑会造成很多空间的浪费；还有就是这种表示法如果要查找双亲的话需要增加额外的指针域

二叉树

二叉树是n（n>=0）个结点的有限集合，该集合或者为空集（称为空二叉树），或者由一个根节点和两颗互不相交的、分别称为根结点的左子树和右子树的二叉树组成

二叉树的特点

• 每个结点最多有两颗子树，所以二叉树中不存在度大于2的结点，注意不是只有两颗子树，二十最多有两颗子树，没有子树或者只有一颗子树也是可以的
• 左子树和右子树是有顺序的，次序不能颠倒
• 即使树中某结点只有一颗子树，也要区分它是左子树还是右子树

下面来介绍一些特殊二叉树

• 斜树

所有的结点都只有左子树的二叉树叫做左斜树；所有结点只有右子树的二叉树叫做右斜树，这两者统称为斜树

其实线性表结构就可以理解为树的一种极其特殊的表现形式

• 满二叉树

在一棵二叉树中，如果所有的分支结点都存在左子树和右子树，并且所有叶子都在同一层上，这样的二叉树称为满二叉树

单是每个结点都存在左右子树，不能算是满二叉树，还必须要所有的叶子都在同一层上，这就做到了整棵树的平衡

• 完全二叉树

对一颗具有n个结点的二叉树按层序编号，如果编号为i（1<=i<=n）的结点与同样深度的满二叉树的编号为i的结点在二叉树中位置完全相同，则这颗二叉树称为完全二叉树

二叉树的性质

• 在二叉树的第i层上至多有2^（i-1）个结点
• 深度为k的二叉树至多有2^k-1个结点（k>=1）
• 对任意一颗二叉树T，如果其叶子结点数为n0, 度为2的结点数为n2，那么n0 = n2+1

解释：

对于任意一颗二叉树而言，所有的结点可以分为叶子结点和度为1或者度为2的结点，设度为1的结点个数为n1，那么结点个数等于n0+n1+n2；n个结点中又有n-1个分支，度为2的结点有两个分支，度为1的结点有一个分支，所以n-1 = 2*n2 + n1，这样就可以推出来n0 = n2+1

• 具有n个结点的完全二叉树的深度为[log2(n)] + 1(中括号表示不大于这个数的最大整数)

解释：

这个根据结点个数简单推一下就可以得到结果

二叉树的存储结构

二叉树的顺序存储结构

二叉树的顺序存储结构就是用一维数组存储二叉树中的结点，并且结点的存储位置，也就是数组的下标要能体现结点之间的逻辑关系

但是这种存储方式也会有一些问题：

上面就是一个右斜树，可以看到如果采用顺序存储结构进行存储的话会造成空间的极大浪费

二叉链表

二叉树每个结点最多有两个孩子，所以为他们设计一个数据域和两个指针域是比较自然的想法，我们称这样的链表为二叉链表

遍历二叉树

前序遍历

规则是若二叉树为空，则空操作返回，否则先访问根结点，然后前序遍历左子树，再前序遍历右子树

中序遍历

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

左上右

后序遍历

规则是若树为空，则空操作返回，否则从左到右先叶子后结点的方式遍历访问左右子树，最后是访问根节点

层序遍历

规则是若树为空，则空操作返回，否则从树的第一层，也就是根节点开始访问，从上而下逐层遍历，在同一层中，按从左到右的顺序对结点逐个访问