Основанная на указателе реализация BST в Python - PullRequest
Новая
       6

Основанная на указателе реализация BST в Python

0 голосов
/ 07 апреля 2019

У меня проблемы с пониманием кода, предоставленного моим учебником для реализации BST в Python.Я знаю, что есть гораздо более простые способы сделать это, но экзаменационные вопросы основаны на подходе, использованном в приведенном ниже коде, который эмулирует использование указателей.

Одна вещь, которая меня беспокоит, это то, что в связанном списке напо крайней мере, для вставки нет необходимости использовать «метод червячного преобразования предыдущего узла / текущего узла», поэтому я скептически отношусь к необходимости строк типа 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
...