python - 二叉树 : How Do Class Instances Link?

Question

我试图理解二叉树，但这样做让我对类实例如何交互、每个实例如何链接到另一个实例感到困惑？

我的实现:

class Node(object):
    def __init__(self, key):
        self.key= key
        self.L  = None
        self.R  = None



class BinaryTree(object):
    def __init__(self):
        self.root = None

    def get_root(self):
        return self.root

    def insert(self, key):
        if self.get_root()==None:
            self.root = Node(key)
        else:
            self._insert(key, self.root)

    def _insert(self, key, node):
        if key < node.key:
            if node.L == None:
                node.L = key
            else: 
                self._insert(key, Node(node.L))
        if key > node.key:
            if node.R == None:
                node.R = key
            else: 
                self._insert(key, Node(node.R))

myTree= BinaryTree()

场景

假设我想插入 10，我执行 myTree.insert(10) ，这将实例化 Node() 的新实例，这很清楚我。

现在我想添加11，我希望它成为根节点的右节点；即它将被存储在根节点Node()的属性R中。

现在我不明白的部分来了。当我添加12时，它应该成为根节点右 child 的 child 。在我的代码中，这会创建一个 Node() 的新实例，其中 11 应该是 key ，12 应该是 R >。

所以我的问题有两个:Node() 的最后一个实例会发生什么？是否已删除，如果不删除如何访问？

或者是二叉树的结构，抽象为将每个Node()连接在一起，就像在图中一样

注意:此实现很大程度上源自此问题 How to Implement a Binary Tree? 的 djra 实现

Answer 1

使用 L 和 R Node 代替 int。您可以通过更改 _insert 函数的部分来实现此目的:

if node.L == None:
    node.L = key

对此:

if node.L == None:
    node.L = Node(key)

这一行也有问题:

self._insert(key, Node(node.L))

按照您现在的方式，无法访问 Node() 的最后一个引用，因为您的 _insert 函数将其插入到匿名构造的没有父节点的节点，因此不是树的一部分。传入插入函数的节点不是树中任何其他节点的 L 或 R，因此您实际上并没有使用此方法向树添加任何内容.

现在我们将 L 和 R 更改为 Node，您可以通过一种方法传入属于其一部分的节点树的插入功能:

self._insert(key, node.L)

现在，您将节点的左子节点传递到递归插入中，从外观上看，这就是您最初想要做的事情。

一旦您在代码中对 L 和 R 插入情况进行了这些更改，您就可以到达 Node() 的最后一个实例> 在你的

10
  \
   11
     \
      12

来自myTree.root.R.R的示例树。您可以通过 myTree.root.R.R.key 获取其 key ，该 key 等于 12。