第59课 - 树到二叉树的转换

1、树到二叉树的转换 

        讨论中。。。 

            

        通用树结构的回顾 

             - 双亲孩子表示法 

                    每个结点都有一个指向其双亲的指针 

                    每个结点都有若干个指向其孩子的指针 

        

        另一种树结构模型 

            －孩子兄弟表示法 

                    每个结点都有一个指向其第一个孩子的指针 

                    每个结点都有一个指向其第一个右兄弟的指针

        

        孩子兄弟表示法的特点 

                1. 能够表示任意的树形结构 

                2. 每个结点包含一个数据成员和两个指针成员 

                3. 孩子结点指针和兄弟结点指针构成了“树杈” 

        二叉树的定义 

            －二叉树是由n(n>=0)个结点组成的有限集合，该集合或者为 

                空，或者是由一个根结点加上两棵分别称为左子树和右子树 

                的、互不相交的二叉树组成。 

                    

        二叉树的5种形态 

    

        特殊的二叉树 

            －满二叉树(Full Binary Tree) 

                    如果二叉树中所有分支结点的度数都为2, 且叶子结点都在同 

                    一层次上，则称这类二叉树为满二叉树。 

            －完全二叉树(Complete Binary Tree) 

                    如果一棵具有n个结点的高度为k的二叉树，它的每一个结点 

                    都与高度为k的满二叉树中编号为1一n的结点一一对应， 

                    则称这棵二叉树为完全二叉树。 （从上到下从左到右编号）

        完全二叉树的特性 

             - 同样结点数的二叉树，完全二叉树的高度最小 

            －完全二叉树的叶结点仅出现在最下面两层 

                    最底层的叶结点一定出现在左边 

                    倒数第二层的叶结点一定出现在右边 

                    完全二叉树中度为1的结点只有左孩子

                

                    满二叉树是完全二叉树，反过来看完全二叉树是还未形成的满二叉树

 2、小结 

            通用树结构采用了双亲结点表示法进行描述 

            孩子兄弟表示法有能力描述任意类型的树结构 

            孩子兄弟表示法能够将通用树转化为二叉树 

            二叉树是最多只有两个孩子的树