请写出二叉树层次遍历的算法，即从根结点开始按层次由上至下，从左到右访问二叉树中的每个结点。（15分） 注：二叉树结点定义如下： typedef char elemtype; typedef struct btnode { elemtype data; struct btnode *lchild ,*rchild; } bitnode, *bitree;
请写出二叉树层次遍历的算法，即从根结点开始按层次由上至下，从左到右访问二叉树中的每个结点。（15分） 注：二叉树结点定义如下： typedef char elemtype; typedef struct btnode { elemtype data; struct btnode *lchild ,*rchild; } bitnode, *bitree;
参考答案和解析
上;下;左;右
相关考题：
设计递归算法,判断二叉树t是否满足小根堆的特点。二叉链表的类型定义如下: typedef int datatype;//结点的数据类型，假设为inttypedef struct NODE *pointer;//结点指针类型struct NODE {datatype data;pointer lchild,rchild;};typedef pointer bitree;//根指针类型
●试题三阅读下列函数说明和C函数，将应填入(n)处的字句写在答题纸的对应栏内。【函数3说明】函数DeleteNode(Bitree*r,int e)的功能是：在树根结点指针为r的二叉查找(排序)树上删除键值为e的结点，若删除成功，则函数返回0，否则函数返回-1。二叉查找树结点的类型定义为：typedef struct Tnode{int data;/*结点的键值*/struct Tnode*Lchild,*Rchild;/*指向左、右子树的指针*/}*Bitree;在二叉查找树上删除一个结点时，要考虑三种情况：①若待删除的结点p是叶子结点，则直接删除该结点;②若待删除的结点p只有一个子结点，则将这个子结点与待删除结点的父结点直接连接，然后删除结点p;③若待删除的结点p有两个子结点，则在其左子树上，用中序遍历寻找关键值最大的结点s ,用结点s的值代替结点p的值，然后删除结点s，结点s必属于上述①、②情况之一。【函数3】int DeleteNode(Bitree*r,int e){Bitree p=*r,pp,s,c;while( (1) ){/*从树根结点出发查找键值为e的结点*/pp=p;if(e＜p-＞data)p=p-＞Lchild;else p=p-＞Rchild;}if(!p)return-1;/*查找失败*/if(p-＞Lchild p-＞Rchild) { /*处理情况③*/s= (2) ;pp=p;while( (3) ){pp=s;s=s-＞Rchild;}p-＞data=s-＞data;p=s;}/*处理情况①、②*/if( (4) )c=p-＞Lchild;else c=p-＞Rchild;if(p==*r)*r=c;else if( (5) )pp-＞Lchild=c;else pp-＞Rchild=c;free(p);return 0;}
下面是对二叉树的叙述，其中错误的是 （ ）A．二叉树的遍历是指不重复地访问二叉树中的所有结点B．二叉树的遍历允许重复地访问二叉树中的个别结点C．在遍历二叉树的过程中，一般先遍历左子树，然后再遍历右子树D．在先左后右的原则下，根据访问根结点的次序，二叉树的遍历可以分为三种：前序遍历、中序遍历、后序遍历
阅读下列C函数和函数说明，将应填入(n)处的字句写在对应栏内。【说明】函数DeleteNode (Bitree *r, int e)的功能是：在树根结点指针为r的二叉查找(排序)树上删除键值为e的结点，若删除成功，则函数返回0，否则函数返回-1。二叉查找树结点的类型定义为：typedef struct Tnode{int data； /*结点的键值*/struct Tnode *Lchild, *Rchild； /*指向左、右子树的指针*/}*Bitree：在二叉查找树上删除一个结点时，要考虑3种情况：①若待删除的结点p是叶子结点，则直接删除该结点；②若待删除的结点p只有一个子结点，则将这个子结点与待删除结点的父结点直接连接，然后删除结点p；③若待删除的结点p有两个子结点，则在其左子树上，用中序遍历寻找关键值最大的结点s，用结点s的值代替结点p的值，然后删除结点s，结点s必属于上述①、②情况之一。【函数】int DeleteNode (Bitree *r，int e) {Bitree p=*r,pp，s，c；while ( (1) ){ /*从树根结点出发查找键值为e的结点*/pp=p;if(e＜p-＞data) p=p-＞Lchild；else p=p-＞Rchild；}if(!P) return-1； /*查找失败*/if(p-＞Lchild p-＞Rchild) {/*处理情况③*/s=(2)；pp=pwhile (3) {pp=s；s=s-＞Rchild;}p-＞data=s-＞data； p=s；}/*处理情况①、②*/if ( (4) ) c=p-＞Lchild；else c=p-＞Rchild；if(p==*r) *r=c；else if ( (5) ) pp-＞Lchild=c；else pp-＞Rchild=c；free (p)；return 0；}
试题四阅读下列函数说明和C函数，将应填入 （n） 处的字句写在答题纸的对应栏内。[函数说明]函数DeleteNode(Bitree *r,int e)的功能是：在树根结点指针为r的二叉查找（排序）树上删除键值为e的结点，若删除成功，则函数返回0，否则函数返回-1。二叉查找树结点的类型定义为：typedef struct Tnode{int data;struct Tnode *Lchild,*Rchild;}*Bitree;在二叉查找树上删除一个结点时，要考虑三种情况：1若待删除的结点p是叶子结点，则直接删除该结点；2若待删除的结点p只有一个子结点，则将这个子结点与待删除结点的父结点直接连接，然后删除结点p；3若待删除的结点p有两个子结点，则在其左子树上，用中序遍历寻找关键值最大的结点s,用结点s的值代替结点p的值，然后删除结点s,结点s必属于上述1、2情况之一。[函数代码]int DeleteNode(Bitree *r,int e) {Bitreep = *r, pp, s, c;while( (1) ) { /*从树根结点出发查找键值为e的结点*/pp = p;if ( e p-data) p = p - Lchild;else p = p-Rchild;}if(!p) return –1; /* 查找失败 */if(p-Lchild p-Rchild) { /* 处理情况3 */s = (2);pp = p;while ( (3) ) { pp = s; s = s- Rchild; }p-data = s -data; p = s;}/*处理情况1、2*/if( (4) ) c = p - Lchild;elsec = p - Rchild;if(p == *r) *r = c;elseif ( (5) ) pp - Lchild = c;elsepp-Rchild = c;free(p);return 0;}
阅读下列函数说明和C函数，将应填入(n)处。【函数3说明】函数DeleteNode(Bitree * r，int e)的功能是：在树根结点指针为r的二叉查找(排序)树上删除键值为e的结点，若删除成功，则函数返回0，否则函数返回-1。二叉查找树结点的类型定义为：typedef struct Tnode{int data； /*结点的键值*/struct Tnode * Lchild，*Rchild； /*指向左、右子树的指针*/} * Bitree；在二叉查找树上删除一个结点时，要考虑三种情况：①若待删除的结点p是叶子结点，则直接删除该结点；②若待删除的结点p只有一个子结点，则将这个子结点与待删除结点的父结点直接连接，然后删除结点P；③若待删除的结点p有两个子结点，则在其左子树上，用中序遍历寻找关键值最大的结点s，用结点s的值代替结点p的值，然后删除结点s，结点s必属于上述①、②情况之一。【函数3】int DeleteNode(Bitree * r，int e){Bitree p=*r，pp，s，c；while((1)){ /*从树根结点出发查找键值为e的结点*/pp=p；if(e＜p-＞data)p=p-＞Lchild；else p=p-＞Rchild；{if(!p)return-1； /*查找失败*/if(p-＞Lchild p-＞Rchild){/*处理情况③*/s=(2)； pp=p；while((3)){pp=s；s=s-＞Rchild；}p-＞data=s-＞data；p=s；}/*处理情况①、②*/if((4))c=p-＞Lchild；else c=p-＞Rchild；if(p==*r)*r=c；else if((5))pp-＞Lchild＝c；else pp-＞Rchild＝c；free(p)；return 0；}
阅读下列说明和c函数代码，将应填入 (n) 处的字句写在答题纸的对应栏内。【说明】对二叉树进行遍历是二叉树的一个基本运算。遍历是指按某种策略访问二叉树的每个结点，且每个结点仅访问一次的过程。函数InOrder。()借助栈实现二叉树的非递归中序遍历运算。设二叉树采用二叉链表存储，结点类型定义如下：typedef struct BtNode{ElemTypedata； ／*结点的数据域，ElemType的具体定义省略*／struct BtNode*ichiid，*rchild； ／*结点的左、右弦子指针域*／)BtNode，*BTree；在函数InOrder()中，用栈暂存二叉树中各个结点的指针，并将栈表示为不含头结点的单向链表(简称链栈)，其结点类型定义如下：typedef struct StNode{ ／*链栈的结点类型*／BTree elem； ／*栈中的元素是指向二叉链表结点的指针*／struct StNode*link；}S％Node；假设从栈顶到栈底的元素为en、en-1、…、e1，则不含头结点的链栈示意图如图5—5所示。【C函数】int InOrder(BTree root) ／*实现二叉树的非递归中序遍历*／{BTree ptr； ／*ptr用于指向二又树中的结点*／StNode*q； ／*q暂存链栈中新创建或待删除的结点指针+／StNode*stacktop=NULL； ／*初始化空栈的栈顶指针stacktop*／ptr=root； ／*ptr指向二叉树的根结点*／while( (1 ) I I stacktop!=NULL){while(ptr!=NULL){q=(StNode*)malloc(sizeof(StNode))；if(q==NULL)return-1；q-elem=ptr；(2) ；stacktop=q； ／*stacktop指向新的栈顶*／ptr=(3 ) ； ／*进入左子树*／}q=stacktop； (4) ； ／*栈顶元素出栈*／visit(q)； ／*visit是访问结点的函数，其具体定义省略*／ptr= (5) ； ／*进入右子树*／free(q)； ／*释放原栈顶元素的结点空间*／}return 0；}／*InOrder*／
阅读以下说明和C语言函数，将应填入(n)处的字句写在对应栏内。[说明]完成以下中序线索化二叉树的算法。[函数]Typedef int datatype;Typedef struct node {Int ltag, rtag;Datatype data;*lchild,* rchild;}bithptr;bithptr pre;void inthread ( p );{if{inthread ( p-＞lchild );if ( p-＞lchild==unll ) (1);if ( P-＞RCHILD=NULL) p-＞rtag=1;if (2){if (3) pre-＞rchild=p;if ( p-＞1tag==1 )(4);}INTHREAD ( P-＞RCHILD );(5);}}
阅读以下函数说明和C语言函数，将应填入(n)处的字句写在对应栏内。[说明]已知一棵二叉树用二叉链表存储，t指向根结点，p指向树中任一结点。下列算法为输出从t到P之间路径上的结点。[C程序]define Maxsize 1000typedef struct node{TelemType data;struct node*1child,*rchild;}BiNode,*BiTree;void Path(BiTree t,BiNode*P){ BiTree*stack[Maxsize],*stackl[Maxsize],*q;int tag[Maxsize],top=0,topl;q=t;/*通过先序遍历发现P*/do(while(q!=NULL q!=p)/*扫描左孩子，且相应的结点不为P*/{ (1);stack[top]=q;tag[top]=0;(2);}if(top＞0){ if(stack[top]==P) break; /*找到P，栈底到栈顶为t到P*/if(tag[top]==1)top--;else{q=stack[top];q=q-＞rchild;tag[top]=1;}}} (3);top--; topl=0;while(top＞0){q=stack[top]; /*反向打印准备*/topl++;(4);top--;}while((5)){ /*打印栈的内容*/q=stackl[topl];printf(q-＞data);topl--;}}
阅读下列说明和C程序，将应填入(n)处的字句写在对应栏中。[说明]借助一个栈结构，可实现二叉树的非递归遍历算法。InOrderTraverse数实现中序非递归遍历，遍历过程如下：若不是空树，根节点入栈，进入左子树；若已经是空树，则栈顶元素出栈，访问该元素(根节点)，进入该节点的右子树，继续直到遍历完成。函数中使用的预定义符号如下：typedef struct BiTNode{int data；struct BiTNode *iChiid，*rChiid；} BiTNode，*BiTree；typedef struct SNode{/*链栈的节点类型*/BiTree elem；struct SNode *next；}SNode；[函数]int InOrderTraverse(BiTree root){BiTree P；SNode *q，*stop=NULL；/*不带头节点的单链表作为栈的存储结构*/P=root；while(p !=NULL || stop !=NULL){if( (1) ){ /*不是空树*/q=(SNode*)malloc(sizeof q)；if(q==NULL)return-1；/*根节点指针入栈*/(2)；q-＞elem=P；stop=q；P=(3)； /*进入根的左子树*/}else{q=stop；(4)； /*栈顶元素出栈*/printf("%d|，q-＞elem-＞data)； /*防问根节点*/P=(5)； /*进入根的右子树*/free(q)； /*释放原栈顶元素*/}/*if*/}/*while*/return 0；}/*InOrderTraverse*/(1)
阅读以下说明和C语言函数，将应填入(n)处的语句写在对应栏内。【说明】本程序利用非递归算法实现二叉树后序遍历。【函数】include＜stdio.h＞include＜stdlib.h＞typedef struct node{/*二叉树的结点数据结构类型*/char data;struct node *left;struct node *right;}BTREE;void SortTreelnsert(BTREE **tree, BTREE *s){if(*tree==NULL)*tree=s;elseif(s-＞data＜(*tree)-＞data)SortTreelnsert((1),s);else if(s-＞data＞=(*tree)-＞data)SortTreelnsert((2),s);}void TraversalTree(BTREE *tree){BTREE *stack[1 000],*p;int tag[1000],top=0;p=tree;do{while(p !=NULL){stack[++top]=p;(3);tag[top]=0; /*标记栈顶结点的左子树已进行过后序遍历*/}while(top＞0(4))/*栈顶结点的右子树是否被后序遍历过*/{p=stack[top--];putchar(p-＞data);}if(top＞0)/*对栈顶结点的右子树进行后序遍历*/{(5);tag[top]=1;}}while(top＞0);}void PrintSortTree(BTREE *tree){if(tree !=NULL){printSortTree(tree-＞left);putchar(tree-＞data);pdntSortTree(tree-＞right);}}main(){BTREE *root=NULL, *node;char ch;ch=getchar();while(ch !=''){node=(BTREE*)malloc(sizeof(BTREE));node-＞data=ch;node-＞left=node-＞right=NULL;SortTreelnsert(root, node);ch=getchar();}PrintSortTree(root);putchar('\n');TraversalTree(root);}
前序遍历序列与中序遍历序列相同的二叉树为(1)，前序遍历序列与后序遍历序列相同的二叉树为(2)。A．根结点无左子树的二叉树B．根结点无右子树的二叉树C．只有根结点的二叉树或非叶子结点只有左子树的二叉树D．只有根结点的二叉树或非叶子结点只有右子树的二叉树
阅读下列函数说明和C函数，将应填入(n)处的字句写对应栏内。[说明]二叉树的二叉链表存储结构描述如下：typedef struct BiTNode{ datatype data;struct BiTNode *lchild, * rchild; /*左右孩子指针*/}BiTNode,* BiTree;对二叉树进行层次遍历时，可设置一个队列结构，遍历从二叉树的根结点开始，首先将根结点指针入队列，然后从队首取出一个元素，执行下面两个操作：(1) 访问该元素所指结点；(2) 若该元素所指结点的左、右孩子结点非空，则将该元素所指结点的左孩子指针和右孩子指针顺序入队。此过程不断进行，当队列为空时，二叉树的层次遍历结束。下面的函数实现了这一遍历算法，其中Visit(datatype a)函数实现了对结点数据域的访问，数组queue[MAXNODE]用以实现队列的功能，变量front和rear分别表示当前队首元素和队尾元素在数组中的位置。[函数]void LevelOrder(BiTree bt) /*层次遍历二叉树bt*/{ BiTree Queue[MAXNODE];int front,rear;if(bt= =NULL)return;front=-1;rear=0;queue[rear]=(1);while(front (2) ){(3);Visit(queue[front]-＞data); /*访问队首结点的数据域*/if(queue[front]—＞lchild!：NULL){ rear++;queue[rear]=(4);}if(queue[front]-＞rchild! =NULL){ rear++;queue[rear]=(5);}}}
阅读下列函数说明和C函数，将应填入(n)处的字句写在对应栏内。[说明]二叉树的二叉链表存储结构描述如下：lypedef struct BiTNode{ datatype data;street BiTNode *lchiht, *rchild; /*左右孩子指针*/ } BiTNode, *BiTree;下列函数基于上述存储结构，实现了二叉树的几项基本操作：(1) BiTree Creale(elemtype x, BiTree lbt, BiTree rbt)：建立并返回生成一棵以x为根结点的数据域值，以lbt和rbt为左右子树的二叉树；(2) BiTree InsertL(BiTree bt, elemtype x, BiTree parent)：在二叉树bt中结点parent的左子树插入结点数据元素x；(3) BiTree DeleteL(BiTree bt, BiTree parent)：在二叉树bt中删除结点parent的左子树，删除成功时返回根结点指针，否则返回空指针；(4) frceAll(BiTree p)：释放二叉树全体结点空间。[函数]BiTree Create(elemtype x, BiTree lbt, BiTree rbt) { BiTree p;if ((p = (BiTNode *)malloc(sizeof(BiTNode)))= =NULL) return NULL;p-＞data=x;p-＞lchild=lbt;p-＞rchild=rbt;(1);}BiTree InsertL(BiTree bt, elemtype x,BiTree parent){ BiTree p;if (parent= =NULL) return NULL;if ((p=(BiTNode *)malloc(sizeof(BiTNode)))= =NULL) return NULL;p-＞data=x;p-＞lchild= (2);p-＞rchild= (2);if(parent-＞lchild= =NULL) (3);else{p-＞lchild=(4);parent-＞lchild=p;}return bt;}BiTree DeleteL(BiTree bt, BiTree parent){ BiTree p;if (parent= =NULL||parent-＞lchild= =NULL) return NULL;p= parent-＞lchild;parent-＞lchild=NULL;freeAll((5));return bt;
阅读以下预备知识、函数说明和C代码，将应填入(n)处的字句写在对应栏内。[预备知识]①对给定的字符集合及相应的权值，采用哈夫曼算法构造最优二叉树，并用结构数组存储最优二叉树。例如，给定字符集合{a，b，c，d}及其权值2、7、4、5，可构造如图3所示的最优二叉树和相应的结构数组Ht(数组元素Ht[0]不用)(见表5)。结构数组HT的类型定义如下：define MAXLEAFNUM 20struct node {char ch; / * 当前结点表示的字符，对于非叶子结点，此域不用*/int weight; / * 当前结点的权值*/int parent; / * 当前结点的父结点的下标，为0时表示无父结点*/int Ichild, rchild/ *当前结点的左、右孩子结点的下标，为0时表示无对应的孩子结点* /} Ht[2 * MAXLEAFNUM];②用'0'或'1'标识最优二叉树中分支的规则是：从一个结点进入其左(右)孩子结点，就用'0'('1')标识该分支(示例如图3所示)。③若用上述规则标识最优二叉树的每条分支后，从根结点开始到叶子结点为止，按经过分支的次序，将相应标识依次排列，可得到由'0'、'1'组成的一个序列，称此序列为该叶子结点的前缀编码。如图3所示的叶子结点a、b、c、d的前缀编码分别是110、0、111、10。【函数5.1说明】函数void LeafCode (int root, int n)的功能是：采用非递归方法，遍历最优二叉树的全部叶子结点，为所有的叶子结点构造前缀编码。其中形参root为最优二叉树的根结点下标；形参 n为叶子结点个数。在构造过程中，将Ht[p]. weight域用作被遍历结点的遍历状态标志。【函数5.1】char * * Hc;void LeafCode (int root, int n){/*为最优二叉树中的n个叶子结点构造前缀编码，root是树的根结点下标* /int i,p = root,cdlen =0;char code[20];Hc=(char* * )malloc(.(n +]) *sizeof(char* )); /* 申请字符指针数组* /for(i=1;i＜ =p;++i)Ht[ i]. weight =0;/* 遍历最优二叉树时用作被遍历结点的状态标志*/while(p) {/*以非递归方法遍历最优二叉树，求树中每个叶子结点的编码*/if(Ht[p], weight ==0) { /*向左*/Ht[ p]. weight =1if (Ht[p],lchild !=0) { p=Ht[P].lchild; code[cdlen++] ='0';]else if (Ht[p]. rchild ==0) {/* 若是叶子结点，则保存其前缀编码*/Hc[p] = ( char * ) malloc( (cdlen + 1 ) * sizeof (char) );(1); strcpy(He[ p] ,code);}}else if (Ht[ pi, weight == 1) { /*向右*/Ht[p]. weight =2;if(Ht[p].rchild !=0) {p=Ht[p].rchild; code[cdlen++] ='1';}}else{/* Ht[p]. weight ==2,回退*/Ht[p]. weight =0;p=(2);(3); /*退回父结点*/}}/* while结束* /}【函数5.2说明】函数void Decode(char*buff, int root)的功能是：将前缀编码序列翻译成叶子结点的字符序列并输出。其中形参root为最优二叉树的根结点下标；形参buff指向前缀编码序列。【函数5.2】void Decode( char * buff, int root)Iint pre =root,p;while ( * buff! = '\0') {p = root;while (p!=0){/*存在下标为p的结点*/pre=p;if((4))p=Ht[p].lchild; /*进入左子树*/else p = Ht[p]. rchild; / *进入右子树*./buff ++; / * 指向前缀编码序列的下一个字符* /}(5);printf("%c", Ht [ pre]. ch);}}
阅读以下说明和C函数，填补代码中的空缺(1)～(6)，将解答填入答题纸的对应栏内。【说明】二叉树的宽度定义为含有结点数最多的那一层上的结点数。函数GetWidth()用于求二叉树的宽度。其思路是根据树的高度设置一个数组counter[]. counter[i]存放第i层上的结点数，并按照层次顺序来遍历二叉树中的结点，在此过程中可获得每个结点的层次值，最后从countler[]中取出最大的元素就是树的宽度。按照层次顺序遍历二叉树的实现方法是借助一个队列，按访问结点的先后顺序来记录结点，离根结点越近的结点越先进入队列，具体处理过程为；先令根结点及其层次号（为1）进入初始为空的队列，然后在队列非空的情况下，取出队头所指示的结点及其层次号，然后将该结点的左子树根结点及层次号八队列（若左子树存在），其次将该结点的右子树根结点及层次号八队列（若右子树存在），然后再取队头，重复该过程直至完成遍历。设二叉树采用二叉链表存储，结点类型定义如下：typedef struct BTNode{TElemType data;struct BTNode *left. *right} BTNode , *BiTree _队列元素的类型定义如下typedef struct {BTNode *ptr;int LevelNumber) QElemType;【C函数】int GetWidth (BiTree root){QUEUE Q;QElemType a, b;int width.height = GetHeight(root);int i, *counter =(lnt*) calloc (helght+l. sizeof (int));if ( 1) return -1; ／*申请空间失败*/If(!root ) return -0; /*空树的宽度为0*／if ( 1) return -1 /*初始化队列失败时返回*／A.ptr=root; a.leveinumber=1;If(!Enqueue(＆Q,a)) return-1; ／*元素入队列操作失败时返回*／while (！isEmpty(Q》{if( (3) )return -1; /*出队列操作失败时返回*／Counter[b．LevelNumber]++；／*对层号为b．LevelNumber的结点计数*/if（bNaNr=＞left）{／*若左子树存在，则左于树根结点及其层次号入队*／aNaNr =bNaNr=＞left;a.LevelNurnber =(4) ；If(!EnQueue (Q,a))return -1;}if( bNaNr=＞right){／*若右子树存在，则右子树根结点及其层次号入队*／a．ptr= bNaNr-＞right;a LevelNumber (5) iIf(!EnQueue (Q,a))return -1}}width= counter[1];For(i=1; iheight+1;i++1) /*求counter[ ]中的最大值*/If(6) width =counter[i];Free(counter);Return width;}
●试题五阅读以下预备知识、函数说明和C代码，将应填入(n)处的字句写在答题纸的对应栏内。【预备知识】①对给定的字符集合及相应的权值，采用哈夫曼算法构造最优二叉树，并用结构数组存储最优二叉树。例如，给定字符集合{a，b，c，d}及其权值2、7、4、5，可构造如图3所示的最优二叉树和相应的结构数组Ht(数组元素Ht［0］不用)(见表5)。图3最优二叉树表5 结构数组Ht结构数组Ht的类型定义如下：define MAXLEAFNUM 20struct node{char ch;/*当前结点表示的字符，对于非叶子结点，此域不用*/int weight;/*当前结点的权值*/int parent;/*当前结点的父结点的下标，为0时表示无父结点*/int lchild,rchild;/*当前结点的左、右孩子结点的下标，为0时表示无对应的孩子结点*/}Ht［2*MAXLEAFNUM］;②用′0′或′1′标识最优二叉树中分支的规则是：从一个结点进入其左(右)孩子结点，就用′0′(′1′)标识该分支(示例如图3所示)。③若用上述规则标识最优二叉树的每条分支后，从根结点开始到叶子结点为止，按经过分支的次序，将相应标识依次排列，可得到由′0′、′1′组成的一个序列，称此序列为该叶子结点的前缀编码。例如图3所示的叶子结点a、b、c、d的前缀编码分别是110、0、111、10。【函数5．1说明】函数void LeafCode(int root,int n)的功能是：采用非递归方法，遍历最优二叉树的全部叶子结点，为所有的叶子结点构造前缀编码。其中形参root为最优二叉树的根结点下标；形参n为叶子结点个数。在构造过程中 ，将Ht［p］．weight域用作被遍历结点的遍历状态标志。【函数5．1】char**Hc；void LeafCode(int root,int n){/*为最优二叉树中的n个叶子结点构造前缀编码，root是树的根结点下标*/int i,p=root,cdlen=0;char code［20］;Hc=(char**)malloc((n+1)*sizeof(char*));/*申请字符指针数组*/for(i=1;i＜=p;++i)Ht［i］．weight=0;/*遍历最优二叉树时用作被遍历结点的状态标志*/while(p){/*以非递归方法遍历最优二叉树，求树中每个叶子结点的编码*/if(Ht［p］．weight==0){/*向左*/Ht［p］．weight=1;if (Ht［p］．lchild !=0) { p=Ht［p］．lchild; code［cdlen++］=′0′;}else if (Ht［p］．rchild==0) {/*若是叶子结 点，则保存其前缀编码*/Hc［p］=(char*)malloc((cdlen+1)*sizeof(char));(1) ;strcpy(He［p］，code);}}else if (Ht［p］．weight==1){/*向右*/Ht［p］．weight=2;if(Ht［p］．rchild !=0){p=Ht［p］．rchild;code［cdlen++］=′1′;}}else{/*Ht［p］．weight==2,回退*/Ht［p］．weight=0;p= (2) ; (3) ;/*退回父结点*/}}/*while结束*/}【函数5．2说明】函数void Decode(char*buff,int root)的功能是：将前缀编码序列翻译成叶子结点的字符序列并输出。其中形参root为最优二叉树的根结点下标;形参buff指向前缀编码序列。【函数5．2】void Decode(char*buff,int root){ int pre=root,p;while(*buff!=′＼0′){p=root;while(p!=0){/*存在下标为p的结点*/pre=p;if( (4) )p=Ht［p］．lchild;/*进入左子树*/else p=Ht［p］．rchild;/*进入右子树*/buff++;/*指向前缀编码序列的下一个字符*/｝(5) ;printf(″%c″,Ht［pre］．ch);}}
先序遍历序列和中序遍历序列相同的二叉树为()。A.根结点无左子树的二叉树B.根结点无右子树的二叉树C.只有根结点的二叉树或非子结点只有左子树的二叉树D.只有根结点的二叉树或非叶子结点只有右子树的二叉树
对于前序遍历与中序遍历结果相同的二叉树为（）A、一般二叉树B、只有根结点的二叉树C、根结点无左孩子的二叉树D、根结点无右孩子的二叉树E、所有结点只有左子数的二叉树F、所有结点只有右子树的二叉树
单选题前序遍历和中序遍历结果相同的二叉树是（）。A根结点无左孩子的二叉树B根结点无右孩子的二叉树C所有结点只有左子树的二叉树D所有结点只有右子树的二叉树