-
云南大学软件学院
数据结构实验报告
（本实验项目方案受“教育部人才培养模式创新实验区
（
X3108005
）
”
项目 资助）
实验难度：
A
□
B
□
C
□
序号
1
2
3
指导教师
学号
姓名
成绩
（签名）
学
期：
2010
秋季学期
任课教师
:
朱艳萍
实验题目
:
实验五
树及其应用
小
组
长
:
联系电话
:
电子邮件
:
完成提交时间：
2010
年
12
月
27
日
（下面的内容由学生填写，
格式统一为，
字体
:
楷体
,
行距
:
固定行距
18
，
字号
:
小四，个人报告按下面每一项的百分比打分。难度
A
满分
70
分，难度B
满分
90
分）
一、
【实验构思（
Conceive
）
】
(10%) （本部分应包括：描述实验实现的基本思路，包括所用到的离散数学、工程数学、程
序设计、算法等 相关知识）
本实验需要完成的操作是：
首先让用户输入其想要转化为二叉 树的树，
将用户输入的树以孩子双亲表示法存
储，即需要用户按层次遍历的顺序输入一棵树中每 个结点的信息，则可得出每个结点
对应顺序表中的位置序号，还要让用户输入每个结点所对应的双亲结点 的位置号。
然后通过二重循环将用户输入的树转变为以孩子兄弟法表示的树。
即从第 二个结
点开始循环，如果当前结点为其双亲结点的最左孩子，则将当前结点赋为其双亲结点
的左 孩子；若当前结点不为其双亲结点的最左孩子，说明当前结点为前一个结点的相
邻的兄弟，则将其赋为其 前一个结点的右孩子。
然后把生成的用孩子兄弟表示法表示的顺序表用二叉链表表示成二叉树 ，
实现树
到二叉树的转化。
最后对二叉树进行先序、中序和后序遍历并直接输出遍历序列。
二、
【实验设计
(
Design
)
】
(20%)
（本部分应包括：抽象数据类型的功能规格说明、主程序模块、各子程序模块的伪码
说明，主程 序模块与各子程序模块间的调用关系）
抽象数据类型说明：
creattable( Node table[])
提示用户输入树的相关信息，
即结点的信息和每个结点对应的双亲结点的位置，且将
其转化为以孩子兄弟法表示的顺序表
t able
（即根据用户输入的
data
和
parent
值给
ichild
和
rchild
赋值）
，并将该表打印出来（该表为表示二叉树 的一种方式）
Build ( TreeNode*& current,Node node[], int pos ,int n )
根据以孩子兄弟法表示的顺序表
tab le
（这里调用时为
node
）创建二叉链表
Preorder( TreeNode* root )
对创建成功的二叉链表进行先序遍历，并输出先序序列
InOrder(TreeNode* root)
对创建成功的二叉链表进行中序遍历，并输出中序序列
PostOrder(TreeNode* root)
对创建成功的二叉链表进行后序遍历，并输出后序序列
主程序：
int main(){
Node node [20];
int n = creattable( node );
TreeNode* root = 0;
Build ( root, node, 0 , n);
if (root){
printf(
先序遍历：
n
Preorder ( root );
printf(
中序遍历
: n
InOrder(root);
printf(
后序遍历：
n
PostOrder(root);
}
else
printf(
空树！
n
system(
return 0;
}
主程序与子程序间的调用关系：
Main
Creattable Build Preorder InOrder PostOrder
三、
【实现描述（
Implement
）
】
(30%)
（本部分应包括：抽象数据类型具体实现的函数原型说明、
关键操作实现的伪码算
法、
函数设计、函数间的调用关系，关键的程序流程 图等，给出关键算法的时间复
杂度分析。
）
顺序表和二叉链表的类型：
struct Node { //
以表的形式存储的树结点
char data;
int parent;
int lchild;
int rchild;
};
struct TreeNode { //
以二叉链表存储的树的结点
char data;
TreeNode* left;
TreeNode* right;
};
基本操作实现：
int creattable( Node table[]){ //
创建树的表并转化为二叉树，然后将二叉树以
表的形式表示出来
int n,k,i,j;
char e;
printf(
请输入您要建立的树的结点个数
:(<20)
scanf(
用一个字符输入符接受用户输入结点个数时一定会输入
的回车
if ( n>0 )
{
print f(
请按序输入所有结点信息
:n
即输入结点所带数据，
如
‘
A
’
，
‘
B
’等
for( i = 0; i < n; i++)
{
scanf(
table[i].lchild = table[i].rchild = 0;
}
printf(
您输入的结点对应的位置号为：
n
for( i = 0;i < n; i++)
printf(
printf(
对应位置号，请您按序输入每个 结点对应的双亲结点的位置号：
n
显示用户输入的结点所对应的位置，让用户输入其双亲位置时 有参照
for( i = 0;i < n; i++)
{
printf(
请输入第
%d
个节点的双亲信息：
scanf(
}
}
for( i = 0; i < n; i++ )//
将用户输入的树以孩子兄弟表示法构建，并以表的
形式存储
{
for( j = 1;j < n; j++ )
{
if( table[j].parent == i )
if( table[i].lchild == 0 )//
如果
i
结点是
j
结点的双亲结点，且
i< br>结点的左孩子为空，则
j
赋为
i
的左孩子
{
table[i].lchild = j;
k = j;
}
else//
如果
i
结点的左孩子不为空，说明
j不为
i
的最左孩子，则
j
为其前一个兄弟的右孩子
{
table[k].rchild = j;
k = j;
}
}
}
printf(
您输入的树转化为二叉树表示为：
n
printf(
结点
该结点的双亲
该结点的左孩子
该结点的右孩子
for( i = 0; i < n; i++)
printf(
.data,tabl e[i].parent,table[i].lchild,table[i].rchild);
return n;
}
void Build ( TreeNode*& current,Node node[], int pos ,int n ){ //
将以表的
形式存储的树转化为二叉链表
if (n>0)
{if ( current == 0 ){
current = new TreeNode; //
动态为存储
TreeNode
型的数据分配空间
current->left = current->right = 0;
}
current->data = node[pos].data;
if (node[pos].lchild )
Build( current->left, node, node[pos].lchild, n);//
一直构建当前结点
的左子树
if (node[pos].rchild )
Build( current->right ,node, node[pos].rchild, n);
< br>}//
若当前结点的左子树为空，则构建当前结点的右子树，若当前结点的右子树，
则又 开始构建其双亲结点的右子树
}
void Preorder( TreeNode* root ){ //
对建立好的二叉树按先序遍历
TreeNode* current = root;
if( current != 0 ){
printf(
Preorder( current->left );
Preorder( current->right );
}
}
void InOrder(TreeNode* root)//
对建立好的二叉树按中序遍历
{
TreeNode* current = root;
if(current != 0)
{
InOrder(current->left);
printf(
InOrder(current->right);
}
}
void PostOrder(TreeNode* root)//
对建立好的二叉树按后序遍历
{
}
TreeNode* current = root;
if(current != 0)
{
PostOrder(current->left);
PostOrder(current->right);
printf(
}
关键操作的时间复杂度分析：
< br>Creattable
（
)
函数的时间复杂度为
O
（
n^2
）
，
Build ()Preorder()
、
InOrde r()
、
PostOrder()
函数的时间复杂度为
O
（
n
）
关键的程序流程图
:
-
-
-
-
-
-
-
-
本文更新与2021-01-25 09:03，由作者提供，不代表本网站立场，转载请注明出处：https://www.bjmy2z.cn/gaokao/565015.html
-
上一篇：新概念英语——语文章翻译
下一篇：(A)英语翻译高级口译英译中文化历史(一)