0

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

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，我将非常感激。
感谢你们。

4

3 回答 3

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 不够熟悉，无法说出如何最好地用该语言编写字符串。

于 2016-09-23T01:01:10.020 回答
0
  1. 您将需要水平顺序遍历您的树。
  2. 选择节点长度和空间长度。
  3. 获取相对于每个级别的树的基本宽度，即.node_length * nodes_count + space_length * spaces_count*
  4. 找出分支、间距、缩进和计算的基础宽度之间的关系。

GitHub 上的代码： YoussefRaafatNasry/bst-ascii-visualization

                                             07                     
                                             /\                     
                                            /  \                    
                                           /    \                   
                                          /      \                  
                                         /        \                 
                                        /          \                
                                       /            \               
                                      /              \              
                                     /                \             
                                    /                  \            
                                   /                    \           
                                 03                      11         
                                 /\                      /\         
                                /  \                    /  \        
                               /    \                  /    \       
                              /      \                /      \      
                             /        \              /        \     
                           01          05          09          13   
                           /\          /\          /\          /\   
                          /  \        /  \        /  \        /  \  
                        00    02    04    06    08    10    12    14
于 2019-07-19T14:30:29.870 回答
0

根据 Mr.Jim Mischel 在 C# 中的示例代码，我在 Node 类中添加了以下函数：

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

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

于 2016-09-23T08:58:53.300 回答