binarytree.h 头文件
#ifndef LINKEDBINARYTREE_H
#define LINKEDBINARYTREE_H
#include<c++/algorithm>
#include<c++/cstdio>
#include<string>
#include<c++/string>
#include<c++/vector>
#include<vector>
#include<iostream>
#include"cirqueue.h" 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;
// void PreOrder(BinTreeNode * bt); // 前序遍历函数调用
// void InOrder(BinTreeNode * bt); // 中序遍历函数调用
// void PostOrder(BinTreeNode * bt); // 后序遍历函数调用
public:
//记录前中后 层次遍历以后的数据
vector<char> listPre;
vector<char> listMid;
vector<char> listLast;
vector<char> listLevel; 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 ;
int i = getHeight(subTree->leftChild);
int j = getHeight(subTree->rightChild);
return (i < j) ? j + : i + ;
}
void PreOrder(BinTreeNode * bt) ; // 递归前序遍历二叉树
void InOrder(BinTreeNode * bt) ; // 递归中序遍历二叉树
void PostOrder(BinTreeNode * bt); // 递归后序遍历二叉树
void LeverOrder(); // 层序遍历二叉树 }; inline void linkedBinaryTree::LeverOrder()
{
Queue<BinTreeNode *> Q; // 定义一个队列
Q.front=Q.rear=-; // 顺序队列
if (root == NULL)
return;
Q.queue[++Q.rear]=root;// 根指针入队
while (Q.front != Q.rear)
{
BinTreeNode * q = Q.queue[++Q.front]; // 出队
cout<<q->data;
listLevel.push_back(q->data);
if (q->leftChild != NULL)
Q.queue[++Q.rear] = q->leftChild; // 左孩子入队
if (q->rightChild != NULL)
Q.queue[++Q.rear] = q->rightChild; // 右孩子入队
} } inline void linkedBinaryTree::PreOrder(BinTreeNode * bt)
{
if (bt == NULL)// 递归调用的结束条件
return;
cout << bt->data;// 访问根节点bt的数据域
listPre.push_back(bt->data);
PreOrder(bt->leftChild);// 前序递归遍历bt的左子树
PreOrder(bt->rightChild);// 前序递归遍历bt的右子树
} inline void linkedBinaryTree::InOrder(BinTreeNode * bt)
{
if (bt == NULL)
return;
InOrder(bt->leftChild);
cout << bt->data;
listMid.push_back(bt->data);
InOrder(bt->rightChild);
} inline void linkedBinaryTree::PostOrder(BinTreeNode * bt)
{
if (bt == NULL)
return;
PostOrder(bt->leftChild);
PostOrder(bt->rightChild);
cout << bt->data;
listLast.push_back(bt->data);
} #endif // LINKEDBINARYTREE_H
binarytree.cpp文件
#include<c++/vector>
#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 == )
return NULL;
vector<char> leftPre, leftMid, rightPre, rightMid;
BinTreeNode* Root = new BinTreeNode(pre[]);
int rootPos = ;
for (int i = ; i < nodeSize; i++)
{
if (mid[i] == pre[])
{
rootPos = i;
break;
}
}
for (int i = ; i < nodeSize; i++)
{
if (i < rootPos)
{ leftMid.push_back(mid[i]); leftPre.push_back(pre[i + ]);
}
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;
}
cirqueue.h头文件
#ifndef CIRQUEUE_H
#define CIRQUEUE_H
#pragma once
#include <iostream>
template<class T>
class Queue {
// FIFO 对象
public :
Queue(int MaxQueueSize = );
~Queue() {delete [] queue;}
bool IsEmpty() const {return front == rear;}
bool IsFull() const {return (
((rear + ) % MaxSize == front) ? : );}
T First() const; //返回队首元素
T Last() const; // 返回队尾元素
Queue<T>& Add(const T& x);
Queue<T>& Delete(T& x);
int front; //与第一个元素在反时针方向上相差一个位置
int rear; // 指向最后一个元素
int MaxSize; // 队列数组的大小
T *queue; // 数组
} ; template<class T>
Queue<T>::Queue(int MaxQueueSize)
{// 创建一个容量为 M a x Q u e u e S i z e的空队列
MaxSize = MaxQueueSize + ;
queue = new T[MaxSize];
front = rear = ;
}
template<class T>
T Queue<T>::First() const
{// 返回队列的第一个元素
// 如果队列为空，则引发异常O u t O f B o u n d s
if (IsEmpty()) throw "OutOfBounds()";
return queue[(front + ) % MaxSize];
}
template<class T>
T Queue<T>::Last() const
{// 返回队列的最后一个元素
// 如果队列为空，则引发异常O u t O f B o u n d s
if (IsEmpty()) throw "OutOfBounds()";
return queue[rear];
}
template<class T>
Queue<T>& Queue<T>::Add(const T& x)
{// 把 x 添加到队列的尾部
// 如果队列满，则引发异常 NoMem
if (IsFull()) throw "NoMem()";
rear = (rear + ) % MaxSize;
queue[rear] = x;
return *this;
}
template<class T>
Queue<T>& Queue<T>::Delete(T& x)
{// 删除第一个元素，并将其送入 x
// 如果队列为空，则引发异常 O u t O f B o u n d s
if (IsEmpty()) throw "OutOfBounds()";
front = (front + ) % MaxSize;
x = queue[front];
return *this;
} #endif // CIRQUEUE_H
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,linkedBinaryTree *myTree);
void paintEvent(QPaintEvent *);
void draw(BinTreeNode *node, int x, int y, int angle, bool isLeft, int depth, QPainter *p);
BinTreeNode* test();
//绘制前中后 层次遍历的函数
void draw_preOrder(vector<int>x,vector<int>y,vector<char>data,QPainter *painter);
void draw_midOrder(vector<int>x,vector<int>y,vector<char>data,QPainter *painter);
void draw_lastOrder(vector<int>x,vector<int>y,vector<char>data,QPainter *painter);
void draw_levelOrder(vector<int>x,vector<int>y,vector<char>data,QPainter *painter);
private:
linkedBinaryTree* myTreepaint;
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>
#include<cmath>
#include<c++/vector>
#include<QTimer>
#include<string> //按照顺序保存生成的树
vector<int>xslot;vector<int>yslot;
vector<char>xyData;
static int numberPre=;//用来记录执行次数
static int numberMid=;
static int numberLast=;
static int numberLevel=;
//extern vector<char> listPre; Paint::Paint(QWidget *parent) : QWidget(parent)
{ //设置计时器
QTimer *timer = new QTimer(this);
timer->start();//一秒钟
connect(timer,SIGNAL(timeout()),this,SLOT(update()));
// if(number>xyData.size())
// {
// number=0;
// timer->stop(); // } resize(, );
// myTree = new linkedBinaryTree();
} bool Paint::setInput(QString input1, QString input2,linkedBinaryTree *myTree)
{
std::string s1 = input1.toStdString();
std::string s2 = input2.toStdString();
vector<char>v1;
vector<char>v2;
for(int i=;i<s1.size();i++){v1.push_back(s1[i]);};
for(int i=;i<s2.size();i++){v2.push_back(s2[i]);};
myTree->set(v1,v2);
myTreepaint=myTree;
return true;
} void Paint::draw(BinTreeNode *node, int x, int y, int angle, bool isLeft, int depth, QPainter *p)
{ xslot.push_back(x);yslot.push_back(y);
xyData.push_back(node->data); int leftAngle, rightAngle;
int dx,dy,nx,ny;
if (node==NULL)
return;
p->save();
p->setBrush(QColor(, , ));
p->drawEllipse(x-,y-,,);
p->restore();
p->drawText(x,y,QChar(node->data));
if (node->leftChild!=NULL)
{
if (depth<)
{
leftAngle = angle + rand()%;
} else
{
if (!isLeft) {
leftAngle = angle + rand()% + ;
} else {
leftAngle = rand()%;
}
}
int lenEdge = rootLengt-depth*;
dx = -cos(leftAngle*PI/)*lenEdge;
dy = sin(leftAngle*PI/)*lenEdge;
nx = x+dx;
ny = y+dy;
p->drawLine(x,y,nx,ny);
draw(node->leftChild,nx,ny,leftAngle,true,depth+,p);
}
if (node->rightChild!=NULL)
{
if (depth<)
{
rightAngle = angle + rand()%;
} else
{
if (isLeft)
{
rightAngle = angle + rand()% + ;
}
else
{
rightAngle = rand()%;
}
}
int lenEdge = rootLengt-depth*;
dx = cos(rightAngle*PI/)*lenEdge;
dy = sin(rightAngle*PI/)*lenEdge;
nx = x+dx;
ny = y+dy;
p->drawLine(x,y,nx,ny);
draw(node->rightChild,nx,ny,rightAngle,false,depth+,p); }
if (node->leftChild==NULL && node->rightChild==NULL) {return ; } } void Paint::draw_preOrder(vector<int>x,vector<int>y,vector<char>data,QPainter *painter){ int pos;
//绘制画图函数
painter->save();
painter->setBrush(QColor(,,,));
for(int i=;i<data.size();i++){
if(data[numberPre]==xyData[i]){
pos=i;
}
}
int a=x[pos];int b=y[pos]; painter->drawEllipse(a-,b-,,);
painter->restore();
painter->drawText(a,b,data[numberPre]+"");
numberPre++;
} void Paint::draw_midOrder(vector<int>x,vector<int>y,vector<char>data,QPainter *painter){
int pos;
//绘制画图函数
painter->save();
painter->setBrush(QColor(,,,));
for(int i=;i<data.size();i++){
if(data[numberMid]==xyData[i]){
pos=i;
}
}
int a=x[pos];int b=y[pos]; painter->drawEllipse(a-,b-,,);
painter->restore();
painter->drawText(a,b,data[numberMid]+"");
numberMid++;
} void Paint:: draw_lastOrder(vector<int>x,vector<int>y,vector<char>data,QPainter *painter){
int pos;
//绘制画图函数
painter->save();
painter->setBrush(QColor(,,,));
for(int i=;i<data.size();i++){
if(data[numberLast]==xyData[i]){
pos=i;
}
}
int a=x[pos];int b=y[pos]; painter->drawEllipse(a-,b-,,);
painter->restore();
painter->drawText(a,b,data[numberLast]+"");
numberLast++;
}
void Paint::draw_levelOrder(vector<int>x,vector<int>y,vector<char>data,QPainter *painter){
int pos;
//绘制画图函数
painter->save();
painter->setBrush(QColor(,,,));
for(int i=;i<data.size();i++){
if(data[numberLevel]==xyData[i]){
pos=i;
}
}
int a=x[pos];int b=y[pos]; painter->drawEllipse(a-,b-,,);
painter->restore();
painter->drawText(a,b,data[numberLevel]+"");
numberLevel++;
}
void Paint::paintEvent(QPaintEvent *e)
{
QPainter p(this);
draw(myTreepaint->getRoot(), width()/, height()/, , true, , &p);
//?????????
//??????????
//?????????
//???????????传不进来参数嘤嘤嘤！
if(false){//前序
vector<char> pre={'A','B','C','E','H','F','I','J','D','G','K'};
draw_preOrder(xslot,yslot,pre,&p);
}
if(false){//中序 vector<char> mid={'A', 'H', 'E', 'C', 'I', 'F', 'J' ,'B', 'D', 'K', 'G'};
draw_midOrder(xslot,yslot,mid,&p);
}
if(false){//后序
vector<char> last={'H','E','I','J','F','C','K','G','D','B','A'};
draw_lastOrder(xslot,yslot,last,&p);
}
//层次
if(false){
vector<char> level={'A','B','C','D','E','F','G','H','I','J','K'};
draw_preOrder(xslot,yslot,level,&p);} }
widget.h
#ifndef WIDGET_H
#define WIDGET_H #include <QWidget>
#include"binarytree.h"
namespace Ui {
class Widget;
} class Widget : public QWidget
{
Q_OBJECT public:
explicit Widget(QWidget *parent = );
~Widget();
linkedBinaryTree* myTree;
public slots:
void on_btnCreat_clicked();
void on_clear_clicked();
private slots:
void on_preButton_clicked(); void on_midButton_clicked(); void on_lastButton_clicked(); void on_levelButton_clicked(); private:
Ui::Widget *ui;
}; #endif // WIDGET_H
widget.cpp文件
#include "widget.h"
#include"paint.h"
#include"binarytree.h"
#include "ui_widget.h"
#include<c++/vector>
#include<QMessageBox>
#include <iterator>
#include <algorithm>
#include<QTimer>
#include<QTime> 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()));
connect(ui->preButton,SIGNAL(clicked(bool)),this,SLOT(on_preButton_clicked()));
connect(ui->midButton,SIGNAL(clicked(bool)),this,SLOT(on_midButton_clicked()));
connect(ui->lastButton,SIGNAL(clicked(bool)),this,SLOT(on_lastButton_clicked()));
connect(ui->levelButton,SIGNAL(clicked(bool)),this,SLOT(on_levelButton_clicked()));
} Widget::~Widget()
{
delete ui;
}
void Widget::on_btnCreat_clicked()
{ myTree = new linkedBinaryTree();
QString input1 = ui->lEdInput1->text();
QString input2 = ui->lEdInput2->text();
Paint *p = new Paint();
p->setInput(input1,input2,myTree);
p->show();
}
void Widget::on_clear_clicked()
{
ui->lEdInput2->clear();
ui->lEdInput1->clear();
} void Widget::on_preButton_clicked()
{ myTree = new linkedBinaryTree();
QString input1 = ui->lEdInput1->text();
QString input2 = ui->lEdInput2->text();
Paint *p = new Paint();
p->setInput(input1,input2,myTree); BinTreeNode *root=myTree->getRoot();
myTree->PreOrder(root); } void Widget::on_midButton_clicked()
{
myTree = new linkedBinaryTree();
QString input1 = ui->lEdInput1->text();
QString input2 = ui->lEdInput2->text();
Paint *p = new Paint();
p->setInput(input1,input2,myTree); BinTreeNode *root=myTree->getRoot();
myTree->InOrder(root); } void Widget::on_lastButton_clicked()
{
myTree = new linkedBinaryTree();
QString input1 = ui->lEdInput1->text();
QString input2 = ui->lEdInput2->text();
Paint *p = new Paint();
p->setInput(input1,input2,myTree); BinTreeNode *root=myTree->getRoot();
myTree->PostOrder(root);
} void Widget::on_levelButton_clicked()
{
myTree = new linkedBinaryTree();
QString input1 = ui->lEdInput1->text();
QString input2 = ui->lEdInput2->text();
Paint *p = new Paint();
p->setInput(input1,input2,myTree); myTree->LeverOrder(); }
main.cpp
#include "widget.h"
#include <QApplication> int main(int argc, char *argv[])
{
QApplication a(argc, argv);
Widget w;
w.show();
return a.exec();
}