Requirements
- Basic C++ programming skills
- Qt4 libraries
- Graphviz
Goal
We’re going to implement the Binary Tree algorithm in C++ using Qt4 Libraries. Instead of using the 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, decided to publish mine.
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.
Project file
QT += core gui
TARGET = List7E
TEMPLATE = app
SOURCES += main.cpp \
BST.cpp
HEADERS += \
BST.h
FORMS +=
CONFIG += console
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
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();
}
Main.cpp
#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();
}
Demo
Source are available here BST.tar.gz