第7课 树与二叉树的转换

数据结构有序树转⼆叉树（树的遍历）Description计算输⼊有序树的深度和有序树转化为⼆叉树之后树的深度。

Input输⼊包含多组数据。

每组数据第⼀⾏为⼀个整数n（2<=n<=30000）代表节点的数量，接下来n-1⾏，两个整数a、b代表a是b的⽗亲结点。

Output输出当前树的深度和转化成⼆叉树之后的深度。

Sample Input51 51 35 21 4Sample Output3 4HINTAppend Code析：这个题很好说，只要遍历⼀次就能得到答案，由于要先有序树转成⼆叉树，我也没听过，我百度了⼀下怎么转，看到百度百科中有，我总结⼀下就是，左⼉⼦，右兄弟，和那个字典树有的⼀拼，也就是左结点是⼉⼦结点，⽽右结点是兄弟结点，那么我们可以⽤两个参数来记录深度，⼆叉树既然是右兄弟，那么同⼀深度的就会多⼀层，加1，这样最⼤的就是答案。

代码如下：#pragma comment(linker, "/STACK:1024000000,1024000000")#include <cstdio>#include <string>#include <cstdlib>#include <cmath>#include <iostream>#include <cstring>#include <set>#include <queue>#include <algorithm>#include <vector>#include <map>#include <cctype>#include <cmath>#include <stack>#define debug puts("+++++")//#include <tr1/unordered_map>#define freopenr freopen("in.txt", "r", stdin)#define freopenw freopen("out.txt", "w", stdout)using namespace std;//using namespace std :: tr1;typedef long long LL;typedef pair<int, int> P;const int INF = 0x3f3f3f3f;const double inf = 0x3f3f3f3f3f3f;const LL LNF = 0x3f3f3f3f3f3f;const double PI = acos(-1.0);const double eps = 1e-8;const int maxn = 3e4 + 5;const LL mod = 1e3 + 7;const int N = 1e6 + 5;const int dr[] = {-1, 0, 1, 0, 1, 1, -1, -1};const int dc[] = {0, 1, 0, -1, 1, -1, 1, -1};const char *Hex[] = {"0000", "0001", "0010", "0011", "0100", "0101", "0110", "0111", "1000", "1001", "1010", "1011", "1100", "1101", "1110", "1111"}; inline LL gcd(LL a, LL b){ return b == 0 ? a : gcd(b, a%b); }inline int gcd(int a, int b){ return b == 0 ? a : gcd(b, a%b); }inline int lcm(int a, int b){ return a * b / gcd(a, b); }int n, m;const int mon[] = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};const int monn[] = {0, 31, 29, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};inline int Min(int a, int b){ return a < b ? a : b; }inline int Max(int a, int b){ return a > b ? a : b; }inline LL Min(LL a, LL b){ return a < b ? a : b; }inline LL Max(LL a, LL b){ return a > b ? a : b; }inline bool is_in(int r, int c){return r >= 0 && r < n && c >= 0 && c < m;}vector<int> G[maxn];bool in[maxn];int ans1, ans2;void dfs(int u, int cnt1, int cnt2){ans1 = Max(ans1, cnt1);ans2 = Max(ans2, cnt2);for(int i = 0; i < G[u].size(); ++i)dfs(G[u][i], cnt1+1, cnt2+i+1);}int main(){while(scanf("%d", &n) == 1){for(int i = 0; i <= n; ++i) G[i].clear(), in[i] = 0;int u, v;for(int i = 1; i < n; ++i){scanf("%d %d", &u, &v);G[u].push_back(v);in[v] = true;}ans1 = ans2 = 0;for(int i = 1; i <= n; ++i) if(!in[i]){dfs(i, 1, 1); break;}printf("%d %d\n", ans1, ans2);}return 0;}。

综合练习一、单项选择题1.数据在计算机存储器内表示时，物理地址与逻辑地址不相同的，称之为（C ).A.存储结构B。

逻辑结构C.链式存储结构D。

顺序存储结构2.设语句x++的时间是单位时间，则以下语句的时间复杂度为( B ).for（i=1; i<=n; i++)for（j=i；j〈=n；j++）x++;A。

O（1) B.O（2n）C。

O(n） D.O（3n)3.链式存储结构的最大优点是（ D ）。

A。

便于随机存取B。

存储密度高C.无需预分配空间D.便于进行插入和删除操作4.假设在顺序表{a0,a1,……，a n－1｝中，每一个数据元素所占的存储单元的数目为4，且第0个数据元素的存储地址为100，则第7个数据元素的存储地址是（ D ).A。

106 B. 107 C。

124 D.1285.在线性表中若经常要存取第i个数据元素及其前趋,则宜采用（ A )存储方式.A.顺序表B. 带头结点的单链表C。

不带头结点的单链表 D. 循环单链表6.在链表中若经常要删除表中最后一个结点或在最后一个结点之后插入一个新结点，则宜采用（ C ）存储方式。

A.顺序表B。

用头指针标识的循环单链表C。

用尾指针标识的循环单链表D。

双向链表7.在一个含有n个结点的有序单链表中插入一个新结点，使单链表仍然保持有序的算法的时间复杂度是（ C )。

O(1） B。

O（log2n） C。

O(n) D。

O（n2)8.要将一个顺序表｛a0，a1,……,a n—1｝中第i个数据元素a i(0≤i≤n—1）删除，需要移动（ B ）个数据元素。

A.i B。

n—i-1 C. n-i D. n—i+19.在栈中存取数据的原则是（ B ）。

A。

先进先出 B。

先进后出C。

后进后出 D。

没有限制10.若将整数1、2、3、4依次进栈，则不可能得到的出栈序列是（ D ）。

A．1234 B. 1324 C. 4321 D. 142311.在链栈中，进行出栈操作时（B ）。

《数据结构》课程教学大纲课程类别：专业基础课适用专业：计算机应用技术适用层次：高起专适用教育形式：成人教育考核形式：考试所属学院：计算机科学与技术学院先修课程：C语言程序设计一、课程简介《数据结构》课程是计算机专业的核心基础课程，是一门理论与实践相结合的课程，整个计算机专业教学体系中处于举足轻重的地位。

数据结构是程序设计（特别是非数值计算的程序设计）的基础，也是设计和实现编译程序、操作系统、数据库系统及其它系统程序和大型应用程序的重要基础。

基于该门课程的重要性，现在该课程已经是计算机相关专业研究生考试必考专业课之一，是反映学生数据抽象能力、编程能力的重要体现。

二、课程学习目标通过本课程的学习，使学生具备下列能力：1、能够理解常用数据结构和算法的基本思路、思考方法、使用场合以及算法设计中考虑的各种因素，能运用于非数值型计算问题的建模和算法设计；深入体会经典算法的思路和分析解决问题的方法，能运用于解决其他领域的相关问题。

2、能够针对基本数据结构和算法方面的特定问题进行分析或推导，分析相应的逻辑结构、选择合适的物理结构或给出问题的解；能对简单算法进行复杂度分析。

3、能针对特定问题需求和给定的数据结构进行算法设计。

三、与其他课程的关系数据结构是计算机及其相关专业的专业基础课，是《操作系统》、《数据库原理》等课程的先导课。

四、课程主要内容和基本要求第1单元数据结构及算法性能分析『知识点』本章作为本课程的绪论部分，主要介绍数据结构课程的研究内容，以及数据结构课程中用到的与课程内容相关的概念和基本术语。

另外，在本章还重点介绍了算法的概念、算法的特性以及算法设计的基本要求，分析算法的方法。

本章重点讲解数据结构的相关概念以及算法及其算法分析。

『基本要求』1、识记：数据、数据元素、数据项、数据对象、数据结构、逻辑结构、存储结构、数据类型、抽象数据类型等基本概念。

2、领会：顺序存储结构和链式存储结构。

3、简单应用：能够实现顺序存储结构和链式存储结构，并在简单问题中应用。

第6章 树和二叉树内容概要：本章主要介绍树，二叉树，最优二叉树的相关概念和操作，存储结构和相应的操作，并在综合应用设计中，给出了对应算法的C 语言实现。

教学目标1．理解各种树和森林与二叉树的相应操作。

2．熟练掌握二叉树的各种遍历算法，并能灵活运用遍历算法实现二叉树的其他操作。

3．熟练掌握二叉树和树的各种存储结构及其建立的算法。

4．掌握哈夫曼编码的方法。

5．通过综合应用设计，掌握各种算法的C 语言实现过程。

基本知识点：树和二叉树的定义、二叉树的存储表示、二叉树的遍历以及其它操作的实现、树和森林的存储表示、树和森林的遍历以及其它操作的实现、最优树和赫夫曼编码重点：二叉树的性质、二叉树的遍历及其应用，构造哈夫曼树。

难点：编写实现二叉树和树的各种操作的递归算法。

本章知识体系结构：课时安排：6个课时树的定义 树树的性质 树的逻辑表示法 树形表示法 树的存储结构 双亲存储结构 文氏表示法凹入表示法 括号表示法 孩子存储结构 孩子双亲存储结构二叉树二叉树的定义 二叉树的性质二叉树的逻辑表示法（采用树的逻辑表示法）二叉树的存储结构二叉树的顺序存储结构先序遍历 中序遍历 后序遍历二叉树的遍历 二叉树的链式存储结构（二叉链） 由先序序列和中序序列构造二叉树 由中序序列和后序序列构造二叉树二叉树的构造 二叉树的线索化 哈夫曼树二叉树和树之间的差别 二叉树与树、森林之间的转换二叉树和树课程数据结构教学教具多媒体课件学时2班级06网络教学日期/课时 /2课时教学单元第6章树和二叉树教学方法讲授（PPT）教学目标掌握树、二叉树的基本概念和术语，二叉树的性质教学重点二叉树的定义、二叉树的性质、链式存储结构教学难点二叉树的性质、链式存储二叉树的基本操作组织教学一、树的定义二、树的基本概念三、二叉树的定义、性质四、二叉树的顺序存储结构和链式存储结构五、小结作业复习本讲内容并预习下一讲内容课堂情况及课后分析课程数据结构教学教具多媒体课件学时2班级06网络教学日期/课时 /2课时教学单元第6章树和二叉树教学方法讲授（PPT）教学目标掌握二叉树遍历的三种方法及二叉树的基本操作教学重点二叉树的遍历算法教学难点中序与后序遍历的非递归算法组织教学一、复习二叉树的定义二、遍历二叉树的三种方法三、递归法遍历二叉树四、二叉树的基本操作五、总结作业复习本讲内容并预习下一讲内容课堂情况及课后分析课程数据结构教学教具多媒体课件学时2班级06网络教学日期/课时 /2课时教学单元第6章树和二叉树教学方法讲授（PPT）教学目标理解树与森林的转换，掌握哈夫曼树教学重点哈夫曼树教学难点树与森林的转换组织教学一、导入二、树与森林三、哈夫曼树四、小结作业习题6课堂情况及课后分析前面几章讨论的数据结构都属于线性结构，线性结构的特点是逻辑结构简单，易于进行查找、插入和删除等操作，可用于描述客观世界中具有单一前驱和后继的数据关系。

第7章树和森林树形结构是一类重要的非线性结构。

树形结构的特点是结点之间具有层次关系。

本章介绍树的定义、存储结构、树的遍历方法、树和森林与二叉树之间的转换以及树的应用等内容。

重点提示：●树的存储结构●树的遍历●树和森林与二叉树之间的转换7-1 重点难点指导7-1-1 相关术语1．树的定义：树是n（n>=0）个结点的有限集T，T为空时称为空树，否则它满足如下两个条件：①有且仅有一个特定的称为根的结点；②其余的结点可分为m（m>=0）个互不相交的子集T1，T2，…，T m，其中每个子集本身又是一棵树，并称为根的子树。

要点：树是一种递归的数据结构。

2．结点的度：一个结点拥有的子树数称为该结点的度。

3．树的度：一棵树的度指该树中结点的最大度数。

如图7-1所示的树为3度树。

4．分支结点：度大于0的结点为分支结点或非终端结点。

如结点a、b、c、d。

5．叶子结点：度为0的结点为叶子结点或终端结点。

如e、f、g、h、i。

6．结点的层数：树是一种层次结构，根结点为第一层，根结点的孩子结点为第二层，…依次类推，可得到每一结点的层次。

7．兄弟结点：具有同一父亲的结点为兄弟结点。

如b、c、d；e、f；h、i。

8．树的深度：树中结点的最大层数称为树的深度或高度。

9．有序树：若将树中每个结点的子树看成从左到右有次序的（即不能互换），则称该树为有序树，否则称为无序树。

10．森林：是m棵互不相交的树的集合。

7-1-2 树的存储结构1．双亲链表表示法以图7-1所示的树为例。

（1）存储思想:因为树中每个元素的双亲是惟一的，因此对每个元素，将其值和一个指向双亲的指针parent构成一个元素的结点，再将这些结点存储在向量中。

（2）存储示意图:-1 data:parent:（3）注意: Parrent域存储其双亲结点的存储下标，而不是存放结点值。

下面的存储是不正确的：-1 data:parent:2．孩子链表表示法（1）存储思想：将每个数据元素的孩子拉成一个链表，链表的头指针与该元素的值存储为一个结点，树中各结点顺序存储起来，一般根结点的存储号为0。

交换二叉树的左右子树算法今天我们来聊聊一个有趣的小话题——交换二叉树的左右子树。

说到二叉树，很多人脑海里可能会闪现出一个一根根分叉的树形结构。

简单来说，它就是一个每个节点最多有两个孩子的树结构。

我们这次要做的，就是让树上的每个节点的左右孩子“交换位置”。

咋听上去有点神奇对不？就像是把两个相邻的楼房互换个位置，看似简单，但真要操作起来就有点技巧了。

这就像家里的沙发和电视柜，突然有一天你决定把它们互换一下位置，哎哟，咋就这么难呢？一开始你可能还挺兴奋的，想着“这下我就能发现新的布置方式了”。

可当你动手之后，才发现地板上的尘土比想象中的多，沙发底下藏了好多丢了的零食，电视柜也变得比原来重了不少。

要不是因为看上去好看，谁愿意折腾呀？交换左右子树也是一样的，理论简单，实际操作得慢慢摸索，慢慢琢磨。

好啦，不废话了，我们直接进入“战斗”状态。

想想，树上的每个节点本来就有左右孩子，对吧？那你要做的就是，直接把这个节点的左右孩子交换位置。

不难吧？你可以把它当做一个人类的动作——左手换右手，右手换左手。

就这么简单的一个操作，树的结构就发生了变化。

想象一下，原本树的左边繁荣，右边空旷，经过交换之后，整个树的景象就焕然一新，左边成了空旷，右边变得繁荣。

就像是你把家里的一切摆放颠倒了，竟然有点新奇的感觉。

当然了，咱也不能只是眼花缭乱地交换啊。

我们得考虑清楚每一层节点，不然把某个节点的左右孩子交换了，结果下面的树就变成了“牛头不对马嘴”。

比如说，假如你的左边的节点本来就是空的，那交换一下也就没有什么意义，反而可能把一切搞得乱七八糟。

所以你得从根节点开始，逐层交换，确保每个交换都做到位。

如果你不细心，那二叉树就可能变成一堆乱麻，差不多就是鸡飞狗跳的场面，谁也搞不清楚谁是谁了。

说起来很简单，但是做起来就得小心谨慎了。

你可以用递归来做这个事情。

你知道的，递归就像是递给自己的礼物，一步步拆开，拆到最小的部分，就像是一个个小人不断地说“我来，我来”，最后问题被拆解得简清明了。

一、判断题（第一章绪论）1.数据元素是数据的最小单元。

答案：错误2.一个数据结构是由一个逻辑结构和这个逻辑结构上的基本运算集构成的整体。

答案：错误3.数据的存储结构是数据元素之间的逻辑关系和逻辑结构在计算机存储器内的映像。

答案：正确4.数据的逻辑结构是描述元素之间的逻辑关系，它是依赖于计算机的。

答案：错误5.用语句频度来表示算法的时间复杂度的最大好处是可以独立于计算机的软硬件，分析算法的时间答案：正确（第二章线性表）6.取顺序存储线性表的第i个元素的时间同i的大小有关。

答案：错误7.线性表链式存储的特点是可以用一组任意的存储单元存储表中的数据元素。

答案：正确8.线性链表的每一个节点都恰好包含一个指针域。

答案：错误9.顺序存储方式的优点的存储密度大，插入和删除效率不如练市存储方式好。

答案：正确10.插入和删除操作是数据结构中最基本的两种操作，所以这两种操作在数组中也经常使用。

答案：错误（第三章栈）11.栈是一种对进栈和出栈作了限制的线性表。

答案：错误12.在C（或C++）语言中设顺序栈的长度为MAXLEN，则top=MAXLEN表示栈满。

答案：错误13.链栈与顺序栈相比，其特点之一是通常不会出现满栈的情况。

答案：正确14.空栈就是所有元素都为0上的栈。

答案：错误15.将十进制数转换为二进制数是栈的典型应用之一。

答案：正确（第四章队列）16.队列式限制在两端进行操作的线性表。

答案：正确17.判断顺序队列为空的标准是头指针和尾指针都指向同一结点。

答案：错误18.在循环链列队中无溢出现像。

答案：错误19.在循环队列中，若尾指针rear大于头指针front，则元素个数为rear-front。

答案：正确20.顺序队列和循环队列关于队满和队空的判断条件是一样的。

答案：错误（第五章串）21.串是n个字母的有限序列。

答案：错误22.串的堆分配存储是一种动态存储结构。

答案：正确23.串的长度是指串中不同字符的个数。

继续教育学院本科学位考试课程《数据结构》知识点一、必须掌握的基本概念（可能的题型为名词解释）算法、数据、数据元素、数据类型、数组、串、模式匹配、顺序表、链表、栈、队列、树、二叉树、满二叉树、完全二叉树、线索二叉树、图、网、有向图、无向图、检索、哈希函数、哈希表、顺序检索、二分法检索、排序、堆二、一般掌握的知识点（可能的题型为填空、单选、多选、判断等客观题）1、算法的5个重要特性。

2、评价算法优劣的5条标准。

3、算法的时间复杂度分析。

4、算法与程序的联系和区别。

5、数据的逻辑结构的基本概念和分类。

什么是线性结构？什么是非线性结构？6、数组的顺序存储结构，数组元素的地址计算。

7、空串与空格串的区别。

8、简单模式匹配算法。

9、线性表的顺序存储和链式存储的特点。

10、栈和队列的特性。

11、循环队列为空的条件和为满的条件。

12、循环链表和双向链表的特点。

13、二叉树的特点和性质。

14、二叉树的存储结构。

15、二叉树的3种遍历（前序、中序、后序）。

16、满二叉树与完全二叉树的异同。

17、完全二叉树的相关计算。

18、计算二叉树的节点数和叶子数。

19、图的存储结构。

20、n个顶点的无向完全图有n(n-1)/2条边，n个顶点的有向完全图有n(n-1)条弧。

有向图中所有结点的入度之和、出度之和均等于边数。

21、有生成树的图是连通图。

对于n个顶点的连通图，其生成树均有n个结点和n-1条边。

22、对有序表进行顺序检索，求其检索成功和不成功的平均检索长度。

23、对有序表进行二分法检索，求其检索成功和不成功的平均检索长度。

24、用线性探查法消除地址冲突构造哈希表。

25、直接插入排序、希尔排序、冒泡排序、快速排序、堆排序、基数排序的时间复杂度、空间复杂度以及稳定性。

三、重点掌握的知识点（可能的题型为简答、论述等主观题）1、线性表的顺序存储和链式存储的具体实现。

2、栈和队列的顺序存储和链式存储的具体实现。

3、已知一棵二叉树的中序遍历和先序（或后序、层序）遍历画出该二叉树。

森林、树、⼆叉树的性质与关系森林、树、⼆叉树的性质与关系这篇博客写的太累了。

本⽂中对于这部分的讲解没有提到的部分：对于⼆叉树的遍历：重点讲了⾮递归遍历的实现⽅式和代码（递归⽅法使⽤的相对较多，请直接参考博客代码）对于哈夫曼编码和线索⼆叉树的代码实现没有列出。

树我们对于树和⼆叉树这⼀部分的内容主要研究树的逻辑结构和存储结构，由于计算机的特殊性存储结构及⼆叉树的简单性，我们更主要讨论⼆叉树的逻辑结构和存储结构并对其进⾏实现（其中包含⼆叉树的⼀些重要性质），另外我们在研究这⼀类问题时，⾸先要考虑到树与森林之间的转换，以及树与⼆叉树之间的转换。

从⽽简化为最简单的⼆叉树问题。

知识体系结构图：树的定义：（采⽤递归⽅法去定义树）树：n（n≥0）个结点的有限集合。

当n＝0时，称为空树；任意⼀棵⾮空树满⾜以下条件：（1）有且仅有⼀个特定的称为根的结点；（2）当n＞1时，除根结点之外的其余结点被分成m（m>0）个互不相交的有限集合T1,T2,… ,Tm，其中每个集合⼜是⼀棵树，并称为这个根结点的⼦树。

（⽤图的定义法去描述树：连通⽽不含回路的⽆向图称为⽆向树，简称树，常⽤T表⽰树）树的基本术语：结点的度：结点所拥有的⼦树的个数。

树的度：树中各结点度的最⼤值。

叶⼦结点：度为0的结点，也称为终端结点。

分⽀结点：度不为0的结点，也称为⾮终端结点。

孩⼦、双亲：树中某结点⼦树的根结点称为这个结点的孩⼦结点，这个结点称为它孩⼦结点的双亲结点；兄弟：具有同⼀个双亲的孩⼦结点互称为兄弟。

祖先、⼦孙：在树中，如果有⼀条路径从结点x到结点y，那么x就称为y的祖先，⽽y称为x的⼦孙。

路径：如果树的结点序列n1, n2, …, nk有如下关系：结点ni是ni+1的双亲（1<=i<k），则把n1, n2, …, nk称为⼀条由n1⾄nk的路径；路径上经过的边的个数称为路径长度。

结点所在层数：根结点的层数为1；对其余任何结点，若某结点在第k层，则其孩⼦结点在第k+1层。

2021~2022学年第二学期《程序设计、算法与数据结构（二）》课程教学实施方案一、课程概况【课程名称】程序设计、算法与数据结构（二）【课程性质】计算机类专业基础课程【教学对象】四年制大一本科生【前修课程】程序设计、算法与数据结构（一）【后修课程】程序设计、算法与数据结构（三）二、教学地位与作用及主要教学目的【地位作用】程序设计、算法与数据结构（二）是计算机、软件工程、网络工程、通信工程专业基础课程，融合了面向对象程序设计基础（C++语言）和数据结构部分内容，包括类与对象、封装、继承、多态、容器、栈、队列、树等。

通过本课程的学习，使学生掌握基本的面向对象的编程思想与能力，并能将面向对象的编程方法和技术应用于数据结构中栈、队列、树等简单问题的实现，培养学生基本的抽象能力、问题解决能力，为后续的专业课程的学习打下坚实的基础。

【教学目的】通过本课程的教学，使学生把握C++面向对象的程序设计方法，掌握一定的抽象思维能力。

利用面向对象的基本机制进行问题的抽象、封装、继承，应用面向对象的技术来进行数据结构的学习、实践，更好地培养学生的程序思维、动手实践能力。

【能力目标】1)掌握c++面向对象方法和数据结构基础知识，能针对一些数据存储、数据表达和数据分析等复杂问题进行建模并求解。

2)能针对一些复杂数据结构问题，自己查阅相关文献和资源，分析问题求解思路，给出合理解决方案。

3)掌握面向对象程序设计复用、迭代、多态等多种结构知识；针对计算机数据结构实现的多样性、复杂性，培养学生对同一工程问题或数据结构进行多种解答的能力，具备自主学习和终身学习的意识。

三、教学手段和方法采取课前预习、针对授课、作业修订、上机实验、主题研讨、阶段考试、作业批改、课后指导等手段督促学生主动学习、编程实现、完成作业。

特别是在每个星期会安排一次研讨，其内容是一个主题知识点的综合应用，能够显著提升学生的思考能力、知识获取与组织能力、交流能力、动手实践能力。

森林转化为二叉树的口诀
森林转化为二叉树的口诀是：
1. 将森林中的每一棵树转化为一颗二叉树；
2. 对于每一棵树，将其根节点作为二叉树的根节点；
3. 对于每一个子树，将其余子树作为其二叉树的左子树，然后依次连接后续子树作为右子树；
4. 对于同一个父节点的子树，按照从左到右的顺序连接；
5. 对于每一颗二叉树，将其根节点的左子树和右子树之间添加指针连接。

6. 重复以上步骤，直到所有的森林中的树都转化为了二叉树。

总结起来，就是将森林中的每一棵树的子树按照从左到右的顺序连接起来，并且将每一颗二叉树的根节点的左子树和右子树之间添加指针连接。