0

我在 Python 中实现了创建二叉搜索树的函数。它目前按顺序显示节点，现在我正试图让它按preorder显示。

我根据我的笔记创建了inorder函数，但我不知道如何让预购正常工作。现在它显示最左边的节点，但我无法让它回溯到正确的节点。我将发布带有示例值的代码。任何让我走上正轨的提示将不胜感激。谢谢！

我放了我所有的代码，只放了 Preorder 功能代码。

完整的 Python 代码：

####
#
# Binary Search Tree
#
########

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

    def insert(self,data):
        if(data < self.data):
            if(self.left is None):
                self.left = Node(data)
            else:
                self.left.insert(data)
        elif(data > self.data):
            if(self.right is None):
                self.right = Node(data)
            else:
                self.right.insert(data)


    #lookup node containing data
    #data to lookup and parent nodes parent
    #returns node and its parent if found, otherwise none
    def lookup(self,data,parent=None):
        if(data < self.data):
            if(self.left is None):
                return None, None
            return self.left.lookup(data,self)
        elif(data > self.data):
            if(self.right is None):
                return None, None
            return self.right.lookup(data,self)
        else:
            return self,parent


    #return the number of children (either 0,1,or 2)
    def childrenCount(self):
        children = 0
        if(self.left):
            children += 1
        if(self.right):
            children += 1
        return children

    #delete the node containing data
    #data node content to be deleted
    def delete(self,data):
        node, parent = self.lookup(data)
        if(node is not None):
            childrenCount = node.childrenCount()
        if(childrenCount == 0):
            if(parent):
                if(parent.left is node):
                    parent.left = None
                else:
                    parent.right = None
            del node
        elif(childrenCount == 1):
            if(node.left):
                n = node.left
            else:
                n = node.right
            if(parent):
                if(parent.left is node):
                    parent.left = n
                else:
                    parent.right = n
            del node
        else:
            parent = node
            nextNode = node.right
            while(nextNode.left):
                parent = nextNode
                nextNode = nextNode.left
            node.data = nextNode.data
            if(parent.left == nextNode):
                parent.left = nextNode.right
            else:
                parent.right = nextNode.right

    #display the tree via inorder
    def displayInorder(self):
        global dspList2
        if(self.left):
            self.left.displayInorder()
        dspList2.append(self.data)
        if(self.right):
            self.right.displayInorder()

    def preOrder(self):
        global dspList
#        dspList.append(self.data)
        if(self.left):
            print("Left.. appending",self.data)
            dspList.append(self.data)
            self.left.preOrder()
        if (self.right is None):
            print("No right.. append",self.data)
            dspList.append(self.data)
            

        

dspList = []
dspList2 = []
def main():
    global dspList2
    global dspList
    root = Node(8)
    root.insert(3)
    root.insert(10)
    root.insert(1)
    root.insert(6)
    root.insert(4)
    root.insert(7)
    root.insert(14)
    root.insert(13)
    node,parent = root.lookup(6)


    root.preOrder()
    root.displayInorder()
    print("Inorder:",dspList2)
    print("Preorder:",dspList)

main()

预购功能：

    def preOrder(self):
        global dspList
#        dspList.append(self.data)
        if(self.left):
            print("Left.. appending",self.data)
            dspList.append(self.data)
            self.left.preOrder()
        if (self.right is None):
            print("No right.. append",self.data)
            dspList.append(self.data)
4

1 回答 1

0

查看Wikipedia上对遍历的解释。您的解决方案非常简单，并且将解释清楚地转换为代码。Pre-order 与 in-order 的区别仅在于它在树中递归的顺序。除此之外，它同样简单明了。为使预购工作所需的代码更改同样应该是从按订单到预购的简单更改。下面的代码应该可以工作：

def inOrder(self):
    global dspList2
    if(self.left):
        self.left.inOrder()
    dspList2.append(self.data)
    if(self.right):
        self.right.inOrder()

def preOrder(self):
    global dspList
    dspList.append(self.data)
    if(self.left):
        self.left.preOrder()
    if (self.right):
        self.right.preOrder()

请注意，与其使用全局变量，不如将其委托给采用累加器的辅助方法会更安全、更好：

def inOrder(self):
    acc = []
    self.inOrderAcc(self, acc)
    return acc

def inOrderAcc(self, acc):
    if (self.left):
        self.left.inOrderAcc(acc)
    acc.append(self.data)
    if (self.right):
        self.right.inOrderAcc(acc)
于 2014-12-01T08:34:50.370 回答