1.树

回顾之前所学的向量结构（Vector）和列表结构（List），对于以查找为代表的静态操作和以插入为代表的动态操作，两者都无法兼顾静态和动态的高效性。而本章要介绍的树结构恰好能将二者的优势结合起来，即可快速查找，又可以快速插入和删除。树可以理解为列表的列表，或二维的列表。树并不是严格意义上的线性结构，但又带有一定的线性特征，因此树可以被称为半线性结构。

树是用来按照层次关系组织一系列数据项的一种方式，如：表达式、文件系统、函数调用和递归过程、Internet URL等等。

1.1.有根树

树是特殊的图T = ( V, E)，可以认为树是定义在一组元素之间的二元关系，节点（Vertex）数 |V| = n，边（edge）数 |E| = e。
为树指定任一节点 r $\in$ V作为根后，树T 即称作有根树（rooted tree）。

对于任何一组有根树都可以通过引入一个新的顶点，并且在新的这个顶点与此前各棵有根树的树根之间引入对应的一条连边，从而构成一棵规模更大的有根树，这棵新的有根树的树根就是所引入的这个新的节点，通常记作r，暗示着它就是root树根。而对于这棵更大的树，参与组成它的每一棵有根树都相对地称作是它的子树subtree。

若：$T_1,T_2,\dots ,T_d$是有根树，则：$T=\left( (\cup V_i)\cup\{r\},\,(\cup E_i)\cup\{|1\le i\le d\} \right)$也是有根树。
相对于$T$，$T_i$称作以$r_i$为根的子树（subtree rooted at $r_i$），记作$T_i$ = subtree( $r_i$ )。

1.2.有序树

$r_i$称作$r$的孩子（child），$r_i$之间互称兄弟（sibling）；

$r$为其父亲（parent），d = degree( r )为$r$的（出）度（degree）。
可归纳证明： e（节点数总和）= $\sum_{r\in V}degree(r)$ = n - 1 = $\Theta(n)$，即任何一棵树中的边数与其中顶点的数目是同阶的，一棵树的总体规模也可度量为( n + e )，故在衡量相关复杂度时，可以n作为参照。
若指定$T_i$为$T$的第$i$棵子树，$r_i$作为$r$的第$i$个孩子（即在兄弟间定义了次序），则$T$称作有序树（ordered tree）。

1.3.连通与无环

上面从递归嵌套的角度定义了树，但我们并没有看到树结构相对于一般的图结构而言在拓扑上到底有什么不同。那么接下来将从连通性和无环性两个角度来揭示树结构的特性。

V中的k+1个节点，通过E中的k条边依次相连，构成一条路径（path）：

$\pi=\{ \, (V_0,V_1),\, (V_1,V_2),\,\dots,\,(V_{k-1},V_k)\, \}$
路径长度：$|\pi|=$边数$=k$
任意节点之间均有路径的图，称作连通图（connected graph）

若$V_k=V_0$，则该路径是环路（cycle/loop），不含环路的图，称作无环图（acyclic graph）。

树结构是无环连通图，即是极小连通图，也是极大无环图。
故在树中，任一节点V与根之间存在唯一路径，故可记 path(v, r) = path(v)
因此可以|path(v)|为指标，对所有节点做等价类划分。

1.4.深度与层次

在不致歧义的情况下，路径、节点和子树可相互指代： path(v) ~ v ~ subtree(v)
v的深度：depth(v) = |path(v)|
path(v)上的节点均为v的祖先（ancestor），v是它们的后代（descendent）；除v自身以外的祖先，是真（proper）祖先。
在任一深度：v的祖先若存在则必然唯一；v的后代未必唯一。从这个意义上讲也应该将数称为半线性结构。

根节点是所有节点的（公共）祖先，深度为0；没有后代的节点称作叶子（leaf）。
所有叶子深度中的最大者称为子树的高度：height(v) = height( subtree( v ) )；注意与树根的高度（height(T))区分开。
特别低，只有一个节点的树的高度为1，空树的高度为-1。
depth( v ) + height( v ) $\le$ height( T )

2.树的表示

上一节介绍了树的基本概念，这一节将来讨论在计算机中如何从逻辑上来表示一棵树，从抽象数据类型的角度来看树结构应该提供大致如下这些接口：

2.1.父节点

除根外，任一节点有且仅有一个父节点。

不妨将所有的节点组织为一个序列：其中的每一个元素都分别包括三项，data是节点本身的信息，rank或者position指明的是这个节点的记录在这个序列中所对应的秩或者是位置，而parent恰好就是节点唯一的父节点所对应的秩或者是位置。树根也有一个“虚构的”父节点-1或NULL。

空间性能：$O(n)$
时间性能：
- parent()：$O(1)$
- root()：$O(n)$或$O(1)$
- firstChild()：$O(n)$
- nextSibling()：$O(n)$

这样做有一定的好处，不幸的是如果要向下索取某个节点的后代比如长子，依然需要去遍历所有的元素并且逐一地确认它的父节点是否就是当前查询的元素，这个基本操作在最坏情况下需要线性时间$O(n)$；而查找兄弟节点也是类似的在最坏情况下需要遍历整棵树。因此我们下一步改进自然就集中在这两种向下方向的查询上。

2.2.孩子节点

不妨对于任何一个节点都将它的孩子汇聚起来构成一个更小的数据集，为每一个节点准备一个名为children的引用，所指向的是由它的所有的孩子构成的一个序列，如使用列表来实现这个序列，列表的长度分别等于对应节点当前的度数。

这个方法解决了向下的查找问题，而向上的查找优势却丧失殆尽，不难发现为了查找某一个节点的父亲不得不去遍历整个线性序列，并且逐一地翻看它所对应的孩子记录，在最坏的情况下仍需要线性时间$O(n)$。

2.3.父节点+孩子节点

如果将刚才的两个线性的序列组合起来，即对于同一个节点不仅保留它的parent域，同时还要保留它的children这样的一个引用，那么刚才两个方向的优势是可以兼而有之的。如果要去查找父亲就在parent这一列中进行查找，需要$O(1)$的时间；如果要是去查找孩子，就在children所指向的序列中再去查找，若是长子就可在$O(1)$的时间内直接返回，若是其它的孩子最多是去遍历序列。

但这种方法仍有一些不足：每一个节点的children引用所指向的序列在规模上有可能相差极其悬殊，每一个序列的长度恰好是节点对应的出度，而出度的总和为$\sum_{r\in V}degree(r)$ = n - 1 = $\Theta(n)$，与n同阶。而这种组织方式有时需要长达$O(n)$的一个数据集，为此需要找到一些新的办法，更加规范并相应也更简洁和高效。

2.4.长子+兄弟

反观上小节方法存在根源在于每一个节点的出度是不尽相同的，为进行改进我们必须发现每个节点所具有的某种不变性。就向下的引用而言每一个节点只需记两个信息就够了，第一个就是它的长子，第二个是每一个节点的下一个兄弟。

每个节点均设两个引用：
- 纵向：firstChild()
- 横向：nextSibling()

如此，对于度数为d的节点，可在$O(n+1)$时间内遍历其所有孩子
若再设置parent引用，则parent()接口也仅需$O(1)$时间

相对于此前的表示方法，这种表示方法的规整性非常的突出，由于每个节点只需记录两个引用，因此其点所需要占用的空间依然是常数，，而且都彼此接近，这是此前的常规方法所无法比拟的。

这种长子兄弟法不仅是树的一种很好的表示方法，而且也是对树的本质的一种更深刻的理解，在此后介绍二叉树
并且用二叉树来代表所有的树的时候，我们将再次用到这样一种表示方法。对于树这样的一个全集来说尽管二叉树只是它的一个特殊的子集，但是很有趣的是在施加了某些条件之后，二叉树却足以来表示和实现所有的树，而这样一种方法背后的原理在很大程度上就是基于长子兄弟法。

3.二叉树

这一节介绍树的一种特殊但又不失代表性的特例：二叉树（binary tree）

节点数不超过2的树，称作二叉树
同一节点的孩子和子树，均以左、右区分（隐含着有序性）
- lChild() ~ lSubtree()
- rChild() ~ rSubtree()

3.1.基数

二叉树中深度为k的节点至多$2^k$个
含n个节点、高度为h的二叉树中有：$h<n<2^{h+1}$
- 当 $n=h+1$时，退化为一条单链
- 当$n=2^{h+1}-1$时，称作满二叉树（full binary tree）

由此也可见一棵二叉树在横向上的宽度与它在纵向上的高度是呈一个指数的关系的，宽度是高度的指数，而指数意味着爆炸（剧烈的增长），所以如果节点的总数固定，宽度大致与它相当，但是高度却会增长的非常的缓慢呈一个对数的形式。也就是说对于一棵二叉树而言，它非常倾向于“涨宽”，它“涨宽”的速度更快，而它的高度呢如果控制得当的话会增长的异常的缓慢，这个特点也是之后介绍的二叉搜索树的重要理论基础。

3.2.真二叉树

上面介绍的二叉树只对每个节点的出度做了个上限的约定，即不得超过2。这样一般性的一棵二叉树在很多操作，包括算法的实现以及对算法的理解上都会引来一些不必要的麻烦。而反过来一个比较有效的改进方法就是将任何的这样一棵一般性的二叉树转化为一棵真二叉树（proper binary tree）。

通过引入$n_0+n_2$个外部节点，可是原有节点度数同一为2，如此即可将任一二叉树转化为真二叉树。
经过转换之后，从渐进意义上，全树自身的复杂度并未实质增加。

在之后实现相应的算法的时候就会看到这种添加实际上完全是假想的，即并不需要真正去引入节点，只需要假想着它们存在，你的算法就可以更加简洁的实现而且更加简洁的被理解。

3.3.描述多叉树

接下来来介绍这一节最重要的一点：如何通过二叉树来描述多叉树。其实上需要的条件只有两条：有根和有序。

二叉树是多叉树的特例，但在有根且有序时其描述能力却足以覆盖后者；
即任意有根有序的多叉树均可转换为二叉树——回顾“长子-兄弟”表示法；
为此只需将节点处旋转45度，将长子，兄弟与左、右孩子等效地相互对应：
- firstChild() ~ lChild()
- nextSibling() ~ rChild()

如果说这一章的任务是描述并且实现以及利用树结构的话，不如说我们只需研究并且实现二叉树。接下来几节将介绍二叉树结构的实现和相关的算法。

4.二叉树实现

在此前的几节先后介绍了树的概念，了解了树的特点，并且懂得了如何来表示一棵树。最重要的方法就是借助二叉树来表示任何一棵有根有序树，所以接着就来介绍如何在C++语言中实现一棵二叉树。

4.1.BinNode模板类

二叉树的基本组成单位是二叉树节点（Binary Node，或简称BinNode），每一个BinNode的逻辑组成可以用下图来表示。每一个BinNode节点首先应该有一个data域，记录它携带的信息，这是BinNode节点的核心的要素；它也应该配备相应的引用域，分别指向左右孩子以及父亲；此外作为在树中的一个特定元素它也需要记录一些重要的指标，比如height 高度，对于红黑树而言就会有颜色的区别，对于左式堆而言有npl指标，所以也需要为它们留有余地。

下面定义名为BinNode的类

#define BinNodePosi(T) BinNode<T>* //节点位置

template <typename T> struct BinNode { //二叉树节点模板类
    
	BinNodePosi(T) parent, lChild, rChild; //父节点及左、右孩子
	T data; int height; //数据，/高度（通用）

// 构造函数
   BinNode() :
      parent ( NULL ), lc ( NULL ), rc ( NULL ), height ( 0 ), npl ( 1 ), color ( RB_RED ) { }
   BinNode ( T e, BinNodePosi(T) p = NULL, BinNodePosi(T) lc = NULL, BinNodePosi(T) rc = NULL,
             int h = 0, int l = 1, RBColor c = RB_RED ) :
      data ( e ), parent ( p ), lc ( lc ), rc ( rc ), height ( h ), npl ( l ), color ( c ) { }
	
// 操作接口
	int size(); //统计当前节点后代总数，亦即以其为根的子树的规模
	BinNodePosi(T) insertAsLC(T const&); //作为当前节点的左孩子插入新节点
	BinNodePosi(T) insertAsRC(T const&); //作为当前节点的右孩子插入新节点
	BinNodePosi(T) succ(); //取当前节点的直接后继
	template <typename VST> void travLevel(VST&); //子树层次遍历
	template <typename VST> void travPre(VST&); //子树先序遍历
	template <typename VST> void travIn(VST&); //子树中序遍历
	template <typename VST> void travPost(VST&); //子树后序遍历
 
};

4.2.BinNode接口实现

这一小节介绍BinNode类的几个常用接口，首先是insertAsLC接口，我们要对传入的参数e进行封装
使之成为一个新的节点，并且将它作为当前节点的左孩子接入所属的这棵树中。当然作为入口条件可以假设当前节点的左孩子现在是空的。

这个功能的实现方法是：通过BinNode构造函数创建一个新的BinNode节点，而它的父节点就是this即当前这个节点。从下面的图来看，这一步就相当于将新的BinNode节点的parent引用指向当前的这个节点。这只是自下而上一个方向的连接，为了保证整体的一致性我们还需要相应地完成自上而下的连接，也就是令当前这个节点this的左孩子引用lChild能够指向新创建的节点，这一步可以通过直接用这个新生成的节点赋予当前节点的lChild引用来实现。

insertAsRC接口实现的方式完全对称，只需相应地将左孩子引用替换为右孩子引用。两个插入操作的复杂度均为$O(1)$。

template <typename T> BinNodePosi(T) BinNode<T>::insertAsLC(T const& e){
	return lc = new BinNode(e, this);
} //将e作为当前节点的左孩子插入二叉树,  O(1)

template <typename T> BinNodePosi(T) BinNode<T>::insertAsRC(T const& e){
	return rc = new BinNode(e, this);
} //将e作为当前节点的右孩子插入二叉树,  O(1)

BinNode的size()接口，返回包括当前节点在内所有后代的总数，可以通过递归来实现，复杂度为$O(n=|size|)$。

template <typename T> int BinNode<T>::size() { //统计当前节点后代总数，即以其为根的子树规模
	int s = 1; //计入本身
	if (lChild) s += lChild->size(); //递归计入左子树规模
	if (rChild) s += rChild->size(); //递归计入右子树规模
	return s;
}  //O(n = |size|)

4.3.BinTree模板类

在完成了对二叉树节点类BinNode的定义之后，我们就可以基于它来实现整体的binary tree简称BinTree这样一种模板类，代码的主体结构如下：

#include"BinNode.h"

template <typename T> class BinTree { //二叉树模板类
protected:
	int _size; BinNodePosi(T) _root; //规模、根节点
	virtual int updateHeight(BinNodePosi(T) x); //更新节点x的高度
	void updateHeightAbove(BinNodePosi(T) x); //更新节点x及其祖先的高度
public:
	BinTree() : _size(0), _root(NULL) { } //构造函数
	~BinTree() { if (0 < _size) remove(_root); } //析构函数
	int size() const { return _size; } //规模
	bool empty() const { return !_root; } //判空
	BinNodePosi(T) root() const { return _root; } //树根

 //操作接口
	BinNodePosi(T) insertAsRoot(T const& e); //插入根节点
	BinNodePosi(T) insertAsLC(BinNodePosi(T) x, T const& e); //e作为x的左孩子（原无）插入
	BinNodePosi(T) insertAsRC(BinNodePosi(T) x, T const& e); //e作为x的右孩子（原无）插入
	BinNodePosi(T) attachAsLC(BinNodePosi(T) x, BinTree<T>* &T); //T作为x左子树接入
	BinNodePosi(T) attachAsRC(BinNodePosi(T) x, BinTree<T>* &T); //T作为x右子树接入
	int remove(BinNodePosi(T) x); //删除以位置x处节点为根的子树，返回该子树原先的规模
	BinTree<T>* secede(BinNodePosi(T) x); //将子树x从当前树中摘除，并将其转换为一棵独立子树
	template <typename VST> //操作器
	void travLevel(VST& visit) { if (_root) _root->travLevel(visit); } //层次遍历
	template <typename VST> //操作器
	void travPre(VST& visit) { if (_root) _root->travPre(visit); } //先序遍历
	template <typename VST> //操作器
	void travIn(VST& visit) { if (_root) _root->travIn(visit); } //中序遍历
	template <typename VST> //操作器
	void travPost(VST& visit) { if (_root) _root->travPost(visit); } //后序遍历
	bool operator< (BinTree<T> const& t) //比较器（其余自行补充）
	{
		return _root && t._root && lt(_root, t._root);
	}
	bool operator== (BinTree<T> const& t) //判等器
	{
		return _root && t._root && (_root == t._root);
	}
}; //BinTree

需要注意的是：其中updateHeight这个接口是以virtual来修饰的，即虚函数。后面我们会看到二叉树，尤其是二叉搜索树是一个庞大的家族，其中的每一个成员对于高度的定义包括更新的方法都不尽相同，因此通过将它定义为虚方法可以便于各种派生类对这个方法进行适当的重写。

4.4.高度更新

对于任何一个节点x，它的高度是在以它为根的子树中，从它通往那个最深的叶节点的路径长度。有两种特殊情况：单节点的树高度取0，空树高度取-1，这里采用宏定义的封装的方式，通过重新命名一个新的等价意义上的高度，将常规情况下的高度与退化情况下的高度统一起来，使得此后对算法的描述和理解可以更为简便，同时也不致于影响到算法的正确性。

一个节点的高度恰好等于它的左孩子与右孩子高度中的更大者再加1，因此可以相应地得到对任意节点x进行高度更新的算法。而如果x的祖先节点存在，那么祖先节点的高度可能因为x的高度变化而变化，整个这样的过程需要从x开始遍历它的所有历代祖先，算法的复杂度正比于x节点的深度，即$O(n=depth(x))$。

#define stature(p) ( (p) ? (p)->height : -1 ) //节点高度—约定空树高度为-1

template <typename T> int BinTree<T>::updateHeight(BinNodePosi(T) x) //更新节点x高度
{
	return x->height = 1 + __max(stature(x->lc), stature(x->rc));
} //具体规则，因树而异

template <typename T> void BinTree<T>::updateHeightAbove(BinNodePosi(T) x) //更新节点x及其历代祖先的高度
{
	while (x) { updateHeight(x); x = x->parent; }
} //可优化：一旦高度未变，即可终止。 O(n = depth(x))

4.5.节点插入

insertAsRC接口为原树中一个没有右孩子的节点插入一个右孩子节点，插入后原树的规模会增加1，x节点的高度有可能因为它新加入了一个孩子而发生变化，因此还要调用updateHeightAbove来对x这个节点以及它的历代祖先更新高度。

template <typename T> BinNodePosi(T) BinTree<T>::insertAsRC(BinNodePosi(T) x, T const& e)
{
	_size++; x->insertAsRC(e); 
	updateHeightAbove(x);   //x及其祖先的高度可能增加，其余节点必然不变
	return x->rc;
} //e插入为x的右孩子，insertAsLC()完全对称