实现二叉树时必须有两个类(Node,Tree) 吗？

Question

这听起来可能很傻，但请相信我，我在网上搜索了各种文章，找不到合适的解释或根本没有解释，真的需要两个 classes 一个用于 Node 另一个用于树实现二叉树？对于 Instance ，让我们使用一个简单的 python 代码：

class Node():
    def __init__(self,data):
        self.data = data
        self.left = None
        self.right = None
        

class BinaryTree():
    def __init__(self):
        self.head = None

这基本上是我在许多在线文章中看到的，最近我开始研究 AlgoExpert 课程，其中有一个关于将二叉树作为输入并将目标值作为另一个输入并获得最接近的函数的问题值到树中的目标值和return它。

给出的代码片段：

 #This is the class of the input root. Do not edit it.
    class BinaryTree:
        def __init__(self, data):
            self.data = data
            self.left = None
            self.right = None

现在看到这个片段我完全糊涂了，我怎么能只用一个 class 呢？我试图在这里理解这个概念，这对某些人来说可能听起来很愚蠢，但我宁愿问这个问题也不愿后悔根本不问。感谢任何输入。

Answer 1

是的，您可以只使用一个 class 来实现一棵树，例如，您提供的第一个片段中的 Node class 就足够了。

也就是说，如果您只有一个 class，则必须始终保留一个引用根节点的对象，以便您可以访问树。

class BinaryTree（在第一个片段中）可以帮助做到这一点，但这不是必需的。

使用第二个代码段中的 BinaryTree 并声明树的示例代码：

class BinaryTree:
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None



def main():
    root = BinaryTree(1)
    root.left = BinaryTree(2)
    root.right = BinaryTree(3)



if __name__ == "__main__":
    main()

Answer 2

不，您只需要节点 class。然后通过根节点引用您的整个树。从数学上讲，你的树的任何子树也是一棵树，即使你只有一个节点，它也会同时是该子树的叶子和根。

如果您想更简单地查看 heaps，它们是通过数组实现的。

Answer 3

你可以只用一个 class 实现一棵树，但它的 API 比你用两个单独的树实现的要有限得多class是的。在许多情况下，拥有一个单独的容器对象会更有意义，并且单个 class 实现将需要其用户处理特殊情况。

例如，一棵空树很容易用两个单独的 class 表示。它将是 Tree class 的实例及其 head 引用，通常指向 Node 实例，而不是指向 None。所有 Tree 方法都知道如何处理这种情况，因此用户不需要做任何特殊的事情。

要表示只有一个 class 的空树，您只需引用 None，因为没有要指向的根节点。这可能很不方便，因为您将无法在其上调用任何 Tree 相关方法。任何尝试引用根节点的情况都需要有特殊的逻辑来处理空树情况。

但有时您不需要花哨的东西 API，只需一个非常基本的东西就可以满足您对数据结构的有限使用。在那种情况下，处理一个微不足道的特殊情况并没有那么大的负担。写一个额外的 class 可能会更麻烦。

实现二叉树时必须有两个类(Node,Tree) 吗？

Is it a mandatory to have two classes(Node,Tree) while implementing a binary tree?

python

binary-tree

class

object

data-structures

实现二叉树时必须有两个 类(Node,Tree) 吗？

Is it a mandatory to have two classes(Node,Tree) while implementing a binary tree?

python

binary-tree

class

object

data-structures

实现二叉树时必须有两个类(Node,Tree) 吗？