第6章_数据结构习题题目及答案_树和二叉树_参考答案
一、基础知识题
6.1设树T的度为4，其中度为1，2，3和4的结点个数分别为4，2，1，1，求树T中的叶子数。
【解答】设度为m的树中度为0,1,2,…,m的结点数分别为n0, n1, n2,…, nm，结点总数为n，分枝数为B，则下面二式成立
n= n0+n1+n2+…+nm (1)
n=B+1= n1+2n2 +…+mnm+1 (2)
由(1)和(2)得叶子结点数n0=1+
即： n0=1+(1-1)*4+(2-1)*2+(3-1)*1+(4-1)*1=8
6.2一棵完全二叉树上有1001个结点，求叶子结点的个数。
【解答】因为在任意二叉树中度为2 的结点数n2和叶子结点数n0有如下关系：n2=n0-1,所以设二叉树的结点数为n, 度为1的结点数为n1，则
n= n0+ n1+ n2
n=2n0+n1-1
1002=2n0+n1
由于在完全二叉树中，度为1的结点数n1至多为1，叶子数n0是整数。本题中度为1的结点数n1只能是0，故叶子结点的个数n0为501.
注：解本题时要使用以上公式，不要先判断完全二叉树高10，前9层是满二叉树，第10层都是叶子，……。虽然解法也对，但步骤多且复杂，极易出错。
6.3 一棵124个叶结点的完全二叉树，最多有多少个结点。
【解答】由公式n=2n0+n1-1,当n1为1时，结点数达到最多248个。
6.4．一棵完全二叉树有500个结点，请问该完全二叉树有多少个叶子结点？有多少个度为1的结点？有多少个度为2的结点？如果完全二叉树有501个结点，结果如何？请写出推导过程。
【解答】由公式n=2n0+n1-1，带入具体数得，500=2n0+n1-1，叶子数是整数，度为1的结点数只能为1，故叶子数为250，度为2的结点数是249。
若完全二叉树有501个结点，则叶子数251，度为2的结点数是250，度为1的结点数为0。
6.5 某二叉树有20个叶子结点，有30个结点仅有一个孩子，则该二叉树的总结点数是多少。
【解答】由公式n=2n0+n1-1，得该二叉树的总结点数是69。
6.6 求一棵具有1025个结点的二叉树的高h。
【解答】该二叉树最高为1025（只有一个叶子结点），最低高为11。因为210-1<1025<211-1，故1025个结点的二叉树最低高为11。
6.7 一棵二叉树高度为h，所有结点的度或为0，或为2，则这棵二叉树最少有多少结点。
【解答】第一层只一个根结点，其余各层都两个结点，这棵二叉树最少结点数是2h-1。
6.8将有关二叉树的概念推广到三叉树，则一棵有244个结点的完全三叉树的高度是多少。
【解答】设含n个结点的完全三叉树的高度为h，则有
<2n< 本题n=244, 故h=6。 6.9 对二叉树的结点从1开始进行连续编号，要求每个结点的编号大于其左、右 孩子的编号，同一结点的左、右孩子中，其左孩子的编号小于其右孩子的编号，是采用何种次序的遍历实现编号的。 【解答】后序遍历二叉树，因为后序遍历顺序为左子树-右子树-根结点。 6.10 高度为h(h>0)的满二叉树对应的森林由多少棵树构成。 【解答】因为在二叉树转换为森林时，二叉树的根结点，根结点的右子女，右子女的右子女，……，都是树的根，所以，高度为h(h>0)的满二叉树对应的森林由h棵树构成。 6.11 某二叉树结点的中序序列为BDAECF，后序序列为DBEFCA，则该二叉树对应的森林包括几棵树？ 【解答】3棵树。（本题不需画出完整的二叉树，更不需要画出森林，只需画出二叉树的右子树就可求解。如上题所述，二叉树的根结点，根结点的右子女，右子女的右子女，……，在二叉树转为森林时，都是树的根。） 6.12 对任意一棵树，设它有n个结点，这n个结点的度数之和为多少？ 【解答】n-1。度数其实就是分支个数。根结点无分支所指，其余结点有且只有一个分支所指。 6.13 一棵左子树为空的二叉树在先序线索化后，其中空的链域的个数是多少？【解答】对二叉树线索化时，只有空链域才可加线索。一棵左子树为空的二叉树在先序线索化时，根结点的左链为空，应加上指向前驱的线索，但根结点无前驱，故该链域为空。同样分析知道最后遍历的结点的右链域为空。故一棵左子树为空的二叉树在先序线索化后，其中空的链域的个数是2个。 6.14 一棵左、右子树均不空的二叉树在先序线索化后，其中空的链域的个数是多少? 【解答】1个。 6.15 设B是由森林F变换得的二叉树。若F中有n个非终端结点，则B中右指针域为空的结点有几个？ 【解答】n+1。森林中任何一个非终端结点在转换成二叉树时，其第一个子女结点成为该非终端结点的左子女，其余子女结点成为刚生成的左子女结点的右子女，右子女结点的右子女，……，最右子女结点的右链域为空。照此分析，n个非终端结点在转换后，其子女结点中共有n个空链域。另外，森林中各棵树的根结点可以看做互为兄弟，转换成二叉树后也产生1个空链域。因此，本题的答案是n+1。 6.16 试分别找出满足以下条件的所有二叉树： (1) 二叉树的前序序列与中序序列相同； (2) 二叉树的中序序列与后序序列相同； (3) 二叉树的前序序列与后序序列相同； (4) 二叉树的前序序列与层次序列相同； (5) 二叉树的前序、中序与后序序列均相同。 【解答】前序遍历二叉树的顺序是“根—左子树—右子树”，中序遍历的顺序是“左子树—根—右子树”，后序遍历顺序是：“左子树—右子树―根＂，根据以上原则，本题解答如下： 若前序序列与中序序列相同，则或为空树，或为任一结点至多只有右子树的二叉树。 若中序序列与后序序列相同，则或为空树，或为任一结点至多只有左子树的二叉树。 若前序序列与后序序列相同，则或为空树，或为只有根结点的二叉树。 若二叉树的前序、中序与后序序列均相同，则或为空树，或为只有根结点的二叉树。 6.17 已知一棵二叉树的前序遍历的结果是ABECDFGHIJ，中序遍历的结果是EBCDAFHIGJ，试画出这棵二叉树，对二叉树进行中序线索化，并将该二叉树转换为森林。 【解答】 6.18 已知一棵二叉树的后序遍历序列为EICBGAHDF，同时知道该二叉树的中序遍历序列为CEIFGBADH，试画出该二叉树。 6.19设二叉树中每个结点均用一个字母表示，若一个结点的左子树或右子树为空，用#表示，现前序遍历二叉树，访问的结点序列为ABD##C#E##F##，写出中序和后序遍历二叉树时结点的访问序列。 【解答】中序遍历二叉树时结点的访问序列：#D#B#C#E#A#F# 后序遍历二叉树时结点的访问序列。##D###ECB##FA 6.20有n个结点的k叉树（k≥2）用k叉链表表示时，有多少个空指针？ 【解答】k叉树（k≥2）用k叉链表表示时,每个结点有k个指针，除根结点没有指针指向外，其余每个结点都有一个指针指向，故空指针的个数为： nk-(n-1)=n(k-1)+1 6.21 一棵高度为h的满k叉树有如下性质：根结点所在层次为0；第h层上的结点都是叶子结点；其余各层上每个结点都有k棵非空子树，如果按层次自顶向下，同一层自左向右，顺序从1开始对全部结点进行编号，试问： (1)各层的结点个数是多少? (2)编号为i的结点的双亲结点（若存在）的编号是多少? (3)编号为i的结点的第m个孩子结点（若存在）的编号是多少？ (4)编号为i的结点有右兄弟的条件是什么？其右兄弟结点的编号是多少？【解答】 (1)kl(l为层数，按题意，根结点为0层) （2）因为该树每层上均有kl个结点，从根开始编号为1，则结点i的从右向左数第２个孩子的结点编号为ki。设n 为结点i的子女，则关系式(i-1)k+2<=n<=ik+1成立，因i是整数，故结点i的双亲的编号为?(i-2)/k?+1。 (3) 结点i(i>1)的前一结点编号为i-1（其最右边子女编号是(i-1)*k+1），故结点 i的第 m个孩子的编号是(i-1)*k+1+m。 (4) 根据以上分析，结点i有右兄弟的条件是，它不是双亲的从右数的第一子女，即 (i-1)%k!=0，其右兄弟编号是i+1。 6.22．证明任一结点个数为n(n>0) 的二叉树的高度至少为?(logn)?+1。 【解答】最低高度二叉树的特点是，除最下层结点个数不满外，其余各层的结点数都应达到各层的最大值。设n个结点的二叉树的最低高度是h，则n应满足2h-1≦n≦2h-1关系式。解此不等式，并考虑h是整数，则有h=?logn?+1，即任一结点个数为n 的二叉树的高度至少为?(logn)?+1。 6.23 已知A[1..N]是一棵顺序存储的完全二叉树，如何求出A[i]和A[j]的最近的共同祖先？ 【解答】根据顺序存储的完全二叉树的性质，编号为i的结点的双亲的编号是?i/2?，故A[i]和A[j]的最近公共祖先可如下求出： while(i/2!=j/2) if(i>j) i=i/2; else j=j/2; 退出while后，若i/2=0,则最近公共祖先为根结点，否则最近公共祖先是i/2。 6.24已知一棵满二叉树的结点个数为20到40之间的素数，此二叉树的叶子结点有多少个？ 【解答】结点个数在20到40的满二叉树且结点数是素数的数是31，其叶子数是16。 6.25求含有n个结点、采用顺序存储结构的完全二叉树中的序号最小的叶子结 点的下标。要求写出简要步骤。 【解答】根据完全二叉树的性质，最后一个结点（编号为n）的双亲结点的编号是?n/2?，这是最后一个分枝结点，在它之后是第一个终端（叶子）结点，故序号最小的叶子结点的下标是?n/2?+1。 6.26 试证明:同一棵二叉树的所有叶子结点，在前序序列、中序序列以及后序序列中都按相同的相对位置出现（即先后顺序相同），例如前序abc，后序bca，中序bac。 【证明】前序遍历是“根－左－右”，中序遍历是“左－根－右”，后序遍历是“左－右－根”。三种遍历中只是访问“根”结点的时机不同，对左右子树均是按左右顺序来遍历的，因此所有叶子都按相同的相对位置出现。 6.27设具有四个结点的二叉树的前序遍历序列为ａｂｃｄ；Ｓ为长度等于4的由ａ，ｂ，ｃ，ｄ排列构成的字符序列，若任取Ｓ作为上述算法的中序遍历序列，试问是否一定能构造出相应的二叉树，为什么？试列出具有四个结点二叉树的全部形态及相应的中序遍历序列。 【解答】若前序序列是abcd，并非由这四个字母的任意组合（4!=24）都能构造出二叉树。因为以abcd为输入序列，通过栈只能得到1/(n+1)*2n!/(n!*n!)=14 种，即以abcd为前序序列的二叉树的数目是14。任取以abcd作为中序遍历序列，并不全能与前序的abcd序列构成二叉树。例如：若取中序序列dcab就不能。该14棵二叉树的形态及中序序列略。 6.28已知某二叉树的每个结点，要么其左、右子树皆为空，要么其左、右子树皆不空。又知该二叉树的前序序列为：JFDBACEHXIK；后序序列为：ACBEDXIHFKJ。请给出该二叉树的中序序列，并画出相应的二叉树树形。 【解答】一般说来，仅仅知道二叉树的前序遍历序列和后序遍历序列并不能确定这棵二叉树，因为并不知道左子树和右子树两部分各有多少个结点。但本题有特殊性，即每个结点“要么其左、右子树皆为空，要么其左、右子树皆不空”。具体说，前序序列的第一个结点是二叉树的根，若该结点后再无其它结点，则二 叉树只有根结点；否则，该结点必有左右子树，且根结点后的第一个结点就是“左子树的根”。到后序序列中查找这个“左子树的根”，它将后序序列分成左右两部分：左部分(包括所查到的“左子树的根结点”)是二叉树的左子树(可能为空)，右部分(除去最后的根结点)则是右子树(可能为空)。这样，在确定根结点后，就可以将后序遍历序列（从而也将前序遍历序列）分成左子树和右子树两部分了。本题中，先看前序遍历序列，第一个结点是J，所以J是二叉树的根，J后面还有结点，说明J有左、右子树，J后面的F必是左子树的根。到后序遍历序列中找到F,F将后序遍历序列分成两部分：左面ACBEDXIH，说明FACBEDXIH是根J 的左子树；右面K(K的右面J已知是根)，说明K是根J的右子树。这样，问题就转化为“以前序序列FDBACEHXI和后序序列ACBEDXIHF去构造根J的左子树”，以及“以前序序列K和后序序列K去构造根J的右子树”了。如此构造下去，所构造的二叉树如下。易见，中序序列为ABCDEFXHIJK。 6.29 已知一个森林的先序序列和后序序列如下，请构造出该森林。 先序序列：ABCDEFGHIJKLMNO 后序序列：CDEBFHIJGAMLONK 【解答】森林的先序序列和后序序列对应其转换的二叉树的先序序列和中序序列，应先据此构造二叉树，再构造出森林。 6.30 画出同时满足下列两条件的两棵不同的二叉树。 (1)按先根序遍历二叉树顺序为ABCDE。 (2)高度为5其对应的树（森林）的高度最大为4。 【解答】 6.31用一维数组存放的一棵完全二叉树；ABCDEFGHIJKL。请写出后序遍历该二叉树的结点访问序列。 【解答】后序遍历该二叉树的结点访问序列为：DECGHFBKJLIA 6.32一棵二叉树的先序、中序和后序序列如下，其中有部分未标出，试构造出该二叉树。 先序序列为： C D E G H I K 中序序列为：C B F A _ J K I G 后序序列为： E F D B J I H A 【解答】 6.33设树形T在后根次序下的结点排列和各结点相应的度数如下： 后根次序：ＢＤＥＦＣＧＪＫＩＬＨＡ 次数：００００３０００２０２４ 请画出Ｔ的树形结构图。 【解答】在树在后根遍历次序下，根结点在最后，任何结点的子树的所有结点都直接排在该结点之前。例如，挨着根结点的是根结点的最右边的子女。每棵子树的所有结点都聚集在一起，中间不会插入其它结点，也不会丢掉子树的任何结点。按照这种理论解答本题，在遍历次序中从右到左分析，A是根，它有4个子女，H是它的最右边的子女（第4子女）。H有2个子女，L是H的最右边的子女，L 无子女，故I是H的第1子女。I又有2个子女：K和J，二者均无子女。由此推断出下一个结点G是根结点A的第3子女。……，继续构造，直至最左面的结点B，结果树形如下： 6.34 若森林共有n个结点和b条边(b 【解答】n-b 森林的n个结点开始可看作是n个连通分量，加入一条边将减少一个连通分量。因为树可以定义为无环的图，故加入b条边将减少b个连通分量，因而n个结点b条边的森林有n-b棵树。 6.35 求高度为k的完全二叉树至少有多少个叶结点？ 【解答】当高度为k的完全二叉树的第k层只有一个结点时，结点数达到最少，这也是高度为k的完全二叉树具有的最少叶结点数，我们知道，第k-1层有2k-2-1个叶结点，第k层只有一个叶结点，但这个结点的双亲已不再是叶子结点，故高度为k的完全二叉树至少有2k-2-1个叶结点。 6.36 某通信电文由Ａ、Ｂ、Ｃ、Ｄ、Ｅ、Ｆ六个字符组成，它们在电文中出现的次数分别是16，5，9，3，20，1。试画出其哈夫曼树并确定其对应的哈夫曼编码。 【解答】答案不唯一，其中一个解答如下 对应的哈夫曼编码: A—10, B—1101, C—111, D—11001, E—0, F—11000 二、算法设计题 6.37以二叉链表作为存储结构，设计算法求出二叉树T中度为0、度为1和度为2的结点数。 【题目分析】结点计数可以在遍历中解决。根据“访问根结点”在“递归遍历左 子树”和“递归遍历右子树”中位置的不同，而有前序、后序和中序遍历。【算法6.37】 int n2,n1,n0; ∥设置三个全局变量，分别记度为2，1和0的结点个数void Count(BiTree t) {if(t) {if(t->lchild && t->rchild) n2++; else if(t->lchild && !t->rchild || !t->lchild && t->rchild) n1++; else n0++; if(t->lchild!=null) Count(t->lchild); if(t->rchild!=null) Count(t->rchild); }∥Count 6.38一棵n个结点的完全二叉树存放在二叉树的顺序存储结构中，试编写非递归算法对该树进行先序遍历。 【题目分析】二叉树的顺序存储是按完全二叉树的顺序存储，双亲与子女结点下标间有确定关系。顺序存储结构的二叉树用结点下标大于n（完全二叉树）或0（对一般二叉树的“虚结点”）判空。本题是完全二叉树。 【算法6.38】 void PreOrder(ElemType bt[],int n) ∥对以顺序结构存储的完全二叉树bt进行前序遍历 {int i=1,top=0,s[]; ∥top是栈s的栈顶指针，栈容量足够大 while(i<=n || top>0) {while(i<=n) {printf(bt[i]); ∥访问根结点； if(2*i+1<=n) s[++top]=2*i+1; ∥右子女的下标位置进栈 i=2*i; ∥沿左子女向下 } if(top>0) i=s[top--]; ∥取出栈顶元素 }∥while }∥结束PreOrder 6.39以二叉链表作为存储结构的二叉树，按后序遍历时输出的结点顺序为a1，a2，…，an。试编写一算法，要求输出后序序列的逆序an，an-1…，a2 ，a1 。【题目分析】二叉树后序遍历是按“左子树－右子树－根结点”的顺序遍历二叉树，根据题意，若将遍历顺序改为“根结点－右子树－左子树”，就可以实现题目要求。 【算法6.39】 void PostOrder(BiTree bt) //对二叉树bt进行先右后左的“先根”遍历 {if(bt) {printf(bt->data); //访问根结点 PostOrder(bt->rchild); //先根遍历右子树 PostOrder(bt->lchild); //先根遍历左子树 } } 6.40以二叉链表作为存储结构，设计算法交换二叉树中所有结点的左、右子树。【算法6.40】 void exchange(BiTree bt) ∥将二叉树bt所有结点的左右子树交换 {if(bt){BiTree s； s=bt->lchild; bt->lchild=bt->rchild; bt->rchild=s; ∥左右子女交换exchange(bt->lchild); ∥交换左子树上所有结点的左右子树 exchange(bt->rchild); ∥交换右子树上所有结点的左右子树 }∥if }∥结束 【算法讨论】将上述算法中两个递归调用语句放在前面，将交换语句放在最后，则是以后序遍历方式交换所有结点的左右子树。中序遍历方式不适合本题。 6.41以二叉链表为存储结构，写出在二叉树中求值为x的结点在树中层次数的算法。 [题目分析] 按层次遍历，设一队列Q，用front和rear分别指向队头和队尾元素，last指向各层最右结点位置。 【算法6.41】 int Level_x(BiTree bt，ElemType x)∥求值为x的结点在树中层次数 {if(bt!=null) {int front=0,last=1,rear=1,level=1;∥level记层次数 BiTree Q[];Q[1]=bt;∥根结点入队 while(front<=last) {bt=Q[++front]; if(bt->data==x) {printf(“%3d\n”,level); return level;}∥值为x的结点在树中层次数 if(bt->lchild!=null) Q[++rear]=bt->lchild;∥左子女入队列 if(bt->rchild!=null) Q[++rear]=bt->rchild;∥右子女入队列 if(front==last) {last=rear; level++; }∥本层最后一个结点已处理完 } } }∥算法结束 6.42已知深度为h的二叉树以一维数组作为存储结构。试编写算法求该二叉树中叶子的个数。 【题目分析】按完全二叉树形式顺序存储二叉树时，无元素的位置要当作“虚结点”。设虚结点取二叉树结点以外的值（这里设为0）。设结点序号为i,则当i<=(2h-1)/2时，若其2i和2i+1位置为虚结点，则i为叶子结点；当i>(2h-1)/2时，若i位置不是虚结点，则必为叶子结点。 【算法6.42】 int Leaves(int BT[],int n) ∥计算深度为h以一维数组BT作为存储结构的二叉树的叶子结点数，n为数组长度 {int num=0; ∥记叶子结点数 for(i=0;i if(BT[i]!=0) {if(i<=n/2) {if(BT[2*i]==0 && 2*i+1<=n && BT[2*i+1]==0) num++;} ∥若结点无孩子，则是叶子 else if(BT[i]!=0) num++; ∥存储在数组后一半的元素是叶子结点 } return num; }∥结束Leaves 6.43已知二叉树以一维数组作为存储结构。试编写算法求下标为i和j的两个结点的最近共同祖先结点的值。 【题目分析】二叉树顺序存储，是按完全二叉树的格式存储，利用完全二叉树双亲结点与子女结点编号间的关系，求下标为i和j的两结点的双亲，双亲的双亲，等等，直至找到最近的公共祖先。 【算法6.43】 void Ancestor(ElemType bt[],int n,i,j,) ∥求顺序存储在bt[1..n]的二叉树中下标为i和j的两个结点的最近公共祖先结点 {if(i<1 || j<1) {printf(“参数错误\n”);exit(0);}; if(i==j) {if(i==1) {printf(“所查结点为根结点，无祖先\n”);exit(0);}; else {printf (“结点的最近公共祖先是%d，值是%d”,i/2,A[i/2]);exit(0)} } while(i!=j) if(i>j) i=i/2; ∥下标为i的结点的双亲结点的下标 else j=j/2; ∥下标为j的结点的双亲结点的下标 printf(“所查结点的最近公共祖先的下标是%d，值是%d”,i,A[i]); ∥设元素类型整型。 }∥ Ancestor 6.44已知一棵完全二叉树顺序存储于向量s[1..n]中，试编写算法由此顺序存储结构建立该二叉树的二叉链表。 【算法6.44】 BiTree Creat(ElemType A[],int i) ∥n个结点的完全二叉树存于一维数组A中，本算法建立二叉链表表示的完全二叉树 {BiTree tree; if(i<=n) {tree=(BiTree)malloc(sizeof(BiNode)); tree->data=A[i]; if(2*i>n) tree->lchild=null； else tree->lchild=Creat(A,2*i)； if(2*i+1>n) tree->rchild=null； else tree->rchild=Creat(A,2*i+1)； } return (tree)； }∥Creat 【算法讨论】初始调用时,i=1。 6.45编写算法判别给定二叉树是否为完全二叉树。 【题目分析】判定是否是完全二叉树，可以使用队列，在遍历中利用完全二叉树“若某结点无左子女就不应有右子女”的原则进行判断。具体说，在层次遍历时，若碰到一个空指针后，在遍历结束前又碰到结点，则结论为该二叉树不是完全二叉树。 【算法6.45】 int JudgeComplete(BiTree bt) ∥判断二叉树是否是完全二叉树,如是，返回1，否则，返回0 {int tag=0; ∥出现空指针时，置tag=1 BiTree p=bt, Q[]; ∥ Q是队列，元素是二叉树结点指针，容量足够大 if(p==null) return (1); QueueInit(Q); QueueIn(Q,p); ∥初始化队列，根结点指针入队 while(!QueueEmpty(Q)) {p=QueueOut(Q); ∥出队 if(p->lchild && !tag) QueueIn(Q,p->lchild);∥左子女入队 else if(p->lchild) return 0; ∥前边已有结点空，本结点不空 else tag=1; ∥首次出现结点为空 if(p->rchild && !tag) QueueIn(Q,p->rchild);∥右子女入队 else if(p->rchild) return 0; else tag=1; } ∥while return 1; } ∥JudgeComplete [算法讨论]完全二叉树证明还有其它方法。判断时易犯的错误是证明其左子树和右子树都是完全二叉树，由此推出整棵二叉树必是完全二叉树的错误结论。 6.46设树以双亲表示法存储，编写计算树的深度的算法。 【题目分析】以双亲表示法作树的存储结构，对每一结点，找其双亲，双亲的双亲，直至（根）结点,就可求出每一结点的层次，取其结点的最大层次就是树的深度。 【算法6.46】 int Depth(Ptree t) ∥求以双亲表示法为存储结构的树的深度 {int maxdepth=0; for(i=1;i<=t.n;i++) {temp=0; f=i; while(f>0) {temp++; f=t.nodes[f].parent; } ∥深度加1,并取新的双亲 if(temp>maxdepth) maxdepth=temp; ∥最大深度更新 } return(maxdepth);∥返回树的深度 } ∥结束Depth 6.47已知在二叉树中，*root为根结点，*p和*q为二叉树中两个结点，试编写求距离它们最近的共同祖先的算法。 【题目分析】后序遍历最后访问根结点，即在递归算法中，根是压在栈底的。采用后序非递归遍历。栈中存放二叉树结点的指针，当访问到某结点时，栈中所有元素均为该结点的祖先。本题要找p和q 的最近共同祖先结点r ,不失一般性，设p在q的左边。后序遍历必然先遍历到结点p，栈中元素均为p的祖先。将栈拷入另一辅助栈中。再继续遍历到结点q时，将栈中元素从栈顶开始逐个到辅助栈中去匹配，第一个匹配（相等）的元素就是结点p 和q的最近公共祖先。【算法6.47】 先设二叉树的结点结构为： typedef struct {BiTree t; int tag; ∥tag=0表示结点的左子女已访问，tag=1为右子女已访问 }stack; stack s[],s1[];∥栈，容量足够大 BiTree Ancestor(BiTree root, BiTree p, BiTree q, BiTree r) ∥求二叉树上结点p和q的最近的共同祖先结点r { top=0; bt=root; while(bt!=null ||top>0) { while(bt!=null && bt!=p && bt!=q) ∥结点入栈 { s[++top].t=bt; s[top].tag=0; bt=bt->lchild; } ∥沿左分枝向下 if(bt==p) ∥不失一般性，假定p在q的左侧,遇结点p时，栈中元素均为p的祖先结点{ for(i=1;i<=top;i++) s1[i]=s[i]; top1=top; ∥将栈s的元素转入辅助栈s1保存, top1记住栈顶 } if(bt==q) ∥找到q 结点 for(i=top;i>0;i--) ∥将栈中元素的树结点到s1去匹配 { pp=s[i].t; for(j=top1;j>0;j--) if(s1[j].t==pp) { printf(“共同的祖先已找到\n”)； return (pp); } ｝ while(top!=0 && s[top].tag==1) top--; ∥退栈 if(top!=0)｛ 数据结构中二叉树中序遍历的教学分析 袁宇丽, 胡 玲 Ξ(内江师范学院计算机与信息科学系, 四川 内江 641112) 摘 要:数据结构的教学应注重方法的应用,在二叉树的中序遍历中使用投影法可以使遍历过程简单化, 再由其中的一种遍历递归算法(先序)推导得到另外两种(中序,后序)的遍历递归算法,让学生加深对整个遍 历过程的了解与掌握。 关键词:数据结构;二叉树;遍历;算法 中图分类号:G 642 文献标识码:A 文章编号:1671-1785(2006)04-0109-03 1 引言 《数据结构》是计算机学科的一门专业技术基础课,也是计算机程序设计的重要理论技术基础课。目的是在于让学生学会分析研究计算机加工的数据结构的特性,以便为应用涉及的数据结构选择适当的逻辑结构,存储结构及其相应的算法;并初步掌握算法的时间分析和空间分析的技术;培养学生进行复杂程序设计的能力和数据抽象的能力。但从学生角度而言,在学习该门课程时普遍反映较难,总觉得课程内容抽象,不易理解,好些具体算法不知从何下手。针对以上情况,任课教师在讲授该门课程时更应注重方法的应用,从多角度,多侧面展现知识点,化抽象为具体,化特殊为一般,不应只局限于教材上的一种解题模式,应结合自己的理解,补充新方法,这样才能更好的拓宽学生的思路,达到化难为易,举一反三的效果。下面以具体实例说明。 2 二叉树中序遍历的投影法 在二叉树的一些应用中,常常要求在树中查找具有某种特征的结点,或者对树中全部结点逐一进行某种处理。这就提出了一个遍历二叉树的问题,即如何按某条搜索路径巡访树中每个结点,使得每个结点均被访问一次,而且仅被访问一次。“访问”的含义很广,可以是对结点作各种处理,如输出结点的信息等。遍历对线性结构来说,是一个容易解决的问题。而对二叉树则不然,由于二叉树是一种非线性结构,每个结点都可能有两棵子树,因而需要寻找一种规律,以便使二叉树上的结点能排列在一个线性队列上,从而便于访问。 回顾二叉树的定义可知,二叉树是由三个基本单元组成:根结点、左子树、右子树。因此,若能依次遍历这三部分,便是遍历了整个二叉树。若限定先左后右的顺序,则分为三种情况:先(根)序遍历,中(根)序遍历,后(根)序遍历。二叉树的遍历及其应用是数据结构中一个很重要的知识点,要求学生能根据所给二叉树得到相应的三种遍历序列(前序,中序,后序),并能写出这三种遍历算法。以中序遍历而言,教材[1]结合图给出了中序遍历过程示意图,并具体分析了该遍历的递归执行过程。但递归调用及返回对学生来说本身就是一个较难掌握的知识,往往出现进入递归后不知怎样层层返回,所图1 二叉树 以书上在说明二叉树的中序遍历时借用递归调用与返回的 方法向学生展示整个遍历过程对初学者总感觉有一定难度。 我们在这里补充一种教材上没有提到的二叉树中序遍历的 直观方法:投影法。分析中序遍历的实质,是按先中序访问左子树,再访问根结点,最后中序访问右子树的顺序进行的。直 观上想,处于二叉树最左下方的结点应该是第一个要访问的结点,再结合二叉树本身的构造特点,是有严格的左右子树 之分的,所以投影法就是根据二叉树的结构特征得来的。对 于一棵二叉树,从根结点所在的层开始,将所有非空左子树 完全位于当前根结点的左方,将所有非空右子树完全位于当? 901?第21卷第4期N o 14V o l 121 内江师范学院学报JOU RNAL O F N E I J I AN G T EA CH ER S COLL EGE 收稿日期:2005-11-11 作者简介:袁字丽(1979-),女,四川自贡人,内江师范学院助教,硕士。 《数据结构》课程实验报告 实验名称树和二叉树实验序号 5 实验日期 姓名院系班级学号 专业指导教师成绩 教师评语 一、实验目的和要求 (1)掌握树的相关概念，包括树、结点的度、树的度、分支结点、叶子结点、儿子结点、双亲结点、树 的深度、森林等定义。 (2)掌握树的表示，包括树形表示法、文氏图表示法、凹入表示法和括号表示法等。 (3)掌握二叉树的概念，包括二叉树、满二叉树和完全二叉树的定义。 (4)掌握二叉树的性质。 (5)重点掌握二叉树的存储结构，包括二叉树顺序存储结构和链式存储结构。 (6)重点掌握二叉树的基本运算和各种遍历算法的实现。 (7)掌握线索二叉树的概念和相关算法的实现。 (8)掌握哈夫曼树的定义、哈夫曼树的构造过程和哈夫曼编码产生方法。 (9)掌握并查集的相关概念和算法。 (10)灵活掌握运用二叉树这种数据结构解决一些综合应用问题。 二、实验项目摘要 1．编写一程序，实现二叉树的各种基本运算，并在此基础上设计一个主程序完成如下功能： （1）输出二叉树b; （2）输出H结点的左、右孩子结点值； （3）输出二叉树b的深度； （4）输出二叉树b的宽度； （5）输出二叉树b的结点个数； （6）输出二叉树b的叶子结点个数。 2．编写一程序，实现二叉树的先序遍历、中序遍历和后序遍历的各种递归和非递归算法，以及层次遍历的算法。 三、实验预习内容 二叉树存储结构，二叉树基本运算（创建二叉树、寻找结点、找孩子结点、求高度、输出二叉树） 三、实验结果与分析 7-1 #include 第6章树和二叉树 一、选择题 1.有一“遗传”关系，设x是y的父亲，则x可以把它的属性遗传给y，表示该遗传关系最适合的数据结构是（ B ） A、向量 B、树 C、图 D、二叉树 2.树最适合用来表示（ B ） A、有序数据元素 B、元素之间具有分支层次关系的数据 C、无序数据元素 D、元素之间无联系的数据 3.树B 的层号表示为1a,2b,3d,3e,2c，对应于下面选择的（ C ） A、1a(2b(3d,3e),2c) B、a(b(D,e),c) C、a(b(d,e),c) D、a(b,d(e),c) 4.对二叉树的结点从1 开始连续编号，要求每个结点的编号大于其左、右孩子的编号，同一结点的左右孩子中， 其左孩子的编号小于其右孩子的编号，则可采用（ C ）次序的遍历实现二叉树的结点编号。 A、先序 B、中序 C、后序 D、从根开始按层次遍历 5.按照二叉树的定义，具有3 个结点的二叉树有（C ）种。 A、3 B、4 C、5 D、6 6.在一棵有n个结点的二叉树中，若度为2的结点数为n2，度为1的结点数为n1，度为0的结点数为n0，则树的最大高 度为（ E ），其叶结点数为（ H ）；树的最小高度为（ B ），其叶结点数为（ G ）；若采用链表存储结构，则有（ I ）个空链域。 log+1 C、log2n D、n A、n/2 B、??n2 E、n0+n1+n2 F、n1+n2 G、n2+1 H、1 I、n+1 J、n1K、n2L、n1+1 7.对一棵满二叉树，m 个树叶，n 个结点，深度为h，则（ D ） A、n=m+h B、h+m=2n C、m=h-1 D、n=2h-1 8.设高度为h 的二叉树中只有度为0 和度为2 的结点，则此类二叉树中所包含的结点数至少为（ B ），至多 为（D ）。 A、2h B、2h-1 C、2h-1 D、2h-1 9.在一棵二叉树上第5 层的结点数最多为（B）（假设根结点的层数为1） A、8 B、16 C、15 D、32 10.深度为5 的二叉树至多有（ C ）个结点。 A、16 B、32 C、31 D、10 11.一棵有124 个叶结点的完全二叉树，最多有（B ）个结点 A、247 B、248 C、249 D、250 12.含有129 个叶子结点的完全二叉树，最少有（ D ）个结点 A、254 B、255 C、256 D、257 13.假定有一棵二叉树，双分支结点数为15，单分支结点数为30，则叶子结点数为（ B ）个。 A、15 B、16 C、17 D、47 14.用顺序存储的方法将完全二叉树中所有结点逐层存放在数组R[1…n]中，结点R[i]若有左子树，则左子树是结 点（ B ）。 A、R[2i+1] B、R[2i] C、R[i/2] D、R[2i-1] 数据结构第6章树和二叉树 一、下面是有关二叉树的叙述，请判断正误 （√）1.若二叉树用二叉链表作存贮结构，则在n个结点的二叉树链表中只有n-1个非空指针域。 n个结点的二叉树有n-1条分支 （×）2.二叉树中每个结点的两棵子树的高度差等于1。 （√）3.二叉树中每个结点的两棵子树是有序的。 （×）4.二叉树中每个结点有两棵非空子树或有两棵空子树。 （×）5.二叉树中每个结点的关键字值大于其左非空子树（若存在的话）所有结点的关键字值，且小于其右非空子树 （若存在的话）所有结点的关键字值。 （应当是二叉排序树的特点） （×）6.二叉树中所有结点个数是2k-1-1，其中k是树的深度。（应2k-1） （×）7.二叉树中所有结点，如果不存在非空左子树，则不存在非空右子树。 （×）8.对于一棵非空二叉树，它的根结点作为第一层，则它的第i层上最多能有2i -1个结点。 （应2i-1） （√）9.用二叉链表法（link-rlink）存储包含n个结点的二叉树，结点的2n个指针区域中有n+1个为空指针。（用二叉链表存储包含n个结点的二叉树，结点共有2n个链域。由于二叉树中，除根结点外，每一个结点有且仅有一个双亲，所以只有n-1个结点的链域存放指向非空子女结点的指针，即有后继链接的指针仅n-1个，还有n+1个空指针。）采用二叉链表存储有2n个链域，空链域为：2n-（n-1）=n+1 （√）10.具有12个结点的完全二叉树有5个度为2的结点。 最快方法：用叶子数＝[ n/2] ＝6，再求n2=n0-1=5 [n/2] 除的结果四舍五入 二、填空 1．由３个结点所构成的二叉树有5种形态。 2. 一棵深度为6的满二叉树有n1+n2=0+ n2= n0-1=31 个分支结点和26-1 =32个叶子。 注：满二叉树没有度为1的结点，所以分支结点数就是二度结点数。 (或：总结点数为n=2k-1=26-1=63，叶子数为n0= [ n/2] =32，满二叉数没有度为1的结点，由n0=n2+1得n2=n0-1=32-1=31) 习题六树和二叉树 一、单项选择题 1．以下说法错误的是 ( ) A．树形结构的特点是一个结点可以有多个直接前趋 B．线性结构中的一个结点至多只有一个直接后继 C．树形结构可以表达(组织)更复杂的数据 D．树(及一切树形结构)是一种"分支层次"结构 E．任何只含一个结点的集合是一棵树 2．下列说法中正确的是 ( ) A．任何一棵二叉树中至少有一个结点的度为2 B．任何一棵二叉树中每个结点的度都为2 C．任何一棵二叉树中的度肯定等于2 D．任何一棵二叉树中的度可以小于2 3．讨论树、森林和二叉树的关系，目的是为了（） A．借助二叉树上的运算方法去实现对树的一些运算 B．将树、森林按二叉树的存储方式进行存储 C．将树、森林转换成二叉树 D．体现一种技巧，没有什么实际意义 4．树最适合用来表示 ( ) A．有序数据元素 B．无序数据元素 C．元素之间具有分支层次关系的数据 D．元素之间无联系的数据 5．若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点个数是（）A．9 B．11 C．15 D．不确定 6．设森林F中有三棵树，第一，第二，第三棵树的结点个数分别为M1，M2和M3。与森林F对应的二叉树根结点的右子树上的结点个数是（）。 A．M1 B．M1+M2 C．M3 D．M2+M3 7．一棵完全二叉树上有1001个结点，其中叶子结点的个数是（） A． 250 B． 500 C．254 D．505 E．以上答案都不对 8. 设给定权值总数有n 个，其哈夫曼树的结点总数为( ) A．不确定 B．2n C．2n+1 D．2n-1 9．二叉树的第I层上最多含有结点数为（） A．2I B． 2I-1-1 C． 2I-1 D．2I -1 10．一棵二叉树高度为h,所有结点的度或为0，或为2，则这棵二叉树最少有( )结点A．2h B．2h-1 C．2h+1 D．h+1 11. 利用二叉链表存储树，则根结点的右指针是（）。 A．指向最左孩子 B．指向最右孩子 C．空 D．非空 14．在二叉树结点的先序序列，中序序列和后序序列中，所有叶子结点的先后顺序（）A．都不相同 B．完全相同 C．先序和中序相同，而与后序不同 D．中序和后序相同，而与先序不同 15．在完全二叉树中，若一个结点是叶结点，则它没（）。 A．左子结点 B．右子结点 C．左子结点和右子结点 D．左子结点，右子结点和兄弟结点 16．在下列情况中，可称为二叉树的是（） 第6章树和二叉树 部分答案解释如下。 12. 由二叉树结点的公式：n=n0+n1+n2=n0+n1+(n0-1)=2n0+n1-1，因为n=1001,所以1002=2n0+n1,在完全二叉树树中，n1只能取0或1,在本题中只能取0，故n=501，因此选E。 42.前序序列是“根左右”，后序序列是“左右根”，若要这两个序列相反，只有单支树，所以本题的A和B均对，单支树的特点是只有一个叶子结点，故C是最合适的，选C。A或B 都不全。由本题可解答44题。 47. 左子树为空的二叉树的根结点的左线索为空（无前驱），先序序列的最后结点的右线索为空（无后继），共2个空链域。 52．线索二叉树是利用二叉树的空链域加上线索，n个结点的二叉树有n+1个空链域。 部分答案解释如下。 6．只有在确定何序（前序、中序、后序或层次）遍历后，遍历结果才唯一。 19．任何结点至多只有左子树的二叉树的遍历就不需要栈。 24. 只对完全二叉树适用，编号为i的结点的左儿子的编号为2i(2i<=n)，右儿子是2i+1（2i+1<=n） 37. 其中序前驱是其左子树上按中序遍历的最右边的结点（叶子或无右子女），该结点无右孩子。 38 . 新插入的结点都是叶子结点。 42. 在二叉树上，对有左右子女的结点，其中序前驱是其左子树上按中序遍历的最右边的结点（该结点的后继指针指向祖先），中序后继是其右子树上按中序遍历的最左边的结点（该结点的前驱指针指向祖先）。 44．非空二叉树中序遍历第一个结点无前驱，最后一个结点无后继，这两个结点的前驱线索和后继线索为空指针。 三.填空题 1.(1)根结点(2)左子树(3)右子树 2.(1)双亲链表表示法(2)孩子链表表示法(3)孩 子兄弟表示法 3．p->lchild==null && p->rchlid==null 4.(1) ++a*b3*4-cd (2)18 5.平衡 因子 6. 9 7. 12 8.(1)2k-1 (2)2k-1 9.(1)2H-1 (2)2H-1 (3)H=?log2N?+1 10. 用顺序存储二叉树时，要按完全二叉树的形式存储，非完全二叉树存储时，要加“虚结 点”。设编号为i和j的结点在顺序存储中的下标为s 和t ,则结点i和j在同一层上的条 件是?log2s?=?log2t?。 11. ?log2i?=?log2j?12.(1)0 (2)(n-1)/2 (3)(n+1)/2 (4) ?log2n?+1 13.n 14. N2+1 15.(1) 2K+1-1 (2) k+1 16. ?N/2? 17. 2k-2 18. 64 19. 99 20. 11 21.(1) n1-1 (2)n2+n3 22.(1)2k-2+1（第k层1个结点，总结点个数是2H-1，其双亲是2H-1/2=2k-2）(2) ?log2i?+1 23.69 24. 4 25.3h-1 26. ?n/2? 27. ?log2k?+1 28.(1)完全二叉树 (2)单枝树，树中任一结点（除最后一个结点是叶子外）,只有左子女或 只有右子女。 29.N+1 30.(1) 128(第七层满，加第八层１个) (2) 7 31. 0至多个。任意二叉树，度为１的结点个数没限制。只有完全二叉树，度为１的结点个 数才至多为1。 32．21 33.(1)2 (2) n-1 (3) 1 (4) n (5) 1 (6) n-1 34.(1) FEGHDCB (2)BEF（该二叉树转换成森林，含三棵树，其第一棵树的先根次序是 BEF） 35.(1)先序（2）中序 36. (1)EACBDGF （2）2 37.任何结点至多只有右子女 的二叉树。 38.(1)a (2) dbe (3) hfcg 39.(1) . (2) ...GD.B...HE..FCA 40.DGEBFCA 41．(1)5 （2）略 42.二叉排序树 43.二叉树 44. 前序 45.(1)先根次序（2）中根次序46.双亲的右子树中最左下的叶子结点47.2 48.(n+1)/2 49.31（x的后继是经x的双亲y的右子树中最左下的叶结点） 50.(1)前驱 (2)后 继 51.(1)1 (2)y^.lchild (3)0 (4)x (5)1 (6) y (7)x(编者注：本题按 中序线索化) 52.带权路径长度最小的二叉树，又称最优二叉树 53.69 54.(1)6 (2)261 55.(1)80 (2)001（不唯一）56.2n0-1 57.本题①是表达式求值，②是在二叉排序树中删除值为x的结点。首先查找x，若没有x， 则结束。否则分成四种情况讨论：x结点有左右子树；只有左子树；只有右子树和本身是叶 子。 (1)Postoder_eval(t^.Lchild) (2) Postorder_eval(t^.Rchild) (3)ERROR(无此运 算符)(4)A (5)tempA^.Lchild (6)tempA=NULL(7)q^.Rchild (8)q (9)tempA^.Rchild (10)tempA^.Item 树与二叉树 一.选择题 1.假定在一棵二叉树中，双分支结点数为15，单分支结点数为30个，则叶子结 点数为（）个。 A．15B．16C．17D．47 2.按照二叉树的定义，具有3个结点的不同形状的二叉树有（）种。 A. 3 B. 4 C. 5 D. 6 3.按照二叉树的定义，具有3个不同数据结点的不同的二叉树有（）种。 A. 5 B. 6 C. 30 D. 32 4.深度为5的二叉树至多有（）个结点。1 A. 16 B. 32 C. 31 D. 10 5.设高度为h的二叉树上只有度为0和度为2的结点，则此类二叉树中所包含的 结点数至少为（）。 A. 2h B. 2h-1 C. 2h+1 D. h+1 6.对一个满二叉树2，m个树叶，n个结点，深度为h，则（）。 A. n=h+m3 B. h+m=2n C. m=h-1 D. n=2 h-1 1深度为n的二叉树结点至多有2n-1 2满二叉树是除最后一层无任何子节点外，每一层上的所有结点都有两个子结点的二叉树7.任何一棵二叉树的叶结点在先序.中序和后序遍历序列中的相对次序（）。 A.不发生改变 B.发生改变 C.不能确定 D.以上都不对 8.如果某二叉树的前根次序遍历结果为stuwv，中序遍历为uwtvs，那么该二叉 树的后序为（）。 A. uwvts B. vwuts C. wuvts D. wutsv 9.某二叉树的前序遍历结点访问顺序是abdgcefh，中序遍历的结点访问顺序是 dgbaechf，则其后序遍历的结点访问顺序是（）。 A. bdgcefha B. gdbecfha C. bdgaechf D. gdbehfca 10.在一非空二叉树的中序遍历序列中，根结点的右边（）。 A. 只有右子树上的所有结点 B. 只有右子树上的部分结点 C. 只有左子树上的部分结点 D. 只有左子树上的所有结点 11.树的基本遍历策略可分为先根遍历和后根遍历；二叉树的基本遍历策略可分为 先序遍历.中序遍历和后序遍历。这里，我们把由树转化得到的二叉树4叫做这棵数对应的二叉树。结论（）是正确的。 A.树的先根遍历序列与其对应的二叉树的先序遍历序列相同 B.树的后根遍历序列与其对应的二叉树的后序遍历序列相同 3对于深度为h的满二叉树，n=20+21+…+2h-1=2h-1，m=2h-1。故而n=h+m。 4树转化为二叉树的基本方法是把所有兄弟结点都用线连起来，然后去掉双亲到子女的连线，只留下双亲到第一个子女的连线。因此原来的兄弟关系就变为双亲与右孩子的关系。 1/ 9 第6章树和二叉树自测卷解答 一、下面是有关二叉树的叙述，请判断正误 （√）1. 若二叉树用二叉链表作存贮结构，则在n个结点的二叉树链表中只有n—1个非空指针域。（×）2.二叉树中每个结点的两棵子树的高度差等于1。 （√）3.二叉树中每个结点的两棵子树是有序的。 （×）4.二叉树中每个结点有两棵非空子树或有两棵空子树。 （×）5.二叉树中每个结点的关键字值大于其左非空子树（若存在的话）所有结点的关键字值，且小于其右非空子树（若存在的话）所有结点的关键字值。（应当是二叉排序树的特点） （×）6.二叉树中所有结点个数是2k-1-1，其中k是树的深度。（应2i-1） （×）7.二叉树中所有结点，如果不存在非空左子树，则不存在非空右子树。 （×）8.对于一棵非空二叉树，它的根结点作为第一层，则它的第i层上最多能有2i—1个结点。（应2i-1）（√）9.用二叉链表法（link-rlink）存储包含n个结点的二叉树，结点的2n个指针区域中有n+1个为空指针。 （正确。用二叉链表存储包含n个结点的二叉树，结点共有2n个链域。由于二叉树中，除根结点外，每一个结点有且仅有一个双亲，所以只有n-1个结点的链域存放指向非空子女结点的指针，还有n+1个空指针。）即有后继链接的指针仅n-1个。 （√）10. 具有12个结点的完全二叉树有5个度为2的结点。 最快方法：用叶子数＝[n/2]＝6，再求n2=n0-1=5 二、填空（每空1分，共15分） 1．由３个结点所构成的二叉树有5种形态。 2. 一棵深度为6的满二叉树有n1+n2=0+ n2= n0-1=31 个分支结点和26-1 =32个叶子。 注：满二叉树没有度为1的结点，所以分支结点数就是二度结点数。 3．一棵具有２５７个结点的完全二叉树，它的深度为9。 （注：用? log2(n) ?+1= ? 8.xx ?+1=9 4.设一棵完全二叉树有700个结点，则共有350个叶子结点。 答：最快方法：用叶子数＝[n/2]＝350 5. 设一棵完全二叉树具有1000个结点，则此完全二叉树有500个叶子结点，有499个度为2的结点，有1个结点只有非空左子树，有0个结点只有非空右子树。 答：最快方法：用叶子数＝[n/2]＝500 ，n2=n0-1=499。另外，最后一结点为2i属于左叶子，右叶子是空的，所以有1个非空左子树。完全二叉树的特点决定不可能有左空右不空的情况，所以非空右子树数＝0. 6. 一棵含有n个结点的k叉树，可能达到的最大深度为n，最小深度为2。 答：当k=1(单叉树)时应该最深，深度＝n（层）；当k=n-1（n-1叉树）时应该最浅，深度＝2（层），但不包括n=0或1时的特例情况。教材答案是“完全k叉树”，未定量。) 7.二叉树的基本组成部分是：根（N）、左子树（L）和右子树（R）。因而二叉树的遍历次序有六种。最常用的是三种：前序法（即按N L R次序），后序法（即按L R N次序）和中序法（也称对称序法，即按L N R次序）。这三种方法相互之间有关联。若已知一棵二叉树的前序序列是BEFCGDH，中序序列是FEBGCHD，则它的后序序列必是 F E G H D C B。 解：法1：先由已知条件画图，再后序遍历得到结果； 法2：不画图也能快速得出后序序列，只要找到根的位置特征。由前 序先确定root，由中序先确定左子树。例如，前序遍历BEFCGDH中， 根结点在最前面，是B；则后序遍历中B一定在最后面。 法3：递归计算。如B在前序序列中第一，中序中在中间（可知左 右子树上有哪些元素），则在后序中必为最后。如法对B的左右子树同 数据结构之二叉树 第一篇：数据结构之链表 第二篇：数据结构之栈和队列 在这篇文章里面，我们主要探讨和树相关的话题。 首先，我们来对树进行定义：树是n（n>= 0）个节点的有限集。在任何一个非空树中：（1）有且仅有一个特定的称为“根”的节点；（2）当n>1时，其余节点可分为m（m>0）个互相相关的有限集T1、T2、T3……，其中每一个集合本身又是一棵树，并且称为根的子树。 对于我们这篇文章里讨论的二叉树，它是一种特殊的树形结构，每个节点至多只有两颗子树，并且子树有左右之分，其次序不能随意颠倒。 接下来，我们使用java代码来定义一棵树： 1public class BinNode { 2private int m_Value; 3private BinNode m_Left; 4private BinNode m_Right; 5public void setValue(int m_Value) { 6this.m_Value = m_Value; 7 } 8public int getValue() { 9return m_Value; 10 } 11public void setLeft(BinNode m_Left) { 12this.m_Left = m_Left; 13 } 14public BinNode getLeft() { 15return m_Left; 16 } 17public void setRight(BinNode m_Right) { 18this.m_Right = m_Right; 19 } 20public BinNode getRight() { 21return m_Right; 22 } 23 24public boolean isLeaf() 25 { 26return m_Left == null && m_Right == null; 27 } 28 } 数据结构练习（二叉树） 学号31301374 姓名张一博班级软件工程1301 . 一、选择题 1．按照二叉树定义，具有3个结点的二叉树共有 C 种形态。 (A) 3 (B) 4 (C) 5 (D) 6 2．具有五层结点的完全二叉树至少有 D 个结点。 (A) 9 (B) 15 (C) 31 (D) 16 3．以下有关二叉树的说法正确的是 B 。 (A) 二叉树的度为2 (B)一棵二叉树的度可以小于2 (C) 至少有一个结点的度为2 (D)任一结点的度均为2 4．已知二叉树的后序遍历是dabec，中序遍历是debac，则其前序遍历是 D 。 （A）acbed （B）decab (C) deabc (D) cedba 5．将一棵有1000个结点的完全二叉树从上到下，从左到右依次进行编号，根结点的编号为1，则编号为49的结点的右孩子编号为 B 。 (A) 98 (B) 99 (C) 50 (D) 没有右孩子 6．对具有100个结点的二叉树，若有二叉链表存储，则其指针域共有 D 为空。 (A) 50 (B) 99 (C) 100 (D) 101 7．设二叉树的深度为h，且只有度为1和0的结点，则此二叉树的结点总数为 C 。 (A) 2h (B) 2h-1 (C) h (D) h+1 8．对一棵满二叉树，m个树叶，n个结点，深度为h，则 D 。 (A) n=h+m (B) h+m=2n (C)m=h-1 (D)n=2h-1 9．某二叉树的先序序列和后序序列正好相反，则下列说法错误的是 A 。 (A) 二叉树不存在 (B) 若二叉树不为空，则二叉树的深度等于结点数 (C) 若二叉树不为空，则任一结点不能同时拥有左孩子和右孩子 (D) 若二叉树不为空，则任一结点的度均为1 10．对二叉树的结点从1开始进行编号，要求每个结点的编号大于其左右孩子的编号，同一结点的左右孩子中，其左孩子的编号小于其右孩子的编号，可采用 A 遍历实现编号。 (A) 先序(B)中序(C)后序(D)层序 11．一个具有1025个结点的二叉树的高h为 C 。 (A) 10 (B)11 (C)11~1025 (D)10~1024 12．设n,m为一棵二叉树上的两个结点，在中序遍历时，n在m前的条件是 C 。 ( A) n在m右方(B)n是m祖先 (C) n在m左方(D) n是m子孙 13．实现对任意二叉树的后序遍历的非递归算法而不使用栈结构，最佳方案是二叉树采用 C 存储结构。 (A) 二叉链表(B) 广义表(C)三叉链表(D)顺序 14. 一棵树可转换成为与其对应的二叉树，则下面叙述正确的是 A 。 (A) 树的先根遍历序列与其对应的二叉树的先序遍历相同 (B) 树的后根遍历序列与其对应的二叉树的后序遍历相同 (C) 树的先根遍历序列与其对应的二叉树的中序遍历相同 (D) 以上都不对 二、填空题 1．对一棵具有n个结点的二叉树，当它为一棵完全二叉树时具有最小高度；当它为单分支二叉树时，具有最大高度。 ******************************* 实验题目：二叉树的操作 实验者信息：班级 13007102,姓名 庞文正，学号 1300710226 实验完成的时间 3:00 ****************************** 一、 实验目的 1, 掌握二叉树链表的结构和二叉树的建立过程。 2, 掌握队列的先进先出的运算原则在解决实际问题中的应用。 3, 进一步掌握指针变量、指针数组、动态变量的含义。 4, 掌握递归程序设计的特点和编程方法。 二、 实验内容 已知以二叉链表作存储结构，试编写按层次遍历二叉树的算法。 （所谓层次遍历，是 指从二叉树的根结点开始从上到下逐层遍历二叉树， 在同一层次中从左到右依次访问各个节 点。）调试程序并对相应的输出作出分析；修改输入数据，预期输出并验证输出的结果。加 深对算法的理解。 三、 算法设计与编码 1. 本实验用到的理论知识 总结本实验用到的理论知识， 实现理论与实践相结合。 总结尽量简明扼要， 并与本次实验密 切相关，最好能加上自己的解释。 本算法要采用一个循环队列 que,先将二叉树根结点入队列，然后退队列，输出该 结点；若它 有左子树，便将左子树根结点入队列； 若它有右子树，便将右子树根结点入队列， 直到队列空为止。因为队列的特点是先进先出，从而达到按层次顺序遍历二叉的目的。 2. 算法概要设计 给出实验的数据结构描述，程序模块、功能及调用关系 #include 第6章树和二叉树 6.1 知识点概述 树（Tree）形结构是一种很重要的非线性结构，它反映了数据元素之间的层次关系和分支关系。在计算机科学中具有广泛的应用。 1、树的定义 树（Tree）是n（n≥0）个数据元素的有限集合。当n＝0时，称这棵树为空树。在一棵非空树T中： （1）有一个特殊的数据元素称为树的根结点，根结点没有前驱结点。 （2）若n>1，除根结点之外的其余数据元素被分成m（m>0）个互不相交的集合T1，T2，…，Tm，其中每一个集合Ti（1≤i≤m）本身又是一棵树。树T1，T2，…，Tm称为这个根结点的子树。 2、树的基本存储结构 （1）双亲表示法 由于树中的每一个结点都有一个唯一确定的双亲结点，所以我们可用一组连续的 存储空间（即一维数组）存储树中的结点。每个结点有两个域：一个是data域，存放结点信息，另一个是parent域，用来存放双亲的位置(指针)。 （2）孩子表示法 将一个结点所有孩子链接成一个单链表形，而树中有若干个结点，故有若干个单 链表，每个单链表有一个表头结点，所有表头结点用一个数组来描述这种方法通常是把每个结点的孩子结点排列起来，构成一个单链表，称为孩子链表。 （3）双亲孩子表示法 双亲表示法是将双亲表示法和孩子表示法相结合的结果。其仍将各结点的孩子结点分别组成单链表，同时用一维数组顺序存储树中的各结点，数组元素除了包括结点本身的信息和该结点的孩子结点链表的头指针之外，还增设一个域，存储该结点双亲结点在数组中的序号。 （4）孩子兄弟表示法 这种表示法又称为树的二叉表示法，或者二叉链表表示法，即以二叉链表作为树的存储结构。链表中每个结点设有两个链域，分别指向该结点的第一个孩子结点和下一个兄弟（右兄弟）结点。 3、二叉树的定义 二叉树（Binary Tree）是个有限元素的集合，该集合或者为空、或者由一个称为根(root)的元素及两个不相交的、被分别称为左子树和右子树的二叉树组成。当集合为空时，称该二叉树为空二叉树。在二叉树中，一个元素也称作一个结点。 4、满二叉树 定义：在一棵二叉树中，如果所有分支结点都存在左子树和右子树，并且所有叶子结点都在同一层上，这样的一棵二叉树称作满二叉树。 5、完全二叉树 定义：一棵深度为k的有n个结点的二叉树，对树中的结点按从上至下、从左到右的顺序进行编号，如果编号为i（1≤i≤n）的结点与满二叉树中编号为i的结点在二叉树中的位置相同，则这棵二叉树称为完全二叉树。完全二叉树的特点是：叶子结点只能出现在最下层和次下层，且最下层的叶子结点集中在树的左部。 6、二叉树的性质 树是一种比较重要的数据结构，尤其是二叉树。二叉树是一种特殊的树，在二叉树中每个节点最多有两个子节点，一般称为左子节点和右子节点（或左孩子和右孩子），并且二叉树的子树有左右之分，其次序不能任意颠倒。二叉树是递归定义的，因此，与二叉树有关的题目基本都可以用递归思想解决，当然有些题目非递归解法也应该掌握，如非递归遍历节点等等。本文努力对二叉树相关题目做一个较全的整理总结，希望对找工作的同学有所帮助。 二叉树节点定义如下： structBinaryTreeNode { intm_nValue; BinaryTreeNode* m_pLeft; BinaryTreeNode* m_pRight; }; 相关链接： 轻松搞定面试中的链表题目 题目列表： 1. 求二叉树中的节点个数 2. 求二叉树的深度 3. 前序遍历，中序遍历，后序遍历 4.分层遍历二叉树（按层次从上往下，从左往右） 5. 将二叉查找树变为有序的双向链表 6. 求二叉树第K层的节点个数 7. 求二叉树中叶子节点的个数 8. 判断两棵二叉树是否结构相同 9. 判断二叉树是不是平衡二叉树 10. 求二叉树的镜像 11. 求二叉树中两个节点的最低公共祖先节点 12. 求二叉树中节点的最大距离 13. 由前序遍历序列和中序遍历序列重建二叉树 14.判断二叉树是不是完全二叉树 详细解答 1. 求二叉树中的节点个数 递归解法： （1）如果二叉树为空，节点个数为0 （2）如果二叉树不为空，二叉树节点个数= 左子树节点个数+ 右子树节点个数+ 1 参考代码如下： 1.int GetNodeNum(BinaryTreeNode * pRoot) 2.{ 3.if(pRoot == NULL) // 递归出口 4.return 0; 5.return GetNodeNum(pRoot->m_pLeft) + GetNodeNum(pRoot->m_pRight) + 1; 6.} 学生实验报告 学院：软通学院 课程名称：数据结构与算法 专业班级：软件142 班 姓名：邹洁蒙 学号： 0143990 学生实验报告 （二） 一、实验综述 1、实验目的及要求 目的：1）掌握树与二叉树的基本概念； 2）掌握二叉树的顺序存储，二叉链表的先序遍历中序遍历和后序遍历算法； 3）掌握树的双亲表示法。 要求：1）编程：二叉树的顺序存储实现； 2）编程：二叉链表的先序遍历中序遍历和后序遍历实现； 3）编程：树的双亲表示法实现。 2、实验仪器、设备或软件 设备：PC 软件：VC6 二、实验过程(编程，调试，运行；请写上源码，要求要有注释) 1.编程：二叉树的顺序存储实现 代码： BiTree::BiTree()//建立存储空间 { data = new int[MAXSIZE]; count = 0; } void BiTree::AddNode(int e)//加结点 { int temp = 0; data[count] = e; count++;//从编号0开始保存 } 运行截图： 2.编程：二叉链表的先序遍历中序遍历和后序遍历实现代码： void InOrderTraverse(BiTree* Head)//中序遍历 { if (Head) { InOrderTraverse(Head->LeftChild); cout << Head->data<<" "; InOrderTraverse(Head->RightChild); } } void PreOrderTraverse(BiTree* Head)//先序遍历 { if (Head) { cout << Head->data << " "; PreOrderTraverse(Head->LeftChild); PreOrderTraverse(Head->RightChild); } } void PostOrderTraverse(BiTree* Head)//后序遍历 { if (Head) { PostOrderTraverse(Head->LeftChild); PostOrderTraverse(Head->RightChild); cout << Head->data << " "; } } 运行截图： 1.设二叉树bt 的存储结构如下，其中bt为树根结点指针，left，right分别为结 点的左、右孩子指针，dada为结点的数据域。请完成下列各题： 1）画出二叉树bt的逻辑结构 2）写出按先序、中序、后序遍历二叉树所得到的结点序列 3）画出二叉树bt的后序线索化树 1 2 3 4 5 6 7 8 9 10 2.二叉树结点数值采用顺序存储结构，如图所示， 1）画出二叉树表示 2）写出前序遍历，中序遍历和后序遍历的结果 3）写出结点值c的父结点，其左、右孩子。 4）画出将此二叉树还原成森林的图 3.已知一棵二叉树的中序序列为cbedahgijk，后序序列为cedbhjifa，画出该二叉 树的先序线索二叉树。 4.有一份电文中共使用五个字符：a、b、c、d、e，它们的出现频率依次为4、7、5、 2、9，试画出对应的Huffman树（请按左子树根结点的权小于等于右子树根结点 的权的次序构造），求出每个字符的Huffman编码。 5.设给定权集w={2，3，4，8，9}，试构造关于w的一棵哈夫曼树，并求其加权路 径长度WPL。 6.假设二叉树采用链接存储方式存储，编写一个中序遍历二叉树的非递归过程。 7.假设二叉树采用链接存储方式存储，root指向根结点，p所指结点为任一给定的 结点。编写一个求出从根结点到p所指结点之间路径的函数。 8.在二叉树中查找值为x的结点，试设计打印值为x的结点的所有祖先的算法，假 设值为x的结点不多于1个。 9.假设二叉树采用链接存储方式存储，试设计一个算法计算一棵给定二叉树的所有 结点数。 10.假设二叉树采用链接存储方式存储，试设计一个算法计算一棵给定二叉树的单孩 子结点数。 数据结构课程设计 题目：二叉树的操作 学生姓名： 学号： 系部名称：计算机科学与技术系 专业班级： 指导教师： 课程设计任务书 第一章程序要求 1）完成二叉树的基本操作。 2）建立以二叉链表为存储结构的二叉树； 3）实现二叉树的先序、中序和后序遍历； 4）求二叉树的结点总数、叶子结点个数及二叉树的深度。 第二章算法分析 建立以二叉链表为存储结构的二叉树，在次二叉树上进行操作； 1先序遍历二叉树的操作定义为： 若二叉树唯恐则为空操作；否则 （1）访问根节点； （2）先序遍历做字数和； （3）先序遍历有子树； 2中序遍历二叉树的操作定义为： 若二叉树为空，则空操作;否则 （1）中序遍历做子树； （2）访问根节点； （3）中序遍历有子树； 3后续遍历二叉树的操作定义为： 若二叉树为空则为空操作；否则 （1)后序遍历左子树; （2)后序遍历右子树; （3）访问根节点； 二叉树的结点总数、叶子结点个数及二叉树的深度。 第三章二叉树的基本操作和 算法实现二叉树是一种重要的非线性数据结构，是另一种树形结构，它的特点是每个节点之多有两棵子树(即二叉树中不存在度大于2的结点)，并且二叉树的结点有左右之分，其次序不能随便颠倒。 1.1二叉树创建 二叉树的很多操作都是基于遍历实现的。二叉树的遍历是采用某种策略使得采用树形结构组织的若干年借点对应于一个线性序列。二叉树的遍历策略有四种：先序遍历中续遍历后续遍历和层次遍历。 基本要求 1 从键盘接受输入数据（先序），以二叉链表作为存储结构，建立二叉树。 2 输出二叉树。 3 对二叉树进行遍历（先序，中序，后序和层次遍历） 4 将二叉树的遍历打印出来。 一．问题描述 二叉树的很多操作都是基于遍历实现的。二叉树的遍历是采用某种策略使得采用树型结构组织的若干结点对应于一个线性序列。二叉树的遍历策略有四种：先序遍历、中序遍历、后序遍历和层次遍历。 二．基本要求 1．从键盘接受输入数据（先序），以二叉链表作为存储结构，建立二叉树。 2．输出二叉树。 3．对二叉树进行遍历（先序、中序、后序和层次遍历）。 4．将二叉树的遍历结果打印输出。 三．提示与分析 1．主要数据类型 ①二叉链表 # define DataType char /*元素类型*/ typedef struct BiTNode {DataType data; struct BiTNode *lchild, *rchild; }BiTNode, *BiTree; ②二叉树的遍历序列 DataType preorder[n]; DataType inorder[n]; DataType postorder[n]; 2．基本功能分析 ①采用教材上类似于先序遍历的方法逐个输入结点，建立二叉链表存储的二叉树。 ②采用递归算法对二叉树分别进行先序、中序、后序遍历。 ③以队列为辅助结构实现二叉树的层次遍历。 ④结合先序遍历，以凹入表形式输出二叉树。 //定义二叉树结点结构和操作的头文件btree1.h //定义二叉树结点值的类型为字符型 typedef char ElemType; //定义二叉树结点类型 struct BTreeNode { ElemType data; BTreeNode* left; BTreeNode* right; };数据结构中二叉树中序遍历的教学分析
数据结构树和二叉树实验报告
《数据结构》习题集：_树和叉树
数据结构 二叉树练习题答案
第六章树和二叉树习题数据结构
目前最完整的数据结构1800题包括完整答案树和二叉树答案
数据结构树和二叉树习题
数据结构第6章二叉树自测题参考答案
数据结构之二叉树概述
数据结构练习(二叉树)
数据结构实验-二叉树的操作
数据结构—— 树和二叉树知识点归纳
数据结构中二叉树各种题型详解及程序
数据结构实验报告之树与二叉树
数据结构习题 树 数据机构c语言版
数据结构课程设计---二叉树的操作