Python中基于指针的BST实现

Question

我很难理解我的教科书提供的用Python实现BST的代码。我知道有更简单的方法可以做到这一点，但考试问题是基于下面代码中使用的方法，它模拟使用指针

让我感到困扰的一件事是，至少在链表中，没有必要使用“前一个节点/当前节点英寸蠕动技术”进行插入，因此我怀疑是否需要像self.PreviousNodePointer = ThisNodePointer这样的行。我当然可能错了。我猜我们在处理有序结构的时候可能需要这个英寸的虫子？我对教科书解决方案的不信任是基于这样一个事实，即它确实包含许多已确认的错误

有人能告诉我，如果插入可以做得更简单，而仍然使用相同的基本方法吗

class TreeNode: # object for each node
    def __init__(self):
        self.Data = ""
        self.LeftPointer = -1
        self.RightPointer = -1

class BinaryTree:
    def __init__(self, n): # initialisation with list length n
        self.null = -1
        self.RootPointer = self.null
        self.FreePointer = 0
        self.Tree = []
        for i in range (0, n):
            self.Tree.append(TreeNode())
            self.Tree[i].LeftPointer = i + 1
        self.Tree[n-1].LeftPointer = self.null

    def display(self): # print a display in order of index positions
        print("{0:^5}|{1:^10}|{2:^10}|{3:^10}|".format("", "Left", "Data", "Right"))
        for i in range (0, len(self.Tree)):
            index = "[" + str(i) + "]"
            print("{0:^5}|{1:^10}|{2:^10}|{3:^10}|".format(index, self.Tree[i].LeftPointer, self.Tree[i].Data, self.Tree[i].RightPointer))
        print("RootPointer:", self.RootPointer)
        print("FreePointer:", self.FreePointer)

    def insert(self, item): # insert item, returns true if inserted and false if set full
        if self.FreePointer == self.null:
            return False # no room in list
        NewNodePointer = self.FreePointer
        # set free pointer to next position in "free list" if that is
        # the right term
        self.FreePointer = self.Tree[self.FreePointer].LeftPointer
        # Add data to node at free node pointer
        self.Tree[NewNodePointer].Data = item
        # Why do we need to set these to null?
        self.Tree[NewNodePointer].LeftPointer = self.null
        self.Tree[NewNodePointer].RightPointer = self.null
        #If this is the first node to be inserted into tree
        if self.RootPointer == self.null:
            self.RootPointer = NewNodePointer
        else:
            ThisNodePointer = self.RootPointer
            while ThisNodePointer != self.null:
                self.PreviousNodePointer = ThisNodePointer
                if self.Tree[ThisNodePointer].Data > item:
                    self.TurnedLeft = True
                    ThisNodePointer = self.Tree[ThisNodePointer].LeftPointer
                else:
                    self.TurnedLeft = False
                    ThisNodePointer = self.Tree[ThisNodePointer].RightPointer
            if self.TurnedLeft:
                self.Tree[self.PreviousNodePointer].LeftPointer = NewNodePointer
            else:
                self.Tree[self.PreviousNodePointer].RightPointer = NewNodePointer
        return True

    def find(self, item): # returns position of an item, -1 if not found
        ThisNodePointer = self.RootPointer
        while ThisNodePointer != self.null and self.Tree[ThisNodePointer].Data != item:
            if self.Tree[ThisNodePointer].Data > item:
                ThisNodePointer = self.Tree[ThisNodePointer].LeftPointer
            else:
                ThisNodePointer = self.Tree[ThisNodePointer].RightPointer
        return ThisNodePointer

#######################
##  Example commands ##
#######################

MyTree = BinaryTree(6) # Create a tree of length 6
MyTree.display() # display tree in a table
MyTree.insert(10) # insert number 10
MyTree.insert(40)
MyTree.insert(30)
MyTree.insert(50)
MyTree.insert(60)
MyTree.display()
print("Item found at position", MyTree.find(30)) # print the position of number 30