数据结构与算法A 第六章树

树的定义和基本术语

树和森林

• 定义：树 (tree) 是包括 n 个结点的有限集合 T（n ≥ 1）：

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

• 树的逻辑结构：树是一个包含n个结点的有穷集合K,满足二元关系R={r}

  1. 有且仅有一个结点 k0∈K，它对于关系 r 来说没有前驱。结点 k0 称作树的根
  2. 除结点 k0 外，K中的每个结点对于关系 r 来说都有且仅有一个前驱
  3. 除结点k0外的任何结点k，都存在一个结点序列k0,k1,…,ks，使得k0就是树根，ks=k，其中有序对<ki-1,ki>。这样的节点序列称为从根k0到结点k的一条路径
     • 例如
     – 结点集合 K={ A，B，C，D，E，F，G，H，I，J }
     – K 上的关系 r = { <A，B>，<A，C>，<B，D>，<B，E>，<B，F>，<C，G>，<C，H>，<E，I>，<E，J> }

• 根据次序分类：

  1. 无序树：子结点的次序没有必要加以区别
  2. 有序树：往往把子结点从左到右的次序顺序编号
  • 度为2的有序树并不是二叉树

• 定义：森林(forest)是零棵或多棵不相交的树的集合（通常是有序）

• 树形结构的各种表示法：

  1. 树形表示法
  2. 凹入表示法
  3. 文氏图表示法
  4. 嵌套括号表示法

森林和二叉树的等价转换

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

• 树和森林到二叉树的转换过程：

  1. 连线：将兄弟结点用线连接起来(同父亲兄弟)
  2. 切线：保留父结点与其第一个子结点的连线，将父结点到其他子结点的连线切掉
  3. 旋转：以根为轴，平面向下顺时针方向旋转一定的角度

• 森林F转换成二叉树B(F)的递归定义：

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

• 二叉树转换为树或森林过程：

  1. 旋转：以根为轴，平面逆时针方向旋转
  2. 补线：若结点x是父结点y的左子结点，则把x的右子结点、右子结点的右子结点以此类推，用连线与y连起来
  3. 删线：去掉所有父结点到原右子结点的连线

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

  1. 若 B 为空，则 F(B) 是空的森林
  2. 若 B 不为空，则 F(B)是一棵树T1加上森林 F(BR)，其中树 T1 的根为 root，root 的子树为 F(BL)

树的ADT

• 类似于二叉树，输的抽象数据类型包括结点类和树类

template<class T>
class TreeNode 
{ // 树结点的ADT
    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); // 创建值为rootValue的根结点
        bool isEmpty(); // 判断是否为空树
        TreeNode<T>* Parent(TreeNode<T> *current); // 返回父结点
        TreeNode<T>* PrevSibling(TreeNode<T> *current); //返回前一个兄弟
        void DeleteSubTree(TreeNode<T> *subroot); // 删除以subroot子树
        void RootFirstTraverse(TreeNode<T> *root); // 先根深度优先遍历树
        void RootLastTraverse(TreeNode<T> *root); // 后根深度优先遍历树
        void WidthTraverse(TreeNode<T> *root); // 广度优先遍历树
};

树的周游

深度优先周游树

• 由于一个结点可能多于两个字数，因此不能像二叉树的中序周游法那样给出树的中跟次序周游方式。而只存在前序法(先根次序周游森林)和后序法(后根次序周游森林)：

  1. 先根次序周游森林：
     1. 访问森林中第一棵树的根结点
     2. 在先根次序下周游第一课树根结点的字数森林
     3. 在先根次序下周游其他树构成的森林
  2. 后根次序周游森林：
     1. 在后根次序下周游第一棵树根结点的子树森林
     2. 访问森林中的一个棵树的根结点
     3. 在后根次序下周游其他树构成的森林

• 先根次序周游森林的序列正好等同于其对应的二叉树的前序序列

• 后跟次序周游得到的排列正好是对应的二叉树在中序次序周游下的结点序列

• 先根深度优先遍历森林

template<class T>
void Tree<T>::RootFirstTraverse(TreeNode<T> * root) 
{
    while (root != NULL) 
    {
        Visit(root->Value()); // 访问当前结点
        // 遍历第一棵树根的子树森林(树根除外)
        RootFirstTraverse(root->LeftMostChild());
        root = root->RightSibling(); // 遍历其他树
    }
}

• 后根深度优先遍历森林

template<class T>
void Tree<T>::RootLastTraverse(TreeNode<T> * root) 
{
    while (root != NULL) 
    {
        // 遍历第一棵树根的子树森林
        RootLastTraverse(root->LeftMostChild());
        Visit(root->Value()); // 访问当前结点
        root = root->RightSibling(); // 遍历其他树
    }
}

广度优先周游

• 广度优先周游也称“宽度优先周游”或者“层次周游”：从树的第零层(根结点)开始，自上而下逐层周游，在同一层中则按照从左到右的顺序对结点注意访问

• 森林的层次序列和对应的二叉树的层次序列不同

• 广度优先遍历森林

template<class T>
void Tree<T>::WidthTraverse(TreeNode<T> * root) 
{
    using std::queue; // 使用STL队列
    queue<TreeNode<T>*> aQueue;
    TreeNode<T> * pointer = root;
    while (pointer != NULL) 
    {
        aQueue.push(pointer); // 当前结点进入队列
        pointer = pointer->RightSibling(); // pointer指向右兄弟
    }
    while (!aQueue.empty()) 
    {
        pointer = aQueue.front(); // 获得队首元素
        aQueue.pop(); // 当前结点出队列
        Visit(pointer->Value()); // 访问当前结点
        pointer = pointer-> LeftMostChild(); // pointer指向最左孩子
        while (pointer != NULL) 
        { // 当前结点的子结点进队列
            aQueue.push(pointer);
            pointer = pointer->RightSibling(); // 注意在等价二叉链结构中是 L 型访问
        } 
    } 
}

树的链式存储结构

“子结点表”表示方法

• “子结点表”表示方法：每个分支结点按照从左至右的顺序形成一个链表存储在改分支结点中，主体是存储了树中各结点信息的数组

• 3个域：分别用来存放结点信息的值、父结点指针、指向其子结点表的指针

• 索引从0开始，链表中子结点的顺序由左至右。最左子结点可由子结点链表的第一个表项直接找到，顺链可得所有子结点

静态“左子/右兄”表示法

• 4个域：分别用来存储结点的值、指向其父结点指针、指向最左子结点指针、指向右侧兄弟结点的指针

• 比“子结点表”表示法空间效率更高，而且每个结点的存储空间大小固定

动态表示法

• 为每个结点分配可变的存储空间，每一个结点都存储一个子结点指针表，子结点的数目也存储在结点中

• 本质上域“子结点表”表示法相同，但是可以动态的分配结点空间，而不是把所有结点都分配在一个数组中

动态“左子/右兄”二叉链表表示法

• 左子结点在树中是结点的最左子结点，右子结点是结点原来的右侧兄弟结点，根的右链就是森林中每棵树的根结点

// 在TreeNode的抽象类中增加以下私有数据成员
private:
    T m_Value; // 树结点的值
    TreeNode<T> *pChild; // 第一个左孩子指针
    TreeNode<T> *pSibling; // 右兄弟指针

父指针表示法和在并查集中的应用

父指针表示法

• 用数组存储树结点，同时在每个结点中附设一个指针指示其父结点的位置

• 寻找一个结点的父结点只需要O(1)

• 父指针表示法适合于无序树的情况而且只适合于查询结点的根和合并树等操作

等价类和并查集

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

  1. find：判断两个结点是否在同一个集合中
  2. union：归并两个集合

• 并查集也是一种重要的抽象数据类型，可以用于求解等价类问题。若关系 R 是一个 等价关系，当且仅当如下条件为真时成立：

  1. 自反：对于所有的x,(x,x)∈R
  2. 对称：当且仅当(x,y)∈R,(y,x)∈R
  3. 传递：若(x,y)∈R,(y,z)∈R,则有(x,z)∈R

• 如果(x,y)∈R,则元素x和y是等价的。等价类指相互等价的元素所组成的最大集合。即不存在类以外的元素，与类内部的元素等价

• 划分等价类需要对集合进行3种操作：

  1. 给每一个元素构造一个独立的集合
  2. 判定某个元素所在的子集，从而确定两个元素是否在同一个集合中。即搜索包含该元素的等价类，对于同一个集合中的元素返回相同的结果，否则返回不同的结果
  3. 归并两个集合为一个集合

• 用树来表示等价类的并查：

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

• 查找所需要的时间由树的高度所决定，合并所需要的时间是O(1)

• 为了防止树退化为单链，应该让每个结点到其相应根结点的距离尽可能小，改进方式：

  1. “重量权衡合并原则”：合并操作根据子集中包含的元素的数目，令含有元素少的子集的树根指向含元素多的子集的根。整体深度限制在O(logn),find操作只需要O(logn)
  2. 路径压缩技术：执行find时，把结点到树根的路径上所有结点的父指针都指向根结点。设X最终到达根R，顺着由X到R的路径把每个结点的父指针域均设置为直接指向R
     

• 树的父指针表示与Union/Find算法实现

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,int j); // 判定下标为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;
}

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());
        }
    }
}

• 路径压缩

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();
}

树的顺序存储结构

带右链的先根次序表示

• 3个域：每个结点包括本身数据以及两个表示结构信息的ltag和rlink域

• rlink是右指针，指向结点的下一个兄弟，即树或森林所对应的二叉树中结点的右子结点。ltag是一个标记位，结点是叶结点，即对应的二叉树中没有左子结点时，ltag为1，否则为0

带双标记的先根次序表示

• 3个域：本身数据以及两个标记位ltag和rtag

• 由先根次序以及ltag、rtag两个标记位就可以确定树“左子/右兄”链表中的结点llink和rlink值

• 需要用到栈结构：扫描到一个rtag为0的结点就将其进栈；扫描到一个ltag为1的结点就从栈顶弹出一个结点并为其设置rlink

• 操作步骤：

  1. rtag=0就入栈，树一直往左走
  2. 直到碰到ltag=1，从栈顶弹出元素，并给这个元素加上右链链接下一个元素

• 带双标记位先根次序树构造算法

template<class T>
class DualTagTreeNode 
{ // 双标记位先根次序树结点类
    public:
        T info; // 结点数据信息
        int ltag, rtag; // 左、右标记
        DualTagTreeNode(); // 构造函数
        virtual ~DualTagTreeNode(); 
};

template <class T>
Tree<T>::Tree(DualTagTreeNode<T> *nodeArray, int count) 
{
    // 利用带双标记位的先根次序表示构造左孩子右兄弟表示的树
    using std::stack; // 使用STL中的栈
    stack<TreeNode<T>* > aStack;
    TreeNode<T> *pointer = new TreeNode<T>; // 准备建立根结点
    root = pointer;
    for (int i = 0; i < count-1; i++) 
    { // 处理一个结点
        pointer->setValue(nodeArray[i].info); // 结点赋值
        if (nodeArray[i].rtag == 0) // 若右标记为0则将结点压栈
            aStack.push(pointer);
        else pointer->setSibling(NULL); // 右标记为1，则右兄弟指针为空
        TreeNode<T> *temppointer = new TreeNode<T>; // 预先准备下一个
        if (nodeArray[i].ltag == 0) // 左标记为0，则设置孩子结点
            pointer->setChild(temppointer);
        else 
        { // 若左标记为1
            pointer->setChild(NULL); // 孩子指针设为空
            pointer = aStack.top(); // 取栈顶元素
            aStack.pop();
            pointer->setSibling(temppointer); 
        } // 为栈顶设置一个兄弟结点
        pointer = temppointer; 
    }
    pointer->setValue(nodeArray[count-1].info); // 处理最后一个结点
    pointer->setChild(NULL); pointer->setSibling(NULL); 
}

带度数的后根次序表示

• 2个域：info用于存放结点的数据，degree用于存放结点的度数

• 不包括指针，但仍能反映树的结构。带度数的后根次序表示转化成森林：

  1. 从从左至右扫描，度数为0的结点是叶子结点
  2. 遇到度数非0(k)的结点时，则排在结点之前且离他最近的k个子树的根就是该结点的k个子结点，并将其视为一个整体

带双标记的层次次序表示

• 3个域：info是结点的数据域；当结点没有左子结点时标记位ltag为1，否则为0；当结点没有下一个兄弟时标记位rtag为1，否则为0

• 需要用到队列结构：当一个结点的ltag值为0，应该将其加入队列中。遇到rtag为1的结点后，取出队列中第一个元素，将其llink指向下一个元素

K叉树

• K叉树T是具有下列性质的有线结点集：

  1. 集合可以为空
  2. 非空集合是由一个根结点 root 及 K 棵互不相交的 K 叉树构成。其余结点被划分成 T0，T1，…，TK - 1（K ≥ 1）个子集，每个子集都是 K 叉树，使得T = {R， T0，T1 ，…，TK - 1}

• K 叉树的各分支结点都有 K 个子结点

• 满K叉树和完全K叉树与满二叉树和完全二叉树是类似的

• 也可以把完全K叉树存储在一个数组中

---

第六章 树 OJ作业

1:宗教信仰

/*描述
世界上有许多宗教，你感兴趣的是你学校里的同学信仰多少种宗教。
你的学校有n名学生（0 < n <= 50000），你不太可能询问每个人的宗教信仰，因为他们不太愿意透露。
但是当你同时找到2名学生，他们却愿意告诉你他们是否信仰同一宗教，你可以通过很多这样的询问估算学校里的宗教数目的上限。
你可以认为每名学生只会信仰最多一种宗教。
输入
输入包括多组数据。
每组数据的第一行包括n和m，0 <= m <= n(n-1)/2，其后m行每行包括两个数字i和j，表示学生i和学生j信仰同一宗教，学生被标号为1至n。输入以一行 n = m = 0 作为结束。
输出
对于每组数据，先输出它的编号（从1开始），接着输出学生信仰的不同宗教的数目上限。
样例输入
10 9
1 2
1 3
1 4
1 5
1 6
1 7
1 8
1 9
1 10
10 4
2 3
4 5
4 8
5 8
0 0
样例输出
Case 1: 1
Case 2: 7*/

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

class Unionfind
{
public:
    vector<int> parent;
    vector<int> height;
    Unionfind(int n)
    {
        parent.resize(n);
        for (int i = 0; i < n; i++)
        {
            parent[i] = i; // 初始化成自己的父结点
        }
        height.resize(n, 0);
    }
    int find(int x)
    {
        if (parent[x] != x)
        {
            parent[x] = find(parent[x]); // 路径压缩
        }
        return parent[x];
    }

    void unionsets(int x, int y)
    {
        int rootX = find(x);
        int rootY = find(y);
        if (rootX != rootY)
        {
            if (height[rootX] > height[rootY])
            {
                parent[rootY] = rootX;
            }
            else if (height[rootX] < height[rootY])
            {
                parent[rootX] = rootY;
            }
            else
            {
                parent[rootY] = rootX;
                height[rootX]++;
            }
        }
    }
};

int main()
{
    int n, m, index = 1;
    while (cin >> n >> m)
    {
        if (n == 0 && m == 0)
        {
            return 0;
        }
        Unionfind a(n);
        for (int k = 0; k < m; k++)
        {
            int i, j;
            cin >> i >> j;
            a.unionsets(i - 1, j - 1);
        }
        int total = 0;
        for (int i = 0; i < n; ++i)
        {
            if (a.find(i) == i)
            {
                total++;
            }
        }
        cout << "Case " << index++ << ": " << total << endl;
    }
    return 0;
}

2:发现它，抓住它

/*描述
一个城市中有两个犯罪团伙A和B，你需要帮助警察判断任意两起案件是否是同一个犯罪团伙所为，警察所获得的信息是有限的。
假设现在有N起案件（N<=100000），编号为1到N，每起案件由团伙A或团伙B所为。
你将按时间顺序获得M条信息（M<=100000），这些信息分为两类：
1. D [a] [b]
其中[a]和[b]表示两起案件的编号，这条信息表明它们属于不同的团伙所为
2. A [a] [b]
其中[a]和[b]表示两起案件的编号，这条信息需要你回答[a]和[b]是否是同一个团伙所为
注意你获得信息的时间是有先后顺序的，在回答的时候只能根据已经接收到的信息做出判断。
输入
第一行是测试数据的数量T（1<=T<=20）。
每组测试数据的第一行包括两个数N和M，分别表示案件的数量和信息的数量，其后M行表示按时间顺序收到的M条信息。
输出
对于每条需要回答的信息，你需要输出一行答案。如果是同一个团伙所为，回答"In the same gang."，
如果不是，回答"In different gangs."，
如果不确定，回答”Not sure yet."。
样例输入
1
5 5
A 1 2
D 1 2
A 1 2
D 2 4
A 1 4
样例输出
Not sure yet.
In different gangs.
In the same gang.*/

#include <iostream>
#include <string>
#include <vector>

using namespace std;
int n, m, i, j, k = 0, t, w, flag, x, y, z, sum;
string s1, s2, s;
int tree[1000010], relative[1000010];

int head(int x)
{
    return x == tree[x] ? x : tree[x] = head(tree[x]);
}

int main()
{
    while (cin >> k)
    {
        while (k--)
        {
            cin >> n >> m;
            for (i = flag = 0, t = w = -1; i <= n; i++)
                tree[i] = i, relative[i] = 0;
            for (i = 0; i < m; i++)
            {
                cin >> s >> x >> y;
                x = head(x);
                y = head(y);
                if (s == "D")
                {
                    int a = relative[x], b = relative[y];
                    if (a)
                    {
                        a = head(a);
                        if (a != y)
                            tree[a] = y;
                    }
                    if (b)
                    {
                        b = head(b);
                        if (b != x)
                            tree[b] = x;
                    }
                    relative[x] = y;
                    relative[y] = x;
                }
                else
                {
                    if (x == y)
                        cout << "In the same gang." << endl;
                    else if (relative[x] == y)
                        cout << "In different gangs." << endl;
                    else
                        cout << "Not sure yet." << endl;
                }
            }
        }
    }
}

3:树的转换

/*描述
我们都知道用“左儿子右兄弟”的方法可以将一棵一般的树转换为二叉树，如：
    0                             0
  / | \                          /
 1  2  3       ===>             1
   / \                           \
  4   5                           2
                                 / \
                                4   3
                                 \
                                  5
现在请你将一些一般的树用这种方法转换为二叉树，并输出转换前和转换后树的高度。
输入
输入包括多行，最后一行以一个#表示结束。
每行是一个由“u”和“d”组成的字符串，表示一棵树的深度优先搜索信息。
比如，dudduduudu可以用来表示上文中的左树，因为搜索过程为：
0 Down to 1 Up to 0 Down to 2 Down to 4 Up to 2 Down to 5 Up to 2 Up to 0 Down to 3 Up to 0。
你可以认为每棵树的结点数至少为2，并且不超过10000。
输出
对于每棵树，按如下格式输出转换前和转换后树的高度：
Tree t: h1 => h2
其中t是树的编号（从1开始），h1是转换前树的高度，h2是转换后树的高度。
样例输入
dudduduudu
ddddduuuuu
dddduduuuu
dddduuduuu
#
样例输出
Tree 1: 2 => 4
Tree 2: 5 => 5
Tree 3: 4 => 5
Tree 4: 4 => 4*/

#include <iostream>
#include <cstring>
#include <stack>


using namespace std;

const int MAX_NODE = 100005;

char s[MAX_NODE * 2];

int main()
{
    int cnt = 0;
    while (cin.getline(s, MAX_NODE * 2))
    {
        if (s[0] == '#')
            break;

        int n = strlen(s);
        int d = 0;
        int tree_dep = 0, btree_dep = 0;

        /* general tree */
        for (int i = 0; i < n; ++i)
        {
            int add = s[i] == 'd' ? 1 : -1;
            d += add;
            tree_dep = max(d, tree_dep);
        }

        /* binary tree */
        stack<int> fa;
        d = 0;
        for (int i = 0; i < n; ++i)
        {
            if (s[i] == 'd')
            {
                fa.push(d);
                d += 1;
            }
            else
            {
                if (s[i + 1] == 'd')
                    d += 1, ++i;
                else
                {
                    d = fa.top();
                    fa.pop();
                }
            }
            btree_dep = max(d, btree_dep);
        }

        /* print result */
        printf("Tree %d: %d => %d\n", ++cnt, tree_dep, btree_dep);
    }

    return 0;
}

---