如何显示二叉搜索树

Question

我正在尝试使用下面的 _displayRec 方法在 Python 中显示二叉搜索树。然而，当我用一个简单的例子测试它时，右侧的显示变得不平衡：

def display(self):
        print("Displaying tree:")
        print("----------------")
        lines, *_ = self._displayRec(self._root)
        for line in lines:
            print(line)
        print("----------------")

    def _displayRec(self, node):
        if node is None:
            line = "Empty"
            width = len(line)
            height = 1
            middle = width // 2
            return [line], width, height, middle
        else:
            key = str(node.getKey())
            value = str(node.getValue())
            label = f"{key} ({value})"
            left_lines, left_width, left_height, left_middle = self._displayRec(node.getLeft())
            right_lines, right_width, right_height, right_middle = self._displayRec(node.getRight())
            node_label = label
            node_label_width = len(node_label)
            first_line = (left_middle + 1) * " " + (left_width // 2) * "_" + node_label + (right_width // 2) * "_"
            second_line = left_middle * " " + "/" + (left_middle + node_label_width + right_middle) * " " + "\\" + (right_width - right_middle - 1) * " "
            if left_height < right_height:
                left_lines += [left_width * " "] * (right_height - left_height)
            elif right_height < left_height:
                right_lines += [right_width * " "] * (left_height - right_height)
            zipped_lines = zip(left_lines, right_lines)
            lines = [first_line, second_line] + [a + " " * (node_label_width + 1) + b for a, b in zipped_lines]
            width = left_width + node_label_width + right_width + 1
            height = max(left_height, right_height) + 2
            middle = width // 2
            return lines, width, height, middle

这是我用来测试显示方法的代码：

tree.insert(4, "four")
tree.insert(5, "five")
tree.insert(1, "one")
tree.insert(2, "two")
tree.insert(3, "three")
tree.display()

结果显示如下：

Inserted key 4 with value four
Inserted key 5 with value five
Inserted key 1 with value one
Inserted key 2 with value two
Inserted key 3 with value three
Displaying tree:
----------------
                        _______________________4 (four)_________
                       /                                        \
   __1 (one)________________            __5 (five)__
  /                         \                           /            \
Empty           __2 (two)__________         Empty         Empty
               /                   \
             Empty           __3 (three)__
                            /             \
                          Empty          Empty
----------------

如您所见，显示屏的右侧不平衡且难以阅读。我如何修改 _displayRec 方法来解决这个问题并使树显示平衡？

Answer 1

一个问题是你的线条大小不一。以下所有表达式应该是相同的值，但它们是不同的：

• len(first_line)

• len(second_line)

• left_width + node_label_width + 1 + right_width

我采取了一种略有不同的方法，其中返回的行包括一个带有向上边缘“/”的额外行，然后由调用者将其更改为反斜杠或将其丢弃（如果它是初始调用).

.center()

和

.rjust()

字符串方法的使用使一些表达式更容易。

这个版本不会有你遇到的问题：

    def display(self):
        print("Displaying tree:")
        print("----------------")
        lines = self._displayRec(self._root)[1:]
        for line in lines:
            print(line)
        print("----------------")

    def _displayRec(self, node):
        if node is None:
            return [
                "   /   ",
                " Empty "
            ]
        else:
            left_lines = self._displayRec(node.getLeft())
            right_lines = self._displayRec(node.getRight())
            right_lines[0] = right_lines[0].replace("/", "\\")

            label = f"{node.getKey()} ({node.getValue()})"
            label_width = len(label)
            label_offset = left_lines[0].index("/") + 1
            available_label_width = len(left_lines[0]) + right_lines[0].index("\\") - label_offset
            gap = max(0, label_width - available_label_width)
            available_label_width += gap
            width = len(left_lines[0]) + gap + len(right_lines[0])

            diff = len(left_lines) - len(right_lines) 
            if diff < 0:
                left_lines += [len(left_lines[0]) * " "] * (-diff)
            elif diff > 0:
                right_lines += [len(right_lines[0]) * " "] * diff
            return [
                (" " * label_offset + "/".center(available_label_width)).ljust(width),
                (" " * label_offset + label.center(available_label_width, "_")).ljust(width)
            ] + [a + " " * gap + b for a, b in zip(left_lines, right_lines)]