第3关：打印二叉树

任务描述

本关任务：请你实现 tree.cpp 里的DispBTree(BTNode *b)函数，完成二叉树的输出。

相关知识

下面主要介绍几种二叉树的常规操作： 创建二叉树：CreateBTree(*b,*str) 假设用括号表示法，表示二叉树字符串 str 是正确的，用 ch 扫描 str ，其中只有 4 类字符，其处理方式如下：

ch='(': 表示前面刚创建的结点 p 存在孩子结点,需要将其进栈作为栈顶结点,以便建立它和它的孩子结点之间的关系（如果一个结点刚创建完毕，其后一个字符不不是 ‘(’ 表示该结点是叶子结点不需要进栈）。然后开始处埋该结点的左孩子，置 k=1 (表示其后创建的结点将作为这个栈顶结点的左孩子结点）。

ch ')': 表示以栈顶结点为根结点的子树创建完毕，将其退栈。

ch ',': 表示开始处理栈顶结点的右孩子结点 ,置 k=2 （表示其后创建的结点将作为当前栈顶结点的右孩子结点）。

如此循环知道 str 处理完毕。算法中使用一个栈 St 保存双亲结点，top 为栈顶指针， k 指定其后处理的结点是双亲结点（栈顶结点）的左孩子（k=1）还是右孩子（k=2）。 结构体定义如下：

1. #define MaxSize 50
2. typedef char ElemType;
3. typedef struct node
4. {
5. ElemType data; //数据元素
6. struct node *lchild; //指向左孩子结点
7. struct node *rchild; //指向右孩子结点
8. }BTNode;

对应算法如下：

1. //创建二叉树
2. void CreateBtree(BTNode *&b,char *str)
3. {
4. BTNode *St[MaxSize],*p;//St数组作为顺序栈
5. int top=-1,k,j=0;//top作为栈顶指针
6. char ch;
7. b=NULL;//初始时二叉链为空
8. ch=str[j];
9. while(ch!='\0')
10. {
11. switch (ch)
12. {
13. case '(':top++;St[top]=p;k=1;break; //处理左孩子
14. case ')':top--;break; //栈顶的子树处理完毕
15. case ',':k=2;break; //开始处理右孩子
16. default:
17. p=(BTNode*)malloc(sizeof(BTNode)); //创建一个结点由p指向它
18. p->data=ch; //存放结点值
19. p->lchild=p->rchild=NULL; //左右指针都置为空
20. if(b==NULL) //若尚未建立根结点
21. {
22. b=p; //b所指结点作为根结点
23. }
24. else //已建立二叉树根结点
25. {
26. switch(k)
27. {
28. case 1:St[top]->lchild=p;break; //新建结点作为栈顶左孩子
29. case 2:St[top]->rchild=p;break; //新建结点作为栈顶右孩子
30. }
31. }
32. }
33. j++; //继续扫描str
34. ch=str[j];
35. }
37. }

销毁二叉树：DestroyBTree(&b): 设 f(b) 的功能是释放二叉树中的所有结点分配的空间，其递归模型如下：

1. f(b)≡不做任何事 若b=NULL;
2. f(b)≡f(b->lchild);f(b->rchild); 其他情况

对应的递归算法如下：

1. //销毁树
2. void DestroyBTree(BTNode *&b)
3. {
4. if(b!=NULL)
5. {
6. DestroyBTree(b->lchild);
7. DestroyBTree(b->rchild);
8. free(b);
9. }
10. }

图1 样例输入表示的二叉树

编程要求

请你实现 tree.cpp 里的DispBTree(BTNode *b)函数，完成二叉树的输出。

输入的是一个字符串 str, str 是一棵树的括号表示法，用 CreateBTree(*b,*str)创建一棵二叉树 b ，然后调用 DispBTree(BTNode *b)将树以括号表示法进行输出，最后调用DestroyBTree(&b)销毁树释放空间。 测试代码如下： main.cpp:

1. #include "tree.h"
2. #include <stdio.h>
3. #include <stdlib.h>
4. int main()
5. {
6. BTNode *b;
7. char str[100];
8. scanf("%s",str);
9. CreateBtree(b, str);
10. DispBTree(b);
11. printf("\n");
12. DestroyBTree(b);
13. return 0;
14. }

测试说明

本关的测试过程如下： 1. 平台编译 step3/main.cpp ; 2. 平台运行该可执行文件，并以标准输入方式提供测试输入； 3. 平台获取该可执行文件的输出，然后将其与预期输出对比，如果一致则测试通过；否则测试失败。

样例输入： A(B(D(,G)),C(E,F))

样例输出: A(B(D(,G)),C(E,F))

参考资料

数据结构（李春葆版）

---

开始你的任务吧，祝你成功！

最后通关代码：

#include "tree.h"

#include <stdio.h>

#include <stdlib.h>

//创建二叉树

void CreateBTree(BTNode *&b,char *str)

{

    BTNode *St[MaxSize],*p;//St数组作为顺序栈

    int top=-1,k,j=0;//top作为栈顶指针

    char ch;

    b=NULL;//初始时二叉链为空

    ch=str[j];

    while(ch!='\0')

    {

        switch (ch)

        {

            case '(':top++;St[top]=p;k=1;break; //处理左孩子

            case ')':top--;break;               //栈顶的子树处理完毕

            case ',':k=2;break;                 //开始处理右孩子

            default:

                p=(BTNode*)malloc(sizeof(BTNode));  //创建一个结点由p指向它

                p->data=ch;                         //存放结点值

                p->lchild=p->rchild=NULL;           //左右指针都置为空

                if(b==NULL)                         //若尚未建立根结点

                {

                    b=p;                            //b所指结点作为根结点

                }

                else                                //已建立二叉树根结点

                {

                    switch(k)

                    {

                        case 1:St[top]->lchild=p;break;     //新建结点作为栈顶左孩子

                        case 2:St[top]->rchild=p;break;     //新建结点作为栈顶右孩子

                    }

                }

        }

        j++;                                                //继续扫描str

        ch=str[j];

    }

   

}

//销毁树

void DestroyBTree(BTNode *&b)

{

    if(b!=NULL)

    {

        DestroyBTree(b->lchild);

        DestroyBTree(b->rchild);

        free(b);

    }

}

//输出树

void DispBTree(BTNode *b)

{

    /********** Begin **********/

if(b!=NULL)

{

    printf("%c",b->data);

    if(b->lchild!=NULL||b->rchild!=NULL)

    {

        printf("(");

        DispBTree(b->lchild);

        if(b->rchild!=NULL)

        printf(",");

        DispBTree(b->rchild);

        printf(")");

    }

}

    /********** End **********/    

}

第4关：遍历二叉树

任务描述

本关任务：请你实现 tree.cpp 里的PreOrder(b),InOrder(b),PostOrder(b)函数，分别完成二叉树的先序遍历、中序遍历和后序遍历并输出先序序列、中序序列和后序序列。

相关知识

二叉树的遍历是指按照一定的次序访问二叉树中的所有结点，并且每个结点仅被访问一次的过程。 它是二叉树最基本的运算，是二叉树中所有其他运算实现的基础。

一棵二叉树由 3 个部分（即根结点、左子树和右子树）构成 、可以从任何部分开始遍历。所以有 3!=6 种遍历方法 。若规定子树的遍历总是先左后右（先右后左与之对称，则对空二叉树，可得到以下 3 种递归的遍历方法，即先序遍历、中序遍历和后序遍历。另外，还有一种常见的层次遍历方法。

图1 一棵二叉树

先序遍历二叉树的过程如下： (1) 访问根结点； (2) 先序遍历左子树； (3) 先序遍历右子树； 如图 1 ，先序遍历的结果是 ABDGCEF 。

中序遍历二叉树的过程如下： (1) 中序遍历左子树； (2) 访问根结点； (3) 中序遍历右子树； 如图 1 ，中序遍历的结果是 DGBAECF 。

后序遍历二叉树的过程如下： (1) 后序遍历左子树； (2) 后序遍历右子树； (3) 访问根结点； 如图 1 ，后序遍历的结果是 GDBEFCA 。

层次遍历二叉树不是递归算法，其过程如下： (1) 访问根结点（第 1 层）； (2) 从左到右访问第 2 层的所有结点； (3) 从左到右访问第 3 层的所有结点，...，从左到右访问第 h 层的所有结点；。 如图 1 ，层次遍历的结果是 ABCDEFG 。

图1 样例输入表示的二叉树

编程要求

请你实现 tree.cpp 里的PreOrder(b),InOrder(b),PostOrder(b)函数，分别完成二叉树的先序遍历、中序遍历和后序遍历并输出先序序列、中序序列和后序序列。 输入的是一个字符串 str, str 是一棵树的括号表示法，用 CreateBTree(*b,*str)创建一棵二叉树 b ，然后调用 PreOrder(b) , InOrder(b) , PostOrder(b) 分别输出二叉树的先序遍历、中序遍历和后序遍历的结果（即样例输出的三行），最后调用DestroyBTree(&b)销毁树释放空间。

main.cpp:

1. #include "tree.h"
2. #include <stdio.h>
3. #include <stdlib.h>
4. int main()
5. {
6. BTNode *b;
7. char str[100];
8. scanf("%s",str);
9. CreateBtree(b, str);
10. PreOrder(b);
11. printf("\n");
12. InOrder(b);
13. printf("\n");
14. PostOrder(b);
15. printf("\n");
16. DestroyBTree(b);
17. return 0;
18. }

测试说明

本关的测试过程如下： 1. 平台编译 step4/main.cpp ; 2. 平台运行该可执行文件，并以标准输入方式提供测试输入； 3. 平台获取该可执行文件的输出，然后将其与预期输出对比，如果一致则测试通过；否则测试失败。

样例输入： A(B(D(,G)),C(E,F))

样例输出: ABDGCEF DGBAECF GDBEFCA

参考资料

数据结构（李春葆版）

---

开始你的任务吧，祝你成功！

最后通关代码：

#include "tree.h"

#include <stdio.h>

#include <stdlib.h>

//先序遍历

void PreOrder(BTNode *b)

{

    /********** Begin **********/

if(b){

 printf("%c", b->data);

PreOrder(b->lchild);

PreOrder(b->rchild);

}    

    /********** End**********/

}

//中序遍历

void InOrder(BTNode *b)

{

    /********** Begin **********/

if(b){

InOrder(b->lchild);

printf("%c", b->data);

InOrder(b->rchild);

}    

    /********** End **********/

}

//后续遍历

void PostOrder(BTNode *b)

{

    /********** Begin **********/

 if(b){

PostOrder(b->lchild);

PostOrder(b->rchild);

printf("%c", b->data);

}    

    /********** End **********/

}

第5关：由双遍历序列构造二叉树

任务描述

本关任务：请你实现 tree.cpp 里的BTNode *CreateBT1(char *pre,char *in,int n),BTNode *CreateBT2(char *post,char *in,int n)函数，分别根据二叉树的先序和中序得出二叉树以及根据中序和后序得出二叉树。

相关知识

假设二叉树的每个结点值为单个字符，而且所有结点值均不相同，同一棵二叉树具有唯一先序序列、中序序列和后序序列，但是不同的二叉树可以有相同的先序序列、中序序列、和后序序列。例如，图 1 中的二叉树都具有相同的先序序列 ABC ，图 2 中的二叉树都具有相同的中序序列 ACB ，图 3 中的二叉树都具有相同的后序序列 CBA 。

图1

图2

图3

显然，仅仅由先序序列、中序序列和后序序列中任意一个都无法确定这棵二叉树的树形，但是同时知道先序序列和中序序列或者同时知道中序序列和后序序列都可以唯一的确定一棵树。注意：同时知道中序序列和后序序列不能同时确定一棵树。证明略。 例如某二叉树的先序序列为ABDGCEF、中序序列为DGBAECF，那我们可以确定该树的树形如图 4 所示，构造过程如图 5 所示。或者我们知道某二叉树的中序序列为DGBAECF，后序序列为GDBEFCA那我们也可以唯一的确定该树为图 4 ，构造过程如图 6 。

图4

图5

图6

编程要求

请你实现 tree.cpp 里的BTNode *CreateBT1(char *pre,char *in,int n),BTNode *CreateBT2(char *post,char *in,int n)函数，分别根据二叉树的先序和中序得出二叉树以及根据中序和后序得出二叉树。 输入的是三个字符串 pre,in,post, str 分别代表一棵树的先序遍历序列，中序遍历序列和后序遍历序列，调用 CreateBT1(pre,in,n)根据二叉树的先序和中序序列得出二叉树 b1，调用CreateBT2(post,in,n)得出二叉树b2，然后调用DispBTree(b)分别输出二叉树的括号表示法，最后销毁两棵树。值得注意的是，调用两个函数生成的两棵树是相同的。

main.cpp:

1. #include "tree.h"
2. #include <stdio.h>
3. #include <stdlib.h>
4. #include <string.h>
5. int main()
6. {
7. BTNode *b1,*b2;
8. int n;
9. char pre[MaxSize],in[MaxSize],post[MaxSize];
10. scanf("%s",pre);
11. scanf("%s",in);
12. scanf("%s",post);
13. n=strlen(pre);
14. b1=CreateBT1(pre,in,n);
15. b2=CreateBT2(post,in,n);
16. DispBTree(b1);
17. printf("\n");
18. DispBTree(b2);
19. printf("\n");
20. DestroyBTree(b1);
21. DestroyBTree(b2);
22. return 0;
23. }

测试说明

本关的测试过程如下： 1. 平台编译 step5/main.cpp ; 2. 平台运行该可执行文件，并以标准输入方式提供测试输入； 3. 平台获取该可执行文件的输出，然后将其与预期输出对比，如果一致则测试通过；否则测试失败。

样例输入： ABDGCEF DGBAECF GDBEFCA

样例输出: A(B(D(,G)),C(E,F)) A(B(D(,G)),C(E,F))

参考资料

数据结构（李春葆版）

---

开始你的任务吧，祝你成功！

最后通关代码：

#include "tree.h"

#include <stdio.h>

#include <stdlib.h>

//由先序序列和中序序列构造二叉树

BTNode *CreateBT1(char *pre,char *in,int n)

{

    //pre存放先序序列，in存放中序序列，n为二叉树的结点个数

    //算法执行后返回构造二叉链的根结点

    /********** Begin **********/

BTNode *s;

    char *p;

    int k;

    if(n<=0) return NULL;

    s=(BTNode *)malloc(sizeof(BTNode));

    s->data=*pre;

    for(p=in;p<in+n;p++)

    if(*p==*pre)

    break;

    k=p-in;

    s->lchild=CreateBT1(pre+1,in,k);

    s->rchild=CreateBT1(pre+k+1,p+1,n-k-1);

        return s;    

    /********** End **********/

}

//由中序序列和后序序列构造二叉树

BTNode *CreateBT2(char *post,char *in,int n)

{

    //post存放后序序列，in存放中序序列，n为二叉树的结点个数

    //算法执行后返回构造二叉链的根结点

    /********** Begin **********/

BTNode *b; char r, *p; int k;

    if(n<=0) return NULL;

    r = *(post+n-1);

    b=(BTNode *)malloc(sizeof(BTNode));

    b->data=r;

    for(p=in;p<in+n;p++)

    if(*p==r) break;

    k = p-in;

    b->lchild=CreateBT2(post,in,k);

    b->rchild=CreateBT2(post+k,p+1,n-k-1);

    return b;    

    /********** End **********/

}

第6关：线索二叉树

任务描述

本关任务：请你实现 tree.cpp 里的TBTNode *CreateThread(TBTNode *b)函数，生成一棵线索二叉树。

相关知识

对于具有 n 个结点的二叉树，采用二叉链存储结构时，每个结构有两个指针域，总共有 2n 个指针域，又由于只有 n−1 个结点被有效指针域所指向，则共有 2n−(n−1)=n+1 个空指针域。 遍历二叉树的结果是一个结点的线性序列，可以利用这些空链域存放指向结点的前驱结点和后继结点的地址。其规定是当某个结点的左指针为空时，令该指针指向这个线性序列中该结点的前驱结点；当某结点的右指针为空时，令该指针指向这个线性序列中该结点的后继结点，这样指向该线性序列中的“前驱结点”和“后继结点”称为线索。 创建线索的过程称为线索化。线索化的二叉树称为线索二叉树。由于遍历方式不同，产生的遍历线性序列也不同，会得到相应的线索二叉树。一般有先序线索二叉树、中序线索二叉树和后序线索二叉树。创建线索二叉树的目的就是提高该遍历过程的效率。 那么，在线索二叉树中如何区分指向的是左孩子结点还是前驱结点，右指针指向的是右孩子还是右孩子结点呢？为此，在结点的存储结构上增加两个标志位来区分这两种情况：

这样每个结点的存储结构如下：

在某种遍历方式的线索二叉树中，若开始结点 p 没有左孩子，将 p 结点的左指针改为线索，对其指针仍为空；若最后结点 q 没有右孩子，将 q 结点的右指针改为线索，其右指针仍为空。对于其他结点 r ，若它没哟右左孩子，将左指针改为指向前驱结点的非空线索；若它没有右孩子，将右指针改为后继结点的非空线索。 为了使创建二叉树的算法设计方便，为线索二叉树中再增加一个头结点。头结点的 data 域为空；lchild 指向无线索时的根结点，ltag 为 0 ；rtag 指向按某种方式遍历二叉树时的最后一个结点，rtag 为 1 。 如图 3 是图 2 的中序线索二叉树。

图2

图3

为了实现线索二叉树，将前面二叉树结点的类型声明修改如下：

1. #define MaxSize 50
2. typedef char ElemType;
3. typedef struct node
4. {
5. ElemType data; //结点数据域
6. int ltag,rtag; //增加的线索标记
7. struct node *lchild; //左孩子或线索指针
8. struct node *rchild; //右孩子或线索指针
9. }TBTNode;

编程要求

本关任务：请你实现 tree.cpp 里的TBTNode *CreateThread(TBTNode *b)函数，生成一棵线索二叉树，最后返回线索二叉树的根结点。 输入的是一棵用括号表示法表示的二叉树字符串 str ，首先经过 CreateTBTNode(b,str) 创建树并调用 DispTBTNode(b) 输出树作为输出的第一行，其次用 CreateThread(b) 将上述的树线索化，最后调用 ThInOrder(tb) 遍历线索二叉树并输出，作为预期输出的第 2 行。 在tree.cpp文件中有 3 个函数, Thread(b) 是对二叉树进行中序线索化， CreateThread(b) 是中序线索化二叉树，ThInOrder(tb) 是遍历线索二叉树。

测试文件如下： main.cpp:

1. #include <stdio.h>
2. #include <stdlib.h>
3. #include "tree.h"
4. int main()
5. {
6. TBTNode *b,*tb;
7. char str[MaxSize];
8. scanf("%s",str);
9. CreateTBTNode(b,str);
10. DispTBTNode(b);
11. printf("\n");
12. tb=CreateThread(b);
13. ThInOrder(tb);
14. printf("\n");
15. return 0;
16. }

测试说明

本关的测试过程如下： 1. 平台编译 step5/main.cpp ; 2. 平台运行该可执行文件，并以标准输入方式提供测试输入； 3. 平台获取该可执行文件的输出，然后将其与预期输出对比，如果一致则测试通过；否则测试失败。

样例输入： A(B(D(,G)),C(E,F))

样例输出: A(B(D(,G)),C(E,F)) DGBAECF

参考资料

数据结构（李春葆版）

---

开始你的任务吧，祝你成功！

最后通关代码：

 #include <stdio.h>

#include <stdlib.h>

#include "tree.h"

TBTNode *pre;                   //全局变量

//对二叉排序树进行线索化

void Thread(TBTNode *&p)

{

    if(p!=NULL)

    {

        Thread(p->lchild);      //左孩子线索化

        if(p->lchild==NULL)     //左孩子不存在，进行前驱结点线索化

        {

            p->lchild=pre;      //建立当前结点的前驱结点线索

            p->ltag=1;

        }

        else

        {

            p->ltag=0;          //p结点的左子树已线索化

        }

        if(pre->rchild==NULL)   //对pre的后继结点线索化

        {

            pre->rchild=p;      //建立前驱结点的后继结点线索

            pre->rtag=1;

        }

        else

        {

            pre->rtag=0;

        }

        pre=p;

        Thread(p->rchild);      //右子树线索化

    }

}

//中序线索化二叉树

TBTNode *CreateThread(TBTNode *b)

{

    /********** Begin **********/

TBTNode *root;

root=(TBTNode *)malloc(sizeof(TBTNode));

root->ltag=0;root->rtag=1;

root->rchild=b;

if(b==NULL)

root->lchild=root;

else

{

root->lchild=b;

pre=root;

Thread(b);

pre->rchild=root;

pre->rtag=1;

root->rchild=pre;

}

return root;

   

/********** End **********/

}

//遍历线索化二叉树

void ThInOrder(TBTNode *tb)

{

    TBTNode *p=tb->lchild;                      //p指向根结点

    while(p!=tb)

    {

        while(p->ltag==0)p=p->lchild;           //找开始结点

        printf("%c",p->data);                   //访问开始结点

        while(p->rtag==1&&p->rchild!=tb)

        {

            p=p->rchild;

            printf("%c",p->data);

        }

        p=p->rchild;

    }

}

第8关：树与等价问题

任务描述

本关任务：请你实现 tree.cpp 里的void UNION(UFSTree t[],int x,int y)函数，实现查集，解决下面这个问题： 对于亲戚关系问题，现给出一些亲戚关系的信息，如 Marry、Tom 是亲戚、 Tom 、Ben 是亲戚等，需要从这些信息中推出 Marry、Ben 是否为亲戚。

相关知识

等价关系是现实世界中广泛存在的一种关系。对于集合 S 中的关系 R , 若具有自反 、对称和传递性，则 R 是一个等价关系。由等价关系 R 可以产生集合 S 的等价类，可以采用并查集高效地求解等价类问题。

并查集

并查集支持查找一个元素所属的集合以及两个元素各自所属的集合的合并等运算。当给出两个元素的 个无序对 (a,b) 时，需要快速“合并" a 和 b 分别所在的集合，这期间需要 反复 “查找“ 某元素所在的集合。”并"“查”和“集" 3 个字由此而来 在这种数据类型中，n 个不同的元素被分为若干组。每组是一个集合，这种集合叫分离集合，称之为并查集。 问题终点的亲戚关系是一种典型的等价关系，将每个人抽象成为一个点（每个点用其编号唯一标识）， 假设输入数据给出 N 个人的 M 条的关系，最后询问两个人是否是亲戚关系，当两个人是亲戚的时候两点间有一条边，很自然地就得到了 N 个顶点、M 条边的图论模型，在图的一个连通块中的任意点之间都是亲戚 对于最后的提问，即判断所提问的两个顶 点是否在同一个连通块中。采用集合的思路求解： 对于每个人建立一个集合，在开始的时候集合元素是这个人本身，表示开始时不知道任何是他的亲戚，以后每次给出一个亲戚关系时就将两个集合合并，这样实时地得到了在当前状态下总的亲戚关系 如果有提问，即在当前得到的结果中两个元素是否属于集合对于样例数据的解释如表：

由表可以看出，操作是在集合的基础上进行的，没有必要保存所有的边，而且每一步得到的划分方式是动态的。 并查集的数据结构记录了一组分离的动态集合 S={S1​,S2​,⋅⋅⋅,Sk​}。每个动态集合Si​(1≤i≤k) 通过一个“代表“加以标识，该代表即为所代表的集合中的某个元素。对于集合 Si​ ，选取其中哪个元素作为代表是任意的。 对于给定的编号 1∼n 的 n 个元素，x 表示其中的一个元素，设并查集为 S ,选取其中哪个元素作为代表是任意的。 实现需要支持如下运算： (1) MAKE_SET(S,n) : 初始化并查集 S ,即 S={S1​,S2​,⋅⋅⋅,Sn​}, 每个动态集合Si​(1≤i≤n) 仅仅包含一个编号为 i 的元素，该元素作为集合 Si​ 的”代表”。 (2) FIND_SET(S, x) : 返回并查集 S 中元素 x 所在集合的代表。 (3) UNION(S,x,y): 在并查集 S 中将 x 和 y 两个元素所在的动态集合（例如 Sx​ 和 Sy​) 合并为一个新的集合 Sx​∪Sy​ 并且假设在此运算前这两个动态集合是分离的，通常以 Sx​ 或者 Sy​ 的代表作为新集合的代表。

为了方便，采用顺序方法存储森林，对于前面的求亲戚关系的例子，其中结点的类型声明如下：

1. typedef struct node
2. {
3. int data; //结点对应人的编号
4. int rank; //结点对应秩
5. int parent; //结点对应双亲下标
6. } UFSTree;

并查集算法的实现

并查集必须借助某种数据结构来实现数据结构的选择是一个重要的环节，选择不同的数据结构可能会在查找和合并的操作效率上有很大的差别。并查集的数据结构的实现方法很多，使用比较多 的有数组实现、链表实现和树实现 这里主要介绍树实现方法。 用有根树表示集合，树中的每个结点包含集合的一个元素，每棵树表示一个集合。多个集合形成 一个森林，以每棵树的树根作为集合的代表，树中每个结点有一个指向双亲结点的指针，根结点的双亲结点指针指向其自身。

在并查集中，每个分离集合对应的一棵树称为分离集合树。整个并查集也就是一个分离集合森林 。下图所示为表示前面亲戚关系中的各分离集合树，其包含 4 个集合，即{1,2,3,4} , {5,6,7},{8,9} 和{10} 分别以4,7,9 和 10 表示对应集合的编号。

显然在一棵高度较低的树中查找根结点的编号（即该集合的代表）所花的时间较少，那么如何保证构造的分离集合树较低呢？ 如果有两棵分离集合树 A 和 B , 高度分别 hA​ 和 hB​ ,若 hA​>hB​ ,应将 B 树作为 A 树的子树；否则，应将 A 树作为 B 树的子树。总之，总是将高度较小的分离集合树作为子树。得到了新的分离集合树 C 的高度 hc​ ，如以 B 树作为 A 树的子树， hc=MAX{hA​,hB​+1}。 这样合并得到的分离集合树的高度不会超过 log2​n ,是一个比较平衡的树，对应的查找与合并的时间复杂度也就稳定在 O(log2​n)。

编程要求

本关任务：请你实现 tree.cpp 里的void UNION(UFSTree t[],int x,int y)函数，实现两个子树的合并，最终实现并查集。注意：所有测试集都默认人数为 10 ,但每次给定的关系数不一样。具体描述如下： 第一行给定一个数 n 表示后面给出的 10 个人的关系个数，后面 n 行分别表示 n 组有亲戚关系的人，最后一行给出一组数，你的任务是判断最后一行的两个数或者说两个人是否为亲戚，如果是，则输出 Yes ，否则输出 No。

测试文件如下： main.cpp:

1. #include <stdio.h>
2. #include "tree.h"
3. int main()
4. {
5. int i,x,y,n,a,b;
6. UFSTree t[MaxSize];
7. int rel[M][2];
8. scanf("%d",&n);
9. for(i=0;i<n;i++)
10. {
11. scanf("%d %d",&rel[i][0],&rel[i][1]);
12. }
13. scanf("%d %d",&a,&b);
14. MAKE_SET(t); //初始化并查集树t
15. for (i=0;i<n;i++) //根据关系进行合并操作
16. UNION(t,rel[i][0],rel[i][1]);
17. x=FIND_SET(t,a);
18. y=FIND_SET(t,b);
19. if (x==y)
20. printf("Yes\n");
21. else
22. printf("No\n");
23. return 0;
24. }
25. }

测试说明

本关的测试过程如下： 1. 平台编译 step8/main.cpp ; 2. 平台运行该可执行文件，并以标准输入方式提供测试输入； 3. 平台获取该可执行文件的输出，然后将其与预期输出对比，如果一致则测试通过；否则测试失败。

样例输入：

1. 7
2. 2 4
3. 5 7
4. 1 3
5. 8 9
6. 1 2
7. 5 6
8. 2 3
9. 3 4

样例输出: Yes

参考资料

数据结构（李春葆版）

---

开始你的任务吧，祝你成功！

最后通关代码：

#include <stdio.h>

#include "tree.h"

//初始化并查集树

void MAKE_SET(UFSTree t[])

{

    int i;

    for (i=1;i<=N;i++)

    {

        t[i].data=i;                      //数据为该人的编号

        t[i].rank=0;                      //秩初始化为0

        t[i].parent=i;                    //双亲初始化指向自已

    }

}

//在x所在子树中查找集合编号

int FIND_SET(UFSTree t[],int x)

{

    if (x!=t[x].parent)                   //双亲不是自已

        return(FIND_SET(t,t[x].parent));  //递归在双亲中找x

    else

        return(x);                        //双亲是自已,返回x

}

//将x和y所在的子树合并

void UNION(UFSTree t[],int x,int y)

{

    /********** Begin **********/

x=FIND_SET(t,x);

y=FIND_SET(t,y);

if (t[x].rank>t[y].rank)

t[y].parent=x;

else

{

    t[x].parent=y;

    if (t[x].rank==t[y].rank)

    t[y].rank++;

}  

    /********** End **********/

}

第9关：最优二叉树(哈夫曼树)

任务描述

本关任务：假设用于通信的电文仅由a,b,c,d,e,f,g 几个字母组成，字母在电文中出现的频率分别为 0.07,0.19,0.02,0.06,0.32,0.03,0.210.10 , 试为这些子母设计哈夫曼编码并求出最小路径长度。 请你实现 tree.cpp 里的void CreateHT(HTNode ht[],int n)函数和void CreateHCode(HTNode ht[],HCode hcd[],int n),构造相应的哈夫曼树和哈夫曼编码。

相关知识

哈夫曼树

在许多应用中经常将树中的结点赋予一个有某种意义的数值，称此数值为该结点的权。 从根结点到该结点之间的路 径长度与该结点上权 的乘积称为结点的带权路径长度。树中所有叶子结点的带权路径长度之和称为该树的带权路径长度，通常记为： WPL=i=1∑n0​​wi​li​ 其中， n0​ 表示叶子结点的个数，wi​ 和 li​ 分别表示第 i 个叶子结点的权值和根到它之间的路径长度（即从根结点到该叶子结点的路径上经过的分支数）。 在 n0​ 个带权叶子结点构成的所有二叉树中，带权路径长度 WPL 最小的二叉树称为 哈夫曼树或最优二叉树。

那么给定 n0​ 个权值，如何构造一棵含有 个带有给定权值的叶子结点的二叉树，使其带权路径长度 WPL 最小呢？哈夫曼最早给出了一个带有一般规律的算法，称为哈夫曼算法。哈夫曼算法如下： (1) 根据给定的 n0​ 个权值 (w1​,w2​,…,wn0​​)，对应结点构成 n0​ 棵二叉树的森林 F=(T1,T2,...,Tn0​​)，其中每棵二叉树 Ti​(1≤i≤n0​) 中都只有一个带权值为 wi​的根结点，其右子树均为空。 (2) 在森林 F 中选取两棵结点的权值最小的子树分别作为左、右子树构造一棵新的 二叉树，并且置新的二叉树的根结点的权值为其左、右子树上根的权值之和。

(3) 在森林 F 中，用新得到的二叉树代替这两棵树。

(4) 重复 (2)(3) 直到 F 只含一棵树为止，这棵树便是哈夫曼树。 例如，假设仍采用上例中给定的权值 W=(1,3,5,7) 来构造一棵哈夫曼树，按照上述算法，则下图给出了一棵哈夫曼树的构造过程，它的带权路径长度为 29 。

哈夫曼编码

在数据通信中，经常需要将传送的文字转换为二进制字符 0 和 1 组成的二进制字符串，称这个过程为编码。显然，我们希望电文编码的代码长度最短。哈夫曼树可用于构造使电 文编码的代码长度最短的编码方案。 具体构造方法如下：设需要编码的字符集合为 {d1​,d2​,…,dn0​​} 各个字符在电文中出 现的次数集合为 {w1​,w2​,…,wn0​​} ，以 d1​,d2​,…,dn0​​ 作为叶子结点，以 w1​,w2​,...,wn0​​ 作为各根结点到每个叶子结点的权值构造一棵哈夫曼树，规定哈夫曼树中的左分支为 0 右分支为 1 , 则从根结点到每个叶子结点所经过的分支对应的 0 和 1 组成的序列便是该结点对应 的编码这样的编码称为哈夫曼编码 。 哈夫曼编码的实质就是使用频率越高的字符采用越短的。 构造哈夫曼树的过程如下： 第 1 步选择频率最低的 c 和 f 构造一棵二叉树，其根结点的频率为 0.05, 记为结点 d1​； 第 2 步选择频率低的 d1​ 构造二叉树 其根结点的频率为 0.11 , 记为结点d2​； 第 3 步选择频率低的 a 和 h 构造二叉树，其根结点的频率为 0.17, 记为结点 d3​； 第 4 选择频率低的 d2​ 和 d3​ 构造二叉树， 根结点的频率 0.28, 记为结点 d4​; 第 5 步选择频率低的 b 和 g 构造一棵二叉树，其根结点的频率为 0.4, 记为结点 d5​； 第 6 步选择频率低的 d4​ 和 e 构造一棵二叉树，其根结点的频率为 0.6 , 记为结点 d6​； 第 7 步选择频率低的 d5​ 和 d6​ 构造一棵二叉树，其根结点的频率为 1.0 , 记为结点 d7​； 最后构造的哈夫曼树如下图所示（树中的叶子结点用圆或椭圆表示，分支结点用矩形表示，其中的数字表示结点的频率），给所有的左分支加上 0 , 给所有的右分支加上 1 , 从而 得到各字母的哈夫曼编码如下：

这样，该棵哈夫曼树的带权路径长度 WPL=4×0.07+2×0.19+5×0.02+4×0.06+2×0.32+5×0.03+2×0.21+4×0.1=2.61

编程要求

请你实现 tree.cpp 里的void CreateHT(HTNode ht[],int n)函数和void CreateHCode(HTNode ht[],HCode hcd[],int n),构造相应的哈夫曼树和哈夫曼编码。输出为 a∼h 的哈夫曼编码和最短路径长度，格式见预期输出。

测试文件如下： main.cpp:

1. #include <stdio.h>
2. #include "tree.h"
3. #include <stdio.h>
4. #include <string.h>
5. int main()
6. {
7. int n=8,i; /*n表示初始字符串的个数*/
8. char *str[]={"a","b","c","d","e","f","g","h"};
9. double fnum[]={0.07,0.19,0.02,0.06,0.32,0.03,0.21,0.1};
10. HTNode ht[M];
11. HCode hcd[N];
12. for (i=0;i<n;i++)
13. {
14. strcpy(ht[i].data,str[i]);
15. ht[i].weight=fnum[i];
16. }
17. CreateHT(ht,n);
18. CreateHCode(ht,hcd,n);
19. DispHCode(ht,hcd,n);
20. return 0;
21. }

测试说明

本关的测试过程如下： 1. 平台编译 step9/main.cpp ; 2. 平台运行该可执行文件，并以标准输入方式提供测试输入； 3. 平台获取该可执行文件的输出，然后将其与预期输出对比，如果一致则测试通过；否则测试失败。

样例输出:

1. a: 1010
2. b: 00
3. c: 10000
4. d: 1001
5. e: 11
6. f: 10001
7. g: 01
8. h: 1011
9. 平均长度=2.61

参考资料

数据结构（李春葆版）

---

开始你的任务吧，祝你成功！

最后通关代码：

#include <stdio.h>

#include "tree.h"

#include <string.h>

void CreateHT(HTNode ht[], int n)

{

    int i, k, lnode, rnode;

    double min1, min2;

    for (i = 0; i < 2 * n - 1; i++) /*所有结点的相关域置初值-1*/

        ht[i].parent = ht[i].lchild = ht[i].rchild = -1;

    for (i = n; i < 2 * n - 1; i++) /*构造哈夫曼树*/

    {

        min1 = min2 = 1e9; // 初始化最小值为一个很大的数

        lnode = rnode = -1;

        for (k = 0; k <= i - 1; k++)

        {

            if (ht[k].parent == -1)

            {

                if (ht[k].weight < min1)

                {

                    min2 = min1;

                    rnode = lnode;

                    min1 = ht[k].weight;

                    lnode = k;

                }

                else if (ht[k].weight < min2)

                {

                    min2 = ht[k].weight;

                    rnode = k;

                }

            }

        }

        ht[lnode].parent = i;

        ht[rnode].parent = i;

        ht[i].lchild = lnode;

        ht[i].rchild = rnode;

        ht[i].weight = ht[lnode].weight + ht[rnode].weight;

    }

}

void CreateHCode(HTNode ht[], HCode hcd[], int n)

{

    int i, f, c;

    HCode hc;

    for (i = 0; i < n; i++) /*根据哈夫曼树求哈夫曼编码*/

    {

        hc.start = n;

        c = i;

        f = ht[i].parent;

        while (f != -1) /*循环直到树根结点*/

        {

            if (ht[f].lchild == c)

                hc.cd[hc.start--] = '0';

            else

                hc.cd[hc.start--] = '1';

            c = f;

            f = ht[f].parent;

        }

        hc.start++; /*start指向哈夫曼编码最开始字符*/

        hcd[i] = hc;

    }

}

void DispHCode(HTNode ht[], HCode hcd[], int n)

{

    int i, k;

    double sum = 0, m = 0;

    int j;

    for (i = 0; i < n; i++)

    {

        j = 0;

        printf("%s:\t", ht[i].data);

        for (k = hcd[i].start; k <= n; k++)

        {

            printf("%c", hcd[i].cd[k]);

            j++;

        }

        m += ht[i].weight;

        sum += ht[i].weight * j;

        printf("\n");

    }

    printf("平均长度=%g\n", 1.0 * sum / m);

}

第10关：回溯法与树的遍历

任务描述

本关任务：请你实现 tree.cpp 中的void Queens(int n)用回溯法解决 n 皇后问题。

相关知识

回溯法

回溯法实际上是一个类似穷举的搜索尝试过程，主要在搜索尝试的过程中寻找问题的解，当发现已不满足求解条件时就"回溯"（即回退），尝试其他路径，所以回溯法有通用解题法之称。

回溯法实际上是一个类似穷举的搜索尝试过程，主要在搜索尝试的过程中寻找问题的解，当发现已不满足求解条件时就"回溯"（即回退），尝试其他路径，所以回溯法有通用解题法之称。 如图 1 所示是一棵四皇后问题的解空间树，图中的每一个状态由当前放置的皇后的行、列号构成。它给出了四皇后问题的全部搜索过程，共有 18 个结点，其中标有红色 × 的结点无法继续扩展。

图1 四皇后问题的解空间树

在采用回溯法求 4 皇后的一个解时，通过深度有限遍历，从 (∗,∗,∗,∗) 到 (1,∗,∗,∗) 再 (1,3,∗,∗) ，此时无法继续，回退到 (1,4,∗,∗) ，如此等等，找到一个解 (2,4,1,3) 。如果问题是求解四皇后问题的所有解，还需按这个过程继续下去，再找到另外一个解 (3,4,1,2) ，直到所有结点访问完毕。 在采用回溯法求 4 皇后的一个解时，通过深度有限遍历，从 (∗,∗,∗,∗) 到 (1,∗,∗,∗) 再 (1,3,∗,∗) ，此时无法继续，回退到 (1,4,∗,∗) ，如此等等，找到一个解 (2,4,1,3) 。如果问题是求解四皇后问题的所有解，还需按这个过程继续下去，再找到另外一个解 (3,4,1,2) ，直到所有结点访问完毕。 解空间树通常有两种类型。当所给问题是从 n 个元素的集合 S 中找到满足某种性质的子集时，相应的解空间称为子集树，当所给问题是确定 n 个元素满足某种性质的排列时，相应的解空间树称为排列树。 一般来说，采用回溯法解题的一般步骤如下： 1.针对给定的问题确定解空间树，问题的解空间至少包含问题的一个解或者最优解； 2.确定结点的扩展搜索规则； 3.以深度优先方式搜索解空间树，并在搜索过程中可以采用剪枝函数来避免无效搜索。

求解 n 皇后问题

简单的总结 n 皇后求解规则： 1. 用数组 q[] 存放皇后的位置, (i,q[i])表示第 i 个皇后的位置， n 皇后问题的一个解是 (1,q[1]) , (2,q[2]) , (3,q[3]) ,..., (n,q[n]) ,数组的下标为 0 的元素不用； 2.先放置第 1 个皇后，然后依 2,3,4,...,n 的顺序放置其他皇后，当第 n 个皇后放置好后产生一个解。为找到所有解，此时算法还不能结束，继续试探第 n 个皇后的下一个位置。 3.第 i(i<n) 个皇后放置后，接着放置第 i+1 个皇后，在试探第 i+1 个皇后的位置都是从第一列开始的。 4.当第 i 个皇后试探了所有列都不能放置时，则回溯到第 i−1 个皇后，此时与第 i−1 个皇后的位置 (i-1,q[i-1]) 有关，如果第 i−1 个皇后的列号小于 n ，即 q[i-1]<n ，则将其移到下一列，继续试探，否则回溯到第 i−2 个皇后，依次类推。 5.若到第 1 个皇后的所有位置回溯完毕，依次类推。 6.放置第 i 个皇后应与前面已经放置的 i−1 个皇后不发生冲突。

编程要求

请你实现 tree.cpp 中的void Queens(int n)用回溯法解决 n 皇后问题。输入的是一个数字 n ，表示 n 皇后，后面的若干行是 n 皇后的坐标方案，具体格式见测试用例。

测试文件如下： main.cpp:

1. #include <stdio.h>
2. #include <stdlib.h>
3. #include "queens.h"
4. int main()
5. {
6. int n;
7. scanf("%d",&n);
8. printf("%d皇后求解如下：\n",n);
9. Queens(n);
10. return 0;
11. }

测试说明

本关的测试过程如下： 1. 平台编译 step10/main.cpp ; 2. 平台运行该可执行文件，并以标准输入方式提供测试输入； 3. 平台获取该可执行文件的输出，然后将其与预期输出对比，如果一致则测试通过；否则测试失败。

样例输入：

1. 4

样例输出:

1. 4皇后求解如下：
2. 第1个解：(1,2)(2,4)(3,1)(4,3)
3. 第2个解：(1,3)(2,1)(3,4)(4,2)

---

开始你的任务吧，祝你成功！

最后通关代码：

#include <stdio.h>

#include <stdlib.h>

#include "queens.h"

#define MAXN 20              //最多皇后个数

int q[MAXN];                 //存放各皇后所在列号

int count = 0;              //输出一个解

void dispsolution(int n)     //输出一个解

{

    printf("第%d个解：",++count);

    for(int i=1;i<=n;i++)

    {

        printf("(%d,%d)",i,q[i]);

    }

    printf("\n");

}

bool place(int i)               //测试第i行的q[i]列上能否摆放皇后

{

    int j=1;

    if(i==1)return true;

    while(j<i)                  //j=1~i-1是已放置了皇后的行

    {

        if((q[j]==q[i])||(abs(q[j]-q[i])==abs(j-i)))

        {

            //该皇后是否与以前的皇后同列，位置(j,q[j])与(i,q[i])是否同对角线

            return false;

        }

        j++;

    }

    return true;

}

void Queens(int n)                   //求解n皇后问题

{

    int i=1;                        //i表示当前行，也表示放置第i个皇后

    q[i]=0;                         //q[i]是当前列，每个新考虑的皇后的初始位置置为0列

    while(i>=1)                     //尚未回溯到头，循环

    {

        /********** Begin **********/

        while (q[i] < n) //在当前行中逐列查找可摆放的位置

        {

            q[i]++; //列号加1

            if (place(i)) //如果当前位置可以放置皇后

            {

                if (i == n) //如果是最后一行，找到一个解

                {

                    dispsolution(n); //输出解

                }

                else //继续放置下一行的皇后

                {

                    i++;

                    q[i] = 0; //下一行的初始位置置为0列

                }

            }

        }

        i--;

        /********** End **********/

    }

}

第11关：树的计数

任务描述

本关任务：一个有 n 个结点的不同形态的二叉树有多少棵？

相关知识

一般情况下，一棵具有 n 个结点的二叉树可以看成由一个根结点、一棵具有 i 个结点的左子树和一棵具有 n−i−1 个结点的右子树构成，其中 0≤i≤n−1 。由此可以得到下面的递推公式： b0​=1 bn​=i=0∑n​bi​bn−i−1​,n≥1 可以利用这个生成递推公式。 对序列 b0​,b1​,...,bn​,... 定义生成函数：B(z)=b0​+b1​z+b2​z2+...+bn​zn+...=k=0∑∞​bk​zk。 因为 对序列 b0​,b1​,...,bn​,... 定义生成函数：B(z)=b0​+b1​z+b2​z2+...+bn​zn+...=k=0∑∞​bk​zk。 因为B2(z)=b0​b0​+(b0​b1​+b1​b0​)z+(b0​b2​+b1​b1​+b2​b0​)z2+...=p=0∑∞​(i=0∑p​bi​bp​−i)zp 根据之前的递推公式得B2(z)=p=0∑∞​bp+1​zp 由此可得：z2B(z)=B(z)−1 解此二次方程得：B(z)=2z1±1−4z​​ 由初值 b0​=1，应有z→0lim​B(z)=b0​=1 所以：B(z)=2z1−1−4z​​ 利用二项展开(1−4z)21​=k=0∑∞​(21​,k)(−4z)k 当 k=0 时，上式的第一项为 1 ，所以有：B(z)=21​k=1∑∞​(21​,k)22kzk−1=m=0∑∞​(21​,m+1)(−1)m22m+1zm=1+z+2z2+5z3+14z64+42z5+... 综上可以得到： bn​=(21​,n+1)(−1)n22n+1=(n+1)!21​(21​−1)...(21​−n)​(−1)n22n+1 bn​=n+11​∙n!n!(2n)!​=n+11​C2nn​

因此，含有 n 个结点的不相似的二叉树有 n+11​C2nn​ 棵。

当然，在得到二叉树的计数后，也可以推得树的计数。在前面我们介绍过森林与二叉树的转化，可知一棵树可以转换成唯一的一棵没有右子树的二叉树，反之亦然。则具有 n 个结点有不同形态的树的数目 tn​ 和具有 n−1 个结点互不相似的二叉树的数目相同。即 tn​=bn−1​.

编程要求

根据提示，在右侧编辑器 Begin - End 部分补充代码。完成树的计数问题。 输入格式：输入文件第一行是一个正整数 n ，表示树有 n 个结点。 输出格式：输出满足条件的二树有多少棵。

样例输入：

1. 4
2. 2 1 2 1

样例输出:

1. 2

---

开始你的任务吧，祝你成功！

最后通关代码：

#include <stdio.h>

// 计算组合数C(n, k)

int combination(int n, int k) {

    if (k == 0 || k == n) {

        return 1;

    } else {

        return combination(n - 1, k - 1) + combination(n - 1, k);

    }

}

// 计算含有n个节点的不同形态的二叉树的数量

int countBinaryTrees(int n) {

    if (n <= 1) {

        return 1;

    } else {

        int count = 0;

        for (int i = 0; i < n; i++) {

            count += countBinaryTrees(i) * countBinaryTrees(n - i - 1);

        }

        return count;

    }

}

int main() {

    int n;

    scanf("%d", &n);

    int count = countBinaryTrees(n);

    printf("%d\n", count);

    return 0;

}