树与二叉树、哈夫曼树学案.doc

《树与二叉树、哈夫曼树学案.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、信息学科学案序号高一年级班学生树与二叉树学案一、树的定义及特点树(tree)是n(n>0)个结点的有限集T。特点：树中至少有一个结点——根，树的根结点没有_______________，除根结点以外的所有结点有_______个前驱结点。树的所有结点都可以有_______________个后继结点。二、树的术语结点(node)——表示树中的元素，包括数据项及若干指向其子树的分支度(degree)——结点拥有的子树数叶子(leaf)——度为0的结点孩子(child)——结点子树的根称为该结点的孩子双亲(parents

2、)——孩子结点的上层结点叫该结点的双亲兄弟(sibling)——同一双亲的孩子树的度——一棵树中最大的结点度数结点A的度：__________结点B的度：__________结点M的度：__________结点A的孩子：__________结点B的孩子：__________树的度：___________________叶子：___________________结点I的双亲：_________结点L的双亲：_________结点B，C，D为_________结点K，L为____________结点A的层次：___

3、______结点M的层次_________树的深度_______________层次(level)——从根结点算起，根为第一层，它的孩子为第二层……深度(depth)——树中结点的最大层次数森林(forest)——m(m>=0)棵互不相交的树的集合ABCDEFGHIJKLM三、二叉树定义及特点定义：二叉树是n(n>=0)个结点的有限集，它或为空树(n=0)，或由一个根结点和两棵分别称为左子树和右子树的互不相交的二叉树构成。特点：①　每个结点至多有二棵子树(即不存在度大于2的结点)②　二叉树的子树有左、右之分，且其

4、次序不能任意颠倒四、二叉树的性质性质1在二叉树的第i层上至多有________________个结点（i>=1)性质2深度为k的二叉树至多有___________________个结点(k>=1)性质3对任何一棵二叉树T，如果其终端结点数为n0，度为2的结点数为n2，则n0和n2的关系：______________证明：因为二叉树中所有结点的度均不大于2，所以结点总数（记为n）应等于0度结点数、1度结点（记为n1）和2度结点数（记为n2）之和n=_____________（式子1）另一方面，1度结点有一个孩子，2

5、度结点有两个孩子，故二叉树中孩子结点总数是：n1+2n2，树中只有根结点不是任何结点的孩子，故二叉树中的结点总数又可表示为n=_____________（式子2）由式子1和式子2得到：_____________________五、满二叉树定义：一棵深度为k且有2k-1个结点的二叉树称为满二叉树。特点：每一层上的结点数都达到最大值满二叉树中不存在度数为1的结点，每个结点均有两棵高度相同的子树，且树叶都在最下一层。六、完全二叉树定义：若一棵二叉树至多只有最下面的两层上结点的度数小于2，并且最下一层上的结点都集中在该层

6、最左边的若干位置上，则此二叉树称为完全二叉树。特点：满二叉树是完全二叉树，完全二叉树不一定是满二叉树。在满二叉树的最下一层上，从最右边开始连续删去若干结点后得到的二叉树仍然是一棵完全二叉树。若某个结点没有左孩子，则它一定没有右孩子，即该结点必是叶子结点。例：已知一棵完全二叉树共有892个结点，试求：①　树的高度___________________②　叶子结点数___________________③　单支结点数___________________④　最后一个非终端结点的序号__________________

7、_七、二叉树的遍历NLR：前序遍历，访问结点的操作发生在遍历其左右子树之前LNR：中序遍历，访问结点的操作发生在遍历其左右子树之中（间）LRN：后序遍历，访问结点的操作发生在遍历其左右子树之后【练习】ABCDEFG1.一棵完全二叉树上有1001个结点，其中叶子结点的个数是（）A.250B.500C.254D.505E.以上答案都不对2.将有关二叉树的概念推广到三叉树，则一棵有244个结点的完全三叉树的高度是（）A.4B.5C.6D.73.某二叉树中序序列为abcdefg，后序序列为bdcafge，则前序序列是（）

8、A.egfacbdB.egfacbdC.eacbdgfD.eagcfbcE.以上答案都不对4.给定如图1所示的一棵二叉树，写出它的前序、中序、后序遍历。前序：中序：后序：图15.已知，按中序遍历二叉树的结果为：abc，问：有多少种不同形态的二叉树可以得到这一遍历结果？答：6.对于前序遍历与中序遍历结果相同的二叉树为（），对于前序遍历和后序遍历结果相同的二叉树为（）。A.一