1、- 1 -自考 02331 数据结构重点总结(最终修订)第一章 概论1.瑞士计算机科学家沃思提出：算法+数据结构=程序。算法是对数据运算的描述，而数据结构包括逻辑结构和存储结构。由此可见，程序设计的实质是针对实际问题选择一种好的数据结构和设计一个好的算法，而好的算法在很大程度上取决于描述实际问题的数据结构。2.数据是信息的载体。数据元素是数据的基本单位。一个数据元素可以由若干个数据项组成，数据项是具有独立含义的最小标识单位。数据对象是具有相同性质的数据元素的集合。3.数据结构指的是数据元素之间的相互关系，即数据的组织形式。数据结构一般包括以下三方面内容：数据的逻辑结构、数据的存储结构、数据的运
2、算数据的逻辑结构是从逻辑关系上描述数据，与数据元素的存储结构无关，是独立于计算机的。数据的逻辑结构分类: 线性结构和非线性结构。线性表是一个典型的线性结构。栈、队列、串等都是线性结构。数组、广义表、树和图等数据结构都是非线性结构。数据元素及其关系在计算机内的存储方式，称为数据的存储结构（物理结构） 。数据的存储结构是逻辑结构用计算机语言的实现，它依赖于计算机语言。数据的运算。最常用的检索、插入、删除、更新、排序等。4.数据的四种基本存储方法: 顺序存储、链接存储、索引存储、散列存储（1）顺序存储：通常借助程序设计语言的数组描述。（2）链接存储：通常借助于程序语言的指针来描述。（3）索引存储：索
3、引表由若干索引项组成。关键字是能唯一标识一个元素的一个或多个数据项的组合。（4）散列存储：该方法的基本思想是：根据元素的关键字直接计算出该元素的存储地址。5.算法必须满足 5 个准则：输入，0 个或多个数据作为输入；输出，产生一个或多个输出；有穷性，算法执行有限步后结束；确定性，每一条指令的含义都明确；可行性，算法是可行的。算法与程序的区别：程序必须依赖于计算机程序语言，而一个算法可用自然语言、计算机程序语言、数学语言或约定的符号语言来描述。目前常用的描述算法语言有两类：类 Pascal 和类 C。6.评价算法的优劣：算法的“正确性“是首先要考虑的。此外，主要考虑如下三点： 执行算法所耗费的时
4、间，即时间复杂性； 执行算法所耗费的存储空间，主要是辅助空间，即空间复杂性； 算法应易于理解、易于编程，易于调试等，即可读性和可操作性。以上几点最主要的是时间复杂性，时间复杂度常用渐进时间复杂度表示。7.算法求解问题的输入量称为问题的规模,用一个正整数 n 表示。8.常见的时间复杂度按数量级递增排列依次为：常数阶 0(1)、对数阶 0(log2n)、线性阶 0(n)、线性对数阶0(nlog2n)、平方阶 0(n2)立方阶 0(n3)、k 次方阶 0(nk)、指数阶 0(2n)和阶乘阶 0(n!)。9.一个算法的空间复杂度 S(n)定义为该算法所耗费的存储空间，它是问题规模 n 的函数,它包括存
5、储算法本身所占的存储空间、算法的输入输出数据所占的存储空间和算法在运行过程中临时占用的存储空间。第二章 线性表1.数据的运算是定义在逻辑结构上的，而运算的具体实现是在存储结构上进行的。2.只要确定了线性表存储的起始位置，线性表中任意一个元素都可随机存取，所以顺序表是一种随机存取结构。3.常见的线性表的基本运算:(1)置空表 InitList（L） 构造一个空的线性表 L。(2)求表长 ListLength（L）求线性表 L 中的结点个数，即求表长。(3)GetNode（L，i） 取线性表 L 中的第 i 个元素。(4)LocateNode（L，x）在 L 中查找第一个值为 x 的元素，并返回该
6、元素在 L 中的位置。若 L 中没有元素的值为 x ，则返回 0 值。(5)InsertList（L，i，x）在线性表 L 的第 i 个元素之前插入一个值为 x 的新元素，表 L 的长度加 1。(6)DeleteList（L，i）删除线性表 L 的第 i 个元素，删除后表 L 的长度减 1。4.顺序存储方法：把线性表的数据元素按逻辑次序依次存放在一组地址连续的存储单元里的方法。顺序表（Sequential List）：用顺序存储方法存储的线性表称为顺序表。顺序表是一种随机存取结构,顺序表的特点是逻辑上相邻的结点其物理位置亦相邻。- 2 -顺序表中结点 ai 的存储地址: LOC（a i）= L
7、OC（a 1）+（i-1）*c 1in，5.顺序表上实现的基本运算：（1）插入：该算法的平均时间复杂度是 O(n)，即在顺序表上进行插入运算，平均要移动一半结点（n/2） 。在第 i 个位置插入一个结点的移动次数为 n-i+1（2）删除：顺序表上做删除运算，平均要移动表中约一半的结点（n-1）/2，平均时间复杂度也是 O(n)。删除第 i 个结点移动次数为 n-i6.采用链式存储结构可以避免频繁移动大量元素。一个单链表可由头指针唯一确定，因此单链表可以用头指针的名字来命名。生成结点变量的标准函数 p=( ListNode *)malloc(sizeof(ListNode)； /函数 mallo
8、c 分配一个类型为ListNode 的结点变量的空间,并将其首地址放入指针变量 p 中释放结点变量空间的标准函数 free(p)；/释放 p 所指的结点变量空间 结点分量的访问 方法二：p-data 和 p-next指针变量 p 和结点变量*p 的关系: 指针变量 p 的值结点地址, 结点变量*p 的值结点内容7.建立单链表: （1） 头插法建表：算法： p=(ListNode *)malloc(sizeof(ListNode);/生成新结点p-data=ch; /将读入的数据放入新结点的数据域中p-next=head; head=p;（2） 尾插法建表：算法： p=(ListNode *)m
9、alloc(sizeof(ListNode); /生成新结点p-data=ch; /将读入的数据放入新结点的数据域中if (head=NULL) head=p;/新结点插入空表else rear-next=p;/将新结点插到*r 之后rear=p;/尾指针指向新表尾（3） 尾插法建带头结点的单链表：头结点及作用：头结点是在链表的开始结点之前附加一个结点。它具有两个优点:由于开始结点的位置被存放在头结点的指针域中,所以在链表的第一个位置上的操作就和在表的其它位置上操作一致,无须进行特殊处理;无论链表是否为空，其头指针都是指向头结点的非空指针（空表中头结点的指针域空） ，因此空表和非空表的处理也就
10、统一了。头结点数据域的阴影表示该部分不存储信息。在有的应用中可用于存放表长等附加信息。具体算法：r=head;/ 尾指针初值也指向头结点while(ch=getchar()!=n)s=(ListNode *)malloc(sizeof(ListNode);/生成新结点s-data=ch; /将读入的数据放入新结点的数据域中r-next=s;- 3 -r=s;r-next=NULL;/终端结点的指针域置空，或空表的头结点指针域置空以上三个算法的时间复杂度均为 O(n)。8.单链表上的查找：（带头结点）（1）按结点序号查找：序号为 0 的是头结点。算法：p=head;j=0;/从头结点开始扫描wh
11、ile(p-nextj+;if(i=j) return p;/找到了第 i 个结点else return NULL;/当 i0 时，找不到第 i 个结点时间复杂度：在等概率假设下，平均时间复杂度为：为 n/2=O(n)（2）按结点值查找：具体算法：ListNode *p=head-next;/从开始结点比较。表非空，p 初始值指向开始结点while(p/扫描下一结点return p;/若 p=NULL，则查找失败，否则 p 指向值为 key 的结点时间复杂度为：O(n)9.插入运算：插入运算是将值为 x 的新结点插入到表的第 i 个结点的位置上，即插入到 ai-1与 ai之间。s=(ListN
12、ode *)malloc(sizeof(ListNode); s-data=x; s-next=p-next; p-next=s;算法的时间主要耗费在查找结点上，故时间复杂度亦为 O(n)。10.删除运算r=p-next;/使 r 指向被删除的结点 ai p-next=r-next;/将 ai从链上摘下 free(r);/释放结点 ai的空间给存储池算法的时间复杂度也是 O（n）.p 指向被删除的前一个结点。链表上实现的插入和删除运算，无须移动结点，仅需修改指针。11.单循环链表在单链表中，将终端结点的指针域 NULL 改为指向表头结点或开始结点即可。判断空链表的条件是head=head-ne
13、xt;12.仅设尾指针的单循环链表: 用尾指针 rear 表示的单循环链表对开始结点 a1和终端结点 an查找时间都是 O(1)。而表的操作常常是在表的首尾位置上进行，因此，实用中多采用尾指针表示单循环链表。判断空链表的条件为rear=rear-next;13.循环链表：循环链表的特点是无须增加存储量，仅对表的链接方式稍作改变，即可使得表处理更加方便灵活。- 4 -若在尾指针表示的单循环链表上实现，则只需修改指针，无须遍历，其执行时间是 O(1)。具体算法：LinkList Connect(LinkList A,LinkList B) /假设 A，B 为非空循环链表的尾指针LinkList p
14、=A-next;/保存 A 表的头结点位置A-next=B-next-next;/B 表的开始结点链接到 A 表尾free(B-next);/释放 B 表的头结点B-next=p;/return B;/返回新循环链表的尾指针循环链表中没有 NULL 指针。涉及遍历操作时，其终止条件就不再是像非循环链表那样判别 p 或 p-next 是否为空，而是判别它们是否等于某一指定指针，如头指针或尾指针等。在单链表中，从一已知结点出发，只能访问到该结点及其后续结点，无法找到该结点之前的其它结点。而在单循环链表中，从任一结点出发都可访问到表中所有结点，这一优点使某些运算在单循环链表上易于实现。14.双向链表
15、: 双（向）链表中有两条方向不同的链，即每个结点中除 next 域存放后继结点地址外，还增加一个指向其直接前趋的指针域 prior。双链表由头指针 head 惟一确定的。带头结点的双链表的某些运算变得方便。将头结点和尾结点链接起来，为双（向）循环链表。15.双向链表的前插和删除本结点操作双链表的前插操作void DInsertBefore(DListNode *p,DataType x)/在带头结点的双链表中，将值为 x 的新结点插入*p 之前，设pNULLDListNode *s=malloc(sizeof(DListNode);/s-data=x;/s-prior=p-prior;/s-n
16、ext=p;/p-prior-next=s;/p-prior=s;/双链表上删除结点*p 自身的操作- 5 -void DDeleteNode(DListNode *p)/在带头结点的双链表中，删除结点*p，设*p 为非终端结点p-prior-next=p-next;/p-next-prior=p-prior;/free(p); /与单链表上的插入和删除操作不同的是，在双链表中插入和删除必须同时修改两个方向上的指针。上述两个算法的时间复杂度均为 O(1)。16.顺序表和链表比较时间性能：a、线性表：经常性的查找； b、链式存储结构：经常插入删除操作；空间性能：a、对数据量大小事先能够知道的用线
17、性表； b、数据量变化较大的用链式存储结构。存储密度越大，存储空间的利用率越高。显然，顺序表的存储密度是 1，链表的存储密度肯定小于 1。第三章 栈和队列1.栈称为后进先出（Last In First Out）的线性表，简称为 LIFO 表。栈是运算受限的线性表，顺序栈也是用数组表示的。进栈操作：进栈时，需要将 S-top 加 1， S-top=StackSize-1 表示栈满“上溢“现象-当栈满时，再做进栈运算产生空间溢出的现象。退栈操作：退栈时，需将 S-top 减 1， S-topfront=Q-rear=0; 判队空: return Q-rear=Q-front; 判队满: retur
18、n (Q-rear+1)%QueueSize=Q-front; 入队 Q-dataQ-rear=x; /新元素插入队尾- 7 -Q-rear=(Q-rear+1)%QueueSize; 出队 temp=Q-dataQ-front;Q-front=(Q-front+1)%QueueSize; /循环意义下的头指针加 1return temp;取队头元素 return Q-dataQ-front;6.队列的链式存储结构简称为链队列。它是限制仅在表头删除和表尾插入的单链表。为了简化处理，在队头结点之前附加一个头结点，并设队头指针指向此结点。链队列的基本运算:（带头结点）（1） 构造空队：Q-rear
19、=Q-front；Q-rear-next=NULL;（2） 判队空：return Q-rear=Q-front;（3） 入队：QueueNode *p=(QueueNode *)malloc(sizeof(QueueNode);/申请新结点p-data=x; p-next=NULL;Q-rear-next=p; /*p 链到原队尾结点后Q-rear=p; /队尾指针指向新的尾（4） 出队：当队列长度大于 1 时，只需修改头结点指针，尾指针不变s=Q-front-next; Q-front-next=s-next; x=s-data; free(s); return x; 当队列长度等于 1 时
20、，不仅要修改头结点指针，还要修改尾指针s=Q-front-next; Q-front-next=NULL; Q-rear=Q-front;x=s-data; free(s); return x;（5） 取队头元素：return Q-front-next-data; 因为有头结点，所以用了 next和链栈类似，无须考虑判队满的运算及上溢。在出队算法中，一般只需修改队头指针。但当原队中只有一个结点时，该结点既是队头也是队尾，故删去此结点时亦需修改尾指针，且删去此结点后队列变空。7.用计算机来处理计算算术表达式问题，首先要解决的问题是如何将人们习惯书写的中缀表达式转换成后缀表达式。第四章 多维数组和
21、广义表1.数组的顺序存储方式:一般采用顺序存储方法表示数组。（1）行优先顺序 a 11,a12,a1n,a21,a22,a2n,，a m1,am2,，a mn（2）列优先顺序 a 11,a21,am1,a12,a22,am2,，a 1n,a2n,，a mnPascal 和 C 语言是按行优先顺序存储的，而 Fortran 语言是按列优先顺序存储的。按行优先顺序存储的二维数组 Amn地址计算公式LOC(aij)=LOC(a11)+(i-1)n+j-1d (注：此公式下界为 1，如下界为 0，则公式变为in+j)按列优先顺序存储的二维数组 Amn地址计算公式LOC(aij)=LOC(a11)+(j
22、-1)m+i-1d(注：此公式下界为 1，如下界为 0，则公式变为jm+i)按行优先顺序存储的三维数组 Amnp地址计算公式LOC(aijk)=LOC(a111)+(i-1)np+(j-1)p+k-1d (注：此公式下界为 1，如下界为 0，则公式变为inp+jp+k)2.为了节省存储空间，可以对矩阵中有许多值相同或值为零的元素的矩阵，采用压缩存储。特殊矩阵是指相同值的元素或零元素在矩阵中的分布有一定的规律。常见的有对称矩阵、三角矩阵。（1）对称矩阵 在一个 n 阶方阵 A 中，若元素满足下述性质： a ij=aji 0i，jn-1称为 n 阶对称矩阵，它的元素是关于主对角线对称的，所以只需要
23、存储矩阵上三角或下三角元素即可，让两个对称的元素共享一个存储空间。矩阵元素 aij和数组元素 sa【k】之间的关系是- 8 -k=i(i+1)/2+j ij 0kn(n+1)/2-1 k=j(j+1)/2+i ij 0kn(n+1)/2-1对称矩阵的地址计算公式：LOC(a ij)=LOC(sa0)+I(I+1)/2+Jd，其中 I=max(i,j)，J=min(i,j)（2）三角矩阵：以主对角线划分，三角矩阵有上三角和下三角两种。上三角矩阵是指它的下三角(不包括主角线)中的元素均为常数 c 或零；下三角矩阵的主对角线上方均为常数 c 或零。一般情况，三角矩阵的常数 c 均为零。三角矩阵的压缩
24、存储：三角矩阵中的重复元素 c 可共享一个存储空间，其余的元素正好有 n(n+1)/2 个，因此，三角矩阵可压缩存储在一维数组 san(n+1)/2+1中，其中 c 存放在数组的最后一个元素中。上三角矩阵中 aij和 sak之间的对应关系k=i(2n-i+1)/2+j-i 当 ij k=n(n+1)/2 当 ij下三角矩阵中 aij和 sak之间的对应关系k=i(i+1)/2+j 当 ij k=n(n+1)/2 当 ij三角矩阵的压缩存储结构是随机存取结构。3.稀疏矩阵:设矩阵 Amn中有 s 个非零元素，若 s 远远小于矩阵元素的总数，则称 A 为稀疏矩阵。为了节省存储单元，可用压缩存储方法
25、只存储非零元素。由于非零元素的分布一般是没有规律的，因此在存储非零元素的同时，还必须存储非零元素所在的行、列位置，所以可用三元组(i，j，a ij)来确定非零元素。稀疏矩阵进行压缩存储通常有两类方法：顺序存储(三元组表)和链式存储(十字链表)。稀疏矩阵的压缩存储会失去随机存取功能。4.广义表是线性表的推广,又称列表。广义表是 n(n0)个元素 a1，a 2，a i，a n的有限序列。其中 ai或者是原子或者是一个广义表。广义表通常用圆括号括起来，用逗号分隔其中的元素。为了区分原子和广义表，书写时用大写字母表示广义表，用小写字母表示原子。若广义表 Ls 非空(n1)，则 al是 LS 的表头，其
26、余元素组成的表(a 1，a 2，a n)称为 Ls 的表尾。广义表具有递归和共享的性质广义表的深度：一个表展开后所含括号的层数称为广义表的深度。19.广义表是一种多层次的线性结构，实际上这就是一种树形结构。广义表的两个特殊的基本运算：取表头head(Ls)和取表尾 tail(Ls).任何一个非空广义表的表头可以是原子，也可以是子表，而其表尾必定是子表。head=(a，b)=a，tail(a，b)=(b) 对非空表 A 和(y)，也可继续分解。注意:广义表()和()不同。前者是长度为 0 的空表，对其不能做求表头和表尾的运算；而后者是长度为 l 的由空表作元素的广义表，可以分解得到的表头和表尾均
27、是空表()。广义表是一种有层次的非线性结构，通常采用链式存储结构，每个元素用一个结点表示，结点由 3 个域构成，其中一个是 tag 标志位，用来区分结点是原子还是子表，当 tag 为零时结点是子表，第二个域为 slink，用以存放子表的地址；当 tag 为 1 时结点是原子，第二个域为 data，用以存放元素值。第五章 树和二叉树1.树的表示法：最常用的是树形图表示法；还有 3 种嵌套集合、凹形、广义表。树结构的基本术语 （1）结点的度(Degree) 树中的一个结点拥有的子树数称为该结点的 度(Degree) 。一棵树的度是指该树中结点的最大度数。度为零的结点称为叶子(Leaf) 或终端结点
28、。度不为零的结点称 分支结点或非终端结点。除根结点之外的分支结点统称为 内部结点。根结点又称为 开始结点。（2）路径（path）若树中存在一个结点序列 k1，k 2， ，k i，使得 ki是 ki+1的双亲(1ij)，则称该结点序列- 9 -是从 kl到 kj的一条路径(Path)。一个结点的祖先是从根结点到该结点路径上所经过的所有结点，而一个结点的子孙则是以该结点为根的子树中的所有结点。结点的层数(Level)从根起算：根的层数为 1，其余结点的层数等于其双亲结点的层数加 1。双亲在同一层的结点互为堂兄弟。树中结点的最大层数称为树的高度(Height)或深度(Depth)。若将树中每个结点的
29、各子树看成是从左到右有次序的(即不能互换)，则称该树为有序树(OrderedTree)；否则称为无序树(UnoderedTree)。若不特别指明，一般讨论的树都是有序树。森林(Forest)是 m(m0)棵互不相交的树的集合。树和森林的概念相近。删去一棵树的根，就得到一个森林；反之，加上一个结点作树根，森林就变为一棵树。3.二叉树与度数为 2 的有序树不同：在有序树中，虽然一个结点的孩子之间是有左右次序的，但是若该结点只有一个孩子，就无须区分其左右次序。而在二叉树中，即使是一个孩子也有左右之分。二叉树的性质：性质 1 二叉树第 i 层上的结点数目最多为 2i-1(i1)。例如 5 层的二叉树，
30、第 5 层上的结点数目最多为 24=16性质 2 深度为 k 的二叉树至多有 2k-1 个结点(k1)。例如深度为 5 的二叉树，至多有 25-1=31 个结点性质 3 在任意-棵二叉树中，若终端结点的个数为 n0，度为 2 的结点数为 n2，则 no=n2+1。例如一棵深度为 4 的二叉树（a） ，其终端结点数 n0为 8,度为 2 的结点树为 7，则 8=7+1，n o=n2+1 成立（b）其终端结点数 n0为 6,度为 2 的结点树为 5，则 6=5+1，n o=n2+1 成立满二叉树：一棵深度为 k 且有 2k-1 个结点的二又树称为满二叉树。满二叉树的特点：（1）每一层上的结点数都达
31、到最大值。即对给定的高度，它是具有最多结点数的二叉树。（2）满二叉树中不存在度数为 1 的结点，每个分支结点均有两棵高度相同的子树，且树叶都在最下一层上。完全二叉树：若一棵深度为 k 的二叉树，其前 k-1 层是一棵满二叉树，而最下面一层上的结点都集中在该层最左边的若干位置上，则此二叉树称为完全二叉树。特点：（1） 满二叉树是完全二叉树，完全二叉树不一定是满二叉树。（2） 在满二叉树的最下一层上，从最右边开始连续删去若干结点后得到的二叉树仍然是一棵完全二叉树。（3） 在完全二叉树中，若某个结点没有左孩子，则它一定没有右孩子，即该结点必是叶结点。性质 4 具有 n 个结点的完全二叉树的深度为。l
32、ogn +1 或 log(n+1)例，具有 100 个结点的完全二叉树的深度为:lg100 +1=7,26=64 27=128 所以 lg100=6 ,lg(100+1)=74.完全二叉树的编号特点：完全二叉树中除最下面一层外，各层都充满了结点。每一层的结点个数恰好是上一层结点个数的 2 倍。从一个结点的编号就可推得其双亲，左、右孩子等结点的编号。编号从 0 开始若 i=0，则 qi为根结点，无双亲；否则，q i的双亲编号为(i-1)/2。若 2i+1n，则 qi的左孩子的编号是 2i+1；否则，q i无左孩子，即 qi必定是叶子。若 2i+2n，则 qi的右孩子的编号是 2i+2；否则，q
33、i无右孩子。对于完全二叉树而言，使用顺序存储结构既简单又节省存储空间。但对于一般二叉树来说，采用顺序存储时，为了使用结点在数组中的相对位置来表示结点之间的逻辑关系，就必须增加一些虚结点使其成为完全二叉树的形式。5.链式存储结构: 二叉树的每个结点最多有两个孩子。用链接方式存储二叉树时，每个结点除了存储结点本身的数据外，还应设置两个指针域 lchild 和 rchild，分别指向该结点的左孩子和右孩子。结点的结构为：二叉链表是一种常用的二叉树存储结构。建立二叉链表方法：a、按广义表方法，靠近左括号的结点是在左子树上，而逗号右边结点是在右子树上。b、按完全二叉树的层次顺序建立结点。具有 n 个结点
34、的二叉链表中，共有 2n 个指针域。其中有 n-1 个用来指示结点的左、右孩子，其余的 n+1 个为空。二叉树遍历算法中的递归终止条件是二叉树为空。中序遍历的递归算法定义：(1)遍历左子树； (2)访问根结点； (3)遍历右子树。先序遍历的递归算法定义：(1)访问根结点； (2)遍历左子树； (3)遍历右子树。- 10 -后序遍历得递归算法定义：(1)遍历左子树； (2)遍历右子树； (3)访问根结点。递归工作栈中包括两项：一项是递归调用的语句编号，另一项则是指向根结点的指针。已知一棵二叉树的前序和中序遍历序列或中序和后序遍历序列，可唯一确定一棵二叉树。具体方法如下：首先根据前序或后序遍历序列
35、确定二叉树的各子树的的根，然后根据中序遍历序列确定各子树根的左右子树。6.线索二叉树：n 个结点的二叉链表必定存在 n+1 个空指针域，可以利用这些空指针域，存放指向结点在某种遍历次序下的前趋和后继结点的指针，这种指向前驱和后继结点的指针称为“线索“，这种加上线索的二叉链表称为线索链表，相应的二叉树称为线索二叉树(Threaded BinaryTree)。线索链表的结点结构：其中:ltag 和 rtag 是增加的两个标志域，用来区分结点的左、右指针域是指向其左、右孩子的指针，还是指向其前趋或后继的线索。图中的实线表示指针，虚线表示线索。 线索二叉树中，一个结点是叶结点的充要条件为：左、右标志均是 1。7.二叉树的线索化: 把对一棵二叉线索链表结构中所有结点的空指针域按照某种遍历次序加线索的过程称为线索化。和中序遍历算法一样，递归过程中对每结点仅做一次访问。因此对于 n 个结点的二叉树，线索化的算法时间复杂度为 O(n)。8.树、森林到二叉树的转换：树中每个结点最多只有一个最左边的孩子(长子)和一个右邻的兄弟。将树转换成二叉树：在所有兄弟结点之间加一道连线；对每个结点，除了保留与其长子的连线外，去掉该结点与其它孩子的连线。由于树根没有兄弟，故树转化为二叉树后，二叉树的根结点的右子树必为空。
