第60课 - 二叉树的深层特性

时间:2021-04-17 03:59:31

1、二叉树的深层特性 

        性质1 

                在二叉树的第i层录多有2i-1上个结点。(i≧1

                    第一层最多有21-1 = 1个结点 

                    第二层最多有22-1 = 2个结点 

                    第三层最多有23-1= 4个结点 

                     ....... 

                    第60课 - 二叉树的深层特性

        性质2 

                高度为k的二叉树最多有2k-1个结点(k≧0) 

                    如果有一层,最多有1=21-1=1个结点 

                    如果有两层,最多有1+2=22-1=3个结点 

                    如果有三层,最多有1+2+4=23-1=7个结点 

                     ....... 


        性质3 

                对任何一棵二叉树,如果其叶结点有n0个,度为2的非叶结点有n2 

                个,则有n0= n2+1。 

                        证明:假设二叉树中度1的结点有n1个且总结点为n个,则: 

                                            n=n+ n1 + n2 

                        假设二叉树中连接父结点与子结点间的边为e条,则: 

                                            e = n1 + 2n= n - 1 

                        所以: 

                                             n= n2+1 


第60课 - 二叉树的深层特性


        性质4 

                具有n个结点的完全二叉树的高度为⌊log2n⌋+1。 (⌊X⌋表示 

                不大于X的最大整数) 

                        证明:假设这n个结点组成的完全二叉树高度为k 、则: 

                                                2k-1-1< n ≤  2- 1 

                        因为n为整数,所以: 

                                                2k-1 ≤ n < 2

                        取对数: 

                                                k-1 ≤ log2n < k 

                        因为k为整数,所以: 

                                                k = ⌊log2n⌋ + 1

    


        性质5 (这个只针对完全二叉树)

                一棵有n个结点的完全二叉树(高度为log2n⌋+1) ,按层次对 

                结点进行编号(从上到下,从左到右),对任意结点i有: 

                        如果i = 1 , 则结点i是二叉树的根 

                        如果i > 1 则其双亲结点力⌊i/2⌋ 

                        如果2i <= n , 则结点i的左孩子力2i 

                        如果2i > n , 则结点i无左孩子 

                        如果2i+1 <= n , 则结点i的右孩子力2i+l 

                        如果2i+1 > n , 则结点i无右孩子 

                    第60课 - 二叉树的深层特性



2、实战预告 

        To be continued…

        思考: 

                如何实现二叉树的存储结构? 

                如何实现二叉树对应的 数据类型?