二叉树的图形化显示最主要的一步就是计算每个结点的位置。得到位置后，可以使用命令行或者图形界面来显示。应该说使用图形界面可以在任意坐标处画图，实现起来要比命令行简单很多。本文介绍如何计算结点的横纵坐标，并分别给出命令行和基于QT的图形界面显示的C++代码。
本文中的二叉树数据结构代码见 常用数据结构C++实现(3)：二叉树和二叉搜索树 | 雅乐网
福利：本文附带Qt图形显示二叉树、平衡搜索树和红黑树的源代码
计算结点位置
观察一棵二叉树
从水平方向来看，从左到右的结点是按照中序遍历的次序。
从垂直方向来看，结点的深度就是该结点到树根的距离。
计算深度
先通过parent指针一直遍历到树根，求出根节点深度。然后孩子节点深度就等于它的父节点深度+1 ，这要求更新结点的顺序要按照深度来进行，而层次遍历正好符合这一要求。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 |
//更新x到root的距离 用于display template <typename T> void BinTree<T>::updateDistanceToRoot(BinNodePosi(T) x) { if (!x) return; int i = 0; BinNodePosi(T) p = x; while (p != NULL) { p = p->parent; ++i; } x->distance_to_root = i-1; Queue<BinNodePosi(T)> q; q.enqueue(x); while (!q.empty()) { x = q.dequeue(); if (x && x->parent) x->distance_to_root = x->parent->distance_to_root + 1; if (x->lchild) q.enqueue(x->lchild); if (x->rchild) q.enqueue(x->rchild); } } |
计算水平位置
可以稍微改写中序遍历，设置变量记录结点的访问次序，得到每个结点的相对次序。
在此前的二叉树中有一个现成的succ()接口，用来返回中序遍历意义下的下一个结点，利用这个接口，可以方便的计算每个结点的水平位置：
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 |
template <typename T> void BinTree<T>::calculatePosition() { //计算垂直位置 updateDistanceToRoot(_root); //计算水平位置 int count = 0; BinNodePosi(T) x = _root; //找到中序遍历的第一个结点 while (x->lchild != NULL) x = x->lchild; //按照中序遍历的次序记录结点访问次序 while (x != NULL) { x->horizontal_position = ++count; x->horizontal_position *= 4; //水平位置放缩4倍 命令行显示时结点之间的空隙4个字符 x = x->succ(); } } |
使用QT图形化显示二叉树
由于有些小伙伴要源代码，Qt部分的完整代码下载：包含显示搜索树、平衡树和红黑树三个图形界面源代码
使用QT中的paintevent来画图，首先从QWidget继承一个类，然后重写paintEvent函数。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 |
#ifndef DRAW_H #define DRAW_H #include "BST.h" #include <QWidget> #include <QPaintEvent> class DrawWidget : public QWidget { Q_OBJECT public: BST<int> *bst; DrawWidget(QWidget *p = 0); void paintEvent(QPaintEvent *); }; #endif // DRAW_H |
下面是画图函数
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 |
#include "draw.h" #include <QPainter> DrawWidget::DrawWidget(QWidget *p):QWidget(p) { bst = new BST<int>; } void DrawWidget::paintEvent(QPaintEvent *) { QPainter painter(this); if (!bst->empty()) { bst->display(); //调用命令行显示 从而计算结点位置 //层次遍历第一遍 画线 Queue<BinNodePosi(int)> q; BinNodePosi(int) x = bst->root(); q.enqueue(x); while (!q.empty()) { x = q.dequeue(); if (x) { if (x && x->parent) painter.drawLine(30*x->horizontal_position+30, 30+100 * x->distance_to_root, 30*x->parent->horizontal_position+30, 30+100 * x->parent->distance_to_root); } if (x->lchild) q.enqueue(x->lchild); if (x->rchild) q.enqueue(x->rchild); } //层次遍历第二遍 画结点 x = bst->root(); q.enqueue(x); while (!q.empty()) { x = q.dequeue(); if (x) { painter.setBrush(Qt::yellow); painter.drawEllipse(30*x->horizontal_position, 100 * x->distance_to_root, 60, 60); painter.drawText(30*x->horizontal_position+20, 100 * x->distance_to_root+30, QString::number(x->data)); } if (x->lchild) q.enqueue(x->lchild); if (x->rchild) q.enqueue(x->rchild); } } } |
在主窗口界面，实现插入和删除，之后调用update来更新。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
void MainWindow::insertclicked() { QString num = elem->text(); int n = num.toInt(); d->bst->insert(n); d->update(); } void MainWindow::deleteclicked() { QString num = todelete->text(); int n = num.toInt(); d->bst->remove(n); d->update(); } |
最终运行结果如下图
二叉树：
红黑树：
使用命令行显示二叉树
命令行的输出必须从左到右，从上到下，这带来了不必要的繁琐。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 |
template <typename T> void BinTree<T>::display() { calculatePosition(); Queue<BinNodePosi(T)> q; BinNodePosi(T) x = _root; q.enqueue(x); int nowheight = 0; int lastheight = 0; int levelcount = 0; int i = 0; while (!q.empty()) { x = q.dequeue(); long long int tmpposi; if (x) { nowheight = x->distance_to_root; if (nowheight != lastheight) { lastheight = nowheight; cout << endl; levelcount = 0; } for(i = levelcount; i < posilchild(x); ++i) { printf(" "); } int firstprint = 1; for (; i < x->horizontal_position; ++i) { if (firstprint) { printf("_"); firstprint = 0; } else printf("_"); } tmpposi = cout.tellp(); cout << x->data; long long int tellpppp = cout.tellp() - tmpposi; levelcount += (int) (tellpppp); levelcount += x->horizontal_position - levelcount; for (i = levelcount; i < posirchild(x); ++i) { if (i == posirchild(x) - 1) printf("_"); else printf("_"); } levelcount = i; } if (x && x->lchild) q.enqueue(x->lchild); if (x && x->rchild) q.enqueue(x->rchild); } cout << endl << endl; } |
运行结果如图
支付宝打赏 
微信打赏
想问一下博主，QT部分代码如果构造的是一个对称的二叉树的画，在删除根节点的时候会出现段错误，要怎么修改
感谢指出，因为二叉搜索树的代码里 remove 结点的函数有一点bug![[泪]](http://tb2.bdstatic.com/tb/editor/images/face/i_f09.png)
晚上改一下
那个，还想请问下博主，我想在界面加一个按钮，把这个二叉搜索树转变成平衡树，要怎么修改(┌・ω・)┌✧
Qt只是显示二叉树，二叉树具体什么样子是它自己的结构决定的。我的代码里需要把draw.h里面用到的BST数据结构BST改成AVL，源代码： http://7d9rd6.com1.z0.glb.clouddn.com/wp-content/uploads/2016/01/PaintBinTree.zip
改好了删除根节点错误的bug，里面有三个程序，对应的树分别是普通的二叉搜索树，平衡搜索树和红黑树
哇，真的非常感谢博主，晚上回去好好消化代码ლ(́◉◞౪◟◉‵ლ)感谢！！！
请问有QT部分的完整代码么？
发到你邮箱了
大哥 QT有没有源代码，我想学习一下
更新了地址 修复了一个删除结点的bug
http://7d9rd6.com1.z0.glb.clouddn.com/wp-content/uploads/2016/01/PaintBinTree.zip