我有两个关于二叉搜索树的问题，都是关于空树的。
- 空树（null）是否有效？
- 没有子节点的根节点是否有效？
问问题
13203 次
7 回答
11
是的，是的。
于 2009-05-01T10:18:01.140 回答
2
究竟什么是空树当然取决于您的实现，“有效”一词的含义也是如此，但总的来说，我会对这两个问题都说“是”。空树表示您感兴趣的实体集为空的情况，单个节点表示该集合包含一个实体的情况。
于 2009-05-01T10:17:51.827 回答
2
没有子节点的单个节点当然是有效的，并且根据二叉树结构：
（可变）二叉树 BiTree 可以处于空状态或非空状态：
- 当它为空时，它不包含任何数据。
- 当它不为空时，它包含一个称为根元素的数据对象，以及称为左子树和右子树的 2 个不同的 BiTree 对象。
为了完整起见，此Wikipedia 条目是对术语等的非常有用的总结。
于 2009-05-01T10:20:16.737 回答
1
空树（null）是否有效？
如果它是空的，就没有树。因此，有效性问题不会出现。
没有子节点的根节点是否有效？
是的。那是一个只有一个元素的 T 恤。
于 2009-05-01T10:19:51.107 回答
1
我认为您将苹果和橙子混合在一起：
null在某些编程语言中是一个值，它与数据结构实现的具体表示有关- “空”是我们称之为“二叉搜索树”的抽象数据结构的一个属性
现在，一棵树是一个有序集合：不多也不少。当然，集合可以是空的！这意味着，在您的实现中，类似于：
MyTree tree = null
代表一棵空树？好吧，这取决于您的型号。例如，您可以认为空子树应该由一个没有值的节点表示，并且对叶子的引用无效：在该模型中，null从逻辑角度来看，指针是没有意义的。但这只是一种方法！基于哨兵的方法是一种编程的乐趣，但它的内存扩展：然后你可以用空节点建模空节点。在这种情况下，null指针可以是一棵空树。
于 2009-05-01T10:36:34.387 回答
0
二叉树可以递归定义为：
A single node with either no children, or with two children -
each of which is a binary tree.
于 2012-11-30T20:06:48.253 回答
0
是的，这两个条件都成立。对于二叉树，每个节点可以有零个、一个或两个子节点。如果一棵树只有一个根节点而没有其他节点，则称为 NULL 树。
于 2012-12-02T12:30:46.160 回答