上海交大数据结构习题课二_于波.pptxVIP

数据结构习题课二 树和查找TA：于波计算机科学工程系上海交通大学December 5, 2009二叉树的性质1. 一棵非空的二叉树的第i层上最多有 个结点。证明见教材 Page 93页。二叉树的性质2. 一棵高度为 k 的二叉树最多具有 个结点。证明见教材 Page 93页。二叉树的性质3. 对于一棵非空的二叉树如果叶子结点数为 ，度数为2的结点数为 ，则有 成立。证明见教材 Page 93页。对结点： n=n0+n1+n2;对边： n-1=0*n0+1*n1+2*n2二叉树的性质4. 具有n个结点的完全二叉树高度为 。证明见教材 Page 94页。注意： 树的深度 + 1 == 树的高度基础知识题1. 若一个具有N个顶点，K条边的无向图是一个森林（NK），求该森林中有多少棵树。基础知识题解答: 因为一棵具有n个顶个的树有n-1条边，因此设此森林中有m棵树，每棵树具有的定点数为 vi （1= i =m） v1+v2+…+vm=N; (v1-1)+(v2-1)+…+(vm-1)=K; = m=N-K基础知识题2. 已知一棵度为m的树中有N1个度为1的结点，N2个度为2的结点，….，Nm个度为m的结点。试问该树中有多少个叶子结点？基础知识题解答: 关键在于树的结点个数与边的条数联系起来总的结点个数-1 = 边数= ….基础知识题3. 将算术表达式 ((a+b)+c*(d+e)+f)*(g+h) 转化为二叉树基础知识题*++gh+f+*+bcade基础知识题4. 任意一个有n个结点的二叉树，一直它有m个叶子结点，试证明非叶子结点有m-1个度为2，其余的度为1.基础知识题解答: 关键在于树的结点个数与边的条数联系起来设二叉树中度为1和2的结点数为 n1 、 n2 ,总结点数为 n。n=n1+n2+m n-1=1*n1+2*n2= n2=m-1基础知识题5. 有n个结点的二叉树，已知叶子结点的个数为n0，写出求度数为1的结点个数n1的计算公式；若此树是高度为k的完全二叉树，写出n为最小的公式；若二叉树中仅有度为0和度为2的结点，写出求该二叉树结点个数n的公式。基础知识题解答:记度为2的结点个数为n2n=n0+n1+n2n-1=1*n1+2*n2; = n1=n+1-2n0当树是高度为k的完全二叉树， 完全二叉树，最小，那就是高度为k-1的满二叉树加1个结点。仅有度为0和2，n=n0+n2,n-1=2*n2 = n=2*n0 -1基础知识题6. 设高为h的二叉树只有度为0和2的结点，则此类二叉树的结点数至少为____, 至多为______.基础知识题解答:最少的情形 最多的情形 高度为h-1的满二叉树高度为h的满二叉树基础知识题7. 深度为 k-1 的完全二叉树至少有____个结点，至多有_____个结点，k和结点数n之间的关系为______.基础知识题解答:深度为 k-1 的完全二叉树至少有 个结点，至多有 个结点，k和结点数n之间的关系为. 高为h-1满二叉树+1结点高为h满二叉树 二叉树性质四基础知识题8. 回答问题写出推导过程: 含N个结点和N个叶子结点的完全三叉树的高度是多少？基础知识题解答:含N个结点的完全三叉树的高度设为H 基础知识题解答: 2. 含N个叶子结点的完全三叉树的高度设为H H为 a. N为3的幂： 或 b. 其他：基础知识题9. 用一维数组存放的一棵完全二叉树如下：A B C D E F G H I J K L写出后序遍历二叉树时访问结点的顺序基础知识题解答: 画树出解 H I D J K E B L F G C A基础知识题10. 有二叉树中序序列为：ABCEFGHD后序序列为：ABFHGEDC画出此二叉树基础知识题解答:CBDAEGFH基础知识题11. 已知二叉树各结点的先序、中序遍历分别为ABCDEF和CBAEDF，画出该二叉树。基础知识题解答:ABDCEF基础知识题12. 若一棵二叉树，左右子树均有三个结点，其左子树的前序序列与中序序列相同，右子树的中序序列与后序序列相同，试图构造树。基础知识题解答:左子树前序与中序相同前序：根 左 右中序：左 根 右同理右子树中序与后序中序：左 根 右后序：左 右 根基础知识题13. 已知二叉树左右子树均含有3个结点，试图构造满足下面条件的二叉树（1）左右子树先序与中序相同（2）左子树中序与后序，右子树先序与中序相同基础知识题解答:基础知识题14. 对于前序遍历和中序遍历结果相同的二叉树为______;对于前序遍历和后序遍历结果相同的二叉树为______。基础知识题解答:对于前序遍历和中序遍历结果相同的二叉树为 ;对于前序遍历和后序遍历结果相同的二叉树为