资源描述：
《树二叉树答案》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。
1、1、深度为k的完全二叉树至多有（C）个结点，至少有（B）个结点。A.2kl-lB・2k_1C・2k-lD・2k2、在具有200个结点的完全二叉树中，设根结点的层次编号为1,则层次编号为60的结点，其左孩子结点的层次编号为（C2i）,右孩子结点的层次编号为（D2i+l）,双亲结点的层次编号为（60/2=30A）。A.30B.60C.120D.1213、一棵具有224个叶子结点的完全二叉树，最多有（B）个结点。A.247B.248C.249D.2504、已知完全二叉树第6层上有10个叶子结点，则这棵二叉树的结点总数最多是107o26-1=63,25=32,32-10二22,4
2、4+635、一棵具有n个结点的二叉树，若它有m个叶子结点，则该二叉树屮度为1的结点个数是On=n0+nl+n2,n0=n2+l6、深度为k（k>0）的二叉树至多有2*・1个结点,第i层上至多有2***个结点。7、已知二叉树屮有小30个叶子结点，则二叉树的总结点个数至少是30+29+0二59on0=n2+ln0=30n2=29nl二08、一棵深度为6的满二叉树有nl+r】2二0+n2二nO-1二31个分支结点和2=1二32个叶子。9、设一棵完全二叉树具有1000个结点，则此完全二叉树有500个叶子结点,有499个度为2的结点,有1个结点只有非空左子树,有_Q_个结点只有非空
3、右子树。答：最快方法：用叶子数=[n/2]=500,n2=n0-l=499o另外，最后一结点为2i属于左叶子，右叶子是空的，所以有1个非空左子树。完全二叉树的特点决定不可能有左空右不空的情况，所以非空右子树数=0.10、含有11个结点的不相似的二叉树有単棵。n+111、若己知一棵二叉树的前序序列是BEFCGDH,中序序列是FEBGCHD,则它的后序序列必是O基本知识二叉树的创建二叉树的前中后序遍历二叉树的深度、叶子二叉树的前中后序非递归二叉树的层次遍历创建哈弗曼树哈弗曼编码intLayerOrder(BiTreebt)SeqQueue*Q;BiTreep;Q=(SeqQu
4、eue*)malloc(sizeof(SeqQueue));InitQueue(Q);/*初始化空队列Q*/if(bt==NULL)returnERROR;/*若二叉树bt为空树，则结束遍历*/EnterQueue(Q,bt);/*若二叉树bt非空,则根结点bt入队,开始层次遍历*/while(!IsEmpty(Q))/*若队列非空，则遍历为结束，继续进行*/{DeletcQueue(Q,&p);/*队头元素出队并访问*/printf("%c“，p->data);if(p->LChild)EnterQueue(Q,p->LChild);/*若p的左孩子非空,则进队*/if
5、(p->RChild)EnterQueue(Q,p->RChild);/*若p的右孩子非空，则进队*/}/*whi.le*/returnOK;}/*LayerOrder*/编程题20,15,34｝试构造一棵哈夫曼（Huffman1、有数据为{22,10,46,17,13,110,5532101315172、二叉树的深度、叶子个数、公共祖先BiTrccLCA(B订rcoroot,DataTypcT,DataTypcS){BiTree1,r;if(root二二NULL)returnNULL;if(root->data==T
6、
7、root->data==S)returnroot:
8、1=LCA(root->LChilcl,T,S);r=LCA(root->RChild,T,S);if(1!=NULL&&r!=NULL)returnroot;if(1!=NULL)return1;if(r!=NULL)returnr;rcturnNULL;1.BTreeNode_t*GetLastCommonParent(BTreeNode_t*pRoot,BTreeNode_t*pNodel,BTreeNode_t*pNode2){2.if(pRoot==NULL)〃说明是空树，不用查找了，也就找不到对应节点，则返回NULL3.returnNULL;4.4.if(pR
9、oot==pNodel
10、
11、pRoot==pNode2)〃说明在当前子树的根节点上找到两个节点之一5.returnpRoot;7.6.BTreeNodeJ*pLcft=GetLastCommonParent(pRoot->m_pLeft,pNodel,pNode2);〃左子树中的查找两个节点并返回查找结果7.BTreeNode_t*pRight=GetLastCommonParent(pRoot->m_pRight,pNodel,pNode2);〃右子树屮查找两个节点并返回查找结果10.8.if(pLeft==NULL)〃如果在
