树、二叉树习题.doc

1、 深度为k的完全二叉树至多有（ C ）个结点，至少有（ B ）个结点。A 2k-1-1 B 2k-1 C 2k-1 D 2k2、 在具有200个结点的完全二叉树中，设根结点的层次编号为 1，则层次编号为60的结点，其左孩子结点的层次编号为（ C 2i ），右孩子结点的层次编号为（ D 2i+1），双亲结点的层次编号为（ 60/2=30 A ）。A 30 B 60 C 120 D 1213、 一棵具有124个叶子结点的完全二叉树，最多有（B ）个结点。A 247 B 248C 249 D. 2504、 已知完全二叉树第6层上有10个叶子结点，则这棵二叉树的结点总数最多是 107 。5、 一棵具有n个结点的二叉树，若它有m个叶子结点，则该二叉树中度为1的结点个数是 n-2m+1 。6、 深度为k（k0）的二叉树至多有 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/2500 ，n2=n0-1=499。 另外，最后一结点为2i属于左叶子，右叶子是空的，所以有1个非空左子树。完全二叉树的特点决定不可能有左空右不空的情况，所以非空右子树数0.10、 含有11个结点的不相似的二叉树有_棵。11、 若已知一棵二叉树的前序序列是BEFCGDH，中序序列是FEBGCHD，则它的后序序列必是 F E G H D C B 。基本知识二叉树的创建二叉树的前中后序遍历二叉树的深度、叶子二叉树的前中后序非递归二叉树的层次遍历创建哈弗曼树哈弗曼编码int LayerOrder(BiTree bt) SeqQueue *Q;BiTree p;Q=(SeqQueue *)malloc(sizeof(SeqQueue);InitQueue(Q); /*初始化空队列Q*/if(bt = NULL)return ERROR; /* 若二叉树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的右孩子非空，则进队*/*while*/return OK;/* LayerOrder */编程题1、 有数据为 22，10，46，17，13，110，20，15，34 试构造一棵哈夫曼（Huffman树）,并计算WPL。2、 二叉树的深度、叶子个数、公共祖先3、 判断两棵二叉树是否相同4、 给先续和中序建立二叉树5、 求二叉树节点的最大距离6、 判断两颗二叉树是否相似int like(BiTree b1, BiTree b2) int like1, like2;if (b1=NULL & b2=NULL) return (1);else if (b1=NULL | b2=NULL) return (0);else like1=like(b1-LChild, b2-LChild);like2=like(b1-RChild, b2-RChild);return (like1 & like2);7、 求从根结点到某结点间的路径void path(BiTree root, BiTNode *r) BiTNode *p, *q;int i, find=0, top=0;BiTNode *sNUM;q = NULL; /* 用q保存刚遍历过的结点 */p = root;while ( (p != NULL | top != 0) & !find )while ( p != NULL ) top+; stop = p;p = p-LChild; /* 遍历左子树 */if (top 0) p=stop; /* 根结点 */if ( p-RChild = NULL | p-RChild = q ) if(p = r) /*找到r所指结点，则显示从根结点到r所指结点之间的路径*/for(i=1;idata);find=1;elseq = p; /* 用q保存刚遍历过的结点 */top-;p =