如何在Python中打印二叉搜索树？

Question

下面是一个二叉搜索树，它有一个根节点、一个左节点和一个右节点。该代码有效，但我想显示这个二叉搜索树，以便我可以看到层中的每个节点...这是代码...

class Node:
    def __init__(self,value):
        self.value = value
        self.left = None
        self.right = None

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

    def insert(self,value):
        if self.root==None:
            self.root=Node(value)
        else:
            self.insert_after_root(value)

    def insert_after_root(self, value):
        if value > self.root.value:
            self.root.left = Node(value)
        elif value < self.root.value:
            self.root.right = Node(value)

bst = Binary_search_tree()
bst.insert(4)
bst.insert_after_root(2)
bst.insert_after_root(8)

Answer 1

您的实施存在一些问题：

\n\n

\n

• 该树只能有 3 个节点，因为您永远不会创建根的孙子节点，而是始终将新节点设为根节点或其子节点之一

\n

• 左/右颠倒：您应该在左侧插入较小的值。

\n

• 在主程序代码中，您应该只使用insert方法，而不能使用insert_after_root.

\n

\n\n

这是对您的实现的修正，基于递归（在 上放置一个方法Node），以及一组用于生成字符串表示形式的附加方法，90\xc2\xb0 倾斜（根显示在左侧）。

\n\n

class Node:\n    def __init__(self,value):\n        self.value = value\n        self.left = None\n        self.right = None\n\n    def insert_after(self, value):\n        if value < self.value:\n            if self.left:\n                self.left.insert_after(value)\n            else:\n                self.left = Node(value)\n        elif value > self.value:\n            if self.right:\n                self.right.insert_after(value)\n            else:\n                self.right = Node(value)\n        else:\n            raise ValueError("this tree doesn\'t accept duplicates")\n\n    def __repr__(self):\n        lines = []\n        if self.right:\n            found = False\n            for line in repr(self.right).split("\\n"):\n                if line[0] != " ":\n                    found = True\n                    line = " \xe2\x94\x8c\xe2\x94\x80" + line\n                elif found:\n                    line = " | " + line\n                else:\n                    line = "   " + line\n                lines.append(line)\n        lines.append(str(self.value))\n        if self.left:\n            found = False\n            for line in repr(self.left).split("\\n"):\n                if line[0] != " ":\n                    found = True\n                    line = " \xe2\x94\x94\xe2\x94\x80" + line\n                elif found:\n                    line = "   " + line\n                else:\n                    line = " | " + line\n                lines.append(line)\n        return "\\n".join(lines)\n\n\nclass Binary_search_tree:\n    def __init__(self):\n        self.root=None\n\n    def insert(self,value):\n        if self.root==None:\n            self.root=Node(value)\n        else:\n            self.root.insert_after(value)\n\n    def __repr__(self):\n        return repr(self.root)\n\nbst = Binary_search_tree()\nbst.insert(4)\nbst.insert(2)\nbst.insert(8)\nbst.insert(3)\nbst.insert(5)\nbst.insert(7)\nbst.insert(10)\n\nprint(str(bst))\n

\n