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.
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.