说明

\n

\n\t实验原理：\n

\n

\n\t　　二叉树是最重要的一类树型结构。二叉链表是二叉树的一种比较直观和灵活的存储结构。在二叉链表中的每个结点由三部分组成：左孩子指针、右孩子指针和结点数据。\n

\n

\n\t　　其中左右孩子指针分别指向本结点的左右孩子结点，如果一个结点的左右孩子不存在，则对应的指针记录为空值，C语言用NULL表示，画图时用^表示。\n

\n

\n\t　　结点数据的数据类型应该根据实际应用选择，在本次实验中，为了方便输入和输出，我们选用字符类型。\n

\n

\n\t \n

\n

\n\t　　输入创建原理：\n

\n

\n\t　　二叉树虽然可以很复杂，但是创建二叉树可以用递归方式进行，代码只需要几行，下面我们用伪代码来描述创建流程：\n

\n

\n\t　　１、结点* 创建结点函数(){\n

\n

\n\t 定义结点数据;\n

\n

\n\t　　　　　　输入结点数据;\n

\n

\n\t　　　　　　如果　结点数据为空　则返回NULL;//这里比较重要，我们规定输入字符^表示本结点不创建\n

\n

\n\t　　　　　　创建结点* node;\n

\n

\n\t　　　　　　赋值node的数据为刚刚输入的结点数据;\n

\n

\n\t　　　　　　node.左孩子=创建结点函数();\n

\n

\n\t　　　　　　node.右孩子=创建结点函数();\n

\n

\n\t　　　　　　返回 node;\n

\n

\n\t }\n

\n

\n\t　　２、在需要创建整课二叉树的地方写上：\n

\n

\n\t　　　　　　　二叉树根结点　＝　创建结点函数()；\n

\n

\n\t 　遍历原理：先根遍历、后根遍历、中根遍历原理，请自行补充，\n

\n

\n\t \n

\n

\n\t实验步骤：\n

\n

\n\t　　１、定义二叉链表结点类型；\n

\n

\n\t　　２、实现二叉链表创建方法；\n

\n

\n\t　　３、实现二叉链表的三种遍历方法；\n

\n

\n\t　　４、实现主函数\n

\n

\n\t　　\n

\n

\n\t思考题：\n

\n

\n\t　　1：为什么很多数据结构会有遍历的需求？\n

\n

\n\t　　2：如何干净地释放整棵二叉树动态申请的所有结点？\n

\n

\n\t \n

\n

\n\t程欣宇2014年4月\n

\n

输入格式

\n

\n\t每行一棵非空的二叉树，每棵二叉树按先序遍历形式，空指针用字符^占位，如图的一棵二叉树。\n

\n

\n\t如果读到一行的第一个字符就是^，表示没有更多输入了，程序退出。\n

\n

\n\t测试时，每棵树不会超过20个结点。\n

\n

\n\t

统计

递交统计

数据结构/二叉树/创建与遍历

信息

状态

开发

支持

关于

还没有账户？

登录