binary-search-treevisualizationgraphvizgraph-visualization
How to generate binary tree dot file for Graphviz from C++
I have implemented a Binary Search Tree in C++ which support dynamically creating and deleting nodes. To visualize the tree, I firstly tried displaying edges with / and \. However, this gives really awful visualization, as the position of / and \ needs to be calculated precisely. The current figures are as follows:
So I found a tool called Graphviz. The raw language supported by Graphviz is dot language, which I am not familiar with.
I read the documentation and found the dot language easy to write and read, but I still want to use my C++ code to generate the tree as this contains much content such as inserting according to user's input.
Is there any chance to use some function to generate the dot file?
The code of my binary tree:
//BTNode.h
#include <iostream>
using namespace std;
template<class T>
struct BTNode{
BTNode(){
lChild = rChild = NULL;
}
BTNode(const T& x){
element = x;
lChild = rChild = NULL;
}
BTNode(const T& x, BTNode<T>* l, BTNode<T>* r){
element = x;
lChild = l;
rChild = r;
}
T element;
int digit, row;
BTNode<T>* lChild, *rChild;
};
//BSTree.h
#include"ResultCode.h"
#include "BTNode.h"
#include "seqqueue.h"
#include <math.h>
template <class T>
class BSTree
{
public:
BSTree(){ root = NULL; }
ResultCode SearchByRecursion(T& x)const;
ResultCode Insert(T& x);
ResultCode Remove(T& x);
void InOrder(void(*Visit)(T& x));
ResultCode SearchByIteration(T& x);
void GradeOrder(void(*Visit)(T &x), BTNode<T> *t, int height);
BTNode<T>* root;
void printSpace(int num);
int GetHeight();
int GetHeight(BTNode<T> *t);
int **A;
private:
ResultCode SearchByRecursion(BTNode<T> *p, T& x)const;
void InOrder(void(*Visit)(T& x), BTNode<T> *t);
};
template <class T>
ResultCode BSTree<T>::SearchByRecursion(T &x)const{
return SearchByRecursion(root, x);
}
template <class T>
ResultCode BSTree<T>::SearchByRecursion(BTNode<T> *p, T& x)const{
if (!p) return NotPresent;
else if (x < p->element) return SearchByRecursion(p->lChild, x);
else if (x > p->element) return SearchByRecursion(p->rChild, x);
else{
x = p->element;
return Success;
}
}
template <class T>
ResultCode BSTree<T>::SearchByIteration(T& x){
BTNode<T> *p = root;
while (p)
if (x < p->element) p = p->lChild;
else if (x > p->element) p = p->rChild;
else{
x = p->element;
return Success;
}
return NotPresent;
}
template<class T>
ResultCode BSTree<T>::Insert(T& x){
BTNode<T> *p = root, *q = NULL;
while (p){
q = p;
if (x < p->element) p = p->lChild;
else if (x > p->element) p = p->rChild;
else { x = p->element; return Duplicate; }
}
p = new BTNode<T>(x);
if (!root) root = p;
else if (x < q->element) q->lChild = p;
else q->rChild = p;
return Success;
}
template <class T>
ResultCode BSTree<T>::Remove(T& x){
BTNode<T> *c, *s, *r, *p = root, *q = NULL;
while (p && p->element != x){
q = p;
if (x < p->element) p = p->lChild;
else p = p->rChild;
}
if (!p) return NotPresent;
x = p->element;
if (p->lChild&&p->rChild)
{
s = p->rChild;
r = p;
while (s->lChild){
r = s; s = s->lChild;
}
p->element = s->element;
p = s; q = r;
}
if (p->lChild)
c = p->lChild;
else c = p->rChild;
if (p == root)
root = c;
else if (p == q->lChild)
q->lChild = c;
else q->rChild = c;
delete p;
return Success;
}
template <class T>
void BSTree<T>::InOrder(void(*Visit)(T &x)){
InOrder(Visit, root);
}
template <class T>
void BSTree<T>::InOrder(void(*Visit)(T &x), BTNode<T> *t){
if (t){
InOrder(Visit, t->lChild);
Visit(t->element);
InOrder(Visit, t->rChild);
}
}
template <class T>
void BSTree<T>::GradeOrder(void(*Visit)(T &x), BTNode<T> *t, int height)
{
A = new int*[height];
for (int i = 0; i < height; i++){
A[i] = new int[(int)pow(2, height) - 1];
}
for (int i = 0; i < height; i++)
for (int j = 0; j < (int)pow(2, height) - 1; j++){
A[i][j] = -1;
}
SeqQueue<BTNode<T>*> OrderQueue(10);
BTNode<T> * loc = t;
loc->row = 0;
loc->digit = 0;
if (loc){
OrderQueue.EnQueue(loc);
A[loc->row][loc->digit] = loc->element;
}
while (!OrderQueue.IsEmpty())
{
OrderQueue.Front(loc);
OrderQueue.DeQueue();
if (loc->lChild)
{
A[(loc->row) + 1][2 * (loc->digit)] = loc->lChild->element;
loc->lChild->row = (loc->row) + 1;
(loc->lChild->digit) = (loc->digit) * 2;
OrderQueue.EnQueue(loc->lChild);
}
if (loc->rChild)
{
A[(loc->row) + 1][2 * (loc->digit) + 1] = loc->rChild->element;
loc->rChild->row = (loc->row) + 1;
(loc->rChild->digit) = (loc->digit) * 2 + 1;
OrderQueue.EnQueue(loc->rChild);
}
}
cout << endl;
int total = (int)(pow(2, height)) - 1;
for (int i = 0; i < height; i++){
if (i != 0){
cout << endl;
}
int space1 = (total / (int)(pow(2, i + 1)));
int space2;
if (i == 0){
space2 = 0;
}
else{
space2 = (total - 2 * space1 - (int)pow(2, i)) / (int)(pow(2, i) - 1);
}
printSpace(space1);
for (int j = 0; j < (int)pow(2, i); j++){
if (A[i][j] != -1){
cout << A[i][j];
}
else{
cout << " ";
}
printSpace(space2);
}
printSpace(space1);
cout << endl;
}
}
template <class T>
void BSTree<T>::printSpace(int num){
for (int i = 0; i < num; i++){
cout << " ";
}
}
template<class T>
int BSTree<T>::GetHeight()
{
return GetHeight(root);
}
template<class T>
int BSTree<T>::GetHeight(BTNode<T> *t)
{
if (!t)return 0;
if ((!t->lChild) && (!t->rChild)) return 1;
int lHeight = GetHeight(t->lChild);
int rHeight = GetHeight(t->rChild);
return (lHeight > rHeight ? lHeight : rHeight) + 1;
}
template <class T>
void Visit(T& x){
cout << x << " ";
}
//main.cpp
#include <iostream>
#include "BSTree4.h"
#include<Windows.h>
int getDigit(int x);
int main(){
BSTree<int> bt;
int number;
// char choice;
cout << "Welcome to BSTree System, to begin with, you need to create a tree!(Press enter to continue...)" << endl;
getchar();
cout << "Please enter the size of the Binary Search Tree:";
cin >> number;
int *ToBeInserted = new int[number];
cout << "Enter the number of each Node(size:" << number << "):";
for (int i = 0; i < number; i++){
cin >> ToBeInserted[i];
}
cout << "OK,now the tree will be created!" << endl;
for (int i = 0; i < number; i++){
cout << "Inserting Node " << i;
for (int k = 0; k < 3; k++){
cout << ".";
//Sleep(200);
}
showResultCode(bt.Insert(ToBeInserted[i]));
//Sleep(500);
}
cout << "Done." << endl;
//Sleep(500);
int height = bt.GetHeight();
bt.GradeOrder(Visit, bt.root,height);
int a;
cout << "please enter the number to search:";
cin>>a;
showResultCode(bt.SearchByRecursion(a));
bt.GradeOrder(Visit, bt.root,height);
if (bt.SearchByRecursion(a) == 7){
cout << "Now delete the number" << "..." << endl;
showResultCode(bt.Remove(a));
bt.GetHeight();
cout << "Deleted!Now the tree is:" << endl;
bt.GradeOrder(Visit, bt.root, height);
bt.InOrder(Visit);
cout << endl;
}
return 0;
}
//resultcode.h
#include<iostream>
using namespace std;
enum ResultCode{ NoMemory, OutOfBounds, Underflow, Overflow, Failure,
NotPresent, Duplicate, Success };
void showResultCode(ResultCode result)
{
int r = (int)result;
switch (result)
{
case 0:cout << "NoMemory" << endl; break;
case 1:cout << "OutOfBounds" << endl; break;
case 2:cout << "Underflow" << endl; break;
case 3:cout << "Overflow" << endl; break;
case 4:cout << "Failure" << endl; break;
case 5:cout << "NotPresent" << endl; break;
case 6:cout << "Duplicate" << endl; break;
case 7:cout << "Success" << endl; break;
default: cout << "Exception occured:unknown resultcode" << endl;
}
}
Update: I have solved the problem myself, check the answer below.
Solution
The key elements in dot language file in this problem are nodes and edges. Basically the dot file structure for a binary tree would be like the following:
digraph g {
//all the nodes
node0[label="<f0>|<f1> value |<f2>"]
node1[label="<f0>|<f1> value |<f2>"]
node2[label="<f0>|<f1> value |<f2>"]
...
//all the edges
"node0":f2->"node4":f1;
"node0":f0->"node1":f1;
"node1":f0->"node2":f1;
"node1":f2->"node3":f1;
...
}
The following output of the dot file can be used to understand the structure:
Explanation for the dot file:
For the node part node0[label="<f0>|<f1> value |<f2>"] means the node called node0 has three parts: <f0> is the left part, <f1> is the middle part with a value, <f2> is the right part. This just corresponds to leftchild, value and rightchild in a binary node.
For the edges part, "node0":f2->"node4":f1; means the right part of node0(i.e.<f2>) points to the middle part of node4 (i.e. <f1>).
Therefore, the way to generate the dot file is simply through a traverse of a binary tree. Any method is fine. (BFS,DFS...) All we need is to add the code to write the nodes and corresponding edges into file when we do the traverse. I personally used BFS with level order traverse of a binary tree to implement which is shown below as a function called showTree.
void showTree(BSTree<int> &bst,int total,int *Inserted){
char filename[] = "D:\\a.gv"; // filename
ofstream fout(filename);
fout << "digraph g{" << endl;
fout << "node [shape = record,height = .1];" << endl;
SeqQueue<BTNode<int>*> OrderQueue(1000);
BTNode<int> * loc = bst.root;
loc->row = 0;
loc->digit = 0;
int num = 0;
if (loc){
OrderQueue.EnQueue(loc);
loc->ID = num++;
fout << " node" << loc->ID << "[label = \"<f0> |<f1>" << loc->element << "|<f2>\"];" << endl;
}
while (!OrderQueue.IsEmpty())
{
OrderQueue.Front(loc);
OrderQueue.DeQueue();
if (loc->lChild)
{
loc->lChild->row = (loc->row) + 1;
(loc->lChild->digit) = (loc->digit) * 2;
OrderQueue.EnQueue(loc->lChild);
loc->lChild ->ID= (num++);
fout << " node" << loc->lChild->ID << "[label = \"<f0> |<f1>" << loc->lChild->element << "|<f2>\"];" << endl;
//cout << loc->ID;
}
if (loc->rChild)
{
loc->rChild->row = (loc->row) + 1;
(loc->rChild->digit) = (loc->digit) * 2 + 1;
OrderQueue.EnQueue(loc->rChild);
loc->rChild->ID = (num++);
fout << " node" << loc->rChild->ID << "[label = \"<f0> |<f1>" << loc->rChild->element << "|<f2>\"];" << endl;
//cout << loc->ID;
}
}
//begin to draw!
SeqQueue<BTNode<int>*> OrderQueue2(1000);
BTNode<int> * loc2 = bst.root;
loc2->row = 0;
loc2->digit = 0;
if (loc2){
OrderQueue2.EnQueue(loc2);
}
while (!OrderQueue2.IsEmpty())
{
OrderQueue2.Front(loc2);
OrderQueue2.DeQueue();
if (loc2->lChild)
{
loc2->lChild->row = (loc2->row) + 1;
(loc2->lChild->digit) = (loc2->digit) * 2;
OrderQueue2.EnQueue(loc2->lChild);
cout << "\"node" << loc2->ID << "\":f0->\"node" << loc2->lChild->ID << "\":f1;" << endl;
cout << loc2->lChild->element << endl;
fout << "\"node" << loc2->ID << "\":f0->\"node" << loc2->lChild->ID << "\":f1;" << endl;
}
if (loc2->rChild)
{
loc2->rChild->row = (loc2->row) + 1;
(loc2->rChild->digit) = (loc2->digit) * 2 + 1;
OrderQueue2.EnQueue(loc2->rChild);
cout << "\"node" << loc2->ID << "\":f2->\"node" << loc2->rChild->ID << "\":f1;" << endl;
cout << loc2->rChild->element << endl;
fout << "\"node" << loc2->ID << "\":f2->\"node" << loc2->rChild->ID << "\":f1;" << endl;
}
}
fout << "}" << endl;
}
And the final output:
