2025年期末复习笔记——树和二叉树

大家好，我是讯享网，很高兴认识大家。

一、树

1，树型结构

树型结构是一种非线性结构，与之前的线性表，栈，队列还有字符串，数组，广义表不同。相比与之前一对一的线性结构，树型结构展示为一对多的非线性结构。

2，树的定义，术语，森林

太多了，不打了。。。直接二叉树

二、二叉树

二叉树，这个树比较重要，结构简单，规律性强，普通树也可以通过转化为二叉树进行运算，简化步骤。其中运用二叉树的算法也有很多，像最优二叉树哈夫曼树，树状数组，线段树等等，都是在二叉树上进行操作。

1.几个性质

1，一个节点最多只用有两个孩子，所以在二叉树的第i层上至多有 $2^{i-1}$
讯享网个结点

2，深度为k的二叉树至多有 $2^{k}-1$ 个结点

3，对于任何一棵二叉树T,如果其叶子树为 $n{_0}$ ，度为2的结点数为 $n{_2}$ ，则 $n{_0}=n{_2}+1$

咋算的

总边数：

1，每个孩子和双亲都有一条连线，只有根没有双亲，所以n个节点对于有 n-1 条边。

2，再者总边数还可以为度为2结点的边和度为1节点的边的和

所以 $n-1=n{_2}*2+n{_1}*1$ ，又因为节点数等于度为2，度为1，度为0的 $n=n{_0}+n{_1}+n{_2}$ 带入就为 $n{_0}=n{_2}+1$ 。

4，具有n个结点的完全二叉树的深度为 $log _{2}{}^{n}+1$

1，满二叉树：深度为k，且结点数为 $2^{k}-1$ 的二叉树

2，完全二叉树：

我们可以联想到到在排序那章讲的堆排序，堆就是一个完全二叉树，堆中的某个结点的值总是大于等于（最大堆）或小于等于（最小堆）其孩子结点的值,第 k 层所有的结点都连续集中在最左边。

所以二叉树的深度为k，除第 k 层外，其它各层 (1～k-1) 的结点数都达到最大个数，

第 k 层所有的结点都连续集中在最左边,且其中每一个结点都能与满二叉树匹配的二叉树.

2，二叉树的存储结构

学习了前面的队列，栈，串等，思考存储结构可以想到两个方面：顺序存储，链式存储

1，顺序存储

#define MAXTSIZE 100 typedef char SqbiTree[MAXTSIZE]; SqbiTree bt;

讯享网

1	2	3	4	5	6	7	8	9	10	11	12
a	e	b	f		d	c	g				h

空的结点算上，12个结点， $log{_2}{ }^{12}+1$ 有四层

先画出满二叉树，再填上去

2，链式存储

重点还是看链式存储。。。

讯享网typedef struct BiNode { char data; struct BiNode* lchild, * rchild; }Binode,*BiTree;

还可以利用双向链表改写二叉链表的指针域为三叉链表，使其可以询问结点的双亲结点

typedef struct BiNode { char data; struct BiNode* lchild, * rchild; struct BiNode* parent; }Binode,*BiTree;

3，遍历二叉树

1，遍历二叉树的方法有六种

根左右，左根右，左右根，根右左，右根左，右左根

后三个和前三个对称，所以只研究前三个

根左右	先序（根）遍历
左根右	中序（根）遍历
左右根	后序（根）遍历

思考：栈和队列的前缀表达式，中缀表达式，后缀表达式，应该是由二叉树的三种遍历方式展现出来的

可以看出上次使用入栈操作也可以得到三种表达式的结果，猜测三种遍历方式也可以使用栈进行实现。

1.1先根遍历：访问根结点——>左子树——>右子树

递归实现：

讯享网void Preordertravers(BiTree T) { if (T == NULL)return ; else { cout << T->data; Preordertravers(T->lchild); Preordertravers(T->rchild); } }

栈实现：思路和递归一致，先将根压入栈，然后左子树一并压入栈直到空为止开始弹栈，取栈顶结点判断右子树是否存在，如果存在继续压入左子树操作。

void PrevOrder_stack(Binode* T) { stack<Binode*> s; Binode* Bi = T; while (Bi || !s.empty()) { if(Bi) { cout << Bi->data; s.push(Bi); Bi = Bi->lchild; } else { Bi = s.top(); s.pop(); Bi = Bi->rchild; } } cout << "先序遍历_栈" << endl; }

1.2中根遍历：访问左子树——>根结点——>右子树

讯享网void Inordertraverse(BiTree T) { if (T == NULL)return; else { Inordertraverse(T->lchild); cout << T->data; Inordertraverse(T->rchild); } }

栈实现：和先序差不多，左子树压入栈直到叶子开始弹栈并输出，然后再将右子树压入栈中

void InOrder_stack(Binode* T) { stack<Binode*> s; Binode* Bi = T; while (Bi || !s.empty()) { if (Bi) { s.push(Bi); Bi = Bi->lchild; } else { Bi = s.top(); cout << Bi->data; s.pop(); Bi = Bi->rchild; } } cout << "中序遍历_栈" << endl; }

1.3后根遍历：访问左子树——>右子树——>根结点

讯享网void Postordertraverse(BiTree T) { if (T == NULL)return; else { Postordertraverse(T->lchild); Postordertraverse(T->rchild); cout << T->data; } }

栈实现：也是先把左子树压入栈直到空，然后判断是否存在右子树，如果有用vis记录该结点，然后开始重复上述操作，继续将右子树中的左子树压入栈，直到为叶子结点

void PastOrder_stack(Binode* T) { Binode* Bi = T; Binode* vis = NULL; stack<Binode*> s; while (Bi||!s.empty()) { if (Bi) { s.push(Bi); Bi = Bi->lchild; } else { Bi = s.top(); if (Bi->rchild && vis != Bi->rchild) Bi = Bi->rchild; else if (( Bi->rchild==NULL) || (vis == Bi->rchild)) { cout << Bi->data; vis = Bi; s.pop(); Bi = NULL; } } } cout << "后序遍历_栈" << endl; }

1.4层次遍历：

从上到下，从左到右

讯享网void HierarchyOrder(Binode * T) { queue<Binode*>q; q.push(T); Binode* temp; while (!q.empty()) { temp = q.front(); q.pop(); cout << temp->data; if (temp->lchild != NULL) { q.push(temp->lchild); } if (temp->rchild != NULL) { q.push(temp->rchild); } } }

2，二叉树的创建和easyx的可视化操作

二叉树的创建以先根遍历的方式

void CreateBiTree(BiTree* T){ char ch; cin >> ch; if (ch == '.') { *T = NULL; } else { *T = (BiTree)malloc(sizeof(Binode)); (*T)->data = ch; CreateBiTree(&((*T)->lchild)); CreateBiTree(&((*T)->rchild)); } }

用easyx首先画一张图，我想让这棵树的根节点从坐标（360，200）的位置开始生成根结点画个圈，然后先从左子树开始向他六十度方向连线并为当前结点画个圈，直到左子树为空，开始回溯，判断是否有右子树，有则向六十度方向画出右子树为当前结点画个圈并重复上述画左子树的方法。

当然，因为二叉树如果左子树和右子树的连线角度和线长都相等，这可以理解为一个对称图形，那么可能内侧的结点会有重叠覆盖，所以，我将角度设为变量，每增加一层，角度 $x{_p}$ 都除以2，对应的(x,y)到终点（xf,yf）的距离也缩短1.2倍

$x{_f}=x\pm (x{_t}*\left |cos(x{_p}) \right |)/1.2$

$y{_f}=y\pm (x{_t}*\left |sin(y{_p}) \right |)/1.2$

程序到这里也这里也只是画了一张图，最求高级的我想让这份作业高级一点，把他变成动画：

线段细化为无数个点排列在一起，我通过两点公式求出这条显得函数关系式： $y=\frac{y{_t}}{x{_t}}*x-\frac{y{_t}}{x{_t}}*x{_x{_0}}+y{_0}$

之后我们将x到 $x{_f}$ 细化为500份，y由公式可得，通过循环遍历每个点可得到生成线段的动画

讯享网void PrevOrderDraw(BiTree T, double x, double y, double xt, double yt,double xp,int time,int dep)//xp为角度, { if (T) { setfillcolor(BLUE); setbkmode(TRANSPARENT); fillcircle(x, y, 20); outtextxy(x - 5, y - 5, T->data); } if (T->lchild)//左子树 { double i ,j; for (i = x,j=y; i >=x - xt,j<=y+yt;) { i -= (x - xt) / 500, j =(-yt/xt)*i-(-yt/xt)*x+y; line(x,y , i, j); Sleep(time); } setfillcolor(BLUE); setbkmode(TRANSPARENT); fillcircle(x, y, 20); outtextxy(x - 5, y - 5, T->data); PrevOrderDraw(T->lchild, x - xt, y + yt, xt / 1.2 * abs(cos(xp)), yt / 1.2 * abs(sin(xp)), xp / 2, time + 4 * dep, dep + 1); } if (T->rchild)//右子树 { double i, j; for (i = x, j = y; i >= x + xt, j <= y + yt;) { i += (x + xt) / 500, j = (yt / xt) * i - (yt / xt) * x + y; line(x, y, i, j); Sleep(time); } setfillcolor(BLUE); setbkmode(TRANSPARENT); fillcircle(x, y, 20); outtextxy(x - 5, y - 5, T->data); PrevOrderDraw(T->rchild, x + xt, y + yt, xt / 1.2 * abs(cos(xp)), yt / 1.2 * abs(sin(xp)), xp / 2, time + 4 * dep, dep + 1); } } void PrintBiTree(BiTree T) { PrevOrderDraw(T, 360,200, 200* abs(sin(PI / 3)), 200* abs(cos(PI / 3)), PI / 3,6,1); }

考虑到后面线段变短，所以每次睡眠时间通过层数增加，还有每次画完线需要再画一次圆盖掉线的痕迹，不然影响美观。

二叉树AB.C..DE.G..F.H..先序遍历生成动画结束的样子

当然这只是一棵小二叉树，对于5层以上的建议大家长度由短到长，角度由小到大，不会显得太密集。

3,二叉树的遍历和easyx可视化

想法很简单：分别在输出值上加个结点颜色改变的函数，之前想过用圆变大变小来操作，但是变大变小完线会被盖掉，这样我们要重新画线，代表了我们要访问他的双亲结点的x，y，这样需要用到之前说的三叉链表存储，我懒，没有实现。

注意一下，这里加了xy，所以画二叉树那也要更改一下：

typedef struct BiNode { char data; double x, y; struct BiNode* lchild, * rchild; }Binode,*BiTree;

各种遍历：

这个变色是闪三下，写的有点暴力

讯享网void circhange(int x, int y, int data) { settextcolor(BLACK); setfillcolor(YELLOW); setbkmode(TRANSPARENT); fillcircle(x, y, 20); outtextxy(x - 5, y - 5, data); Sleep(400); setfillcolor(BLUE); setbkmode(TRANSPARENT); fillcircle(x, y, 20); outtextxy(x - 5, y - 5, data); Sleep(400); setfillcolor(YELLOW); setbkmode(TRANSPARENT); fillcircle(x, y, 20); outtextxy(x - 5, y - 5, data); Sleep(400); } void Preordertravers(BiTree T) { if (T == NULL)return ; else { cout << T->data; circhange(T->x, T->y,T->data); Preordertravers(T->lchild); Preordertravers(T->rchild); } } void Inordertraverse(BiTree T) { if (T == NULL)return; else { Inordertraverse(T->lchild); cout << T->data; circhange(T->x, T->y, T->data); Inordertraverse(T->rchild); } } void Postordertraverse(BiTree T) { if (T == NULL)return; else { Postordertraverse(T->lchild); Postordertraverse(T->rchild); cout << T->data; circhange(T->x, T->y, T->data); } } void HierarchyOrder(Binode * T) { queue<Binode*>q; q.push(T); Binode* temp; while (!q.empty()) { temp = q.front(); q.pop(); cout << temp->data; circhange(temp->x, temp->y, temp->data); if (temp->lchild != NULL) { q.push(temp->lchild); } if (temp->rchild != NULL) { q.push(temp->rchild); } } }

测试了一下，每个算法没啥问题，接下来就可以实现选择功能的界面了

4,easyx设计操控界面

首先设定生产二叉树窗口

在main中打开文件，利用easyx的鼠标读取对四种二叉树进行读取并生成

int main() { initgraph(720, 720, EW_SHOWCONSOLE); ifstream file; BiTree T; file.open("test.txt"); file >> s1 >> s2 >> s3 >> s4; showjpg(); BeginBatchDraw(); ExMessage msg; int x[5], y[5], w[5], h[5]; x[0] = 260; y[0] = 100; w[0] = 200; h[0] = 50; setfillcolor(YELLOW); fillroundrect(x[0], y[0], x[0] + w[0], y[0] + h[0], 10, 10); botton_table(x[0], y[0], w[0], h[0], "Bitree_1"); x[1] = 260; y[1] = 200; w[1] = 200; h[1] = 50; setfillcolor(YELLOW); fillroundrect(x[1], y[1], x[1] + w[1], y[1] + h[1], 10, 10); botton_table(x[0], y[0], w[0], h[0], "Bitree_2"); x[2] = 260; y[2] = 300; w[2] = 200; h[2] = 50; setfillcolor(YELLOW); fillroundrect(x[2], y[2], x[2] + w[2], y[2] + h[2], 10, 10); botton_table(x[2], y[2], w[2], h[2], "Bitree_3"); x[3] = 260; y[3] = 400; w[3] = 200; h[3] = 50; setfillcolor(YELLOW); fillroundrect(x[3], y[3], x[3] + w[3], y[3] + h[3], 10, 10); botton_table(x[3], y[3], w[3], h[3], "Bitree_4"); x[4] = 260; y[4] = 500; w[4] = 200; h[4] = 50; setfillcolor(YELLOW); fillroundrect(x[4], y[4], x[4] + w[4], y[4] + h[4], 10, 10); botton_table(x[4], y[4], w[4], h[4], "退出"); bool checkt = 0; while (1) { if (peekmessage(&msg, EM_MOUSE)) { switch (msg.message) { case WM_LBUTTONDOWN://点击 if (msg.x >= x[0] && msg.x <= x[0] + w[0] && msg.y >= y[0] && msg.y <= y[0] + h[0] ) { s = s1; ip = 0; cleardevice(); CreateBiTree(&T); PrintBiTree(T); Sleep(800); cleardevice(); showjpg(); Orderchoice(T); } if (msg.x >= x[1] && msg.x <= x[1] + w[1] && msg.y >= y[1] && msg.y <= y[1] + h[1] ) { s = s2; ip = 0; cleardevice(); CreateBiTree(&T); PrintBiTree(T); Sleep(800); cleardevice(); showjpg(); Orderchoice(T); } if (msg.x >= x[2] && msg.x <= x[2] + w[2] && msg.y >= y[2] && msg.y <= y[2] + h[2]) { s = s3; ip = 0; cleardevice(); CreateBiTree(&T); PrintBiTree(T); Sleep(800); cleardevice(); showjpg(); Orderchoice(T); } if (msg.x >= x[3] && msg.x <= x[3] + w[3] && msg.y >= y[3] && msg.y <= y[3] + h[3]) { s = s4; ip = 0; CreateBiTree(&T); cleardevice(); PrintBiTree(T); Sleep(800); cleardevice(); showjpg(); Orderchoice(T); } if (msg.x >= x[4] && msg.x <= x[4] + w[4] && msg.y >= y[4] && msg.y <= y[4] + h[4]) { checkt = true; } FlushBatchDraw(); case WM_MOUSEFIRST://移动 if (msg.x >= x[0] && msg.x <= x[0] + w[0] && msg.y >= y[0] && msg.y <= y[0] + h[0]) { setfillcolor(RED); fillroundrect(x[0], y[0], x[0] + w[0], y[0] + h[0], 10, 10); botton_table(x[0], y[0], w[0], h[0], "Bitree_1"); } else { setfillcolor(YELLOW); fillroundrect(x[0], y[0], x[0] + w[0], y[0] + h[0], 10, 10); botton_table(x[0], y[0], w[0], h[0], "Bitree_1"); } if (msg.x >= x[1] && msg.x <= x[1] + w[1] && msg.y >= y[1] && msg.y <= y[1] + h[1]) { setfillcolor(RED); fillroundrect(x[1], y[1], x[1] + w[1], y[1] + h[1], 10, 10); botton_table(x[1], y[1], w[1], h[1], "Bitree_2"); } else { setfillcolor(YELLOW); fillroundrect(x[1], y[1], x[1] + w[1], y[1] + h[1], 10, 10); botton_table(x[1], y[1], w[1], h[1], "Bitree_2"); } if (msg.x >= x[2] && msg.x <= x[2] + w[2] && msg.y >= y[2] && msg.y <= y[2] + h[2]) { setfillcolor(RED); fillroundrect(x[2], y[2], x[2] + w[2], y[2] + h[2], 10, 10); botton_table(x[2], y[2], w[2], h[2], "Bitree_3"); } else { setfillcolor(YELLOW); fillroundrect(x[2], y[2], x[2] + w[2], y[2] + h[2], 10, 10); botton_table(x[2], y[2], w[2], h[2], "Bitree_3"); } if (msg.x >= x[3] && msg.x <= x[3] + w[3] && msg.y >= y[3] && msg.y <= y[3] + h[3]) { setfillcolor(RED); fillroundrect(x[3], y[3], x[3] + w[3], y[3] + h[3], 10, 10); botton_table(x[3], y[3], w[3], h[3], "Bitree_4"); } else { setfillcolor(YELLOW); fillroundrect(x[3], y[3], x[3] + w[3], y[3] + h[3], 10, 10); botton_table(x[3], y[3], w[3], h[3], "Bitree_4"); } if (msg.x >= x[4] && msg.x <= x[4] + w[4] && msg.y >= y[4] && msg.y <= y[4] + h[4]) { setfillcolor(RED); fillroundrect(x[4], y[4], x[4] + w[4], y[4] + h[4], 10, 10); botton_table(x[4], y[4], w[4], h[4], "退出"); } else { setfillcolor(YELLOW); fillroundrect(x[4], y[4], x[4] + w[4], y[4] + h[4], 10, 10); botton_table(x[4], y[4], w[4], h[4], "退出"); } } EndBatchDraw(); } if (checkt) { break; } } return 0; }

再定义一个遍历选择函数，即选择并生成完所示二叉树，并选择遍历方式

讯享网void Orderchoice(BiTree T) { showjpg(); BeginBatchDraw(); ExMessage msg; int x[5], y[5], w[5], h[5]; x[0] = 260; y[0] = 100; w[0] = 200; h[0] = 50; setfillcolor(YELLOW); fillroundrect(x[0], y[0], x[0] + w[0], y[0] + h[0], 10, 10); botton_table(x[0], y[0], w[0], h[0], "先序遍历"); x[1] = 260; y[1] = 200; w[1] = 200; h[1] = 50; setfillcolor(YELLOW); fillroundrect(x[1], y[1], x[1] + w[1], y[1] + h[1], 10, 10); botton_table(x[0], y[0], w[0], h[0], "中序遍历"); x[2] = 260; y[2] = 300; w[2] = 200; h[2] = 50; setfillcolor(YELLOW); fillroundrect(x[2], y[2], x[2] + w[2], y[2] + h[2], 10, 10); botton_table(x[2], y[2], w[2], h[2], "后序遍历"); x[3] = 260; y[3] = 400; w[3] = 200; h[3] = 50; setfillcolor(YELLOW); fillroundrect(x[3], y[3], x[3] + w[3], y[3] + h[3], 10, 10); botton_table(x[3], y[3], w[3], h[3], "层次遍历"); x[4] = 260; y[4] = 500; w[4] = 200; h[4] = 50; setfillcolor(YELLOW); fillroundrect(x[4], y[4], x[4] + w[4], y[4] + h[4], 10, 10); botton_table(x[4], y[4], w[4], h[4], "退出"); bool checkt = 0; while (1) { if (peekmessage(&msg, EM_MOUSE)) { switch (msg.message) { case WM_LBUTTONDOWN://点击 if (msg.x >= x[0] && msg.x <= x[0] + w[0] && msg.y >= y[0] && msg.y <= y[0] + h[0]) { cleardevice(); Draw(T, 360, 200, 180 * abs(sin(PI / 3)), 180 * abs(cos(PI / 3)), PI / 3); Preordertravers(T); cleardevice(); showjpg(); } if (msg.x >= x[1] && msg.x <= x[1] + w[1] && msg.y >= y[1] && msg.y <= y[1] + h[1]) { cleardevice(); Draw(T, 360, 200, 180 * abs(sin(PI / 3)), 180 * abs(cos(PI / 3)), PI / 3); Inordertraverse(T); cleardevice(); showjpg(); } if (msg.x >= x[2] && msg.x <= x[2] + w[2] && msg.y >= y[2] && msg.y <= y[2] + h[2]) { cleardevice(); Draw(T, 360, 200, 180 * abs(sin(PI / 3)), 180 * abs(cos(PI / 3)), PI / 3); Postordertraverse(T); cleardevice(); showjpg(); } if (msg.x >= x[3] && msg.x <= x[3] + w[3] && msg.y >= y[3] && msg.y <= y[3] + h[3]) { cleardevice(); Draw(T, 360, 200, 180 * abs(sin(PI / 3)), 180 * abs(cos(PI / 3)), PI / 3); HierarchyOrder(T); cleardevice(); showjpg(); } if (msg.x >= x[4] && msg.x <= x[4] + w[4] && msg.y >= y[4] && msg.y <= y[4] + h[4]) { checkt = true; } FlushBatchDraw(); case WM_MOUSEFIRST://移动 if (msg.x >= x[0] && msg.x <= x[0] + w[0] && msg.y >= y[0] && msg.y <= y[0] + h[0]) { setfillcolor(RED); fillroundrect(x[0], y[0], x[0] + w[0], y[0] + h[0], 10, 10); botton_table(x[0], y[0], w[0], h[0], "先序遍历"); } else { setfillcolor(YELLOW); fillroundrect(x[0], y[0], x[0] + w[0], y[0] + h[0], 10, 10); botton_table(x[0], y[0], w[0], h[0], "先序遍历"); } if (msg.x >= x[1] && msg.x <= x[1] + w[1] && msg.y >= y[1] && msg.y <= y[1] + h[1]) { setfillcolor(RED); fillroundrect(x[1], y[1], x[1] + w[1], y[1] + h[1], 10, 10); botton_table(x[1], y[1], w[1], h[1], "中序遍历"); } else { setfillcolor(YELLOW); fillroundrect(x[1], y[1], x[1] + w[1], y[1] + h[1], 10, 10); botton_table(x[1], y[1], w[1], h[1], "中序遍历"); } if (msg.x >= x[2] && msg.x <= x[2] + w[2] && msg.y >= y[2] && msg.y <= y[2] + h[2]) { setfillcolor(RED); fillroundrect(x[2], y[2], x[2] + w[2], y[2] + h[2], 10, 10); botton_table(x[2], y[2], w[2], h[2], "后序遍历"); } else { setfillcolor(YELLOW); fillroundrect(x[2], y[2], x[2] + w[2], y[2] + h[2], 10, 10); botton_table(x[2], y[2], w[2], h[2], "后序遍历"); } if (msg.x >= x[3] && msg.x <= x[3] + w[3] && msg.y >= y[3] && msg.y <= y[3] + h[3]) { setfillcolor(RED); fillroundrect(x[3], y[3], x[3] + w[3], y[3] + h[3], 10, 10); botton_table(x[3], y[3], w[3], h[3], "层次遍历"); } else { setfillcolor(YELLOW); fillroundrect(x[3], y[3], x[3] + w[3], y[3] + h[3], 10, 10); botton_table(x[3], y[3], w[3], h[3], "层次遍历"); } if (msg.x >= x[4] && msg.x <= x[4] + w[4] && msg.y >= y[4] && msg.y <= y[4] + h[4]) { setfillcolor(RED); fillroundrect(x[4], y[4], x[4] + w[4], y[4] + h[4], 10, 10); botton_table(x[4], y[4], w[4], h[4], "退出"); } else { setfillcolor(YELLOW); fillroundrect(x[4], y[4], x[4] + w[4], y[4] + h[4], 10, 10); botton_table(x[4], y[4], w[4], h[4], "退出"); } } EndBatchDraw(); } if (checkt) { break; } } return; }

总程序

#include <graphics.h>
#include<iostream>
#include<easyx.h>
#include <cassert>
#include<Windows.h>
#include<bits/stdc++.h>
using namespace std;

#define PI 3.1415
typedef struct BiNode {
   char data;

   double x, y;
   struct BiNode* lchild, * rchild;
   struct BiNode* parent;
}Binode,*BiTree;
string s,s1, s2, s3, s4;

   settextcolor(RGB(0, 0, 0));
   setbkmode(TRANSPARENT);
   char text_[50];
   strcmp(text_, text);
   int tx = x + (w - textwidth(text)) / 2;
   int ty = y + (h - textheight(text)) / 2;
   outtextxy(tx, ty, text);
}

void showjpg() {
   IMAGE img;
   loadimage(&img, "./1.jpg", 720, 720);
   putimage(0, 0, &img);

}

void circhange(int x, int y, int data)
{
   settextcolor(BLACK);
   setfillcolor(YELLOW);
   setbkmode(TRANSPARENT);
   fillcircle(x, y, 20);
   outtextxy(x - 5, y - 5, data);
   Sleep(400);
   setfillcolor(BLUE);
   setbkmode(TRANSPARENT);
   fillcircle(x, y, 20);
   outtextxy(x - 5, y - 5, data);
   Sleep(400);
   setfillcolor(YELLOW);
   setbkmode(TRANSPARENT);
   fillcircle(x, y, 20);
   outtextxy(x - 5, y - 5, data);
   Sleep(400);
}

void Preordertravers(BiTree T) {
   if (T == NULL)return ;
   else {
       cout << T->data;
       circhange(T->x, T->y,T->data);
       Preordertravers(T->lchild);
       Preordertravers(T->rchild);
   }
}

void Inordertraverse(BiTree T) {
   if (T == NULL)return;
   else {

       Inordertraverse(T->lchild);
       cout << T->data;
       circhange(T->x, T->y, T->data);
       Inordertraverse(T->rchild);
   }
}

void Postordertraverse(BiTree T) {
   if (T == NULL)return;
   else {

       Postordertraverse(T->lchild);
       Postordertraverse(T->rchild);
       cout << T->data;
       circhange(T->x, T->y, T->data);
   }
}

void HierarchyOrder(Binode * T)
{
   queue<Binode*>q;
   q.push(T);
   Binode* temp;
   while (!q.empty()) {
       temp = q.front();
       q.pop();
       cout << temp->data;
       circhange(temp->x, temp->y, temp->data);
       if (temp->lchild != NULL) {
           q.push(temp->lchild);
       }
       if (temp->rchild != NULL) {
           q.push(temp->rchild);
       }
   }
}
int ip ;
char ch;
void CreateBiTree(BiTree* T){

   ch = s[ip++];
   if (ch == '.') {
       *T = NULL;
   }
   else {
       *T = (BiTree)malloc(sizeof(Binode));
       (*T)->data = ch;
       CreateBiTree(&((*T)->lchild));
       CreateBiTree(&((*T)->rchild));
   }
}
void PrevOrder_stack(Binode* T)
{
   stack<Binode*> s;
   Binode* Bi = T;
   while (Bi || !s.empty())
   {
       if(Bi)
       {
           cout << Bi->data;
           s.push(Bi);
           Bi = Bi->lchild;
       }
       else {
           Bi = s.top();
           s.pop();
           Bi = Bi->rchild;
       }
   }
   cout << "先序遍历_栈" << endl;
}
void InOrder_stack(Binode* T)
{
   stack<Binode*> s;

   Binode* Bi = T;

   while (Bi || !s.empty())
   {
       if (Bi)
       {
           s.push(Bi);
           Bi = Bi->lchild;
       }
       else {
           Bi = s.top();
           cout << Bi->data;
           s.pop();
           Bi = Bi->rchild;
       }
   }
   cout << "中序遍历_栈" << endl;
}
void PastOrder_stack(Binode* T)
{
   Binode* Bi = T;
   Binode* vis = NULL;
   stack<Binode*> s;
   while (Bi||!s.empty())
   {
       if (Bi)
       {
           s.push(Bi);
           Bi = Bi->lchild;
       }
       else {
           Bi = s.top();
           if (Bi->rchild && vis != Bi->rchild)
               Bi = Bi->rchild;
           else if (( Bi->rchild==NULL) || (vis == Bi->rchild))
           {
               cout << Bi->data;
               vis = Bi;
               s.pop();
               Bi = NULL;
           }
       }
   }
   cout << "后序遍历栈" << endl;
}

void PrevOrderDraw(BiTree T, double x, double y, double xt, double yt,double xp,int time,int dep)//xp为角度,
{
   if (T)
   {
       T->x = x;
       T->y = y;
       setfillcolor(BLUE);
       settextcolor(WHITE);
       setbkmode(TRANSPARENT);
       fillcircle(x, y, 20);
       outtextxy(x - 5, y - 5, T->data);
   }
   if (T->lchild)//左子树
   {
       double i ,j;
       for (i = x,j=y; i >=x - xt,j<=y+yt;) {
           i -= (x - xt) / 500, j =(-yt/xt)*i-(-yt/xt)*x+y;
           line(x,y , i, j);
           Sleep(time);
       }
       setfillcolor(BLUE);
       setbkmode(TRANSPARENT);
       fillcircle(x, y, 20);
       settextcolor(WHITE);
       T->x = x;
       T->y = y;
       outtextxy(x - 5, y - 5, T->data);
       PrevOrderDraw(T->lchild, x - xt, y + yt, xt / 1.1 * abs(cos(xp)), yt / 1.1 * abs(sin(xp)), xp / 2, time + pow(7, dep), dep + 1);
   }

   if (T->rchild)//右子树
   {
       double i, j;
       for (i = x, j = y; i >= x + xt, j <= y + yt;) {
           i += (x + xt) / 500, j = (yt / xt) * i - (yt / xt) * x + y;
           line(x, y, i, j);
           Sleep(time);
       }
       setfillcolor(BLUE);
       setbkmode(TRANSPARENT);
       fillcircle(x, y, 20);
       T->x = x;
       T->y = y;
       settextcolor(WHITE);
       outtextxy(x - 5, y - 5, T->data);
       PrevOrderDraw(T->rchild, x + xt, y + yt, xt / 1.1 * abs(cos(xp)), yt / 1.1 * abs(sin(xp)), xp / 2, time + pow(7, dep), dep + 1);
   }
}

void PrintBiTree(BiTree T)
{
   PrevOrderDraw(T, 360,200, 180* abs(sin(PI / 3)), 180* abs(cos(PI / 3)), PI / 3,3,1);
}

void Draw(BiTree T, double x, double y, double xt, double yt, double xp)//xp为角度,
{
   if (T)
   {
       T->x = x;
       T->y = y;
       setfillcolor(BLUE);
       setbkmode(TRANSPARENT);
       fillcircle(x, y, 20);
       outtextxy(x - 5, y - 5, T->data);
   }
   if (T->lchild)//左子树
   {
       line(x, y, x-xt,y+yt);
       setfillcolor(BLUE);
       setbkmode(TRANSPARENT);
       fillcircle(x, y, 20);
       T->x = x;
       T->y = y;
       outtextxy(x - 5, y - 5, T->data);
       Draw(T->lchild, x - xt, y + yt, xt / 1.1 * abs(cos(xp)), yt / 1.1 * abs(sin(xp)), xp / 2);
   }

   if (T->rchild)//右子树
   {
       line(x, y, x+xt,y+yt);
       setfillcolor(BLUE);
       setbkmode(TRANSPARENT);
       fillcircle(x, y, 20);
       T->x = x;
       T->y = y;
       outtextxy(x - 5, y - 5, T->data);
       Draw(T->rchild, x + xt, y + yt, xt / 1.1 * abs(cos(xp)), yt / 1.1 * abs(sin(xp)), xp / 2);
   }
}

//int main()
//{
//   ifstream file;
//   file.open("test.txt");
//   file >> s1 >> s2 >> s3 >> s4;
//   s = s1;
//
//   BiTree T;
//
//   CreateBiTree(&T,0);
//
//   PrevOrder_stack(T);
//   InOrder_stack(T);
//   PastOrder_stack(T);
//
//   PrintBiTree(T);
//
//
//
//
//   HierarchyOrder(T);
//   cout << "层次遍历栈" << endl;
//   Draw(T, 360, 200, 180 * abs(sin(PI / 3)), 180 * abs(cos(PI / 3)), PI / 3);
//   /*Preordertravers(T);
//   cout << "先序遍历" << endl;
//   Inordertraverse(T);
//   cout << "中序遍历" << endl;
//   Postordertraverse(T);
//   cout << "后序遍历" << endl;*/
//
//
//   Sleep(80000);
//}

   ExMessage msg;
   int x[5], y[5], w[5], h[5];
   x[0] = 260;
   y[0] = 100;
   w[0] = 200;
   h[0] = 50;
   setfillcolor(YELLOW);
   fillroundrect(x[0], y[0], x[0] + w[0], y[0] + h[0], 10, 10);
   botton_table(x[0], y[0], w[0], h[0], "先序遍历");
   x[1] = 260;
   y[1] = 200;
   w[1] = 200;
   h[1] = 50;
   setfillcolor(YELLOW);
   fillroundrect(x[1], y[1], x[1] + w[1], y[1] + h[1], 10, 10);
   botton_table(x[0], y[0], w[0], h[0], "中序遍历");
   x[2] = 260;
   y[2] = 300;
   w[2] = 200;
   h[2] = 50;
   setfillcolor(YELLOW);
   fillroundrect(x[2], y[2], x[2] + w[2], y[2] + h[2], 10, 10);
   botton_table(x[2], y[2], w[2], h[2], "后序遍历");
   x[3] = 260;
   y[3] = 400;
   w[3] = 200;
   h[3] = 50;
   setfillcolor(YELLOW);
   fillroundrect(x[3], y[3], x[3] + w[3], y[3] + h[3], 10, 10);
   botton_table(x[3], y[3], w[3], h[3], "层次遍历");
   x[4] = 260;
   y[4] = 500;
   w[4] = 200;
   h[4] = 50;
   setfillcolor(YELLOW);
   fillroundrect(x[4], y[4], x[4] + w[4], y[4] + h[4], 10, 10);
   botton_table(x[4], y[4], w[4], h[4], "退出");
   bool checkt = 0;
   while (1) {
       if (peekmessage(&msg, EM_MOUSE)) {
           switch (msg.message) {
           case WM_LBUTTONDOWN://点击
               if (msg.x >= x[0] && msg.x <= x[0] + w[0] && msg.y >= y[0] && msg.y <= y[0] + h[0])
               {
                   cleardevice();
                   Draw(T, 360, 200, 180 * abs(sin(PI / 3)), 180 * abs(cos(PI / 3)), PI / 3);
                   Preordertravers(T);
                   cleardevice();
                   showjpg();

               }
               if (msg.x >= x[1] && msg.x <= x[1] + w[1] && msg.y >= y[1] && msg.y <= y[1] + h[1])
               {
                   cleardevice();
                   Draw(T, 360, 200, 180 * abs(sin(PI / 3)), 180 * abs(cos(PI / 3)), PI / 3);
                   Inordertraverse(T);
                   cleardevice();
                   showjpg();
               }
               if (msg.x >= x[2] && msg.x <= x[2] + w[2] && msg.y >= y[2] && msg.y <= y[2] + h[2])
               {
                   cleardevice();
                   Draw(T, 360, 200, 180 * abs(sin(PI / 3)), 180 * abs(cos(PI / 3)), PI / 3);
                   Postordertraverse(T);
                   cleardevice();
                   showjpg();
               }
               if (msg.x >= x[3] && msg.x <= x[3] + w[3] && msg.y >= y[3] && msg.y <= y[3] + h[3])
               {
                   cleardevice();
                   Draw(T, 360, 200, 180 * abs(sin(PI / 3)), 180 * abs(cos(PI / 3)), PI / 3);
                   HierarchyOrder(T);
                   cleardevice();
                   showjpg();
               }
               if (msg.x >= x[4] && msg.x <= x[4] + w[4] && msg.y >= y[4] && msg.y <= y[4] + h[4])
               {
                   checkt = true;
               }
               FlushBatchDraw();
           case WM_MOUSEFIRST://移动
               if (msg.x >= x[0] && msg.x <= x[0] + w[0] && msg.y >= y[0] && msg.y <= y[0] + h[0])
               {
                   setfillcolor(RED);
                   fillroundrect(x[0], y[0], x[0] + w[0], y[0] + h[0], 10, 10);
                   botton_table(x[0], y[0], w[0], h[0], "先序遍历");
               }
               else {
                   setfillcolor(YELLOW);
                   fillroundrect(x[0], y[0], x[0] + w[0], y[0] + h[0], 10, 10);
                   botton_table(x[0], y[0], w[0], h[0], "先序遍历");
               }
               if (msg.x >= x[1] && msg.x <= x[1] + w[1] && msg.y >= y[1] && msg.y <= y[1] + h[1]) {
                   setfillcolor(RED);
                   fillroundrect(x[1], y[1], x[1] + w[1], y[1] + h[1], 10, 10);
                   botton_table(x[1], y[1], w[1], h[1], "中序遍历");
               }
               else {
                   setfillcolor(YELLOW);
                   fillroundrect(x[1], y[1], x[1] + w[1], y[1] + h[1], 10, 10);
                   botton_table(x[1], y[1], w[1], h[1], "中序遍历");
               }
               if (msg.x >= x[2] && msg.x <= x[2] + w[2] && msg.y >= y[2] && msg.y <= y[2] + h[2]) {
                   setfillcolor(RED);
                   fillroundrect(x[2], y[2], x[2] + w[2], y[2] + h[2], 10, 10);
                   botton_table(x[2], y[2], w[2], h[2], "后序遍历");
               }
               else {
                   setfillcolor(YELLOW);
                   fillroundrect(x[2], y[2], x[2] + w[2], y[2] + h[2], 10, 10);
                   botton_table(x[2], y[2], w[2], h[2], "后序遍历");
               }
               if (msg.x >= x[3] && msg.x <= x[3] + w[3] && msg.y >= y[3] && msg.y <= y[3] + h[3]) {
                   setfillcolor(RED);
                   fillroundrect(x[3], y[3], x[3] + w[3], y[3] + h[3], 10, 10);
                   botton_table(x[3], y[3], w[3], h[3], "层次遍历");
               }
               else {
                   setfillcolor(YELLOW);
                   fillroundrect(x[3], y[3], x[3] + w[3], y[3] + h[3], 10, 10);
                   botton_table(x[3], y[3], w[3], h[3], "层次遍历");
               }
               if (msg.x >= x[4] && msg.x <= x[4] + w[4] && msg.y >= y[4] && msg.y <= y[4] + h[4]) {
                   setfillcolor(RED);
                   fillroundrect(x[4], y[4], x[4] + w[4], y[4] + h[4], 10, 10);
                   botton_table(x[4], y[4], w[4], h[4], "退出");
               }
               else {
                   setfillcolor(YELLOW);
                   fillroundrect(x[4], y[4], x[4] + w[4], y[4] + h[4], 10, 10);
                   botton_table(x[4], y[4], w[4], h[4], "退出");
               }

           }
           EndBatchDraw();
       }
       if (checkt) {
           break;
       }
   }
   return;
}

int main() {
   initgraph(720, 720, EW_SHOWCONSOLE);
   ifstream file;
   BiTree T;
   file.open("test.txt");
   file >> s1 >> s2 >> s3 >> s4;
   showjpg();
   BeginBatchDraw();

   ExMessage msg;
   int x[5], y[5], w[5], h[5];
   x[0] = 260;
   y[0] = 100;
   w[0] = 200;
   h[0] = 50;
   setfillcolor(YELLOW);
   fillroundrect(x[0], y[0], x[0] + w[0], y[0] + h[0], 10, 10);
   botton_table(x[0], y[0], w[0], h[0], "Bitree_1");
   x[1] = 260;
   y[1] = 200;
   w[1] = 200;
   h[1] = 50;
   setfillcolor(YELLOW);
   fillroundrect(x[1], y[1], x[1] + w[1], y[1] + h[1], 10, 10);
   botton_table(x[0], y[0], w[0], h[0], "Bitree_2");
   x[2] = 260;
   y[2] = 300;
   w[2] = 200;
   h[2] = 50;
   setfillcolor(YELLOW);
   fillroundrect(x[2], y[2], x[2] + w[2], y[2] + h[2], 10, 10);
   botton_table(x[2], y[2], w[2], h[2], "Bitree_3");
   x[3] = 260;
   y[3] = 400;
   w[3] = 200;
   h[3] = 50;
   setfillcolor(YELLOW);
   fillroundrect(x[3], y[3], x[3] + w[3], y[3] + h[3], 10, 10);
   botton_table(x[3], y[3], w[3], h[3], "Bitree_4");
   x[4] = 260;
   y[4] = 500;
   w[4] = 200;
   h[4] = 50;
   setfillcolor(YELLOW);
   fillroundrect(x[4], y[4], x[4] + w[4], y[4] + h[4], 10, 10);
   botton_table(x[4], y[4], w[4], h[4], "退出");
   bool checkt = 0;
   while (1) {
       if (peekmessage(&msg, EM_MOUSE)) {
           switch (msg.message) {
           case WM_LBUTTONDOWN://点击
               if (msg.x >= x[0] && msg.x <= x[0] + w[0] && msg.y >= y[0] && msg.y <= y[0] + h[0] )
               {

                   s = s1;
                   ip = 0;
                   cleardevice();
                   CreateBiTree(&T);
                   PrintBiTree(T);
                   Sleep(800);
                   cleardevice();
                   showjpg();
                   Orderchoice(T);
               }
               if (msg.x >= x[1] && msg.x <= x[1] + w[1] && msg.y >= y[1] && msg.y <= y[1] + h[1] )
               {
                   s = s2;
                   ip = 0;
                   cleardevice();
                   CreateBiTree(&T);
                   PrintBiTree(T);
                   Sleep(800);
                   cleardevice();
                   showjpg();
                   Orderchoice(T);
               }
               if (msg.x >= x[2] && msg.x <= x[2] + w[2] && msg.y >= y[2] && msg.y <= y[2] + h[2])
               {
                   s = s3;
                   ip = 0;
                   cleardevice();
                   CreateBiTree(&T);
                   PrintBiTree(T);
                   Sleep(800);
                   cleardevice();
                   showjpg();
                   Orderchoice(T);
               }
               if (msg.x >= x[3] && msg.x <= x[3] + w[3] && msg.y >= y[3] && msg.y <= y[3] + h[3])
               {
                   s = s4;
                   ip = 0;
                   CreateBiTree(&T);
                   cleardevice();
                   PrintBiTree(T);
                   Sleep(800);
                   cleardevice();
                   showjpg();
                   Orderchoice(T);
               }
               if (msg.x >= x[4] && msg.x <= x[4] + w[4] && msg.y >= y[4] && msg.y <= y[4] + h[4])
               {
                   checkt = true;
               }
               FlushBatchDraw();
           case WM_MOUSEFIRST://移动
               if (msg.x >= x[0] && msg.x <= x[0] + w[0] && msg.y >= y[0] && msg.y <= y[0] + h[0])
               {
                   setfillcolor(RED);
                   fillroundrect(x[0], y[0], x[0] + w[0], y[0] + h[0], 10, 10);
                   botton_table(x[0], y[0], w[0], h[0], "Bitree_1");
               }
               else {
                   setfillcolor(YELLOW);
                   fillroundrect(x[0], y[0], x[0] + w[0], y[0] + h[0], 10, 10);
                   botton_table(x[0], y[0], w[0], h[0], "Bitree_1");
               }
               if (msg.x >= x[1] && msg.x <= x[1] + w[1] && msg.y >= y[1] && msg.y <= y[1] + h[1]) {
                   setfillcolor(RED);
                   fillroundrect(x[1], y[1], x[1] + w[1], y[1] + h[1], 10, 10);
                   botton_table(x[1], y[1], w[1], h[1], "Bitree_2");
               }
               else {
                   setfillcolor(YELLOW);
                   fillroundrect(x[1], y[1], x[1] + w[1], y[1] + h[1], 10, 10);
                   botton_table(x[1], y[1], w[1], h[1], "Bitree_2");
               }
               if (msg.x >= x[2] && msg.x <= x[2] + w[2] && msg.y >= y[2] && msg.y <= y[2] + h[2]) {
                   setfillcolor(RED);
                   fillroundrect(x[2], y[2], x[2] + w[2], y[2] + h[2], 10, 10);
                   botton_table(x[2], y[2], w[2], h[2], "Bitree_3");
               }
               else {
                   setfillcolor(YELLOW);
                   fillroundrect(x[2], y[2], x[2] + w[2], y[2] + h[2], 10, 10);
                   botton_table(x[2], y[2], w[2], h[2], "Bitree_3");
               }
               if (msg.x >= x[3] && msg.x <= x[3] + w[3] && msg.y >= y[3] && msg.y <= y[3] + h[3]) {
                   setfillcolor(RED);
                   fillroundrect(x[3], y[3], x[3] + w[3], y[3] + h[3], 10, 10);
                   botton_table(x[3], y[3], w[3], h[3], "Bitree_4");
               }
               else {
                   setfillcolor(YELLOW);
                   fillroundrect(x[3], y[3], x[3] + w[3], y[3] + h[3], 10, 10);
                   botton_table(x[3], y[3], w[3], h[3], "Bitree_4");
               }
               if (msg.x >= x[4] && msg.x <= x[4] + w[4] && msg.y >= y[4] && msg.y <= y[4] + h[4]) {
                   setfillcolor(RED);
                   fillroundrect(x[4], y[4], x[4] + w[4], y[4] + h[4], 10, 10);
                   botton_table(x[4], y[4], w[4], h[4], "退出");
               }
               else {
                   setfillcolor(YELLOW);
                   fillroundrect(x[4], y[4], x[4] + w[4], y[4] + h[4], 10, 10);
                   botton_table(x[4], y[4], w[4], h[4], "退出");
               }
           }
           EndBatchDraw();
       }
       if (checkt) {
           break;
       }
   }
   return 0;
}

总结

第一次写这个。。。没啥经验，单纯想发发玩，有什么说错的地方可以指出来。

总体操作不算繁琐，600行轻松解决作业 OvO