如何用Python构建二叉树

Question

我正试图构建一个二叉树，但在根目录中添加了两个节点。

我应该编写什么函数来启用向这两个节点添加节点？

我有以下代码：

class Btree:
        def __init__(self, root):
                self.key = root
                self.lc = None
                self.rc = None
        def insert_lc(self, newNode):
                if self.lc == None:
                        self.lc = Btree(newNode)
                else:
                        t = Btree(newNode)
                        t.lc = self.lc
                        self.lc = t
        def insert_rc(self, newNode):
                if self.rc == None:
                        self.rc = Btree(newNode)
                else:
                        t = Btree(newNode)
                        t.rc = self.rc
                        self.rc = t
        def get_rc(self):
                return self.rc
        def get_lc(self):
                return self.lc
        def set_Root(self, val):
                self.key = val
        def get_Root(self):
                return self.key
r = Btree(1)
r.insert_lc(2)
r.insert_rc(4)

我想我需要一个函数，这样我就可以将left child和right child添加到值为2和4的节点

Answer 1

首先，我不太明白为什么要将新节点的左（右）子节点分配给该新节点本身。如果您稍后尝试搜索树，这将给您带来一个无限循环。

t = Btree(newNode)
#The line below seems unnecessary
t.lc = self.lc
self.lc = t

其次，在Btree构造函数中，有一个名为root的参数，它似乎是对当前节点根的引用。但是，您将节点的键作为该参数传递，因此无法访问节点的根。我知道在您的情况下，这可能甚至是不必要的，但参数名称仍然很令人困惑。如果你想引用父节点，你应该在构造函数中添加另一个参数：

def __init__(self, root, key):
    self.root = root
    self.key = key
    self.lc = None
    self.rc = None

通过这种方式，您既有关键节点引用，也有父节点引用。您还需要修改insert_rc和insert_lc方法：

def insert_rc(self, newNode):
    if self.rc == None:
        #Parent node is the one the insert_rc method is called on,
        #so we pass self as the root parameter
        self.rc = Btree(self, newNode)
    else:
        t = Btree(self, newNode)
        self.rc = t
#Same with insert_lc

最后，为了回答您的初始问题：要向添加的节点添加子节点，您只需调用get_rc或get_lc，这两个节点都将返回Btree的实例，以便您可以向它们添加子节点：

r = Btree(1)
r.insert_lc(2)
r.insert_rc(4)
#Insert left child to the node with key=2
r.get_lc().insert_lc(3)
#Insert right child to the node with key=4
r.get_rc().insert_rc(5)