空的二进制搜索树有效吗?

是的,是的。

当然,空树究竟是什么取决于您的实现,以及“有效”一词的含义,但一般来说,我会对这两个问题说“是”。空树表示您所涉及的一组实体为空的情况,而单个节点表示包含一个实体的情况。

没有子节点的单个节点当然是有效的,并且根据 Binary Tree Structure :

(可变)二叉树,bitree,can 处于空状态或非空状态 状态:

• 当它为空时,它不包含任何数据。
• 当它不为空时,它包含一个名为根元素的数据对象,以及两个不同的位树对象,分别称为左子树和右子树。

为了完整性,这 Wikipedia entry 是对术语等的非常有用的总结。

空树(空)是否有效?

如果树是空的,就没有树。因此,有效性问题没有出现。

没有子节点的根节点是否有效?

对。这是一个只有一个元素的三通。

我觉得你把苹果和橙子混在一起了:

1. null 在某些编程语言中是一个值,它与数据结构实现的具体表示形式有关
2. “空”是我们称之为“二进制搜索树”的抽象数据结构的属性。

现在,一棵树是一个有序的集合:没有更多,没有更少。当然,一套可以是空的!这意味着,在你的 实施 ,类似于:

MyTree tree = null

表示一棵空树?嗯,这取决于你的型号。 例如,您可以认为一个空子树应该由一个没有值的节点表示,并且对leafs的引用无效:在该模型中, 无效的 从逻辑的角度看,指针毫无意义。但这只是 一 接近!基于Sentinel的方法是一种编程的乐趣,但它的内存是可扩展的:然后您可以用空节点建模。在这种情况下,A 无效的 指针可以是空树。

二叉树可以递归定义为:

A single node with either no children, or with two children - 
each of which is a binary tree.

是的,这两个条件都是正确的。 对于二叉树,每个节点可以有零、一或两个子节点。 如果一个树只有一个根节点而没有其他节点,那么它被称为空树。