在 Python 中打印 BST

Question

我已经在 Python 中制作了 BST，但打印时遇到问题。当我尝试像这样打印它时：tree.BSTinOrder(Node(4))，它只打印 4 及以下“None”。一般来说，我希望它被打印得“很好”，这样它就可以以某种方式绘制树，或者至少我可以看到哪个节点与其他节点相连。如果我想打印整棵树，我应该做某种循环吗？

我的代码：

class Node:
    def __init__(self,x):
        self.key = x
        self.left = None 
        self.right = None 
        self.p = None 

class BST:
    def __init__(self):
        self.root = None

    def BSTsearch(self,k):
        
        x = self.root
        while x!=None and x.key!=k:
            if k<x.key:
                x=x.left
            else:
                x=x.right
        return x 

    def BSTinsert(self, z):
     
        x = self.root
        y = None 
        while x != None:
            y=x
            if z.key<x.key:
                x=x.left
            else:
                x=x.right
        z.p=y
        if y==None: 
            self.root=z
        else:
            if z.key<y.key:
                y.left=z
            else:
                y.right=z

    def bstDelete(self, z):
       
        if z.left == None and z.right == None:
            if z == self.root:
                self.root = None
            else:
                if z == z.p.left:
                    z.p.left = None
                else:
                    z.p.right = None
        elif z.left != None and z.right != None:
            y = self.bstMinimum(z.right)
            z.key = y.key
            self.bstDelete(y)
        else:
            if z.left != None:
                z.left.p=z.p
                if z==self.root:
                    self.root=z.left
                else:
                    if z==z.p.left:
                        z.p.left=z.left
                    else:
                        z.p.right=z.left
            else:
                z.right.p=z.p
                if z==self.root:
                    self.root=z.right
                else:
                    if z==z.p.left:
                        z.p.left=z.left
                    else:
                        z.p.right=z.left

    def bstMinimum(self, x):

        while x.left != None:
            x = x.left
        return x

    def BSTinOrder(self, x):

        if x == None: return
        self.BSTinOrder(x.left)
        print(x.key)
        self.BSTinOrder(x.right)

tree = BST()
tree.BSTinsert(Node(5))
tree.BSTinsert(Node(3))
tree.BSTinsert(Node(7))
tree.BSTinsert(Node(2))
tree.BSTinsert(Node(4))
tree.BSTinsert(Node(9))
tree.BSTinsert(Node(8))

Answer 1

试试这个：

class Node:
    def __init__(self, x):
        self.key = x
        self.left = None
        self.right = None
        self.p = None


class BST:
    def __init__(self):
        self.root = None

    def BSTsearch(self, k):

        x = self.root
        while x != None and x.key != k:
            if k < x.key:
                x = x.left
            else:
                x = x.right
        return x

    def BSTinsert(self, z):

        x = self.root
        y = None
        while x != None:
            y = x
            if z.key < x.key:
                x = x.left
            else:
                x = x.right
        z.p = y
        if y == None:
            self.root = z
        else:
            if z.key < y.key:
                y.left = z
            else:
                y.right = z

    def bstDelete(self, z):

        if z.left == None and z.right == None:
            if z == self.root:
                self.root = None
            else:
                if z == z.p.left:
                    z.p.left = None
                else:
                    z.p.right = None
        elif z.left != None and z.right != None:
            y = self.bstMinimum(z.right)
            z.key = y.key
            self.bstDelete(y)
        else:
            if z.left != None:
                z.left.p = z.p
                if z == self.root:
                    self.root = z.left
                else:
                    if z == z.p.left:
                        z.p.left = z.left
                    else:
                        z.p.right = z.left
            else:
                z.right.p = z.p
                if z == self.root:
                    self.root = z.right
                else:
                    if z == z.p.left:
                        z.p.left = z.left
                    else:
                        z.p.right = z.left

    def bstMinimum(self, x):

        while x.left != None:
            x = x.left
        return x

    def BSTinOrder(self, x):

        if x == None: return
        self.BSTinOrder(x.left)
        print(x.key)
        self.BSTinOrder(x.right)

    def bstGetRoot(self):
        return self.root

tree = BST()
tree.BSTinsert(Node(5))
tree.BSTinsert(Node(3))
tree.BSTinsert(Node(7))
tree.BSTinsert(Node(2))
tree.BSTinsert(Node(4))
tree.BSTinsert(Node(9))
tree.BSTinsert(Node(8))

tree.BSTinOrder(tree.bstGetRoot())

输出：

我想你误解了如何遍历一棵树。你需要根。请注意我是如何添加一个方法来检索树的根，然后将其传递给 inode 遍历函数，它工作得很好。

在 Python 中打印 BST

Printing BST in Python

python

binary-search-tree