树和二叉树复习

树和二叉树复数分别为4，2，1，1则T中的叶子数为（） 结点的度：结点拥有的子树数。(每个结点有多少个分支叶子（终010 机实( 的结点树的度：树内各结点的度的最大值由树的性质知：结点数为所有结点的度数之和加1同时注意到叶子结点的度数为0。则总结点数(设叶子结点数为X)叶子结点数为X=16-4-3-2-具有10个叶结点的二叉树中有（）个度为2的 的结点数n2，结点总数n=n0+n1+n2分支数：n1n1+2n2+1=n=n0+n1+得：n0n2一个具有1025个结点的二叉树的高h为（ C．11至1025之 D．10至1024之 B．2h- 对于有n个结点的二叉树,其高度为（ D．不确n个结点的完全二叉树的树高度（深度）（ C． D．log2n-一个具有1025个结点的二叉树的高h为（C C．11至1025之 D．10至1024之二叉树最少有(B) B．2h- 对于有n个结点的二叉树,其高度为（ D．不确（ C． D．log2n- 满二叉树最矮：210–1最长单支二叉树，每层一个结点，1025面仅包含2个结点，因此结点总数=2h-2k-1-1n≤2k-1，有k-1≤log2nk，k是整数，有k=log2n+242458 满 B．FEDCBA C．CBEDF 二叉树的先序遍历和中序遍历如下：先序遍历：EFHIGJK；中序遍历HFIEJKG。该二叉树根的右子树的根是（）。A、 B、 C、 D、二叉树的先序遍历和中序遍历如下：先序遍历：EFHIGJK；中序遍历HFIEJKG。该二叉树根的右子树的根是（C）。A、 B、 C、 D、化后，其中空的链域的个数是：(B)。A. B. C D结点，且X不为根，则x的前驱为(C)。X的双亲B.X的右子树中最左的点CX的左子树中最右结点DX的左子设森林F对应的二叉树为B，它有m个结点B的根为p,p的右子树结点个数为n,森林中第一棵树的结点个数是（ 设森林F对应的二叉树为B，它有m个结点B的根为p,p的右子树结点个数为n,森林中第一棵树的结点个数是（A 个数是（）。 个数是（D）。 空的结点有（）个。n- C． D．mn综合可得：设给定权值总数有n个，其树的结点总数为(D) 与先序遍历算法比较一下例1求二叉树的叶子结点个数的算法与先序遍历算法比较一下结果：二叉树的叶子结点个voidleaf(structBiTNode//采用二叉链表存贮二叉树，n为全局变量，用于累加二叉树的叶子结点的个数//算法在先序遍历二叉树的过程中，统计叶子结点的个数,第一次被调用时if(root->lchild=NULL&&root->rchild=NULL)n=n+1;//若root所指结点为叶子,则累加AA}}

B∧B∧∧C∧E∧∧F∧例2输出二叉树中voidPreOrder(structBiTNode//先序遍历输出二叉树中的叶子结点,root为指向二叉树根结点的指{if(root!ifrootLChild==NULL&&root>RChild==NULL)printf(root->data); //输出叶子结点PreOrder(root->LChild);//先序遍历左子树PreOrder(root->RChild);//先序遍历右子树}}例2输出二叉树中的双孩子结点数voiddouble(structBiTNode//root为指向二叉树根结点的指{intnum1,num2;intn=0；if(root!=NULL){if(root->LChild!=NULL&&root- double(rootLChild先序遍历左子double(root->RChild先序遍历右子}}例3叉树高二叉树的高度(深度)为二叉树中结点层次的最大值。设根结点为第1层的结点，所有h层的结点的左右孩子结点在1层，则可以通过遍历计算二叉树中每个结点的层次，其中最大值即为二叉树的高度。voidBiTreeDepth(BiTreeT,intlevel,int{T指向二叉树的根，levelT所指结点所在层次//其初值为1，depth为当前求得的最大层次,其初值为if{if(level>depth)depth=level;BiTreeDepth(T->Lchild,level+1,depth);BiTreeDepth(T->Rchild,level+1,depth);}}//主函数中求二叉树root的深度的语句为Flash演求指定结点的层voidfindlevel(BiTreeT,p,intlevel,int{T指向二叉树的根，p待找结点，h待找p结点的层if(T==null)elseif(p==T->data)h=lh;

findlevel(T->Lchild,p,level+1,h);findlevel(T->Rchild,p,level+1,h);}Flash演试编写一个判断任意给定的二叉树是否为类满二叉树（其任何结点或为叶子，或者有左、右两颗非空子树）的递归函数，并把它转化为非归函数递归定义f(b 若b->leftnull且b->rightf(b 若b->left,b->right之一为null，另一不为f(bf(b->left&&f(b->right 若b->leftnullb->rightintfull(btree{if(b->left=null&&b->right=returnelseif(b->left=null||b->right=elsereturn(full(b->left)&&full(b-}intfull1(btree{btreeinttop=1;ftree=if{while(top{if(p->left==null&&b->right!=null)||(p->left!=null&&b->right==ftree=elseif(p->left!=nu