树到二叉树的转换(三十五)

        我们在之前学习了通用树的相关知识,那么通用树的结构实现相对来说比较复杂,有没有一种比较简单的树呢?我们在之前的通用树结构中使用的是双亲孩子表示法每个结点都有一个指向其双亲的指针,每个结点都有若干个指向其孩子的指针。结构如下图所示

创新互联公司主要从事网站建设、网站设计、网页设计、企业做网站、公司建网站等业务。立足成都服务桃江,10年网站建设经验,价格优惠、服务专业,欢迎来电咨询建站服务:18982081108

树到二叉树的转换(三十五)

        那么还有另一种树结构模型 -- 孩子兄弟表示法。每个结点都有一个指向其第一个孩子的指针,每个结点都有一个指向其第一个右兄弟的指针。结构如下图所示

树到二叉树的转换(三十五)

        孩子兄弟表示法的特点:1、能够表示任意的树形结构;2、每个结点包含一个数据成员和两个指针成员;3、孩子结点指针和兄弟结点指针构成了“树杈”。

        下来我们来看看二叉树的定义:二叉树是由 n ( n >= 0 ) 个结点组成的有限集合,该集合或者为空,或者是由一个根结点加上两颗分别称为左子树和右子树的、互不相交的二叉树组成。二叉树有以下 5 种形态

树到二叉树的转换(三十五)

        下来我们来看看两种特殊的二叉树:满二叉树(Full Binary Tree)和完全二叉树(Complete Binary Tree)

        1、满二叉树:如果二叉树中所有分支结点的度数都为 2,且叶子结点都在同一层次上,则称这类二叉树为满二叉树。

        2、完全二叉树:如果一颗具有 n 个结点的高度为 K 的二叉树,它的每一个结点都与高度 K 的满二叉树中编号为 1 -- n 的结点一一对应。则称这颗二叉树为完全二叉树(从上到下从左到右编号)。

        完全二叉树的相关特性:a> 同样结点数的二叉树,完全二叉树的高度最小;b> 完全二叉树的叶结点仅出现在最下面两层:最底层的叶结点一定出现在左边,倒数第二层的叶结点一定出现在右边,完全二叉树中度为 1 的结点只有左孩子。如下图所示

树到二叉树的转换(三十五)

        下来我们来看看二叉树的几个性质:

        1、在二叉树的第 i 层最多有 2i-1 个结点(i >= 1)。

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

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

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

            ......

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

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

            如果有二层,最多有 1 = 22-1 = 3 个结点;

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

            ......

        3、对任何一颗二叉树,如果其叶结点有 n0 个,度为 2 的非叶结点有 n2 个,则有 n0 = n2 + 1。

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

                假设二叉树中连接父结点与子结点间的边为 e 条,则:  e = n1 + 2n2 = n -1 ;

                所以:n0 = n2 + 1

        4、具有 n 个结点的完全二叉树的高度为[log2n] + 1。([X] 表示不大于 X 的最大整数)。

            证明:假设这 n 个结点组成的完全二叉树高度为 k,则: 2k-1-1 < n <= 2k-1;

                因为 n 为整数,所以: 2k-1 <= n < 2k

                取对数: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+1;如果 2i+1 > n,则结点 i 无右孩子;

树到二叉树的转换(三十五)

        通过对二叉树的学习总结如下:1、通用树结构采用了双亲结点表示法进行描述;2、孩子兄弟表示法有能力描述任意类型的树结构;3、孩子兄弟表示法能够将通用树转化为二叉树;4、二叉树是最多只有两个孩子的树。

新闻名称:树到二叉树的转换(三十五)
URL标题:https://www.cdcxhl.com/article2/jhsioc.html

成都网站建设公司_创新互联,为您提供云服务器网站设计网站制作响应式网站网站内链小程序开发

广告

声明:本网站发布的内容(图片、视频和文字)以用户投稿、用户转载内容为主,如果涉及侵权请尽快告知,我们将会在第一时间删除。文章观点不代表本网站立场,如需处理请联系客服。电话:028-86922220;邮箱:631063699@qq.com。内容未经允许不得转载,或转载时需注明来源: 创新互联

搜索引擎优化