#Binary Tree Visualization with Qt4

1. Requirements

  • Basic C++ programming skills
  • Qt4 libraries
  • Graphiz

2. Goal

We’re going to implement the Binary Tree algorithm in C++ using Qt4 Libraries. Instead of using console as an output we’ll draw the tree using Graphiz (as a raw PNG stream contained in QPixmap object).

I’m aware that this task is “yet another implementation” of Binary Tree algorithm but I’ve been looking for some decent piece of code recently and I couldn’t find any. So I’ve decided to publish mine.

3. Editor

I highly recommend “Qt Creator IDE” which seems to be the best editor for this task. But of course you can choose another, more suitable for you.

4. Project file

QT       += core gui

TARGET = List7E
TEMPLATE = app

SOURCES += main.cpp \
    BST.cpp

HEADERS  += \
    BST.h

FORMS    +=

CONFIG += console

5. BST.h – Header file

#ifndef BST_H
#define BST_H
#include <iostream>
#include <qgraphicsview>
#include <qtextstream>
#include <qprocess>

using namespace std;

struct Node{
    Node *p;
    int key;
    Node *left;
    Node *right;
};

class BST
{
    public:
        void init(QGraphicsScene* scene, QGraphicsView* view);
        void insert(int a);

        void preorderWalk();
        void postorderWalk();
        void inorderWalk();

        void deleteNode(int val);
        void deleteNode(Node* p);
        void show();

        int countNodes();
        int countLevels();
        int countLeftNodes();
        Node* findElem(int val);
    protected:
    private:
        int countNodes(Node* p);
        int countLevels(Node* p);
        int countLeftNodes(Node *p);

        void preorderWalk(Node* p);
        void postorderWalk(Node* p);
        void inorderWalk(Node* p);

        Node* findSuccessor(int val);

        QByteArray _prepareGraph();
        void _graphWalk(Node* p,  QTextStream* stream);
        Node* findElem(int val, Node* p);

        Node* _root;
        QGraphicsScene* _scene;
        QGraphicsView* _view;
};

#endif // BST_H

5. BST.cpp – method definitions

#include "BST.h"

void BST::init(QGraphicsScene* scene, QGraphicsView* view){
    this->_root = NULL;
    this->_scene = scene;
    this->_view = view;
}

void BST::insert(int a){
    Node* tmp = new Node;
    tmp->key = a;
    tmp->left = NULL;
    tmp->right = NULL;

    if(this->_root == NULL){
        tmp->p = NULL;
        this->_root = tmp;
    }else{
        Node* cElem = this->_root;
        Node* parent = NULL;

        while(cElem != NULL){
            parent = cElem;
            cElem = (a < cElem->key) ? cElem->left : cElem->right;
        }

        tmp->p = parent;
        if(a < parent->key){
            parent->left = tmp;
        }else{
            parent->right = tmp;
        }
    }
}

void BST::preorderWalk(Node* p) {
    if (p != NULL) {
       cout < < p->key < < " ";
       this->preorderWalk(p->left);
       this->preorderWalk(p->right);
    }
}

void BST::preorderWalk(){
    cout < < "Preorder walk: ";
    this->preorderWalk(this->_root);
    cout < < endl;
}

void BST::postorderWalk(Node* p) {
        if (p != NULL) {
           this->postorderWalk(p->left);
           this->postorderWalk(p->right);
           cout < < p->key < < " ";
        }
}

void BST::postorderWalk(){
    cout << "Postorder walk: ";
    this->postorderWalk(this->_root);
    cout < < endl;
}

void BST::inorderWalk(Node* p){
        if (p != NULL) {
           this->inorderWalk(p->left);
           cout < < p->key < < " ";
           this->inorderWalk(p->right);
        }
}

void BST::inorderWalk(){
    cout < < "Inorder walk: ";
    this->inorderWalk(this->_root);
    cout < < endl;
}

Node* BST::findElem(int val, Node* p){
    if(p != NULL){
        if(val == p->key) return p;

        if(val < p->key){
            return findElem(val, p->left);
        }else{
            return findElem(val, p->right);
        }
    }else{
        return NULL;
    }
}

Node* BST::findElem(int val){
    return this->findElem(val, this->_root);
}

Node* BST::findSuccessor(int val){
    Node* startNode = this->findElem(val);
    Node* parent = startNode;

    startNode = startNode->right;
    while(startNode != NULL && startNode->left != NULL){
        parent = startNode;
        startNode = startNode->left;
    }

    return startNode;
}

void BST::deleteNode(Node* p){
    Node *q = NULL;
    Node *r = NULL;

    if (p->left == NULL || p->right == NULL){
        q = p;
    }else{
        q = this->findSuccessor(p->key);
    }

    if (q->left != NULL){
        r = q->left;
    }else{
        r = q->right;
    }

    if (r != NULL){
        r->p = q->p;
    }

    if (q->p == NULL){
        this->_root = r;
    }else if (q == q->p->left){
        q->p->left = r;
    }else{
        q->p->right = r;
    }

    if (q != p){
        p->key = q->key;
    }
}

void BST::deleteNode(int val){
    this->deleteNode(this->findElem(val));
}

int BST::countLevels(Node* p){
        int h1 = 0, h2 = 0;

        if(p == NULL) return 0;

        if(p->left){
            h1 = countLevels(p->left);
        }

        if(p->right){
            h2 = countLevels(p->right);
        }

        return(max(h1,h2)+1);
}

int BST::countLevels(){
    return this->countLevels(this->_root);
}

int BST::countNodes(Node* p){
      if(p == NULL){
            return 0;
      }else{
            return (countNodes(p->left) + countNodes(p->right)+1);
      }
}

int BST::countNodes(){
    return this->countNodes(this->_root);
}

int BST::countLeftNodes(Node* p) {
    if(p == NULL){
          return 0;
    }else{
        return (countLeftNodes(p->left) + countLeftNodes(p->right)) + (p->left != NULL && p->right == NULL)? 1 : 0;
    }
}

int BST::countLeftNodes(){
    return this->countLeftNodes(this->_root);
}

void BST::_graphWalk(Node* p, QTextStream *stream) {
    if (p != NULL){
        *stream < < "\t\t" << "n" << p->key < < "[label=\"" << p->key < <"\"];" << endl;

        if(p->left != NULL){
            *stream < < "\t\tn" << p->key < < "--" << "n" << p->left->key < < ";" << endl;
            this->_graphWalk(p->left, stream);
        }else{
            *stream < < "\t\t" << "n" << p->key < < "leftNull" << "[style=\"filled\",label=\"NULL\"];" << endl;
            *stream << "\t\tn" << p->key < < "--" << "n" << p->key < < "leftNull" << endl;
        }

        if(p->right != NULL){
            *stream < < "\t\tn" << p->key < < "--" << "n" << p->right->key < < ";" << endl;
            this->_graphWalk(p->right, stream);
        }else{
            *stream < < "\t\t" << "n" << p->key < < "rightNull" << "[style=\"filled\",label=\"NULL\"];" << endl;
            *stream << "\t\tn" << p->key < < "--" << "n" << p->key < < "rightNull" << endl;
        }
    }
}

QByteArray BST::_prepareGraph(){
    QByteArray a = QByteArray();

    QTextStream stream(&a, QIODevice::ReadWrite);
    stream << "graph ""{" << endl;
    stream << "\tnode[fontsize=10,margin=0,width=\".4\", height=\".3\"];" << endl;
    stream << "\tsubgraph cluster17{" << endl;

    this->_graphWalk(this->_root, &stream);
    stream < < "\t}\n" << "}" << endl;
    stream.flush();

    return a;
}

void BST::show(){
    QProcess* p = new QProcess();
    QByteArray a = this->_prepareGraph();

    p->setProcessChannelMode(QProcess::MergedChannels);
    p->start("dot", QStringList() < < "-Tpng");
    p->write(a);

    QByteArray data;
    QPixmap pixmap = QPixmap();

    while(p->waitForReadyRead(100)){
        data.append(p->readAll());
    }

    pixmap.loadFromData(data);

    this->_scene->addPixmap(pixmap);
    this->_view->show();
}

6. Main.cpp

#include
#include "BST.h"

using namespace std;

int main(int argc, char **argv){
    QApplication app(argc, argv);
    QGraphicsScene scene;
    QGraphicsView view(&scene);

    view.setRenderHints(QPainter::SmoothPixmapTransform);

    BST* a = new BST();
    a->init(&scene, &view);

    a->insert(7);
    a->insert(6);
    a->insert(10);
    a->insert(3);
    a->insert(4);
    a->insert(5);
    a->insert(8);
    a->insert(12);
    a->insert(9);
    a->deleteNode(7);

    cout < < "Number of nodes which have only left child: " << a->countLeftNodes() < < endl;
    cout << "Tree height: " << a->countLevels() < < endl;
    cout << "Number of nodes: " << a->countNodes() < < endl;
    cout << "Find element: " << a->findElem(12) < < endl;     a->preorderWalk();
    a->inorderWalk();
    a->postorderWalk();

    a->show();

    return app.exec();
}

7. Demo

8. Downloads

Source code

12 Comments

  1. It’s already working! Just a question, can you explain what its happening in the code section below?

    p->setProcessChannelMode(QProcess::MergedChannels);
    p->start(“dot”, QStringList() <write(a);

    QByteArray data;
    QPixmap pixmap = QPixmap();

    while(p->waitForReadyRead(100)){
    data.append(p->readAll());
    }

    A’m assuming that there is the connection with graphviz, but I don’t figured out how it does, especifically. Thanks in advance.

    • Hi Jose,
      it’s quite simple.

      QProcess* p = new QProcess(); // create new process – in that case it’ll be graphiz process

      p->setProcessChannelMode(QProcess::MergedChannels) // merge stderr to stdout (in order to see potential errors)

      p->start(“dot”, QStringList() <write(a); // You put generated “graphiz” file (definition of your graph) to graphiz via standard input STDIN

      data.append(p->readAll());// Here, you are just waiting for the answer from buffer:)

      I hope that above explanation is quite clear 🙂 If you have any further questions, don’t hesitate to ask!

  2. Nice idea! I’m using this heavily for visualizing complex data structures. One improvement I recommend is to avoid hardcoding the timeout in the waitForReadyRead() call. Otherwise, for big graphs DOT doesn’t have enough time to generate them. It turns out, that just calling waitForReadyRead(-1) is not enough, because DOT is waiting until its input channel is closed. Thus, QProcess::closeWriteChannel() must be called additionally after writing the data. My implementation looks like that:

    QProcess proc;
    proc.setProcessChannelMode(QProcess::MergedChannels);
    proc.start(“dot”, QStringList() << "-Tpng");
    proc.waitForStarted();
    proc.write(strData);
    proc.waitForBytesWritten();
    proc.closeWriteChannel();

    QByteArray data;
    while (proc.waitForReadyRead(-1))
    data.append(proc.readAll());

  3. Hi. I’m new to Qt so I’m trying to run your program on Qt 5.5 but for some reason I get an error “Cannot open include file: ‘QGraphicsView’:No such file or directory” . I was searching for some library issues but everything seems fine. Could you help me?

Leave a Comment.