Есть ли способ иметь простую 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, чтобы сказать, как лучше составлять строки на этом языке.

Answer 2

В соответствии с примером кода 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 переменная, правильный результат будет достигнут.

Answer 3

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