基于Qt的二叉树的绘制
1.这是一个典型的课程设计的题目。根据先序序列和中序序列建树之后在输出。为了避免代码的重复以及前篇一律，我在这个演示中只做99%，剩下关于图形的调整大家自己完成。首先给出项目的结构设计。
UI设计（这里大家就自由发挥了）
下面分别给出每个模块的代码以及修改的地方：
树类的定义以及实现：
#ifndef LINKEDBINARYTREE_H
#define LINKEDBINARYTREE_H
#include<c++/algorithm>
#include<c++/cstdio>
#include<string>
#include<c++/string>
#include<c++/vector>
#include<vector>
using namespace std;
struct BinTreeNode
{
char data;
BinTreeNode*leftChild, *rightChild;
BinTreeNode() { leftChild = NULL; rightChild = NULL; }
BinTreeNode(char x, BinTreeNode*l = NULL, BinTreeNode *r = NULL)
{
data = x;
leftChild = l;
rightChild = r;
}
};
class linkedBinaryTree
{
private:
BinTreeNode * root;
public:
linkedBinaryTree() {}
BinTreeNode* Rebuild(vector<char>pre, vector<char>mid);
void set(vector<char>pre, vector<char>mid)
{
root = this->Rebuild(pre, mid);
}
BinTreeNode*getRoot(){return root;}
int getHeight(){int num=this->getHeight(root);return num;}
int getHeight(BinTreeNode*subTree)
{
if (subTree == NULL)return 0;
int i = getHeight(subTree->leftChild);
int j = getHeight(subTree->rightChild);
return (i < j) ? j + 1 : i + 1;
}
};
#endif // LINKEDBINARYTREE_H
CPP文件：
#include"BinaryTree.h"
#include<c++/vector>
#include<c++/string>
#include<c++/algorithm>
using namespace std;
BinTreeNode* linkedBinaryTree::Rebuild(vector<char> pre, vector<char> mid)
{
int nodeSize = mid.size();
if (nodeSize == 0)
return NULL;
vector<char> leftPre, leftMid, rightPre, rightMid;
BinTreeNode* Root = new BinTreeNode(pre[0]);
int rootPos = 0;
for (int i = 0; i < nodeSize; i++)
{
if (mid[i] == pre[0])
{
rootPos = i;
break;
}
}
for (int i = 0; i < nodeSize; i++)
{
if (i < rootPos)
{
leftMid.push_back(mid[i]);
leftPre.push_back(pre[i + 1]);
}
else if (i > rootPos)
{
rightMid.push_back(mid[i]);
rightPre.push_back(pre[i]);
}
}
Root->leftChild = Rebuild(leftPre, leftMid);
Root->rightChild = Rebuild(rightPre, rightMid);
return Root;
}
paint.h:
#ifndef PAINT_H
#define PAINT_H
#include"BinaryTree.h"
#include <QWidget>
class Paint : public QWidget
{
Q_OBJECT
public:
explicit Paint(QWidget *parent = 0);
bool setInput(QString input1, QString input2);
protected:
void paintEvent(QPaintEvent *);
void draw(BinTreeNode *node, int x, int y, int angle, bool isLeft, int depth, QPainter *p);
BinTreeNode* test();
private:
linkedBinaryTree* myTree;
const int rootLengt=160;
const double PI=3.1415926;
};
#endif // PAINT_H
paint.cpp:
#include"paint.h"
#include <QPainter>
#include<stack>
#include<cstdio>
#include<QStack>
#include<QStack>
#include"BinaryTree.h"
#include<QPoint>
Paint::Paint(QWidget *parent) : QWidget(parent)
{
resize(600, 400);
myTree = new linkedBinaryTree();
}
bool Paint::setInput(QString input1, QString input2)
{
std::string s1 = input1.toStdString();
std::string s2 = input2.toStdString();
vector<char>v1;
vector<char>v2;
for(int i=0;i<s1.size();i++){v1.push_back(s1[i]);};
for(int i=0;i<s2.size();i++){v2.push_back(s2[i]);};
myTree->set(v1,v2);
return true;
}
BinTreeNode*Paint::test()
{
BinTreeNode*root=NULL;
root=new BinTreeNode('A');
root->leftChild=new BinTreeNode('B');
root->rightChild=new BinTreeNode('C');
root->leftChild->leftChild=new BinTreeNode('D');
root->leftChild->rightChild=new BinTreeNode('E');
root->rightChild->leftChild=new BinTreeNode('F');
root->rightChild->rightChild=new BinTreeNode('G');
return root;
}
void Paint::draw(BinTreeNode *node, int x, int y, int angle, bool isLeft, int depth, QPainter *p)
{
int leftAngle, rightAngle;
int dx,dy,nx,ny;
if (node==NULL)
return;
p->drawText(x,y,QChar(node->data));
if (node->leftChild!=NULL)
{
if (depth<2)
{
leftAngle = angle + rand()%15;
} else
{
if (!isLeft) {
leftAngle = angle + rand()%5 + 10;
} else {
leftAngle = rand()%45;
}
}
int lenEdge = rootLengt-depth*35;
dx = -cos(leftAngle*PI/180)*lenEdge;
dy = sin(leftAngle*PI/180)*lenEdge;
nx = x+dx;
ny = y+dy;
p->drawLine(x,y,nx,ny);
draw(node->leftChild,nx,ny,leftAngle,true,depth+1,p);
}
if (node->rightChild!=NULL)
{
if (depth<2)
{
rightAngle = angle + rand()%15;
} else
{
if (isLeft)
{
rightAngle = angle + rand()%5 + 10;
}
else
{
rightAngle = rand()%45;
}
}
int lenEdge = rootLengt-depth*15;
dx = cos(rightAngle*PI/180)*lenEdge;
dy = sin(rightAngle*PI/180)*lenEdge;
nx = x+dx;
ny = y+dy;
p->drawLine(x,y,nx,ny);
draw(node->rightChild,nx,ny,rightAngle,false,depth+1,p);
}
if (node->leftChild==NULL && node->rightChild==NULL) {return ; }
}
void Paint::paintEvent(QPaintEvent *e)
{
QPainter p(this);
draw(myTree->getRoot(), width()/2, height()/2, 10, true, 0, &p);
}
widget.h:
#ifndef WIDGET_H
#define WIDGET_H
#include <QWidget>
namespace Ui {
class Widget;
}
class Widget : public QWidget
{
Q_OBJECT
public:
explicit Widget(QWidget *parent = 0);
~Widget();
public slots:
void on_btnCreat_clicked();
void on_clear_clicked();
private:
Ui::Widget *ui;
};
#endif // WIDGET_H
widget.cpp:
#include "widget.h"
#include"paint.h"
#include "ui_widget.h"
#include<c++/vector>
#include<QMessageBox>
Widget::Widget(QWidget *parent) :
QWidget(parent),
ui(new Ui::Widget)
{
ui->setupUi(this);
connect(ui->Create,SIGNAL(clicked(bool)),this,SLOT(on_btnCreat_clicked()));
connect(ui->clear,SIGNAL(clicked(bool)),this,SLOT(on_clear_clicked()));
}
Widget::~Widget()
{
delete ui;
}
void Widget::on_btnCreat_clicked()
{
QString input1 = ui->lEdInput1->text();
QString input2 = ui->lEdInput2->text();
Paint *p = new Paint();
p->setInput(input1,input2);
p->show();
}
void Widget::on_clear_clicked()
{
ui->lEdInput2->clear();
ui->lEdInput1->clear();
}
main:
#include "widget.h"
#include <QApplication>
int main(int argc, char *argv[])
{
QApplication a(argc, argv);
Widget w;
w.show();
return a.exec();
}
画出来是一个很好看的二叉树，大家可以根据paintEvent函数中的参数修改二叉树的形态。