二叉树算法

发布网友

我来回答

1个回答

热心网友

二叉树是没有度为1的结点。
完全二叉树定义:
若设二叉树的高度为h,除第
h
层外,其它各层
(1~h-1)
的结点数都达到最大个数,第
h
层从右向左连续缺若干结点,这就是完全二叉树。
完全二叉树叶子结点的算法:
如果一棵具有n个结点的深度为k的二叉树,它的每一个结点都与深度为k的满二叉树中编号为1~n的结点一一对应,这棵二叉树称为完全二叉树。
可以根据公式进行推导,假设n0是度为0的结点总数(即叶子结点数),n1是度为1的结点总数,n2是度为2的结点总数,由二叉树的性质可知:n0=n2+1,则n=
n0+n1+n2(其中n为完全二叉树的结点总数),由上述公式把n2消去得:n=
2n0+n1-1,由于完全二叉树中度为1的结点数只有两种可能0或1,由此得到n0=(n+1)/2或n0=n/2,合并成一个公式:n0=(n+1)/2
,就可根据完全二叉树的结点总数计算出叶子结点数。
因此叶子结点数是(839+1)/2=420

声明声明:本网页内容为用户发布,旨在传播知识,不代表本网认同其观点,若有侵权等问题请及时与本网联系,我们将在第一时间删除处理。E-MAIL:11247931@qq.com