第六章 参考答案一、名词解释（略）
二、填空题分支层次、根、直接前趋子孙、祖先空、只含根、非空左子树、非空右子树、非空左右子树
2i-1
2k-1
n2+1
最大值、完全
floor(log2n)+1
根、floor(i/2)、左孩子、右孩子、2i、右孩子、2i+1
顺序、链式根根、root
指向该结点的一个孩子、空指针NULL
2n、n-1、n+1
二叉链表、三叉链表虚结点
*count++,countleaf(l->rchile,count)
访问根结点、遍历左子树、遍历右子树
DLR、LDR、LRD、先根（或前序）遍历、中根（或中序）遍历、后根（或后序）遍历先根遍历、后根遍历、层次遍历非终端结点、终端结点
WPL（T）＝
i<k,x,T[j].wt,k+i,k+i,m+n,x,y
第一先根
floor(n/2),l,n,floor(n/2)+1
后面相同左子树、右子树、左子树、右子树树最短、较近
2m-1
（A），（E、G、I、J、K、L、N、O、P、Q、R），（3），（4），（5），（J、K）（C）
1、0
树、二叉树只有一个根结点的树、空二叉树
n-1
n-2m+1
5、答案见图 A B A C C
B A C C B A
C B A B
WPL＝165
62
37 25
19 18 13 12
10 9 7 6
5 4
41、m-1
42、本题有一定的难度，其求解方法如下：设总结点数为n度为0、1、2、3的结点数分别为n0,n1,n3,则有下面两个等式成立：
n=n0+n1+n2+n3 /*结点数*/
n-1=n1+2n2+3n3 /*分支数*/
两式相减得 n0=1+n2+2n3=1+3+2x4=12 (12)
三、单项选择
1、①2、③3、④4、④5、②6、④7、③8、④9、③10、①
11、④12、②13、④14、①15、②16、①17、②18、④19、①20、②
21、④22、③23、①24、②25、②26、③27、③28、①29、②30、④
31、④32、②33、②34、③35、①36、③37、③
四、简答及应用题二叉链表的类型定义如下：
typedef struct btnode *bitreptr;
struct btnode{ datatype data;
bitreptr lchild,rehild;
}
bitreptr root;
其中，data域称为数据域，用于存储二叉树结点中的数据元素；lchild 域称为左孩子指针域，用于存放指向本结点左孩子的指针（简称左指针）。rchild域称为右孩子指针域，用于存放指向本结点右孩子的指针（简称右指针）。
2．三叉链表与二叉链表的主要区别在于，它的结点比二叉链表的结点多一个指针域，该域用于存储一指向本结点双亲的指针。三叉链表的类型定义如下：
typedef struct ttnode *ttnodeptr;
struct ttnode
{datatype data;
ttnodeptr lchild,rchild,parent;
}
ttnodeptr root;
3．typedef struct tagnode /*表结点类型*/
{int child; /*孩子结点在表头数据组中的序号*/
struct tagnode *next; /*表结点指针域*/
}node,*link;
typedef struct /*头结点类型*/
{datatype data; /*结点数据元素*/
link headptr; /*头结点指针域*/
}headnode;
typedef headnode childlink[axnode]; /*表头结点数组*/
带双亲的孩子链表表示法，其类型定义与孩子链表类似，只需将头结点的定义改为：
typedef struct
{datatype data;
int parent;
link headptr;
}headnodel;
4．就图简答题4.1（a）中的二叉树
⑴根结点是A； ⑵叶结点是：D，F，J；
⑶G的双亲是：E； ⑷G的祖先是：A；
⑸G的孩子是：H； ⑹E的子孙是：F，G，H，I，J；
⑺E的兄弟是：B；C的兄弟是：C无兄弟；⑻结点B和I的层数分别是2，5；
⑼树的深度是：6； ⑽以结点G为根的子树的深度是：4；
⑾树的度数是：2。
就图简答题4.1(b)中的树
⑴根结点是A； ⑵叶结点是：D，F，G，H，I，J；
⑶G的双亲是：C； ⑷G的祖先是：A；
⑸G的孩子是：G无孩子； ⑹E的子孙是：H，I，J；
⑺E的兄弟是：D；C的兄弟是：B； ⑻结点B和I的层数分别是2，4；
⑼树的深度是：4； ⑽以结点G为根的子树的深度是：1；
⑾树的度数是：3。
5．(a)因为该图所示结构，有两个结点没有直接前趋，即有两个根结点，而树只能有一个根结点。
(b)因为找不到树的根结点，所以不满足树的定义。
(c)因为最上面一个结点的后继结点分不出两个不相交的子集，不满足树的定义。
6．答案见图简答题6所示。
7．答案见图简答题7-2所示。
8．先根序列：A B C D E F G H I J;
中根序列：B C D A F E H J I G;
后根序列：D C B F J I H G E A。
9．⑴二叉树中任意一个结点都无左孩子；
⑵二叉树中任意一个结点都无右孩子；
⑶至多只有一个结点的二叉树。
10．由后根遍历序列得到二叉树的根结点A（后根序列中最后一个结点）；在中序序列中，A的左力是A的左子树上的结点，A的右边是A的右子树上的结点；再到后根序列中找左子树和右子树的根结点，依次类推，直到画出该二叉树，如图简答题10所示。
11．答案见图简答题11-2所示。
12．先根序列：A B E F K L C G D H I J；
后根序列：E K L F B G C H I J D A；
层次序列：A B C D E F G H I J K L。
13．答案见图简答题13-2所示。
14．答案见图简答题14-2所示。
(a)(b)(c)(d)(e)
15.答案见图简答题15-1所示。
16．利用先根遍历方法查找结点*A的直接后继：
当A->lchild<>NULL时，A的先根后继结点是A->lchild；否则，当A->rchild<>NULL时，A的先根后继结点是A->rchild。
16．利用先根遍历方法查找结点*A的直接后继：
当A->lchild<>NULL时，A的先根后继结点是A->lchild；否则，当A->rchild<>NULL时，A的先根后继结点是A->rchild。
利用中根遍历方法查找结点*A的直接后继：
当A->lchild<>NULL时，*A的中根前趋是其左子树的“最右下结点”； 当A->rchild<>NULL时，*A的中根后继是其右子树的“最左下结点”。
利用后根遍历方法查找结点*A的直接前趋：
当A->rchild<>NULL时，A的后根前趋结点是A->rchild；否则，A->rchild<>NULL时，A的后根前趋结点是A->lchild；
17．本题的解题过程如下：
①由前根序列各A是二叉树的根结点；由中根序列知GDHBE是A的左子树中的结点，CIJF是A的右子树中的结点。
②由前根序列知B是A的左子树的根结点；由中根序列知GDH是B的左子树中的结点，E是B的右子树中的结点。
③由前根序列知D是B的左子树的根结点；由中根序列知G是B的左子树中的结点，H是B的右子树中的结点
④由前根序列知C是A的右子树的根结点；由中根序列知IJF是C的右子树中的结点（C的左子树为空）。
⑤由前根序列知F是C的右子树的根结点；由中根序列知IJ是F的左子树中的结点，（F的右子树为空）。
⑥由前根序列知I是F的左子树的根结点；由中根序列知J是F的右子树中的结点，（F的左子树为空）。
完整的二叉树如图简答题17所示。
18．第一步，先以给定的权值构造出哈夫曼树，如图简答题18所示。
第二步，假没规定哈夫曼树上所有的左指针用0表示，所有的右指针用1表示。
第三步，从根开始沿每一条通向叶子的路径上的数字，这些数字就是对应叶子结点所代表的字母的哈夫曼编码。8个字母所应的哈夫曼编码为：
7---0010 19---10
2---00000 6---0001
32---01 3---00001
21---11 10---0011
图简答题18
19．任意一棵二叉树只有先转换成完全二叉树后，才能用顺序存储结构进行存储。转换后的二叉树如图19-2所示。任意二叉树的顺序存储结构示意图如图19-3所示。
图简答题19-2
A
B
C
D
E
F
G
……
图简答题19-3
20．转换后的二叉树如图简答题20-2所示。
图简答题20-2
五、算法设计
1．⑴bitreptr PARENT(bitreptr BT,bitreptr p,datatype data) /*调用前p为空指针*/
{if(BT!=NULL)if(BT->data==X) return(p); /*找到,返回其父结点*/
else{p=BT;
PARENT(BT->lchild,p,X); /*查找其左子树*/
PARENT(BT->rchild,p,X); /*查找其右子树*/
}
}
⑵void CREATE(datatype X,bitreptr LBT,bitreptr RBT)
{ BT=malloc(size); /*申请根结点*/
BT->data=x;BT->lchild=LBT; BT->rchild=RBT;
}
(3)void DELLEFT(bitreptr BT,datatype X)
{if (BT!=null ) if (BT->data = X) {BT->lchild=null,BT->rchild=null;}
else{DELLEFT(BT->lchild,X); DELLEFT(BT->rchild,X);}
}
2.(1) ttnodeptr PARENT(ttndoeptr BT,datatype data)
{ if (BT!=null) if (BT->data = X) return (BT->patrnt); /*找到，返回其父结点*/
else {PARENT (BT->lchild,X);PARENT(BT->rchild,X);}
}
(2) void CREATE(datatype X,ttnodeptr LBT,ttnodeper RBT)
{BT=malloc(size); /*申请根结点*/
BT->data=x; BT->lchild=LBT; BT->rchild=RBT;
LBT->parent = BT; R BT->parent = BT;
}
(3)void DELLEFT(ttnodeptr BT,datatype X)
{if (BT!=null) if (BT->data ==X){ BT->lchild =null; BT->rchild=null;}
else {DELLEFT(BT->lchild,X); DELLEFT(BT->rchild,X);}
}
3.采用递归方法，对每一个结点先求其左右子树的深度，取较大值加1作为此结点的深度。
Int depth (bitreptr BT)
{if (BT= =null)return（0);
else {l=hepth (BT->lchild);
r=hepth(BT->rchild);
return((l>r?l:r)+1);
}
4.按照题目要求，附加一个工作栈以完成对该树的非递归遍历，思路如下：
每访问一个结点，将此结点压入栈，查看此结点是否有左子树，若有，访问左子树，转（1）执行。
从栈弹出一结点，如果此结点有右子树，访问右子树并转第（1）步执行，否则转第（2）步执行。
Void preorder(datatype a[n],int n )
{ INISTACK(sd); /*初始工作栈sd*/
I=1; PUSH(sd,0);
If (i<=n)
{visite(a[I]); /*访问此结点*/
PUSH(sd,I);
J=2*I; /* 取左子树*/
While(!EMPTY(sd)) /*若栈sd 非空*/
{while(j<=n) /*若2I<=n,则该结点有左子树*/
{PUSH(sd,j); /*进栈*/
I=j; j=2*I; /*取左子树*/
Visite(a[I]); /*访问此结点*/
}
I=pop(sd); /*出栈*/
J=2*I+1; /*取右子树*/
}
}
}
5.本题用递归方法，采用以下步骤：
若t1和t2都是空树则等价；
若t1和t2有一个为空树另一个非空树，则不等价。
若t1和t2两个都是非空树且它们的值相等，比较它们的左、右子树。
Int same_tree (bitreptr t1,t2)
{if ((t1= =null)&&(t2= =null)) return(1); /*t1,t2都是空树*/
Else if ((t1= =null)||(t2= =null)) return(0); /*t1,t2只有一个空树*/
Else if (t1->data = =t2->data) /*t1和t2的值相等*/
Return (same_tree (t1->lchild,t2->lchild)&&
Same_tree(t1->rchild,t2->rchild));
}
6.采用后根遍历递归访问的方法，交换每一个结点的左右子树。
Void exchg_tree(bitreptr BT)
{if (BT!=null) /*非空*/
{exchg_tree(BT->lchild); /*交换左子树所有结点指针*/
exchg_tree(BT->rchild); /*交换右子树所有结点指针*/
p=BT->lchild; /*交换根结点左右指针*/
BT->lchild=BT->rchild; ->rchild =p;
}
}
7.设置一个栈用于装入查找结点的所有祖先。
栈的元素结构说明如下：
typedef struct
{bitreptr p;
int tag;
}snode;
int search(bitreptr T,datatype X)
{top =0; /*栈s初置为0*/
while ((T!=null)&&(T->data!=X)||(top!=0))
{while (((T!=null)&&(T->data!=X))
{top ++;
s[top ].p=T; s[top].tag=0; /*结点入栈，置标志0*/
T=T->lchild; /*找左子树*/
}
if (((T!=null)&&(T->data==X)) /*找到*/
{for (I=1;I<=top;I++)
printf (“%d\n”,s[I].p->data); /*输出*/
return(1);
}
else while ((top>0)&&(s[top].tag==1)) top --; /*退出右子树已访问过的结点*/
if (top>0){s[top].tag=1;T=s[top]; T=T->rchild;/*置访问标志为1，访问右子树*/
}
}
return(0);
}
8,（1） PARENT(T,X)的功能是查找值为X的结点的双亲。查找的方法是，在表头数组中依次顺序查看每个头结点的链域，查找是否含水量有值为X的结点，如有，则返回其结点的值。
Headnode parent (headnode T,datatype X ) /*n表示树的结点数*／
{k=0;
if (T[k].data= =X) return(null); ／*根结点值是Ｘ返回空值*／
while (k<n)
{p=T[k].headptr; /*取子树指针*/
while (p!=null)
{j=p->child; /*取孩子序号*/
if (T[j].data= =X) return(T[k]); /*查找到X，返回父结点*/
p=p->next; /*取下一个孩子*/
}
k++;
}
return(null); /*没有找到，返回空值*/
}
（2）HILD（T，X，I）的功能是在树T中查找值为X的结点的第I个孩子。算法思路是：先在表头结点中查找值为X的结点，然后再由此结点的链表找第I个孩子，如找到则返回这个孩子的指针值。
Headnode child(headnode T,datatype X,int I)
{k=0;
while ((k<n)&&(T[k].data!=X)) k++; /*在头结点中查找元素*/
if (t[k].data= =X) /*查找到元素X*/
{j=0; p=T[k].headptr ; /*取X结点第一个孩子*/
while ((p!=null )&&(j<I)){j++; p=p->next;};/*查找第I个孩子*/
if ((p!=null)&&(j= =I)) return(p); /*找到第I个孩子*/
else return(null); /*没找到，返回定指针*/
}
else return(null); /*没有找到结点X*/
}
(3) DELETE(T,X,I)的功能是删除值为X的结点的第I个孩子。算法思路是：先在表头数组中查找值为X的结点。找到后再沿此结点的链表查找第I个孩子，如存在将其删除。
Void delete (headnode T,datatype X,int I)
{k=0;
while ((k<n)&&(T[k].data!=X))k++; /*在头结点中查找元素*/
if (k<=n) /*查找到结点X*/
{j=0; p =T[k].headptr;
q=p; /*q为p的前趋*/
while ((p!=null)&&(j<I){j++;q=p p=p->next;} /*查第I个孩子*/
if ((p!null)&&(j==I)) /*找到第I个孩子*/
{t=p->child; q->next=p->next;free(p); /*删除第I个孩子结点*/
while(t<n){T[t]=T[t+1];t++;}
}
else printf(“X没有第I棵子树”)；
}
else printf(“T中不存在结点X”)；
}
9．（1）用孩子兄弟链表为存储结构，实现PARENT（T，X）运算。
本题算法的思路是：①当根结点非空进栈；②当栈非空p=pop(s)(退栈操作)，取元素p的左子树T；③当T非空且值为X，返回双亲P。否则，若T非空，让T进栈，T取它的右子树，转③执行；④转②执行。
本题用到栈S存放查找到的每一个结点，栈中元素结构说明如下：
typedef struct {bitreptr p;}s[max_size];
bitreptr PARENT(bitreptr T,datatype X)
{
if (t!=null)
{top =1; s[top].p=T; /*若头结点非空，进栈*/
while ((T!=null)||(top>0))
{p=s[top].p;topj--; T=p->rchild；/*退栈*/
while ((T->data!=X)&&(T->rchild!=null))
{top++;s[top].p=T; T=T->rchild;}
/*若此结点值不为X，查找其兄弟域*/
if ((T!=null)&&(T->data= =X))return(p) ;/*找到返回其双亲结点*/
}
}
return(null);
}
(2)用孩子兄弟链表为存储结构，实现CHILD（T，X，I）运算。
算法CHILD（T，X，I）的功能是查找结点X的第I个孩子。本算法在查找结点X时，同（1）基本思路相仿，只在找到结点X时，再查找它是否有第I个孩子。
Bitreptr CHILD(bitreptr T,datatype X,int I ) /*用的栈S同（1）*/
{if (T!=null)
{top =1; s[top].p =T; /*若头结点非空，进栈*/
while ((T!=null )||(top >0))
{whhile ((T!=null )&&(T->data==X))
{top ++; s[top].p=T; T=T->lchild } /*若此结点值不为X，查找其左子树*/
if ((T!=null)&&(T->data= =X))
{j=0; p=T->lchild ; /*找到结点X，查找第I个孩子*/
while ((p!=null)&&(j<I)){j++; p=p->rchild;}
if (j= =I) return(p); /*找到返回结点*p*/
else return(null); /*没有找到返回空指针*/
}
while ((top>0)&&(s[top].p->rchild= =null)) top--;
if (top>0){T=s[top].p->rchild ;top--;}
}
}return(null);
}
(3) 用孩子兄弟链表为存储结构，现实DELETE（T，X，I）的运算。
Void DELETE(bitreptr T,datatype X,int I)
{if (T!=null)
{top=1; s[top].p=T; /*若头结点非空，进栈*/
while((T!=null)||(top>0))
{while ((T!=null)&&(T->data!=X)){top++;s[top].p=T; T=T->lchild;}
if (t->data= =X) /*找到结点*/
{j=o; p=T->lchild; /*查找第I个孩子*/
while ((p!=null)&&(j<I)){j++; T=p;p=p->rchild;}
if ((p!=null)&&(j= =I)
{T->rchild =p->rchild ;free(p);} /*找到第I个孩子删除*/
else printf(,没有找到第I个孩子”)；
return;
}
while((top>0) &&(T->rchild!=null))top--;
if (top>0){T=s[top].rchild;top--;}
}
printf(“没有找到结点X返回”)；
}
}
（4）.用静态双亲链表为存储结构，实现PARENT（T，X）运算。
静态双亲链表的类型定义如下：
#define size
typedef struct
{ datatype data; /*数据域*/
int parent; /*双亲域（静态指针域）*/
}node;
typedef node T[size]; /*静态双亲链表*/
node PARENT(node T[],datatype X) /*n表示树的结点数*/
{k=0;
while (k<n)
if (T[k].data= =X) if (T[k.parent ]>=0) return (null);
else {printf(“X在根结点”); return(null);}
else k++;
printf (“找不到Z结点”!); return(null);
}
(5)用静态双亲链表为存储结构，实现CHILD（T，X，I）运算。
算法CHILD（T，X，I）的功能是查找结点X的第I个孩子。本算法在查找结点X时，同（4）基本思路相仿，只在找到结点X时，再查找它是否有第I个孩子。
Node CHILD（node T[]，datatypeX，int I）
{k=0;
while (k<n)
if (T[k].data= =X)
{j=0;h=k;
while (++k<n)
if (T[k].parent= =h) if ((j= =I) return(T[k]);
else j++;
printf (“找不到X结点的第I个孩子！”); return(null);
}else k++;
printf(“找不到X结点！”);return (null);
}
(6)用静态双亲链表为存储结构，现实DELETE（T，X，I）运算。
Int DELETE（bitreptr T，datatypeX，int I）
{k=0;
while (k<n)
if (T[k].data= =X)
{j=0;h=k;
while (++k<n)
if (T[k].parent= =h)
If ((j= =I)
{while (k<(n-1)){T[k]=T[k+1]; k++;}
free(T(n-1)); return(!);}
else j++;
printf (“找不到X结点的第I个孩子！”); return(0);
}else k++;
printf(“找不到X结点！”);return (0);
}
10.(1) 需要设置一个栈，用于存放查找到的每一个结点。本题的思路是：当前的根结点不空时，查找最左下的孩子，并将查找过的结点依次进栈，找到最左下孩子后，
输出该结点，然后转其右子树上，重复前面查找过程。
本题用到栈S存放查长到的每一个结点，栈中元素结构说明如下：
typedef struct{bitreptr p;}s[max_size];
void inorder1(bitreptr T)
{ initstack(s);
while ((T!=null )||(not enpty(s)))
{while(T!=null){push(s,T);T:=T->lchild;} /*向左下找下一个结点*/
if (not empty(s))
{T=pop(s); /*退出下一结点*/
printf(“%datatype”,T->data); /*访问*/
T =T->rchild; /*遍历右子树*/
}
}
}
(2) 本题需用到栈，因此解法同（1）。
Viod inorder2(ttnodeptr T) /*栈同（1）所设*/
{initstack(s);
while ((T!=null)||(not empty(s)))
{while (t!=null){push(s,T);T:=T->lchild;} /*向左下找下一个结点*/
if (not empty(s))
{T=pop(s); /*退出下一结点*/
printf(“%datatype”,T->data); /*访问*/
T=T->rchild; /*遍历右子树*/
}
}
}
11.(1)本题用到栈的结构说明如下：
typedef struct
{ bitreptr p; //tag的说明：tag=0表示访问过左子树；
int tag; tag=1表示访问过右子树。
}snode;
因为本题要求对二叉树的后根序非递归启遍历，解决此问题的算法思路是：
对任一非空结点，让此结点的标志tag=0,并进栈，到其左子树，转①执行。
若左子树为空且栈非空，让栈顶点元素的标志tag=1，然后到其右子树，
转①执行。
若栈非空且顶点的访问标志tag=1,访问此元素，退栈，转③执行；否则，栈非空，
转②执行。
Void postorderl(bitreptr T)
{top=0; /*栈S初值为空栈*/
while((T!=null)||(top!=0))
{while(T!=null)
{top++;s[top].p=T; /*结点及访问标志入栈*/
s[top].tag=0;T=T->lchild;} /*找下一个结点*/
while((top>0)&&(s[top].tag= =1)) /*输出右子树已遍历结点*/
{T=T[top].p;top--; /*取一个结点并退栈*/
printf(“%datatype”,T->data);} /*访问*/
if (top>0){s[top].tag=1;T=T->rchild;} /*置访问右子树并赋指针*/
}
}
⑵本题所用三叉结点结构如下：
mark
data
lchild
parent
rchild
其中：mark=0表示已访问过该结点的左子树；
mark=1表示已访问过该结点的右子树；
mark=2表示已访问过该结点
void postorder2 ( ttnoderptr T) /*T为三叉链表的二叉树 */
{ p=NULL; /*p为T的双亲结点 */
do{
while(T!=NULL) /*遍历左子树 */
{T->mark=0;p=T;T=T->lchild; /*置访问标志，取左子树 */
T=p; /*取其双亲结点 */
while((T!=NULL)&&(T->mark==1)) /*访问所有右子树已访问结点 */
{ printf(“datatype”,T->data); /*访问 */
T->mark=2;T=T->parent; /*置已访问标志并取其双亲结点*/
if(T==NULL) return; /*根结点被访问，结束 */
else if(T->mark==0) /*遍历其右子树 */
{T->mark=1;p=T;T=T->rchild;} /*置标志，取右子树 */
}while(1); /*继续循环 */
}
12．此问题所构造的一棵比较次数最小的判定树见图算法设计12．。
void tran(float score)
{if(score<=70)
if(score<=80) grade=’C’; /*70~79 */
else if(score<=90) grade=’B’; /*80~89 */
else grade=’A’; /*90~100 */
else if(score>=60) grade=’D’; /*60~69 */
else grade=’E’; /*0~59 */
}
图算法设计题12
13．void preorder(bitreptr T)
{if (t!=NULL)
{printf(“%f”,T->data);
preorder(T->rchild);
preorder(T->lchild);
}
}
14．本算法要借用队列来完成，其基本思想是，只要队列不为空，就出队列，然后判断该结点是否有左孩子和右孩子，如有就依次输出左、右孩子的值，然后让左、右孩子进队列。
void layorder (bitreptr T)
{initqueue (q) /*队列初始化*/
if(T!=NULL)
{printf(“%f”,T->data);
enqueue (q,T); /*入队列*/
while (not emptyqueue (q) ) /*若队列非空*/
{outqueue (q,p) ; /*出队*/
if (p->lchild!=NULL)
{printf(“%f”,p->lchild->data);
enqueue (q,p->lchild); /*入队列*/
}
if (p->rchild!=NULL)
{printf(“%”,p->rchild->data);
enqueue (q,p->rchild); /*入队列*/
}
}
}
}
15．本算法的基本思想是：先求左子树的叶子数，再求右子树的叶子数，两都相加就是根结点的叶子数，也就是对应二叉树的叶子数。
int leafcount (bitreptr T) /*求二叉树 T的叶子数*/
{ if(T==NULL)leaf=0; /*当二叉树为空时，叶子数等于0*/
else if(T->lchild==NULL)&&(T->rchild==NULL)leaf=1
/*当二叉树仅含一个根结点时，叶子数为1*/
else{L=leafcount(T->lchild); /*求左子树的叶子数*/ （1）
R=leafcount(T->lchild); /*求右子树的叶子数*/ （2）
leaf=L+R; /*左、右子树叶子数之和等于二叉树的叶子数*/ （3）
}
return(leaf);
}
二、填空题分支层次、根、直接前趋子孙、祖先空、只含根、非空左子树、非空右子树、非空左右子树
2i-1
2k-1
n2+1
最大值、完全
floor(log2n)+1
根、floor(i/2)、左孩子、右孩子、2i、右孩子、2i+1
顺序、链式根根、root
指向该结点的一个孩子、空指针NULL
2n、n-1、n+1
二叉链表、三叉链表虚结点
*count++,countleaf(l->rchile,count)
访问根结点、遍历左子树、遍历右子树
DLR、LDR、LRD、先根（或前序）遍历、中根（或中序）遍历、后根（或后序）遍历先根遍历、后根遍历、层次遍历非终端结点、终端结点
WPL（T）＝
i<k,x,T[j].wt,k+i,k+i,m+n,x,y
第一先根
floor(n/2),l,n,floor(n/2)+1
后面相同左子树、右子树、左子树、右子树树最短、较近
2m-1
（A），（E、G、I、J、K、L、N、O、P、Q、R），（3），（4），（5），（J、K）（C）
1、0
树、二叉树只有一个根结点的树、空二叉树
n-1
n-2m+1
5、答案见图 A B A C C
B A C C B A
C B A B
WPL＝165
62
37 25
19 18 13 12
10 9 7 6
5 4
41、m-1
42、本题有一定的难度，其求解方法如下：设总结点数为n度为0、1、2、3的结点数分别为n0,n1,n3,则有下面两个等式成立：
n=n0+n1+n2+n3 /*结点数*/
n-1=n1+2n2+3n3 /*分支数*/
两式相减得 n0=1+n2+2n3=1+3+2x4=12 (12)
三、单项选择
1、①2、③3、④4、④5、②6、④7、③8、④9、③10、①
11、④12、②13、④14、①15、②16、①17、②18、④19、①20、②
21、④22、③23、①24、②25、②26、③27、③28、①29、②30、④
31、④32、②33、②34、③35、①36、③37、③
四、简答及应用题二叉链表的类型定义如下：
typedef struct btnode *bitreptr;
struct btnode{ datatype data;
bitreptr lchild,rehild;
}
bitreptr root;
其中，data域称为数据域，用于存储二叉树结点中的数据元素；lchild 域称为左孩子指针域，用于存放指向本结点左孩子的指针（简称左指针）。rchild域称为右孩子指针域，用于存放指向本结点右孩子的指针（简称右指针）。
2．三叉链表与二叉链表的主要区别在于，它的结点比二叉链表的结点多一个指针域，该域用于存储一指向本结点双亲的指针。三叉链表的类型定义如下：
typedef struct ttnode *ttnodeptr;
struct ttnode
{datatype data;
ttnodeptr lchild,rchild,parent;
}
ttnodeptr root;
3．typedef struct tagnode /*表结点类型*/
{int child; /*孩子结点在表头数据组中的序号*/
struct tagnode *next; /*表结点指针域*/
}node,*link;
typedef struct /*头结点类型*/
{datatype data; /*结点数据元素*/
link headptr; /*头结点指针域*/
}headnode;
typedef headnode childlink[axnode]; /*表头结点数组*/
带双亲的孩子链表表示法，其类型定义与孩子链表类似，只需将头结点的定义改为：
typedef struct
{datatype data;
int parent;
link headptr;
}headnodel;
4．就图简答题4.1（a）中的二叉树
⑴根结点是A； ⑵叶结点是：D，F，J；
⑶G的双亲是：E； ⑷G的祖先是：A；
⑸G的孩子是：H； ⑹E的子孙是：F，G，H，I，J；
⑺E的兄弟是：B；C的兄弟是：C无兄弟；⑻结点B和I的层数分别是2，5；
⑼树的深度是：6； ⑽以结点G为根的子树的深度是：4；
⑾树的度数是：2。
就图简答题4.1(b)中的树
⑴根结点是A； ⑵叶结点是：D，F，G，H，I，J；
⑶G的双亲是：C； ⑷G的祖先是：A；
⑸G的孩子是：G无孩子； ⑹E的子孙是：H，I，J；
⑺E的兄弟是：D；C的兄弟是：B； ⑻结点B和I的层数分别是2，4；
⑼树的深度是：4； ⑽以结点G为根的子树的深度是：1；
⑾树的度数是：3。
5．(a)因为该图所示结构，有两个结点没有直接前趋，即有两个根结点，而树只能有一个根结点。
(b)因为找不到树的根结点，所以不满足树的定义。
(c)因为最上面一个结点的后继结点分不出两个不相交的子集，不满足树的定义。
6．答案见图简答题6所示。
7．答案见图简答题7-2所示。
8．先根序列：A B C D E F G H I J;
中根序列：B C D A F E H J I G;
后根序列：D C B F J I H G E A。
9．⑴二叉树中任意一个结点都无左孩子；
⑵二叉树中任意一个结点都无右孩子；
⑶至多只有一个结点的二叉树。
10．由后根遍历序列得到二叉树的根结点A（后根序列中最后一个结点）；在中序序列中，A的左力是A的左子树上的结点，A的右边是A的右子树上的结点；再到后根序列中找左子树和右子树的根结点，依次类推，直到画出该二叉树，如图简答题10所示。
11．答案见图简答题11-2所示。
12．先根序列：A B E F K L C G D H I J；
后根序列：E K L F B G C H I J D A；
层次序列：A B C D E F G H I J K L。
13．答案见图简答题13-2所示。
14．答案见图简答题14-2所示。
(a)(b)(c)(d)(e)
15.答案见图简答题15-1所示。
16．利用先根遍历方法查找结点*A的直接后继：
当A->lchild<>NULL时，A的先根后继结点是A->lchild；否则，当A->rchild<>NULL时，A的先根后继结点是A->rchild。
16．利用先根遍历方法查找结点*A的直接后继：
当A->lchild<>NULL时，A的先根后继结点是A->lchild；否则，当A->rchild<>NULL时，A的先根后继结点是A->rchild。
利用中根遍历方法查找结点*A的直接后继：
当A->lchild<>NULL时，*A的中根前趋是其左子树的“最右下结点”； 当A->rchild<>NULL时，*A的中根后继是其右子树的“最左下结点”。
利用后根遍历方法查找结点*A的直接前趋：
当A->rchild<>NULL时，A的后根前趋结点是A->rchild；否则，A->rchild<>NULL时，A的后根前趋结点是A->lchild；
17．本题的解题过程如下：
①由前根序列各A是二叉树的根结点；由中根序列知GDHBE是A的左子树中的结点，CIJF是A的右子树中的结点。
②由前根序列知B是A的左子树的根结点；由中根序列知GDH是B的左子树中的结点，E是B的右子树中的结点。
③由前根序列知D是B的左子树的根结点；由中根序列知G是B的左子树中的结点，H是B的右子树中的结点
④由前根序列知C是A的右子树的根结点；由中根序列知IJF是C的右子树中的结点（C的左子树为空）。
⑤由前根序列知F是C的右子树的根结点；由中根序列知IJ是F的左子树中的结点，（F的右子树为空）。
⑥由前根序列知I是F的左子树的根结点；由中根序列知J是F的右子树中的结点，（F的左子树为空）。
完整的二叉树如图简答题17所示。
18．第一步，先以给定的权值构造出哈夫曼树，如图简答题18所示。
第二步，假没规定哈夫曼树上所有的左指针用0表示，所有的右指针用1表示。
第三步，从根开始沿每一条通向叶子的路径上的数字，这些数字就是对应叶子结点所代表的字母的哈夫曼编码。8个字母所应的哈夫曼编码为：
7---0010 19---10
2---00000 6---0001
32---01 3---00001
21---11 10---0011
图简答题18
19．任意一棵二叉树只有先转换成完全二叉树后，才能用顺序存储结构进行存储。转换后的二叉树如图19-2所示。任意二叉树的顺序存储结构示意图如图19-3所示。
图简答题19-2
A
B
C
D
E
F
G
……
图简答题19-3
20．转换后的二叉树如图简答题20-2所示。
图简答题20-2
五、算法设计
1．⑴bitreptr PARENT(bitreptr BT,bitreptr p,datatype data) /*调用前p为空指针*/
{if(BT!=NULL)if(BT->data==X) return(p); /*找到,返回其父结点*/
else{p=BT;
PARENT(BT->lchild,p,X); /*查找其左子树*/
PARENT(BT->rchild,p,X); /*查找其右子树*/
}
}
⑵void CREATE(datatype X,bitreptr LBT,bitreptr RBT)
{ BT=malloc(size); /*申请根结点*/
BT->data=x;BT->lchild=LBT; BT->rchild=RBT;
}
(3)void DELLEFT(bitreptr BT,datatype X)
{if (BT!=null ) if (BT->data = X) {BT->lchild=null,BT->rchild=null;}
else{DELLEFT(BT->lchild,X); DELLEFT(BT->rchild,X);}
}
2.(1) ttnodeptr PARENT(ttndoeptr BT,datatype data)
{ if (BT!=null) if (BT->data = X) return (BT->patrnt); /*找到，返回其父结点*/
else {PARENT (BT->lchild,X);PARENT(BT->rchild,X);}
}
(2) void CREATE(datatype X,ttnodeptr LBT,ttnodeper RBT)
{BT=malloc(size); /*申请根结点*/
BT->data=x; BT->lchild=LBT; BT->rchild=RBT;
LBT->parent = BT; R BT->parent = BT;
}
(3)void DELLEFT(ttnodeptr BT,datatype X)
{if (BT!=null) if (BT->data ==X){ BT->lchild =null; BT->rchild=null;}
else {DELLEFT(BT->lchild,X); DELLEFT(BT->rchild,X);}
}
3.采用递归方法，对每一个结点先求其左右子树的深度，取较大值加1作为此结点的深度。
Int depth (bitreptr BT)
{if (BT= =null)return（0);
else {l=hepth (BT->lchild);
r=hepth(BT->rchild);
return((l>r?l:r)+1);
}
4.按照题目要求，附加一个工作栈以完成对该树的非递归遍历，思路如下：
每访问一个结点，将此结点压入栈，查看此结点是否有左子树，若有，访问左子树，转（1）执行。
从栈弹出一结点，如果此结点有右子树，访问右子树并转第（1）步执行，否则转第（2）步执行。
Void preorder(datatype a[n],int n )
{ INISTACK(sd); /*初始工作栈sd*/
I=1; PUSH(sd,0);
If (i<=n)
{visite(a[I]); /*访问此结点*/
PUSH(sd,I);
J=2*I; /* 取左子树*/
While(!EMPTY(sd)) /*若栈sd 非空*/
{while(j<=n) /*若2I<=n,则该结点有左子树*/
{PUSH(sd,j); /*进栈*/
I=j; j=2*I; /*取左子树*/
Visite(a[I]); /*访问此结点*/
}
I=pop(sd); /*出栈*/
J=2*I+1; /*取右子树*/
}
}
}
5.本题用递归方法，采用以下步骤：
若t1和t2都是空树则等价；
若t1和t2有一个为空树另一个非空树，则不等价。
若t1和t2两个都是非空树且它们的值相等，比较它们的左、右子树。
Int same_tree (bitreptr t1,t2)
{if ((t1= =null)&&(t2= =null)) return(1); /*t1,t2都是空树*/
Else if ((t1= =null)||(t2= =null)) return(0); /*t1,t2只有一个空树*/
Else if (t1->data = =t2->data) /*t1和t2的值相等*/
Return (same_tree (t1->lchild,t2->lchild)&&
Same_tree(t1->rchild,t2->rchild));
}
6.采用后根遍历递归访问的方法，交换每一个结点的左右子树。
Void exchg_tree(bitreptr BT)
{if (BT!=null) /*非空*/
{exchg_tree(BT->lchild); /*交换左子树所有结点指针*/
exchg_tree(BT->rchild); /*交换右子树所有结点指针*/
p=BT->lchild; /*交换根结点左右指针*/
BT->lchild=BT->rchild; ->rchild =p;
}
}
7.设置一个栈用于装入查找结点的所有祖先。
栈的元素结构说明如下：
typedef struct
{bitreptr p;
int tag;
}snode;
int search(bitreptr T,datatype X)
{top =0; /*栈s初置为0*/
while ((T!=null)&&(T->data!=X)||(top!=0))
{while (((T!=null)&&(T->data!=X))
{top ++;
s[top ].p=T; s[top].tag=0; /*结点入栈，置标志0*/
T=T->lchild; /*找左子树*/
}
if (((T!=null)&&(T->data==X)) /*找到*/
{for (I=1;I<=top;I++)
printf (“%d\n”,s[I].p->data); /*输出*/
return(1);
}
else while ((top>0)&&(s[top].tag==1)) top --; /*退出右子树已访问过的结点*/
if (top>0){s[top].tag=1;T=s[top]; T=T->rchild;/*置访问标志为1，访问右子树*/
}
}
return(0);
}
8,（1） PARENT(T,X)的功能是查找值为X的结点的双亲。查找的方法是，在表头数组中依次顺序查看每个头结点的链域，查找是否含水量有值为X的结点，如有，则返回其结点的值。
Headnode parent (headnode T,datatype X ) /*n表示树的结点数*／
{k=0;
if (T[k].data= =X) return(null); ／*根结点值是Ｘ返回空值*／
while (k<n)
{p=T[k].headptr; /*取子树指针*/
while (p!=null)
{j=p->child; /*取孩子序号*/
if (T[j].data= =X) return(T[k]); /*查找到X，返回父结点*/
p=p->next; /*取下一个孩子*/
}
k++;
}
return(null); /*没有找到，返回空值*/
}
（2）HILD（T，X，I）的功能是在树T中查找值为X的结点的第I个孩子。算法思路是：先在表头结点中查找值为X的结点，然后再由此结点的链表找第I个孩子，如找到则返回这个孩子的指针值。
Headnode child(headnode T,datatype X,int I)
{k=0;
while ((k<n)&&(T[k].data!=X)) k++; /*在头结点中查找元素*/
if (t[k].data= =X) /*查找到元素X*/
{j=0; p=T[k].headptr ; /*取X结点第一个孩子*/
while ((p!=null )&&(j<I)){j++; p=p->next;};/*查找第I个孩子*/
if ((p!=null)&&(j= =I)) return(p); /*找到第I个孩子*/
else return(null); /*没找到，返回定指针*/
}
else return(null); /*没有找到结点X*/
}
(3) DELETE(T,X,I)的功能是删除值为X的结点的第I个孩子。算法思路是：先在表头数组中查找值为X的结点。找到后再沿此结点的链表查找第I个孩子，如存在将其删除。
Void delete (headnode T,datatype X,int I)
{k=0;
while ((k<n)&&(T[k].data!=X))k++; /*在头结点中查找元素*/
if (k<=n) /*查找到结点X*/
{j=0; p =T[k].headptr;
q=p; /*q为p的前趋*/
while ((p!=null)&&(j<I){j++;q=p p=p->next;} /*查第I个孩子*/
if ((p!null)&&(j==I)) /*找到第I个孩子*/
{t=p->child; q->next=p->next;free(p); /*删除第I个孩子结点*/
while(t<n){T[t]=T[t+1];t++;}
}
else printf(“X没有第I棵子树”)；
}
else printf(“T中不存在结点X”)；
}
9．（1）用孩子兄弟链表为存储结构，实现PARENT（T，X）运算。
本题算法的思路是：①当根结点非空进栈；②当栈非空p=pop(s)(退栈操作)，取元素p的左子树T；③当T非空且值为X，返回双亲P。否则，若T非空，让T进栈，T取它的右子树，转③执行；④转②执行。
本题用到栈S存放查找到的每一个结点，栈中元素结构说明如下：
typedef struct {bitreptr p;}s[max_size];
bitreptr PARENT(bitreptr T,datatype X)
{
if (t!=null)
{top =1; s[top].p=T; /*若头结点非空，进栈*/
while ((T!=null)||(top>0))
{p=s[top].p;topj--; T=p->rchild；/*退栈*/
while ((T->data!=X)&&(T->rchild!=null))
{top++;s[top].p=T; T=T->rchild;}
/*若此结点值不为X，查找其兄弟域*/
if ((T!=null)&&(T->data= =X))return(p) ;/*找到返回其双亲结点*/
}
}
return(null);
}
(2)用孩子兄弟链表为存储结构，实现CHILD（T，X，I）运算。
算法CHILD（T，X，I）的功能是查找结点X的第I个孩子。本算法在查找结点X时，同（1）基本思路相仿，只在找到结点X时，再查找它是否有第I个孩子。
Bitreptr CHILD(bitreptr T,datatype X,int I ) /*用的栈S同（1）*/
{if (T!=null)
{top =1; s[top].p =T; /*若头结点非空，进栈*/
while ((T!=null )||(top >0))
{whhile ((T!=null )&&(T->data==X))
{top ++; s[top].p=T; T=T->lchild } /*若此结点值不为X，查找其左子树*/
if ((T!=null)&&(T->data= =X))
{j=0; p=T->lchild ; /*找到结点X，查找第I个孩子*/
while ((p!=null)&&(j<I)){j++; p=p->rchild;}
if (j= =I) return(p); /*找到返回结点*p*/
else return(null); /*没有找到返回空指针*/
}
while ((top>0)&&(s[top].p->rchild= =null)) top--;
if (top>0){T=s[top].p->rchild ;top--;}
}
}return(null);
}
(3) 用孩子兄弟链表为存储结构，现实DELETE（T，X，I）的运算。
Void DELETE(bitreptr T,datatype X,int I)
{if (T!=null)
{top=1; s[top].p=T; /*若头结点非空，进栈*/
while((T!=null)||(top>0))
{while ((T!=null)&&(T->data!=X)){top++;s[top].p=T; T=T->lchild;}
if (t->data= =X) /*找到结点*/
{j=o; p=T->lchild; /*查找第I个孩子*/
while ((p!=null)&&(j<I)){j++; T=p;p=p->rchild;}
if ((p!=null)&&(j= =I)
{T->rchild =p->rchild ;free(p);} /*找到第I个孩子删除*/
else printf(,没有找到第I个孩子”)；
return;
}
while((top>0) &&(T->rchild!=null))top--;
if (top>0){T=s[top].rchild;top--;}
}
printf(“没有找到结点X返回”)；
}
}
（4）.用静态双亲链表为存储结构，实现PARENT（T，X）运算。
静态双亲链表的类型定义如下：
#define size
typedef struct
{ datatype data; /*数据域*/
int parent; /*双亲域（静态指针域）*/
}node;
typedef node T[size]; /*静态双亲链表*/
node PARENT(node T[],datatype X) /*n表示树的结点数*/
{k=0;
while (k<n)
if (T[k].data= =X) if (T[k.parent ]>=0) return (null);
else {printf(“X在根结点”); return(null);}
else k++;
printf (“找不到Z结点”!); return(null);
}
(5)用静态双亲链表为存储结构，实现CHILD（T，X，I）运算。
算法CHILD（T，X，I）的功能是查找结点X的第I个孩子。本算法在查找结点X时，同（4）基本思路相仿，只在找到结点X时，再查找它是否有第I个孩子。
Node CHILD（node T[]，datatypeX，int I）
{k=0;
while (k<n)
if (T[k].data= =X)
{j=0;h=k;
while (++k<n)
if (T[k].parent= =h) if ((j= =I) return(T[k]);
else j++;
printf (“找不到X结点的第I个孩子！”); return(null);
}else k++;
printf(“找不到X结点！”);return (null);
}
(6)用静态双亲链表为存储结构，现实DELETE（T，X，I）运算。
Int DELETE（bitreptr T，datatypeX，int I）
{k=0;
while (k<n)
if (T[k].data= =X)
{j=0;h=k;
while (++k<n)
if (T[k].parent= =h)
If ((j= =I)
{while (k<(n-1)){T[k]=T[k+1]; k++;}
free(T(n-1)); return(!);}
else j++;
printf (“找不到X结点的第I个孩子！”); return(0);
}else k++;
printf(“找不到X结点！”);return (0);
}
10.(1) 需要设置一个栈，用于存放查找到的每一个结点。本题的思路是：当前的根结点不空时，查找最左下的孩子，并将查找过的结点依次进栈，找到最左下孩子后，
输出该结点，然后转其右子树上，重复前面查找过程。
本题用到栈S存放查长到的每一个结点，栈中元素结构说明如下：
typedef struct{bitreptr p;}s[max_size];
void inorder1(bitreptr T)
{ initstack(s);
while ((T!=null )||(not enpty(s)))
{while(T!=null){push(s,T);T:=T->lchild;} /*向左下找下一个结点*/
if (not empty(s))
{T=pop(s); /*退出下一结点*/
printf(“%datatype”,T->data); /*访问*/
T =T->rchild; /*遍历右子树*/
}
}
}
(2) 本题需用到栈，因此解法同（1）。
Viod inorder2(ttnodeptr T) /*栈同（1）所设*/
{initstack(s);
while ((T!=null)||(not empty(s)))
{while (t!=null){push(s,T);T:=T->lchild;} /*向左下找下一个结点*/
if (not empty(s))
{T=pop(s); /*退出下一结点*/
printf(“%datatype”,T->data); /*访问*/
T=T->rchild; /*遍历右子树*/
}
}
}
11.(1)本题用到栈的结构说明如下：
typedef struct
{ bitreptr p; //tag的说明：tag=0表示访问过左子树；
int tag; tag=1表示访问过右子树。
}snode;
因为本题要求对二叉树的后根序非递归启遍历，解决此问题的算法思路是：
对任一非空结点，让此结点的标志tag=0,并进栈，到其左子树，转①执行。
若左子树为空且栈非空，让栈顶点元素的标志tag=1，然后到其右子树，
转①执行。
若栈非空且顶点的访问标志tag=1,访问此元素，退栈，转③执行；否则，栈非空，
转②执行。
Void postorderl(bitreptr T)
{top=0; /*栈S初值为空栈*/
while((T!=null)||(top!=0))
{while(T!=null)
{top++;s[top].p=T; /*结点及访问标志入栈*/
s[top].tag=0;T=T->lchild;} /*找下一个结点*/
while((top>0)&&(s[top].tag= =1)) /*输出右子树已遍历结点*/
{T=T[top].p;top--; /*取一个结点并退栈*/
printf(“%datatype”,T->data);} /*访问*/
if (top>0){s[top].tag=1;T=T->rchild;} /*置访问右子树并赋指针*/
}
}
⑵本题所用三叉结点结构如下：
mark
data
lchild
parent
rchild
其中：mark=0表示已访问过该结点的左子树；
mark=1表示已访问过该结点的右子树；
mark=2表示已访问过该结点
void postorder2 ( ttnoderptr T) /*T为三叉链表的二叉树 */
{ p=NULL; /*p为T的双亲结点 */
do{
while(T!=NULL) /*遍历左子树 */
{T->mark=0;p=T;T=T->lchild; /*置访问标志，取左子树 */
T=p; /*取其双亲结点 */
while((T!=NULL)&&(T->mark==1)) /*访问所有右子树已访问结点 */
{ printf(“datatype”,T->data); /*访问 */
T->mark=2;T=T->parent; /*置已访问标志并取其双亲结点*/
if(T==NULL) return; /*根结点被访问，结束 */
else if(T->mark==0) /*遍历其右子树 */
{T->mark=1;p=T;T=T->rchild;} /*置标志，取右子树 */
}while(1); /*继续循环 */
}
12．此问题所构造的一棵比较次数最小的判定树见图算法设计12．。
void tran(float score)
{if(score<=70)
if(score<=80) grade=’C’; /*70~79 */
else if(score<=90) grade=’B’; /*80~89 */
else grade=’A’; /*90~100 */
else if(score>=60) grade=’D’; /*60~69 */
else grade=’E’; /*0~59 */
}
图算法设计题12
13．void preorder(bitreptr T)
{if (t!=NULL)
{printf(“%f”,T->data);
preorder(T->rchild);
preorder(T->lchild);
}
}
14．本算法要借用队列来完成，其基本思想是，只要队列不为空，就出队列，然后判断该结点是否有左孩子和右孩子，如有就依次输出左、右孩子的值，然后让左、右孩子进队列。
void layorder (bitreptr T)
{initqueue (q) /*队列初始化*/
if(T!=NULL)
{printf(“%f”,T->data);
enqueue (q,T); /*入队列*/
while (not emptyqueue (q) ) /*若队列非空*/
{outqueue (q,p) ; /*出队*/
if (p->lchild!=NULL)
{printf(“%f”,p->lchild->data);
enqueue (q,p->lchild); /*入队列*/
}
if (p->rchild!=NULL)
{printf(“%”,p->rchild->data);
enqueue (q,p->rchild); /*入队列*/
}
}
}
}
15．本算法的基本思想是：先求左子树的叶子数，再求右子树的叶子数，两都相加就是根结点的叶子数，也就是对应二叉树的叶子数。
int leafcount (bitreptr T) /*求二叉树 T的叶子数*/
{ if(T==NULL)leaf=0; /*当二叉树为空时，叶子数等于0*/
else if(T->lchild==NULL)&&(T->rchild==NULL)leaf=1
/*当二叉树仅含一个根结点时，叶子数为1*/
else{L=leafcount(T->lchild); /*求左子树的叶子数*/ （1）
R=leafcount(T->lchild); /*求右子树的叶子数*/ （2）
leaf=L+R; /*左、右子树叶子数之和等于二叉树的叶子数*/ （3）
}
return(leaf);
}
