树

应用场景举例

没有应用场景，我们谈论某个技术也没有意义。 首先我们要谈一下树的应用： 应该主要用于，索引+ 查找：

• 一维空间：各种平衡树,包括红黑树，AVL
• 高维空间： KD-tree R-tree PST等
• 外存索引： B-tree String B-tree, 等
• 字符串索引： patricia tree, trie , suffix tree, wavelet tree等
• 搜索： 可以采用树实现各种搜索策略，其各种遍历方法。
• 表示： 很多事物可以用一棵树来表示，堆，语法树等。

抽象地说，基本上有序列的地方就可以应用树，因为树结构即是一种序列索引结构。 序列的核心接口就是三个cha：插、查、X（增查删）。

对于这个三个接口，我们要解决的核心问题是：

1. 效率：怎么查得快
2. 稳定：如果不支持增删，那么序列就是静态结构，用处不大。而支持增删之后，需要考虑如何保证序列内部结构不会被增删操作破坏，导致查询效率受到影。

树和森林的定义

树 (tree) 是包括 n 个结点的有限集合 T(n ≥ 1):

• 有且仅有一个特定的结点，称为 根 (root)
• 除根以外的其他结点被分成 m 个 (m ≥ 0)不相交的有限集合T1，T2，...，Tm，而每一个集合又都是树 ，称为 T 的子树。

树的逻辑结构

从定义上看，树就是一个集合，并且在集合上定义了节点之间的关系。

树的相关术语

• 度数:一个结点的子树的个数 D
• 层数:根为第 0 层
  • 其他结点的层数等于其父结点的层数加 1
• 深度:层数最大的叶结点的层数
• 高度:层数最大的叶结点的层数加 1

树形结构的各种表示法

• 树形表示法
• 形式语言表示法
• 文氏图表示法（高中的集合表示）
• 凹入表表示法（课本目录）
• 嵌套括号表示法

森林定义及与二叉树的等价转换

森林(forest):零棵或多棵 不相交 的 树的集合(通常是有序)

森林与二叉树之间可以相互转化，而 且这种转换是一一对应的

森林转化成二叉树的形式定义

有序集合 F = {T1，T2，...，Tn} 是树 T1，T2，...，Tn 组成的森林，递归转换成二叉树B(F):

• 若F为空，即n=0，则B(F)为空。
• 若 F 非空，即 n > 0，则 B(F) 的根是森林中第一棵树 T1 的根 W1， B(F) 的左子树是树 T1 中根结点 W1的子树森林 F = {T11，...，T1m} 转换成的二叉树B(T11，...，T1m); B(F)的右子树是从森林 F’ = {T2，...，Tn} 转换而成的二叉树

二叉树转化成森林或树的形式定义

设B是一棵二叉树，root是 B 的根，BL 是 root 的左子树，BR 是 root 的右子树，则对应于二叉树B的森林或树 F(B) 的形式定义是:

• 若 B 为空，则 F(B) 是空的森林
• 若 B 不为空，则 F(B)是一棵树T1加上森林 F(BR)， 其中树 T1 的根为 root，root 的子树为 F(BL) 也就是说转换成了空森林，或者包含两颗树的森林

树的ADT

template<class T> 
class TreeNode { 
public:
    TreeNode(const T& value); 
    virtual ~TreeNode() {}; 
    bool isLeaf();
    T Value();
    TreeNode<T> *LeftMostChild(); 
    TreeNode<T> *RightSibling();
    void setValue(const T& value);
    void setChild(TreeNode<T> *pointer); 
    void setSibling(TreeNode<T> *pointer); 
    void InsertFirst(TreeNode<T> *node); // 以第一个左孩子身份插入结点
    void InsertNext(TreeNode<T> *node);// 以右兄弟的身份插入结点
};

template<class T> 
class Tree { 
public:
    Tree();
    virtual ~Tree();
    TreeNode<T>* getRoot();
    void CreateRoot(const T& rootValue);
    bool isEmpty();
    TreeNode<T>* Parent(TreeNode<T> *current);
    TreeNode<T>* PrevSibling(TreeNode<T> *current);   //返回前一个兄弟
    void DeleteSubTree(TreeNode<T> *subroot); 
    void RootFirstTraverse(TreeNode<T> *root); 
    void RootLastTraverse(TreeNode<T> *root); 
    void WidthTraverse(TreeNode<T> *root);
};
 
复制代码

需要注意的是树没有中序遍历，因为树的度大于二，不好判断从哪一个是中间的子节点访问根节点。

先根遍历森林（等价于二叉树前序遍历）

template<classT>
void Tree<T>::RootFirstTraverse(TreeNode<T> * root){
	while(root!=NULL){
		Visit(root);
		RootFirstTraverse(root->LeftMostChild()); //往最左节点下降
		root = root->RightSibling();  //遍历其他树
	}
}
复制代码

后根遍历（等价于二叉树中序遍历）

template<classT>
void Tree<T>::RootLastTraverse(TreeNode<T> * root){
	while(root!=NULL){
		RootFirstTraverse(root->LeftMostChild()); //往最左节点下降
		visit(root);
		root = root->RightSibling();  //遍历其他树
	}
}
复制代码

宽度优先遍历森林（层次遍历）

template<class T>
void Tree<T>::WidthTraverse(TreeNode<T> * root) {
	std::queue<TreeNode<T>*> aQueue;
	TreeNode *pointer = root;
	while(pointer){
		aQueue.push(pointer);
		pointer = pointer->RightSibling();
	}
	while(!aQueue.empty()){
		pointer = aQueue.front();
		aQueue.pop();
		Visit(pointer);
		pointer = pointer->LeftMostChild();
		while(pointer){
			aQueue.push(pointer);
			pointer = pointer->RightSibling();
		}
	}
}
复制代码

树的存储结构

• 链式存储
  • 子节点表
    • 图的邻接表
    • 索引 值 父结点（索引） 子结点（指针域）
  • 静态左孩子/右兄弟表示法 -实际上是，在数组中存储的“子结点表”
    • 左子节点（指针域） 值 父节点（索引） 右兄弟结点（指针域）
  • 动态表示法
    • 每个结点分配可变的存储空间
      • 子结点数目发生变化，需要重新分配存储空间
  • 动态“左子/右兄”二叉链表示法
    • 左孩子在树中是结点的最左子结点，右子结点是结点原来的右侧兄弟结点
    • 左孩子pchild（指针域） 值info 右兄弟psibling（指针域）
  • 父指针表示法（并查集）
    • 单独介绍
• 顺序存储

动态二叉链表树的关键实现细节

// 在TreeNode的抽象类中增加以下私有数据成员
private:
    T m_Value; 
    TreeNode<T> *pChild; 
    TreeNode<T> *pSibling;
复制代码

父指针表示法

• 只需要知道父结点的应用
• 只需要保存一个指向其父结点的指针域，称为 父指针(parent pointer)表示法
• 用数组存储树结点，同时在每个结点中附设一个指针指示其父结点的位置

并查集

并查集 是一种特殊的集合，由一些不相 交子集构成，合并查集的基本操作是:

• Find: 查询结点所在集合
• Union: 归并两个集合

等价类(equivalence classes)

等价类是指相互等价的元素所组成的最大集合。也就是说在集合上定义了一种等价关系，这个关系把大集合划分为满足与不满足该关系的集合。 所谓最大，就是指不存在类以外的元素，与类内 部的元素等价。

用树来表示等价类的并查

• 用一棵树代表一个集合
  • 集合用父结点代替
  • 若两个结点在同一棵树中，则它们处于同一个集合
• 树的实现
  • 存储在静态指针数组中
  • 结点中仅需保存父指针信息

父指针表示法Union/Find算法实现

template<class T>
class ParTreeNode { 
   private:
Tvalue; ParTreeNode<T>* parent; int nCount;
public:
    ParTreeNode();
    virtual ~ParTreeNode(){};
    TgetValue();
    void setValue(const T& val); 
    ParTreeNode<T>* getParent();
    void setParent(ParTreeNode<T>* par); 
    int getCount();
    void setCount(const int count);
};

template<class T> 
class ParTree { 
    public:
        ParTreeNode<T>* array;
        int Size;
        ParTreeNode<T>* Find(ParTreeNode<T>* node) const; // 查找node结点的根结点
        ParTree(const int size);
        virtual ~ParTree();
        void Union(int i,int j); // 把下标为i，j的结点合并成一棵子树
        bool Different(int i,intj);
        //判定下标为i，j的结点是否在一棵树中
};

template <class T>
ParTreeNode<T>* ParTree<T>::Find(ParTreeNode<T>* node) const 
{
    ParTreeNode<T>* pointer=node; 
    while ( pointer->getParent() != NULL )
        pointer=pointer->getParent(); 
    return pointer;
}
复制代码

Union算法

核心是小树往大树上合并。

template<class T>
void ParTree<T>::Union(int i,int j) {
ParTreeNode<T>* pointeri = Find(&array[i]); //找到结点i的根 ParTreeNode<T>* pointerj = Find(&array[j]); //找到结点j的根 if (pointeri != pointerj) {
if(pointeri->getCount() >= pointerj->getCount()) { pointerj->setParent(pointeri); 
pointeri->setCount(pointeri->getCount() +
pointerj->getCount());
}
else {
pointeri->setParent(pointerj); 
pointerj->setCount(pointeri->getCount() +
pointerj->getCount());
  } 
}}
复制代码

路径压缩

• 查找X
  • 设X最终到达根R
  • 顺着由X到R的路径把每个结点的父指针域均设置 为直接指向R 使用路径压缩规则处理寻找父节点函数Find()

template <class T>
ParTreeNode<T>* ParTree<T>::FindPC(ParTreeNode<T>* node) const {
    if (node->getParent() == NULL) 
        return node;
    node->setParent(FindPC(node->getParent()));
    return node->getParent(); 
}
复制代码

• 对n个结点进行n次Find操作的开销为O(nα(n))，约 为Θ(nlog*n)
• Find至多需要一系列n个Find操作的开销非常接 近于Θ(n) – 在实际应用中，α(n)往往小于4

树的顺序存储结构

• 带右链的先根次序表示
  • 节点按先根次序连续存储
  • Itag（标记有左子节点为0，else 1） info rlink（右指针）
• 带双标记的先根次序表示 *带右链的先根次序表示”中rlink也有冗余，可以把rlink指针替换为一个标志位rtag，成为“带双标记的 先根次序表示”
• 带双标记的层次次序表示
• 带度数的后根次序表示