彩色PDF讲义(4)

《彩色PDF讲义(4)》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、数据结构与算法第四章二叉树张铭http://db.pku.edu.cn/mzhang/DS/北京大学信息科学与技术学院“数据结构与算法”教学小组©版权所有，转载或翻印必究主要内容¢4.1二叉树的概念¢4.2二叉树的主要性质¢4.3二叉树的抽象数据类型¢4.4周游二叉树¢4.5二叉树的实现¢4.6二叉搜索树¢4.7堆与优先队列¢4.8Huffman编码树北京大学信息学院张铭编写©版权所有，转载或翻印必究Page24.1二叉树的概念¢4.1.1二叉树的定义及相关概念¢4.1.2满二叉树完全二叉树扩充二叉树北京大学信息学院张铭编写©版权

2、所有，转载或翻印必究Page3二叉树的定义¢树的特例¢递归的定义：二叉树由结点的有限集合构成:¢或者为空集¢或者由一个根结点及两棵不相交的分别称作这个根的左子树和右子树的二叉树(它们也是结点的集合)组成北京大学信息学院张铭编写©版权所有，转载或翻印必究Page4二叉树的五种基本形态¢二叉树可以是空集合，因此根可以有空的左子树或右子树，或者左右子树皆为空(a)空(b)独根(c)空右(d)空左(e)左右都不空北京大学信息学院张铭编写©版权所有，转载或翻印必究Page5二叉树的相关术语¢结点¢根结点、子结点、父结点、左子结点、右子结点¢

3、分支结点、叶结点A¢边¢路径、路径长度BC¢祖先、后代¢深度、高度、层数、宽度EF¢二叉树的高度定义为二叉树中层数最大的叶结点的层数加1D¢二叉树的深度定义为二叉树中G层数最大的叶结点的层数HI北京大学信息学院张铭编写©版权所有，转载或翻印必究Page6满二叉树¢如果一棵二叉树的任何结点，或者是树叶，树叶或者恰有两棵非空子树，则此二叉树称作两棵非空子树满二叉树ACBDEFGHI北京大学信息学院张铭编写©版权所有，转载或翻印必究Page7完全二叉树¢最多只有最下面的两层结点度数可以小于2¢最下一层的结点都集中最左边AABCBCDEF

4、GDEFGHIJKL北京大学信息学院张铭编写©版权所有，转载或翻印必究Page8扩充二叉树¢所有空子树，都增加空树叶xalwanzolwilyozomwimwenxulyumwulxemyonzi北京大学信息学院张铭编写©版权所有，转载或翻印必究Page9扩充二叉树¢扩充二叉树是满二叉树¢新增加的空树叶(外部结点)的个数等于原来二叉树的结点(内部结点)个数加1¢路径长度¢外部路径长度E从扩充的二叉树的根到每个外部结点的路径长度之和¢内部路径长度I扩充的二叉树里从根到每个内部结点的路径长度之和¢E和I两个量之间的关系为E=I+2n北

5、京大学信息学院张铭编写©版权所有，转载或翻印必究Page104.2二叉树的主要性质¢1.满二叉树定理：非空满二叉树树叶数等于其分支结点数加1¢证明：设结点总数为n，叶结点数m，分支结点数b。有n（总结点数=m（叶)+b（分支）(公式4.1)¢每个分支，恰有两个子结点（满），故有2*b条边；¢一颗二叉树，除根结点外，每个结点都恰有一条边联接父结点，故共有n-1条边,即n-1=2b(公式4.2)¢由(公式4.1)，(公式4.2)得n-1=m+b-1=2b，得出m(叶)=b（分支）+1北京大学信息学院张铭编写©版权所有，转载或翻印必究P

6、age114.2二叉树的性质2.满二叉树定理推论：一个非空二叉树的空子树(指针)数目等于其结点数加1。证明：设二叉树T，将其所有空子树换为树叶，记新的扩充满二叉树为T’。所有原来T的结点现在是T’的分支结点。根据满二叉树定理，新添加的树叶数目等于T结点个数加1。而每个新添加的树叶对应T的一个空子树。因此T中空子树数目等于T中结点数加1。北京大学信息学院张铭编写©版权所有，转载或翻印必究Page124.2二叉树的性质3.任何一颗二叉树，度为0的结点比度为2的结点多一个证明：设有n个结点的二叉树的度为0、1、2的结点数分别为=n，n，

7、n，则012n=n+n+n(公式4.3)012设边数为e。因为除根以外，每个结点都有一条边进入，故n=e+1。由于这些边是有度为1和2的的结点射出的，因此e=n+2·n，于是12n=e+1=n+2·n+1（公式4.4）12因此由公式（1）（2）得n+n+n=n+2·n+101212即n=n+102北京大学信息学院张铭编写©版权所有，转载或翻印必究Page134.2二叉树的性质i¢4.二叉树的第i层（根为第0层，i≥1）最多有2个结点¢5.高度为k(深度为k-1。只有一个根结点的二叉树的高度为1，深度为0)的二叉树至多有2k-1个结

8、点¢6.有n个结点（n>0）的完全二叉树的高度为⎡log(n+1)⎤(深度为⎡log(n+1)⎤-1)22北京大学信息学院张铭编写©版权所有，转载或翻印必究Page144.3二叉树的抽象数据类型¢逻辑结构+运算：¢针对整棵树¢初始化二叉树¢合并两棵