数据结构实验报告-树(二叉树)

2024年2月7日发(作者：)

实验5：树（二叉树）（采用二叉链表存储）

一、 实验项目名称

二叉树及其应用

二、 实验目的

熟悉二叉树的存储结构的特性以及二叉树的基本操作。

三、 实验基本原理

之前我们都是学习的线性结构，这次我们就开始学习非线性结构——树。线性结构中结点间具有唯一前驱、唯一后继关系，而非线性结构中结点的前驱、后继的关系并不具有唯一性。在树结构中，节点间关系是前驱唯一而后继不唯一，即结点之间是一对多的关系。直观地看，树结构是具有分支关系的结构（其分叉、分层的特征类似于自然界中的树）。

四、 主要仪器设备及耗材

Window 11、Dev-C++5.11

五、 实验步骤

1. 导入库和预定义

2. 创建二叉树

3. 前序遍历

4. 中序遍历

5. 后序遍历

6. 总结点数

7. 叶子节点数

8. 树的深度

9. 树根到叶子的最长路径

10. 交换所有节点的左右子女

11. 顺序存储

12. 显示顺序存储

13. 测试函数和主函数

对二叉树的每一个操作写测试函数，然后在主函数用while+switch-case的方式实现一个带菜单的简易测试程序，代码见“实验完整代码”。

实验完整代码：

#include

using namespace std;

#define MAX_TREE_SIZE 100

typedef char ElemType;

ElemType SqBiTree[MAX_TREE_SIZE];

struct BiTNode

{

ElemType data;

BiTNode *l,*r;

}*T;

void createBiTree(BiTNode *&T)

{

ElemType e;

e = getchar();

{

if(!(T = (BiTNode *)malloc(sizeof (BiTNode))))

{

}

cout << "内存分配错误!" << endl;

exit(0);

return;

T = NULL;

if(e == 'n')

else if(e == ' ')

else

}

}

T->data = e;

createBiTree(T->l);

createBiTree(T->r);

void createBiTree2(BiTNode *T,int u)

{

if(T)

{

}

}

void outputBiTree2(int n)

{

int cnt = 0;

for(int i = 0;cnt <= n;i++)

{

}

cout << endl;

}

void preOrderTraverse(BiTNode *T)

{

if(T)

{

}

}

void inOrderTraverse(BiTNode *T)

{

if(T)

{

inOrderTraverse(T->l);

cout << T->data;

cout << T->data;

preOrderTraverse(T->l);

preOrderTraverse(T->r);

cout << SqBiTree[i];

if(SqBiTree[i] != ' ')

cnt ++;

SqBiTree[u] = T->data;

createBiTree2(T->l,2 * u + 1);

createBiTree2(T->r,2 * u + 2);

}

}

inOrderTraverse(T->r);

void beOrderTraverse(BiTNode *T)

{

if(T)

{

}

}

int sumOfVer(BiTNode *T)

{

if(!T)

}

int sumOfLeaf(BiTNode *T)

{

if(!T)

}

int depth(BiTNode *T)

{

if(!T)

}

bool LongestPath(int dist,int dist2,vector &ne,BiTNode *T)

{

if(!T)

if(dist2 == dist)

return false;

return 0;

return max(depth(T->l),depth(T->r)) + 1;

return 0;

return 1;

if(T->l == NULL && T->r == NULL)

return sumOfLeaf(T->l) + sumOfLeaf(T->r);

return 0;

beOrderTraverse(T->l);

beOrderTraverse(T->r);

cout << T->data;

return sumOfVer(T->l) + sumOfVer(T->r) + 1;

{

}

return true;

if(LongestPath(dist,dist2 + 1,ne,T->l))

_back(T->l->data);

return true;

else if(LongestPath(dist,dist2 + 1,ne,T->r))

{

}

return false;

}

void swapVer(BiTNode *&T)

{

if(T)

{

}

}

//以下是测试程序

void test1()

{

getchar();

cout << "请以先序次序输入二叉树结点的值，空结点用空格表示:" << endl;

createBiTree(T);

cout << "二叉树创建成功!" << endl;

}

void test2()

{

cout << "二叉树的前序遍历为:" << endl;

preOrderTraverse(T);

cout << endl;

}

swapVer(T->l);

swapVer(T->r);

BiTNode *tmp = T->l;

T->l = T->r;

T->r = tmp;

_back(T->r->data);

return true;

void test3()

{

cout << "二叉树的中序遍历为:" << endl;

inOrderTraverse(T);

cout << endl;

}

void test4()

{

cout << "二叉树的后序遍历为:" << endl;

beOrderTraverse(T);

cout << endl;

}

void test5()

{

cout << "二叉树的总结点数为：" << sumOfVer(T) << endl;

}

void test6()

{

cout << "二叉树的叶子结点数为：" << sumOfLeaf(T) << endl;

}

void test7()

{

cout << "二叉树的深度为：" << depth(T) << endl;

}

void test8()

{

int dist = depth(T);

vector ne;

cout << "树根到叶子的最长路径:" << endl;

LongestPath(dist,1,ne,T);

_back(T->data);

reverse((),());

cout << ne[0];

for(int i = 1;i < ();i++)

}

cout << "->" << ne[i];

cout << endl;

void test9()

{

swapVer(T);

cout << "操作成功!" << endl;

}

void test10()

{

memset(SqBiTree,' ',sizeof SqBiTree);

createBiTree2(T,0);

cout << "操作成功!" << endl;

}

void test11()

{

int n = sumOfVer(T);

outputBiTree2(n);

}

int main()

{

int op = 0;

while(op != 12)

{

cout << "-----------------menu--------------------" << endl;

cout << "--------------1：创建二叉树--------------" << endl;

cout << "--------------2：前序遍历----------------" << endl;

cout << "--------------3：中序遍历----------------" << endl;

cout << "--------------4：后序遍历----------------" << endl;

cout << "--------------5：总结点数----------------" << endl;

cout << "--------------6：叶子节点数--------------" << endl;

cout << "--------------7：树的深度----------------" << endl;

cout << "--------------8：树根到叶子的最长路径----" << endl;

cout << "--------------9：交换所有节点左右子女----" << endl;

cout << "--------------10：顺序存储---------------" << endl;

cout << "--------------11：显示顺序存储-----------" << endl;

cout << "--------------12：退出测试程序-----------" << endl;

cout << "请输入指令编号:" << endl;

if(!(cin >> op))

{

();

(INT_MAX,'n');

}

cout << "请输入整数!" << endl;

continue;

switch(op)

{

case 1:

test1();

break;

test2();

break;

test3();

break;

test4();

break;

test5();

break;

test6();

break;

test7();

break;

test8();

break;

test9();

break;

test10();

break;

test11();

break;

cout << "测试结束!" << endl;

break;

cout << "请输入正确的指令编号!" << endl;

case 2:

case 3:

case 4:

case 5:

case 6:

case 7:

case 8:

case 9:

case 10:

case 11:

case 12:

default:

}

}

return 0;

}

六、 实验数据及处理结果

测试用例：

1. 创建二叉树（二叉链表形式）

2. 前序遍历

3. 中序遍历

4. 后序遍历

5. 总结点数

6. 叶子结点数

7. 树的深度

8. 树根到叶子的最长路径

9. 交换所有左右子女

10. 顺序存储

七、 思考讨论题或体会或对改进实验的建议

通过这次实验，我掌握了二叉树的顺序存储和链式存储，体会了二叉树的存储结构的特性，掌握了二叉树的树上相关操作。

八、 参考资料

《数据结构（C语言版）》 严蔚敏，吴伟民著