algorithmpython-3.xbinary-search-treeete3

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


I have developed a binary search tree structure and I want to add some function which can visualize the tree. The code below belongs to Binary Search Tree:

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()

you can test the code to see how it traverses the tree recursively:

bst = BST()

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

For the visualization, I have used ete library. In ete3 library if you use the code below:

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())

you will get an output like this:

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

As you can see in the code above if I could be able to create the variable tree_format out of the BST structure, then I would be able to have a visual representation of tree.
To do this,the program has to
1. Traverse the tree in RLV format.
2. during traversing, it has to use () , , and ;.
Can anyone help me to complete the code.
If anyone has any easier way for visualizing the BST, I would be really grateful to see.
Thank you guys.


Solution

  • I think a recursive traversal will be easiest. With a non-recursive solution you end up having to manage the stack yourself.

    Here's some code in C#, which you should be able to port to Python easily enough:

    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;
    }
    

    The only thing missing is the final semicolon. You can call it with:

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

    Given the tree that you posted, that outputs the expected format string.

    Note that I use string concatenation here, which is sub-optimal in C#. If this were a production program, I'd probably use a StringBuilder object to avoid concatenation. I'm not familiar enough with Python to say how best to compose strings in that language.