完全二叉树定义
完全二叉树定义
提问于 2012-08-11 14:17:18
我有一些关于二叉树的问题：
- 维基百科指出，当“一个完整的二叉树是一个二叉树，除可能的最后一个层次被完全填充，并且所有的节点都尽可能地留在最左边”时，二叉树就是完全的。最后一段“越左越远”意味着什么？
- 格式良好的二叉树如果(1)是空的，或者(2)它的左右子树是高度平衡的，而左边的树的高度在右树高度的1以内(取自如何确定二叉树是否平衡？ )，这是正确的还是1-值上有“抖动”？我在答案上读到，我认为右树和左树的高度也有4的差异因子。
- 完整的和高度平衡的定义只适用于二叉树还是其他树？
回答 2
Stack Overflow用户
回答已采纳
发布于 2012-08-11 20:59:03
- 依循维基百科的定义，我进入了此页。该定义取自于此，但作了修改： 定义：--一种二叉树，每个层次(可能是最深的)都被完全填充。在深度n，树的高度，所有的节点必须尽可能的左边。
不过，下面还有一个注释，
一个完整的二叉树在每层都有2k个节点，k
有时，定义因方便而异(对某物有用)。据我所知，该段落可能是一种变化，它要求叶节点首先填充最深层的左侧(即从左到右填充)。我通常发现的定义与上面所描述的完全一样，但没有这一段。
- 通常，高度平衡树的定义就是你所描述的。换言之： 一个树是平衡的当且仅当每个节点的两个子树的高度相差最多1。
这一定义取自这里。同样，有时定义会变得更加灵活，以达到特定的目的。例如，AVL树的定义是：
在AVL树中，任何节点的两个子子树的高度最多相差一个。
不过，我记得有一次我不得不重写一个算法，如果任何节点的两个子树最多相差2，树就会被认为是高度平衡的。请注意，您给出的定义是递归的，这对于二叉树来说是非常常见的。
- 在一个孩子数是可变的树中，你不能说它已经完成了(任何父母都可以有你想要的孩子的数量)。尽管如此，它仍然可以应用于n进制树(有固定数量的
n子)。
Stack Overflow用户
发布于 2012-08-11 22:16:41
完整的和高度平衡的定义只适用于二叉树还是其他树？
简短的回答:是的，它可以扩展到任意的n叉树.
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/11915437
复制相关文章
相似问题
腾讯云开发者
