有没有什么方法可以简单地将二叉搜索树可视化？

Question

我开发了一个二叉搜索树结构，我想添加一些可以可视化树的功能。下面的代码属于二叉搜索树：

class Node(object):
    def __init__(self, data):
        self.data = data
        self.leftChild = None
        self.rightChild = None

    def insert(self, data):
        if data < self.data:
            if not self.leftChild:
                self.leftChild = Node(data)
                return True
            else:
                self.leftChild.insert(data)
        else:
            if not self.rightChild:
               self.rightChild = Node(data)
               return True
            else:
               self.rightChild.insert(data)
    def inOrder(self):
        """
        Traversing the tree in inorder form (LVR).

        """
        if self:
            if self.leftChild:
               self.leftChild.inOrder()
            print(self.data)
            if self.rightChild:
                self.rightChild.inOrder()
class BST(object):
    def __init__(self):
        self.rootNode = None

    def insert(self, data):
        if not self.rootNode:
            self.rootNode = Node(data)
        else:
            self.rootNode.insert(data)
    def inOrder(self):
        self.rootNode.inOrder()

你可以测试代码看看它是如何递归遍历树的：

bst = BST()

bst.insert(12)
bst.insert(14)
bst.insert(8)
bst.insert(11)
bst.insert(7)
bst.inOrder()

对于可视化，我使用了 ete 库。在 ete3 库中，如果您使用以下代码：

from ete3 import Tree
# Loads a tree. Note that we use format 1 to read internal node names
tree_format = '(((J)H,K)D,((S,E)A,(T)B)C)F;'
t = Tree(tree_format, format=1)
print( t.get_ascii())

你会得到这样的输出：

      /H /-J
   /D|
  |   \-K
-F|
  |      /-S
  |   /A|
   \C|   \-E
     |
      \B /-T

正如您在上面的代码中看到的，如果我能够从 BST 结构中创建变量 tree_format，那么我将能够直观地表示树。
为此，程序必须
1.以RLV格式遍历树
2. 遍历时，必须使用 () , , 和 ;.
谁能帮我完成代码。
如果有人有更简单的方法来可视化 BST，我将不胜感激。
谢谢大家。

Answer 1

我认为递归遍历最简单。使用非递归解决方案，您最终必须自己管理堆栈。

下面是一些 C# 代码，您应该能够很容易地将其移植到 Python：

string Traverse(Node node)
{
    string rslt = "";
    bool hasRightNode = false;
    bool hasLeftNode = false;
    if (node.Right != null)
    {
        hasRightNode = true;
        rslt = rslt + "(";
        rslt = rslt + Traverse(node.Right);
    }
    if (node.Left != null)
    {
        hasLeftNode = true;
        if (hasRightNode)
        {
            rslt = rslt + ",";
        }
        else
        {
            rslt = rslt + "(";
        }
        rslt = rslt + Traverse(node.Left);
    }
    if (hasLeftNode || hasRightNode)
    {
        rslt = rslt + ")";
    }
    rslt = rslt + node.Value;
    return rslt;
}

唯一缺少的是最后的分号。你可以这样调用它：

string format = Traverse(root) + ";";

给定您发布的树，输出预期的格式字符串。

请注意，我在这里使用字符串连接，这在 C# 中不是最优的。如果这是一个生产程序，我可能会使用 StringBuilder 对象来避免串联。我对 Python 不够熟悉，无法说明如何最好地用该语言编写字符串。

Answer 2

根据C#中的Mr.JimMischel示例代码，我在节点class中添加了以下函数：

def R_postorder(self):
    ret = ''
    if self:
        hasRightChild = False
        hasLeftChild = False
        if self.rightChild:
            hasRightChild = True
            ret += '('
            ret += self.rightChild.RLV()

        if self.leftChild:
            hasLeftChild = True
            if hasRightChild:
                ret += ','
            else:
                ret += '('
            ret += self.leftChild.RLV()
        if hasRightChild or hasLeftChild:
            ret += ')'
        ret += str(self.data)
    return ret

而且我还将 R_postorder 添加到 BST class:

def R_postorder(self):
    ret = self.rootNode.RLV()
    ret += ';'
    return ret

通过使用 bst.R_postorder() 的返回值作为输入来创建 tree_format 变量，将实现正确的结果。

Answer 3

您将需要级别顺序遍历您的树。
选择节点长度和space长度。
获取树的 基础宽度 相对于每个级别即 node_length * nodes_count + space_length * spaces_count*.
找出分支、间距、缩进与计算出的基宽之间的关系。

代码 GitHub: YoussefRaafatNasry/bst-ascii-visualization

                                             07                     
                                             /\                     
                                            /  \                    
                                           /    \                   
                                          /      \                  
                                         /        \                 
                                        /          \                
                                       /            \               
                                      /              \              
                                     /                \             
                                    /                  \            
                                   /                    \           
                                 03                      11         
                                 /\                      /\         
                                /  \                    /  \        
                               /    \                  /    \       
                              /      \                /      \      
                             /        \              /        \     
                           01          05          09          13   
                           /\          /\          /\          /\   
                          /  \        /  \        /  \        /  \  
                        00    02    04    06    08    10    12    14

有没有什么方法可以简单地将二叉搜索树可视化？

Is there any way to have simple ascii visualization of binary search tree?

algorithm

python-3.x

binary-search-tree

ete3