《数据结构与算法设计》树-习题.ppt
《《数据结构与算法设计》树-习题.ppt》由会员分享,可在线阅读,更多相关《《数据结构与算法设计》树-习题.ppt(37页珍藏版)》请在三一办公上搜索。
1、1,树的练习题,具有n个顶点的二叉树,共有多少边?,2、若一个具有N个顶点,K条边的无向图是一个森林(NK),那么该森林有多少棵树?,3、已知一棵度为m的树中有N1个度为1的节点,N2个度为2的节点,Nm个度为m的节点。问该树有多少叶子节点?,4、层数为k的二叉树中,最大和最小节点数各为多少?,5、有n个节点的二叉树中,有m个叶子节点,问非叶子节点中度为2和度为1的节点各有多少?,n-1,NK,N0=N2+2N3+(m-1)Nm+1,2k-1,k,n2=m-1;n1=n-2m+1,2,B,C,B,3,假定一棵树的广义表示为(A(B(C,D(E,F,G),H(I,J),则树中所含的结点数为()个
2、,树的深度为()个,树的度为()。,3,2、在哈夫曼编码中,若编码长度只允许小于等于4,则除了已对两个字符编码为0和10外,还可以最多对()个字符编码.,4,3、一颗二叉树的前序遍历序列为aebdc,后序遍历序列为bcdea,根节点的孩子节点A.只有e B.e和b C.e和c D.不确定,A,10,4,4,试问利用树的先根次序遍历结果和后根次序遍历结果能否唯一确定一棵树?1、树的先根次序遍历的结果与其对应二叉树的前序遍历结果相同 2、树的后根次序遍历结果与其对应二叉树的中序遍历结果相同;3、对于二叉树而言,先序遍历和中序遍历可以确定一个二叉树,因此,树的先根次序遍历结果和后根次序遍历结果能唯一
3、确定一棵树,5,用二叉链表作为二叉树的存储表示,统计二叉树中叶结点的个数,请完成下列递归程序。,int leaf(BiTNode*ptr)if()return 0;else if(ptr-lChild=NULL,typedef struct BiTNode/结点结构 TElemType data;struct BiTNode*lchild,*rchild;/左右孩子指针 BiTNode,*BiTree;,ptr=NULL,leaf(ptr-lChild),leaf(ptr-rChild),6,二叉树的双序遍历(Double-order traversal)是指:对于二叉树的每一个结点来说,先访
4、问这个结点,再按双序遍历它的左子树,然后再一次访问这个结点,接下来按双序遍历它的右子树。试写出执行这种双序遍历的算法。,void Double_order(BiTNode*current)if(current!=NULL)printf(“%f,”,current-data);printf(“%f,”,current-data);Double_order(current-rChild);,Double_order(current-rChild),7,已知一棵具有n个结点的完全二叉树被顺序存储于一维数组的A1An元素中,试找出编号为i的结点的双亲和所有孩子。假设每一个元素用一个整数表示。完成下列程
5、序,8,void Request(int A,int n,int i)/从数组A中打印出编号为i的结点的双亲和孩子 if()exit(1);printf(current element:%f”,Ai);int j=i/2;/下标为j的结点是下标为i结点的双亲 if()printf(“parent:%f”,Aj);else prinf(“No parent!);if()printf(left child:%f”,A2*i);printf(right child:%f“,A2*i+1;else if()printf(left child:%f,A2*i);printf(no right child
6、!;else printf(no children!“);,in,j0,2*in,2*i=n,9,已知二叉树先序序列为:ABCDEF中序序列为:CBAEDF请画出该二叉树。,10,A,D,11,已知二叉树中序序列为:ABCEFGHD后序序列为:ABFHGEDC请画出该二叉树。中序:LDR后序:LRD,A B C E F G H D,A B F H G E D C,12,将下列森林转化为二叉树,然后对森林进行先序和后序遍历,7,13,将下列树进行中序线索化,中序:CBAGEDF,14,试分别找出满足以下条件的所有二叉树 二叉树的前序序列与中序序列相同 二叉树的中序序列与后序序列相同 二叉树的前序
7、序列与后序序列相同 如果一棵Huffman树有n0个叶子节点,那么该树有多少节点?已知如下序列:8、5、3、2、7、23、9、11、2、35,请构造一棵Huffman树。,2n0-1,请指出下列函数的功能,15,/先序遍历方式,递归void swap(BiTNode*b)BiTNode*t;if(b=NULL)return;t=b-lchild;b-lchild=b-rchild;b-rchild=t;swap(b-lchild);swap(b-rchild);,交换左右子树,16,请指出下列函数的功能,void preserve(BiTNode*b,ElemType a,int n)stat
8、ic int i=0;if(b!=NULL)preserve(b-lChild,a,n);ai+=b-data;preserve(b-rChild,a,n);,得到二叉树b的中序遍历序列,结果放在数组a中,2005考研试题,根据_可以唯一地确定一棵二叉树。A.先序遍历和后序遍历 B.先序遍历和层次遍历 C.中序遍历和层次遍历 D.中序遍历和后序遍历,D.中序遍历和后序遍历,2005考研试题,所有分支结点的度为2的二叉树称为正则二叉树,试用二叉链表做存储结构,编写一递归函数int FormalTree(Bitree t),判断二叉树是否为正则二叉树。,int FormalTree(Bitree
9、t)if(t=NULL)return 1;if(t-lchild=NULL),2006考研试题,下面不能唯一确定一棵二叉树的两个遍历序列是_。A)先序序列和中序序列 B)先序序列和后序序列C)后序序列和中序序列 C)都不能,在树的孩子兄弟表示法中,二叉链表的左指针指向_,右指针指向_。,B)先序序列和后序序列,第一个孩子,下一个兄弟,在二叉链表的每个结点中添加一个域int depth,表示以该结点为根的子树的深度,即:typedef struct BiTNode/结点结构 TElemType data;struct BiTNode*lchild,*rchild;/左右孩子指针 int dept
10、h;/以该结点为根的子树的深度 BiTNode,*BiTree;a.试编写一递归函数BiTreeDepth(BiTree T),计算二叉树T中每个结点的depth值,函数的返回值为树T的深度。b.在a的基础上(即已求出二叉树中每个结点的depth值),编写一递归函数BiTreeBalance(BiTree T),判断二叉排序树T是否为平衡二叉树,如果是平衡二叉树,则函数的返回值为真。,a.int BiTreeDepth(BiTree T)int ldepth,rdepth;if(!T)return-1;ldepth=BiTreeDepth(T-lchild);rdepth=BiTreeDept
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构与算法设计 数据结构 算法 设计 习题
![提示](https://www.31ppt.com/images/bang_tan.gif)
链接地址:https://www.31ppt.com/p-5898666.html