有没有什么办法可以让二叉搜索树有简单的ascii可视化？

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 

正如你可以在上面的代码中看到，如果我能能够创建变量tree_format出于BST结构，那么我将能够具有树的视觉表示。
要做到这一点，程序必须
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不熟悉如何最好地使用该语言来编写字符串。

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类：

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

Answer 2

根据C＃Mr.Jim米契尔示例代码，我在Node类添加下述功能通过使用bst.R_postorder（）的返回值作为输入来创建tree_format变量，可以实现正确的结果。