雅乐网

二叉树的图形化显示最主要的一步就是计算每个结点的位置。得到位置后，可以使用命令行或者图形界面来显示。应该说使用图形界面可以在任意坐标处画图，实现起来要比命令行简单很多。本文介绍如何计算结点的横纵坐标，并分别给出命令行和基于QT的图形界面显示的C++代码。

本文中的二叉树数据结构代码见 常用数据结构C++实现(3)：二叉树和二叉搜索树 | 雅乐网

福利：本文附带Qt图形显示二叉树、平衡搜索树和红黑树的源代码

计算结点位置

观察一棵二叉树

从水平方向来看，从左到右的结点是按照中序遍历的次序。

从垂直方向来看，结点的深度就是该结点到树根的距离。

计算深度

先通过parent指针一直遍历到树根，求出根节点深度。然后孩子节点深度就等于它的父节点深度+1 ，这要求更新结点的顺序要按照深度来进行，而层次遍历正好符合这一要求。

//更新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()接口，用来返回中序遍历意义下的下一个结点，利用这个接口，可以方便的计算每个结点的水平位置：

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部分的完整代码下载：包含显示搜索树、平衡树和红黑树三个图形界面源代码

PaintBinTree

使用QT中的paintevent来画图，首先从QWidget继承一个类，然后重写paintEvent函数。

#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

下面是画图函数

#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来更新。

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();
}

最终运行结果如下图

二叉树：

红黑树：

使用命令行显示二叉树

命令行的输出必须从左到右，从上到下，这带来了不必要的繁琐。

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;
}

运行结果如图