栏目分类:
子分类:
返回
名师互学网用户登录
快速导航关闭
当前搜索
当前分类
子分类
实用工具
热门搜索
名师互学网 > IT > 面试经验 > 面试问答

完整的二叉树定义

面试问答 更新时间: 发布时间: IT归档 最新发布 模块sitemap 名妆网 法律咨询 聚返吧 英语巴士网 伯小乐 网商动力

完整的二叉树定义

  • 在参考了Wikipedia中的定义之后,我进入了 此页面。定义是从那里获取的,但已修改:

定义: 二叉树,其中所有级别(可能最深的级别)都被完全填充。在树的高度n处,所有节点都必须尽可能地向左移。

虽然下面有一个注释,

一个完整的二叉树在每个深度k <n处都有2k个节点,并且在2n和2 ^(n + 1)之间-总共有1个节点。

有时,定义会根据便利性而有所不同(对某些有用)。据我了解,该段落可能是一个变体,需要叶节点首先填充最深层的左侧(即,从左到右填充)。我通常发现的定义与上面的描述完全相同,但没有该段落。

  • 通常,对高度平衡树的定义就是您所描述的。换一种说法:

当且仅当对于每个节点,其两个子树的高度相差最多1时,树才是平衡的。

这个定义是从这里得到的。同样,有时可以使定义变得更灵活以服务于特定目的。例如,AVL树的定义说明

在AVL树中,任何节点的两个子树的高度最多相差一个

仍然,我记得曾经不得不重写算法,以便如果任何节点的两个子子树最多相差2,则该树将被认为是高度平衡的。请注意,您给出的定义是递归的,这对于二进制很常见树木。

  • 在子代数可变的树中,您将不能说它是完整的(任何父代都可以拥有想要的子代数)。尽管如此,它仍然可以应用于 n元树 (具有固定数量的
    n
    子级)。


转载请注明:文章转载自 www.mshxw.com
本文地址:https://www.mshxw.com/it/368492.html
我们一直用心在做
关于我们 文章归档 网站地图 联系我们

版权所有 (c)2021-2022 MSHXW.COM

ICP备案号:晋ICP备2021003244-6号