2

考虑 CLRS 书中完整 k-ary 树的以下定义：

定义：一棵完整的k-ary树是一棵k -ary树，其中所有叶子都具有相同的深度，并且所有内部节点的度数为k。（第 1179 页）

由于这个定义，我认为下一个二叉树是完整的

CLRS 完成二叉树

但是基于这个完整树的答案定义（完整二叉树，k叉树的特例），

一棵二叉树，其中每一层，除了可能是最深的，都被完全填满。在深度n处，即树的高度，所有节点都必须尽可能靠左。

这与 Grimaldi 的离散数学书（第 601 页）中出现的相同，我们认为下面的有根树是一棵完整的树

完成的二叉树

但这对于 CLRS 定义是不正确的，因为G离开它与其他定义不同。这两个定义中哪一个是最常用和最适合该案例的？

4

2 回答 2

1

这取决于用例。

您提到的答案所引用的参考资料以这种资格结尾：

一些作者称完美二叉树为“完整的”。

这确实是 CLRS 中的用法。所以这两个术语都很有用，但用法因参考而异。

这就是为什么数学论文通常以几页术语开头，即使有时看起来是多余的。

于 2016-05-05T00:38:21.390 回答
0

使用后一个定义通常很有用

一棵二叉树，其中每一层，除了可能是最深的，都被完全填满。在深度 n 处，即树的高度，所有节点必须尽可能靠左。

这主要是因为前一个定义的局限性在于你不能拥有一个完整的 k-ary 树

于 2016-05-04T23:08:12.177 回答