下载文档原格式
第六章树和二叉树试题一、单项选择题1.树中所有结点的度等于所有结点数加（）。
A. 0B. 1C. -1D. 22.在一棵树中，（）没有前驱结点。
A. 分支结点B. 叶结点C. 根结点D. 空结点3.在一棵二叉树的二叉链表中，空指针域数等于非空指针域数加（）。
A. 2B. 1C. 0D. -14.在一棵具有n个结点的二叉树中，所有结点的空子树个数等于（）。
A. nB. n-1C. n+1D. 2*n5.在一棵具有n个结点的二叉树的第i层上（假定根结点为第0层，i大于等于0而小于等于树的高度），最多具有（）个结点。
A. 2iB. 2i+1C. 2i-1D. 2n6.在一棵高度为h（假定根结点的层号为0）的完全二叉树中，所含结点个数不小于（）。
A. 2h-1B. 2h+1C. 2h-1D. 2h7.在一棵具有35个结点的完全二叉树中，该树的高度为（）。
假定空树的高度为-1。
A. 5B. 6C. 7D. 88.在一棵具有n个结点的完全二叉树中，分支结点的最大编号为（）。
假定树根结点的编号为0。
A. ⎣(n-1)/2⎦B. ⎣n/2⎦C. ⎡n/2⎤D. ⎣n/2⎦ -19.在一棵完全二叉树中，若编号为i的结点存在左孩子，则左子女结点的编号为（）。
假定根结点的编号为0A. 2iB. 2i-1C. 2i+1D. 2i+210.在一棵完全二叉树中，假定根结点的编号为0，则对于编号为i（i＞0）的结点，其双亲结点的编号为（）。
A. ⎣(i+1)/2⎦B. ⎣(i-1)/2⎦C. ⎣i/2⎦D. ⎣i/2⎦-111.在一棵树的左子女-右兄弟表示法中，一个结点的右孩子是该结点的（）结点。
A. 兄弟B. 子女C. 祖先D. 子12.在一棵树的静态双亲表示中，每个存储结点包含（）个域。
A. 1B. 2C. 3D. 413.已知一棵二叉树的广义表表示为a (b (c), d (e ( , g (h) ), f ) )，则该二叉树的高度为（）。
第六章树和二叉树（下载后用阅读版式视图或web版式可以看清）习题一、选择题1．有一“遗传”关系：设x是y的父亲，则x可以把它的属性遗传给y。
表示该遗传关系最适合的数据结构为( )。
A.向量B.树 C图 D.二叉树2．树最合适用来表示( )。
A.有序数据元素 B元素之间具有分支层次关系的数据C无序数据元素 D.元素之间无联系的数据3．树B的层号表示为la，2b，3d，3e，2c，对应于下面选择的( )。
A. la (2b (3d,3e),2c)B. a(b(D,e),c)C. a(b(d,e),c)D. a(b,d(e),c)4.高度为h的完全二叉树至少有( )个结点，至多有( )个结点。
A. 2h_lB.h C．2h-1 D. 2h5.在一棵完全二叉树中，若编号为f的结点存在右孩子，则右子结点的编号为( )。
A. 2iB. 2i-lC. 2i+lD. 2i+26.一棵二叉树的广义表表示为a(b(c)，d(e(，g(h))，f))，则该二叉树的高度为 ( )。
A.3B.4C.5D.67.深度为5的二叉树至多有( )个结点。
A. 31B. 32C. 16D. 108.假定在一棵二叉树中，双分支结点数为15，单分支结点数为30个，则叶子结点数为( )个。
A. 15B. 16C. 17D. 479.题图6-1中，( )是完全二叉树，( )是满二叉树。
..专业知识编辑整理..10.在题图6-2所示的二叉树中：(1)A结点是A.叶结点 B根结点但不是分支结点 C根结点也是分支结点 D.分支结点但不是根结点(2)J结点是A.叶结点 B．根结点但不是分支结点 C根结点也是分支结点 D.分支结点但不是根结点(3)F结点的兄弟结点是A.EB.D C．空 D.I(4)F结点的双亲结点是A.AB.BC.CD.D(5)树的深度为A.1B.2C.3D.4(6)B结点的深度为A.1B.2C.3D.4(7)A结点所在的层是A.1B.2C.3D.4..专业知识编辑整理..11.在一棵具有35个结点的完全二叉树中，该树的深度为( )。
第六章树和二叉树（下载后用阅读版式视图或web版式可以看清）习题一、选择题1．有一“遗传”关系：设x是y的父亲，则x可以把它的属性遗传给y。
表示该遗传关系最适合的数据结构为( )。
A.向量B.树C图 D.二叉树2．树最合适用来表示( )。
A.有序数据元素 B元素之间具有分支层次关系的数据C无序数据元素 D.元素之间无联系的数据3．树B的层号表示为la，2b，3d，3e，2c，对应于下面选择的( )。
A. la (2b (3d,3e),2c)B. a(b(D,e),c)C. a(b(d,e),c)D. a(b,d(e),c)4.高度为h的完全二叉树至少有( )个结点，至多有( )个结点。
A. 2h_lB.h C．2h-1 D. 2h5.在一棵完全二叉树中，若编号为f的结点存在右孩子，则右子结点的编号为( )。
A. 2iB. 2i-lC. 2i+lD. 2i+26.一棵二叉树的广义表表示为a(b(c)，d(e(，g(h))，f))，则该二叉树的高度为( )。
A.3B.4C.5D.67.深度为5的二叉树至多有( )个结点。
A. 31B. 32C. 16D. 108.假定在一棵二叉树中，双分支结点数为15，单分支结点数为30个，则叶子结点数为( )个。
A. 15B. 16C. 17D. 479.题图6-1中，( )是完全二叉树，( )是满二叉树。
1 / 1710.在题图6-2所示的二叉树中：(1)A结点是A.叶结点 B根结点但不是分支结点C根结点也是分支结点 D.分支结点但不是根结点(2)J结点是A.叶结点 B．根结点但不是分支结点C根结点也是分支结点 D.分支结点但不是根结点(3)F结点的兄弟结点是A.EB.D C．空 D.I(4)F结点的双亲结点是A.AB.BC.CD.D(5)树的深度为A.1B.2C.3D.4(6)B结点的深度为A.1B.2C.3D.4(7)A结点所在的层是A.1B.2C.3D.411.在一棵具有35个结点的完全二叉树中，该树的深度为( )。
数据结构答案第6章第6章数据结构答案1. 栈的应用栈是一种常见的数据结构，其特点是先进后出。
下面是一些关于栈的应用场景。
1.1 函数调用栈在程序中，每当一个函数被调用时，相关的变量和状态信息会被存储在一个称为函数调用栈的栈中。
1.2 表达式求值栈也常用于表达式求值，特别是中缀表达式转后缀表达式的过程中。
通过使用栈，我们可以很方便地进行算术运算。
1.3 逆序输出如果我们需要逆序输出一段文本、字符串或者其他数据，可以使用栈来实现。
将数据依次压入栈中，然后再逐个弹出即可。
2. 队列的实现与应用队列是另一种常见的数据结构，其特点是先进先出。
下面是一些关于队列的实现和应用。
2.1 数组实现队列队列可以使用数组来实现。
我们可以使用两个指针分别指向队列的前端和后端，通过移动指针来实现入队和出队的操作。
2.2 链表实现队列队列还可以使用链表来实现。
我们可以使用一个指针指向队列的头部，并在尾部添加新元素。
通过移动指针来实现出队操作。
2.3 广度优先搜索（BFS）队列常用于广度优先搜索算法。
在BFS中，我们需要按照层级来访问节点。
使用队列可以帮助我们按照顺序存储和访问节点。
3. 树的遍历和应用树是一种非常重要的数据结构，在计算机科学中应用广泛。
下面是一些关于树的遍历和应用的介绍。
3.1 深度优先搜索（DFS）深度优先搜索是树的一种遍历方式。
通过递归或者使用栈的方式，可以按照深度优先的顺序遍历树的所有节点。
3.2 广度优先搜索（BFS）广度优先搜索也可以用于树的遍历。
通过使用队列来保存要访问的节点，可以按照层级的顺序遍历树。
3.3 二叉搜索树二叉搜索树是一种特殊的二叉树，它的每个节点的值都大于左子树中的值，小于右子树中的值。
这种结构可以用于高效地进行数据查找。
4. 图的表示与遍历图是由节点和边组成的一种数据结构。
下面是一些关于图的表示和遍历的说明。
4.1 邻接矩阵表示法邻接矩阵是一种常见的图的表示方法。
使用一个二维数组来表示节点之间的连接关系。
图1. 填空题⑴ 设无向图G中顶点数为n，则图G至少有（）条边，至多有（）条边；若G为有向图，则至少有（）条边，至多有（）条边。
【解答】0，n(n-1)/2，0，n(n-1)【分析】图的顶点集合是有穷非空的，而边集可以是空集；边数达到最多的图称为完全图，在完全图中，任意两个顶点之间都存在边。
⑵ 任何连通图的连通分量只有一个，即是（）。
【解答】其自身⑶ 图的存储结构主要有两种，分别是（）和（）。
【解答】邻接矩阵，邻接表【分析】这是最常用的两种存储结构，此外，还有十字链表、邻接多重表、边集数组等。
⑷ 已知无向图G的顶点数为n，边数为e，其邻接表表示的空间复杂度为（）。
【解答】Ｏ(n+e)【分析】在无向图的邻接表中，顶点表有n个结点，边表有2e个结点，共有n+2e个结点，其空间复杂度为Ｏ(n+2e)=Ｏ(n+e)。
⑸ 已知一个有向图的邻接矩阵表示，计算第j个顶点的入度的方法是（）。
【解答】求第j列的所有元素之和⑹ 有向图G用邻接矩阵A[n][n]存储，其第i行的所有元素之和等于顶点i的（）。
【解答】出度⑺ 图的深度优先遍历类似于树的（）遍历，它所用到的数据结构是（）；图的广度优先遍历类似于树的（）遍历，它所用到的数据结构是（）。
【解答】前序，栈，层序，队列⑻ 对于含有n个顶点e条边的连通图，利用Prim算法求最小生成树的时间复杂度为（），利用Kruskal 算法求最小生成树的时间复杂度为（）。
【解答】Ｏ(n2)，Ｏ(elog2e)【分析】Prim算法采用邻接矩阵做存储结构，适合于求稠密图的最小生成树；Kruskal算法采用边集数组做存储结构，适合于求稀疏图的最小生成树。
⑼ 如果一个有向图不存在（），则该图的全部顶点可以排列成一个拓扑序列。
【解答】回路⑽ 在一个有向图中，若存在弧、、，则在其拓扑序列中，顶点vi, vj, vk的相对次序为（）。
【解答】vi, vj, vk【分析】对由顶点vi, vj, vk组成的图进行拓扑排序。
图1. 填空题⑴设无向图G中顶点数为n，则图G至少有（）条边，至多有（）条边；若G为有向图，则至少有（）条边，至多有（）条边。
【解答】0，n(n-1)/2，0，n(n-1)【分析】图的顶点集合是有穷非空的，而边集可以是空集；边数达到最多的图称为完全图，在完全图中，任意两个顶点之间都存在边。
⑵任何连通图的连通分量只有一个，即是（）。
【解答】其自身⑶图的存储结构主要有两种，分别是（）和（）。
【解答】邻接矩阵，邻接表【分析】这是最常用的两种存储结构，此外，还有十字链表、邻接多重表、边集数组等。
⑷已知无向图G的顶点数为n，边数为e，其邻接表表示的空间复杂度为（）。
【解答】Ｏ(n+e)【分析】在无向图的邻接表中，顶点表有n个结点，边表有2e个结点，共有n+2e个结点，其空间复杂度为Ｏ(n+2e)=Ｏ(n+e)。
⑸已知一个有向图的邻接矩阵表示，计算第j个顶点的入度的方法是（）。
【解答】求第j列的所有元素之和⑹有向图G用邻接矩阵A[n][n]存储，其第i行的所有元素之和等于顶点i的（）。
【解答】出度⑺图的深度优先遍历类似于树的（）遍历，它所用到的数据结构是（）；图的广度优先遍历类似于树的（）遍历，它所用到的数据结构是（）。
【解答】前序，栈，层序，队列⑻对于含有n个顶点e条边的连通图，利用Prim算法求最小生成树的时间复杂度为（），利用Kruskal 算法求最小生成树的时间复杂度为（）。
【解答】Ｏ(n2)，Ｏ(elog2e)【分析】Prim算法采用邻接矩阵做存储结构，适合于求稠密图的最小生成树；Kruskal算法采用边集数组做存储结构，适合于求稀疏图的最小生成树。
⑼如果一个有向图不存在（），则该图的全部顶点可以排列成一个拓扑序列。
【解答】回路⑽在一个有向图中，若存在弧、、，则在其拓扑序列中，顶点vi, vj, vk的相对次序为（）。
【解答】vi, vj, vk【分析】对由顶点vi, vj, vk组成的图进行拓扑排序。
第六章习题1．试分别画出具有3个结点的树和3个结点的二叉树的所有不同形态。
2．对题1所得各种形态的二叉树，分别写出前序、中序和后序遍历的序列。
3．已知一棵度为k的树中有n1个度为1的结点，n2个度为2的结点，……，nk个度为k的结点，则该树中有多少个叶子结点并证明之。
4.假设一棵二叉树的先序序列为EBADCFHGIKJ，中序序列为ABCDEFGHIJK，请画出该二叉树。
5．已知二叉树有50个叶子结点，则该二叉树的总结点数至少应有多少个？6．给出满足下列条件的所有二叉树：①前序和后序相同②中序和后序相同③前序和后序相同7． n个结点的K叉树，若用具有k个child域的等长链结点存储树的一个结点，则空的Child 域有多少个？8．画出与下列已知序列对应的树Ｔ：树的先根次序访问序列为GFKDAIEBCHJ；树的后根次序访问序列为DIAEKFCJHBG。
9．假设用于通讯的电文仅由8个字母组成，字母在电文中出现的频率分别为：0.07，0.19，0.02，0.06，0.32，0.03，0.21，0.10请为这8个字母设计哈夫曼编码。
10．已知二叉树采用二叉链表存放,要求返回二叉树T的后序序列中的第一个结点指针,是否可不用递归且不用栈来完成?请简述原因.11. 画出和下列树对应的二叉树：12．已知二叉树按照二叉链表方式存储，编写算法，计算二叉树中叶子结点的数目。
13．编写递归算法：对于二叉树中每一个元素值为x的结点，删去以它为根的子树，并释放相应的空间。
14．分别写函数完成：在先序线索二叉树T中，查找给定结点*p在先序序列中的后继。
在后序线索二叉树T中，查找给定结点*p在后序序列中的前驱。
15．分别写出算法，实现在中序线索二叉树中查找给定结点*p在中序序列中的前驱与后继。
16．编写算法，对一棵以孩子-兄弟链表表示的树统计其叶子的个数。
17．对以孩子-兄弟链表表示的树编写计算树的深度的算法。
18．已知二叉树按照二叉链表方式存储，利用栈的基本操作写出后序遍历非递归的算法。
第6章 树和二叉树（参考答案）6.1(1)根结点a6.2三个结点的树的形态： 三个结点的二叉树的形态：（1） （1） （2） （4） （5）6．3 设树的结点数是n ，则n=n0+n1+n2+……+nm+ (1)设树的分支数为B ，有n=B+1n=1n1+2n2+……+mnm+1 (2)由（1）和（2）有：n0=n2+2n3+……+(m-1)nm+16.4(1) k i-1 (i 为层数)(2) (n-2)/k+1(3) (n-1)*k+i+1(4) (n-1)%k !=0; 其右兄弟的编号 n+16.5（1）顺序存储结构注：#为空结点6.6(1) 前序 ABDGCEFH(2) 中序 DGBAECHF(3) 后序 GDBEHFCA6.7(1) 空二叉树或任何结点均无左子树的非空二叉树(2) 空二叉树或任何结点均无右子树的非空二叉树(3) 空二叉树或只有根结点的二叉树6.8int height(bitree bt)// bt是以二叉链表为存储结构的二叉树，本算法求二叉树bt的高度{ int bl,br; // 局部变量，分别表示二叉树左、右子树的高度if (bt==null) return(0);else { bl=height(bt->lchild);br=height(bt->rchild);return(bl>br? bl+1: br+1); // 左右子树高度的大者加1（根） }}// 算法结束6.9void preorder(cbt[],int n,int i);// cbt是以完全二叉树形式存储的n个结点的二叉树，i是数// 组下标，初始调用时为1。
本算法以非递归形式前序遍历该二叉树{ int i=1,s[],top=0; // s是栈，栈中元素是二叉树结点在cbt中的序号 // top是栈顶指针，栈空时top=0if (n<=0) { printf(“输入错误”);exit（0）；}while (i<=n ||top>0){ while(i<=n){visit(cbt[i]); // 访问根结点if (2*i+1<=n) s[++top]=2*i+1; //若右子树非空，其编号进栈i=2*i;// 先序访问左子树}if (top>0) i=s[top--]; // 退栈，先序访问右子树} // END OF while (i<=n ||top>0)}// 算法结束//以下是非完全二叉树顺序存储时的递归遍历算法，“虚结点”用‘*’表示void preorder(bt[],int n,int i);// bt是以完全二叉树形式存储的一维数组，n是数组元素个数。
第六章数据结构基础习题及参考答案第六章数据结构基础一、选择题1．下列数据结构中，（C）不是数据逻辑结构。
A.树结构B.线性表结构C.存储器物理结构D.二叉树2．数据结构是（D）。
A.一种数据类型B.数据的存储结构C.一组性质相同的数据元素的结合D.相互之间存在一种或多种特定关系的数据元素的集合3.下列关于队列的叙述中，正确的是（C）。
A.在队列中只能入数据B.在队列中只能删除数据C.队列是先进先出的线性表D.队列是后进先出的线性表4.如果进栈序列为a1，a2，a3，a4，则可能的出栈序列是（B）A.a3，a1，a4，a2B.a2，a4，a3，a1C.a3，a4，a1，a2D.任意顺序5.链表不具备的特点是（A）A.可能随机访问任意一个节点B.插入和删除不需要移动任何元素C.不必事先估计存储空间D.所需空间与其长度成正比、6.已知某二叉树的后续遍历序列是DACBE，中序遍历序列是DEBAC，则它的前序遍历序列是（D）。
A.ACBEDB.DEABCC.DECABD.EDBCA7.某二叉树中度为2的结点有18个，则该二叉树中有（C）个叶子结点。
A.17B.18C.19D.20二、填空题1.数据元素是（数据）的基本单位，是对一个客观实体的数据描述。
2.简单地说，数据结构是指数据之间的（逻辑关系），即数据的逻辑结构。
3.数据的逻辑结构可用一个二元B=（K,R）来表示,其中K表示（数据元素集合），R表示（数据元素之间的前后关系）。
4.数据元素之间的关系有4种基本的存储表示方法，即（集合）、（线性结构）、（树）和（图）。
5.数据的运算中，（移位）是一个很重要的运算过程，插入、删除、修改和排序都包含着这种运算。
6.线性表是一种最简单、最常用的数据结构，通常一个线性表是由n 个性质相同的数据元素组成的（有限序列），其长度即线性表中元素的个数n,当n=0时，称为（空表）。
7.线性表是一种（线性）结构。
8.如果线性表中最常用的操作是存取第i个元素及其前驱的值，则采用（双向链表）存储方式节省时间。
第六章习题1．试分别画出具有3个结点的树和3个结点的二叉树的所有不同形态。
2．对题1所得各种形态的二叉树，分别写出前序、中序和后序遍历的序列。
3．已知一棵度为k的树中有n1个度为1的结点，n2个度为2的结点，……，nk个度为k的结点，则该树中有多少个叶子结点并证明之。
4.假设一棵二叉树的先序序列为EBADCFHGIKJ，中序序列为ABCDEFGHIJK，请画出该二叉树。
5．已知二叉树有50个叶子结点，则该二叉树的总结点数至少应有多少个？6．给出满足下列条件的所有二叉树：①前序和后序相同②中序和后序相同③前序和后序相同7． n个结点的K叉树，若用具有k个child域的等长链结点存储树的一个结点，则空的Child 域有多少个？8．画出与下列已知序列对应的树Ｔ：树的先根次序访问序列为GFKDAIEBCHJ；树的后根次序访问序列为DIAEKFCJHBG。
9．假设用于通讯的电文仅由8个字母组成，字母在电文中出现的频率分别为：0.07，0.19，0.02，0.06，0.32，0.03，0.21，0.10请为这8个字母设计哈夫曼编码。
10．已知二叉树采用二叉链表存放,要求返回二叉树T的后序序列中的第一个结点指针,是否可不用递归且不用栈来完成?请简述原因.11. 画出和下列树对应的二叉树：12．已知二叉树按照二叉链表方式存储，编写算法，计算二叉树中叶子结点的数目。
13．编写递归算法：对于二叉树中每一个元素值为x的结点，删去以它为根的子树，并释放相应的空间。
14．分别写函数完成：在先序线索二叉树T中，查找给定结点*p在先序序列中的后继。
在后序线索二叉树T中，查找给定结点*p在后序序列中的前驱。
15．分别写出算法，实现在中序线索二叉树中查找给定结点*p在中序序列中的前驱与后继。
16．编写算法，对一棵以孩子-兄弟链表表示的树统计其叶子的个数。
17．对以孩子-兄弟链表表示的树编写计算树的深度的算法。
18．已知二叉树按照二叉链表方式存储，利用栈的基本操作写出后序遍历非递归的算法。
19．设二叉树按二叉链表存放，写算法判别一棵二叉树是否是一棵正则二叉树。
正则二叉树是指：在二叉树中不存在子树个数为1的结点。
20．计算二叉树最大宽度的算法。
二叉树的最大宽度是指：二叉树所有层中结点个数的最大值。
21．已知二叉树按照二叉链表方式存储，利用栈的基本操作写出先序遍历非递归形式的算法。
22. 证明：给定一棵二叉树的前序序列与中序序列，可唯一确定这棵二叉树；给定一棵二叉树的后序序列与中序序列，可唯一确定这棵二叉树；23. 二叉树按照二叉链表方式存储，编写算法，计算二叉树中叶子结点的数目。
24. 二叉树按照二叉链表方式存储，编写算法，将二叉树左右子树进行交换。
实习题1.[问题描述] 建立一棵用二叉链表方式存储的二叉树，并对其进行遍历（先序、中序和后序），打印输出遍历结果。
[基本要求] 从键盘接受输入先序序列，以二叉链表作为存储结构，建立二叉树（以先序来建立）并对其进行遍历（先序、中序、后序），然后将遍历结果打印输出。
要求采用递归和非递归两种方法实现。
[测试数据] ABCффDEфGффFффф（其中ф表示空格字符）输出结果为：先序：ABCDEGF中序：CBEGDFA后序：CGBFDBA2．已知二叉树按照二叉链表方式存储，编写算法，要求实现二叉树的竖向显示（竖向显示就是二叉树的按层显示）。
3．如题1要求建立好二叉树，按凹入表形式打印二叉树结构，如下图所示。
2.按凹入表形式打印树形结构，如下图所示。
第六章答案6．1分别画出具有3个结点的树和3个结点的二叉树的所有不同形态。
【解答】具有3个结点的树具有3个结点的二叉树6.3已知一棵度为k的树中有n1个度为1的结点，n2个度为2的结点，……，n k个度为k的结点，则该树中有多少个叶子结点？【解答】设树中结点总数为n,则n=n0 + n1 + …… + n k树中分支数目为B,则B=n1 + 2n2 + 3n3+ …… + kn k因为除根结点外，每个结点均对应一个进入它的分支，所以有n= B + 1即n0 + n1 + …… + n k = n1 + 2n2 + 3n3+ …… + kn k + 1由上式可得叶子结点数为：n0 = n2 + 2n3+ …… + (k-1)n k + 16.5已知二叉树有50个叶子结点，则该二叉树的总结点数至少应有多少个？【解答】n0表示叶子结点数，n2表示度为2的结点数，则n0 = n2+1所以n2=n0 –1=49，当二叉树中没有度为1的结点时，总结点数n=n0+n2=99 6.6 试分别找出满足以下条件的所有二叉树:(1) 前序序列与中序序列相同;(2) 中序序列与后序序列相同;(3) 前序序列与后序序列相同。
【解答】(1) 前序与中序相同：空树或缺左子树的单支树；(2) 中序与后序相同：空树或缺右子树的单支树；(3) 前序与后序相同：空树或只有根结点的二叉树。
6.9 假设通讯的电文仅由8个字母组成，字母在电文中出现的频率分别为：0.07，0.19，0.02，0.06，0.32，0.03，0.21，0.10请为这8个字母设计哈夫曼编码。
【解答】构造哈夫曼树如下：哈夫曼编码为：I 1：11111I5：1100I2：11110I6：10I 3：1110 I7： 01I 4：1101 I8： 006.11画出如下图所示树对应的二叉树。
【解答】6.15分别写出算法，实现在中序线索二叉树T中查找给定结点*p在中序序列中的前驱与后继。
在先序线索二叉树T中，查找给定结点*p在先序序列中的后继。
在后序线索二叉树T中，查找给定结点*p在后序序列中的前驱。
（1）找结点的中序前驱结点BiTNode *InPre (BiTNode *p)/*在中序线索二叉树中查找p的中序前驱结点，并用pre指针返回结果*/{ if (p->Ltag= =1) pre = p->LChild; /*直接利用线索*/else{/*在p的左子树中查找“最右下端”结点*/for ( q=p->LChild; q->Rtag= =0; q=q->RChild);pre = q;}return (pre);}（2）找结点的中序后继结点BiTNode *InSucc (BiTNode *p)/*在中序线索二叉树中查找p的中序后继结点，并用succ指针返回结果*/{ if (p->Rtag= =1) succ = p->RChild; /*直接利用线索*/else{/*在p的右子树中查找“最左下端”结点*/for ( q=p->RChild; q->Ltag= =0; q=q->LChild);succ= q;}return (succ);}(3) 找结点的先序后继结点BiTNode *PreSucc (BiTNode *p)/*在先序线索二叉树中查找p的先序后继结点，并用succ指针返回结果*/{ if (p->Ltag= =0) succ = p->LChild;else succ= p->RChild;return (succ);}(4) 找结点的后序前驱结点BiTNode *SuccPre (BiTNode *p)/*在后序线索二叉树中查找p的后序前驱结点，并用pre指针返回结果*/{ if (p->Ltag= =1) pre = p->LChild;else pre= p->RChild;return (pre);}6.21已知二叉树按照二叉链表方式存储，利用栈的基本操作写出先序遍历非递归形式的算法。
【解答】Void PreOrder(BiTree root) /*先序遍历二叉树的非递归算法*/{InitStack(&S);p=root;while(p!=NULL || !IsEmpty(S) ){ if(p!=NULL){Visit(p->data);push(&S,p);p=p->Lchild;}else{Pop(&S,&p);p=p->RChild;}}}6.24已知二叉树按照二叉链表方式存储，编写算法，将二叉树左右子树进行交换。
【解答】算法(一)Void exchange ( BiTree root ){p=root;if ( p->LChild != NULL || p->RChild != NULL ){temp = p->LChild;p->LChild = p->RChild;p->RChild = temp;exchange ( p->LChild );exchange ( p->RChild );}}算法(二)Void exchange ( BiTree root ){p=root;if ( p->LChild != NULL || p->RChild != NULL ){exchange ( p->LChild );exchange ( p->RChild );temp = p->LChild;p->LChild = p->RChild;p->RChild = temp;}}第六章习题解析1．试分别画出具有3个结点的树和3个结点的二叉树的所有不同形态。
2．对题1所得各种形态的二叉树，分别写出前序、中序和后序遍历的序列。
3．已知一棵度为k的树中有n1个度为1的结点，n2个度为2的结点，……，n k个度为k的结点，则该树中有多少个叶子结点？[提示]：参考P.116 性质3∵n=n0 + n1 + …… + n kB=n1 + 2n2 + 3n3+ …… + kn kn= B + 1∴n0 + n1 + …… + n k = n1 + 2n2 + 3n3+ …… + kn k + 1∴n0 = n2 + 2n3+ …… + (k-1)n k + 14.假设一棵二叉树的先序序列为EBADCFHGIKJ，中序序列为ABCDEFGHIJK，请画出该二叉树。
[提示]：参考P.1486．已知二叉树有50个叶子结点，则该二叉树的总结点数至少应有多少个？[提示]：[方法1]（1）一个叶子结点，总结点数至多有多少个？结论：可压缩一度结点。
（2）满二叉树或完全二叉树具有最少的一度结点（3）可能的最大满二叉树是几层？有多少叶结点？如何增补？25<50<26可能的最大满二叉树是6层有25 = 32个叶结点假设将其中x个变为2度结点后，总叶结点数目为50则：2x + (32 – x) = 50得：x = 18此时总结点数目= ( 26– 1) + 18×2[方法2]假设完全二叉树的最大非叶结点编号为m，则最大叶结点编号为2m+1,(2m+1)-m=50m=49总结点数目=2m+1=99[方法3]由性质3：n0=n2+1即：50=n2+1所以：n2=49令n1=0得：n= n0 + n2=997．给出满足下列条件的所有二叉树：a)前序和中序相同b)中序和后序相同c)前序和后序相同[提示]：去异存同。
