资源描述：
《树、二叉树习题.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、1、深度为k的完全二叉树至多有（C）个结点，至少有（B）个结点。A．2k-1-1B．2k-1C．2k-1D．2k2、在具有200个结点的完全二叉树中，设根结点的层次编号为1，则层次编号为60的结点，其左孩子结点的层次编号为（C2i），右孩子结点的层次编号为（D2i+1），双亲结点的层次编号为（60/2=30A）。A．30B．60C．120D．1213、一棵具有124个叶子结点的完全二叉树，最多有（B）个结点。A．247B．248C．249D.2504、已知完全二叉树第6层上有10个叶子结点，则这棵二叉树的结点总数最多是107。5、一棵具有n个结点的二叉树，若它有m个叶子结点
2、，则该二叉树中度为1的结点个数是n-2m+1。6、深度为k（k>0）的二叉树至多有2k-1个结点，第i层上至多有2i-1个结点。7、已知二叉树中有30个叶子结点，则二叉树的总结点个数至少是30+29+0=59。8、一棵深度为6的满二叉树有n1+n2=0+n2=n0-1=31个分支结点和26-1=32个叶子。9、设一棵完全二叉树具有1000个结点，则此完全二叉树有500个叶子结点，有499个度为2的结点，有1个结点只有非空左子树，有0个结点只有非空右子树。答：最快方法：用叶子数＝[n/2]＝500，n2=n0-1=499。另外，最后一结点为2i属于左叶子，右叶子是空的，所以有
3、1个非空左子树。完全二叉树的特点决定不可能有左空右不空的情况，所以非空右子树数＝0.10、含有11个结点的不相似的二叉树有_______棵。11、若已知一棵二叉树的前序序列是BEFCGDH，中序序列是FEBGCHD，则它的后序序列必是FEGHDCB。基本知识二叉树的创建二叉树的前中后序遍历二叉树的深度、叶子二叉树的前中后序非递归二叉树的层次遍历创建哈弗曼树哈弗曼编码intLayerOrder(BiTreebt){SeqQueue*Q;BiTreep;精选范本,供参考！Q=(SeqQueue*)malloc(sizeof(SeqQueue));InitQueue(Q);/*初
4、始化空队列Q*/if(bt==NULL)returnERROR;/*若二叉树bt为空树，则结束遍历*/EnterQueue(Q,bt);/*若二叉树bt非空，则根结点bt入队，开始层次遍历*/while(!IsEmpty(Q))/*若队列非空，则遍历为结束，继续进行*/{DeleteQueue(Q,&p);/*队头元素出队并访问*/printf("%c",p->data);if(p->LChild)EnterQueue(Q,p->LChild);/*若p的左孩子非空，则进队*/if(p->RChild)EnterQueue(Q,p->RChild);/*若p的右孩子非空，则
5、进队*/}/*while*/returnOK;}/*LayerOrder*/编程题1、有数据为{22，10，46，17，13，110，20，15，34}试构造一棵哈夫曼（Huffman树）,并计算WPL。2、二叉树的深度、叶子个数、公共祖先3、判断两棵二叉树是否相同4、给先续和中序建立二叉树5、求二叉树节点的最大距离6、判断两颗二叉树是否相似intlike(BiTreeb1,BiTreeb2){intlike1,like2;if(b1==NULL&&b2==NULL)return(1);elseif(b1==NULL
6、
7、b2==NULL)return(0);else{lik
8、e1=like(b1->LChild,b2->LChild);like2=like(b1->RChild,b2->RChild);return(like1&&like2);}精选范本,供参考！}1、求从根结点到某结点间的路径voidpath(BiTreeroot,BiTNode*r){BiTNode*p,*q;inti,find=0,top=0;BiTNode*s[NUM];q=NULL;/*用q保存刚遍历过的结点*/p=root;while((p!=NULL
9、
10、top!=0)&&!find){while(p!=NULL){top++;s[top]=p;p=p->LChil
11、d;}/*遍历左子树*/if(top>0){p=s[top];/*根结点*/if(p->RChild==NULL
12、
13、p->RChild==q){if(p==r)/*找到r所指结点，则显示从根结点到r所指结点之间的路径*/{for(i=1;i<=top;i++)printf("%c",s[i]->data);find=1;}else{q=p;/*用q保存刚遍历过的结点*/top--;p=NULL;/*跳过前面左遍历，继续退栈*/}}elsep=p->RChild;/*遍历右子树*/}}}精选范本,供参考！【本文档内容
