时间戳

首页 > 解决方案 > 如何在python中打印二叉搜索树？

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

问题描述

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

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)

标签： pythondata-structures

解决方案

您的实现存在一些问题：

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

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

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

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

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

    def insert_after(self, value):
        if value < self.value:
            if self.left:
                self.left.insert_after(value)
            else:
                self.left = Node(value)
        elif value > self.value:
            if self.right:
                self.right.insert_after(value)
            else:
                self.right = Node(value)
        else:
            raise ValueError("this tree doesn't accept duplicates")

    def __repr__(self):
        lines = []
        if self.right:
            found = False
            for line in repr(self.right).split("\n"):
                if line[0] != " ":
                    found = True
                    line = " ┌─" + line
                elif found:
                    line = " | " + line
                else:
                    line = "   " + line
                lines.append(line)
        lines.append(str(self.value))
        if self.left:
            found = False
            for line in repr(self.left).split("\n"):
                if line[0] != " ":
                    found = True
                    line = " └─" + line
                elif found:
                    line = "   " + line
                else:
                    line = " | " + line
                lines.append(line)
        return "\n".join(lines)


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

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

    def __repr__(self):
        return repr(self.root)

bst = Binary_search_tree()
bst.insert(4)
bst.insert(2)
bst.insert(8)
bst.insert(3)
bst.insert(5)
bst.insert(7)
bst.insert(10)

print(str(bst))

推荐阅读