2012数据结构课程设计报告

树与二叉树的转换

沈阳航空航天大学

课 程 设 计 报 告

课程设计名称：课程设计题目：

院（系）：专 业：班 级：学 号：姓 名：指导教师：完成日期：

数据结构课程设计 树与二叉树转换

树与二叉树的转换

目 录

第1章

题目内容与要求............................................................................................. 1

1 基本功能 ................................................................................................................... 1 2 功能分解 ................................................................................................................... 1 第2章 系统模块结构及流程图 .................................................................................. 2 2.1创建模块 ................................................................................................................. 2 2.2遍历模块 ................................................................................................................. 4 2.3转换模块 ................................................................................................................. 8 2.4线索化模块 ............................................................................................................. 9 2.5主模块 ................................................................................... 错误！未定义书签。 第3章 数据结构的描述 ............................................................................................ 12 第4章 涉及函数的描述 .............................................................................................. 13 第5章 测试运行结果 ................................................................................................ 14 参考文献 ........................................................................................................................ 16 附 录（程序清单） .................................................................................................. 17

树与二叉树的转换

第1章 题目内容与要求

1 基本功能

内容：写一个程序，利用双亲法创建一棵树，将该树转换为二叉链表表示，并给出二叉树的先序、中序、后序的遍历结果以及对该二叉树进行中序遍历线索化。 要求：

1) 给出树的双亲表示和二叉链表表示的存储结构； 2) 要求二叉树三种遍历要采用非递归算法；

3) 给出动态演示（选做）；

2 功能分解

CreateTree(T)：用双亲法建一棵树；

操作函数 （1）PreOrder(ct)：先序非递归方法遍历二叉树； （2）InOrder(ct)：中序非递归方法遍历二叉树； （3）PostOrder(ct)：后续非递归方法遍历二叉树；

（4）InThreading(ct)：中序线索化二叉树；

（5）PTreeToCSTree(T,0)：将树转换为二叉链表表示的二叉树；

main( )：输出主菜单，根据需要输入菜单上对应功能的数字调用各个函数，实现功能；

树与二叉树的转换

第2章 系统模块结构及流程图

本程序主要分为四个模块（见图1）：创建模块，转换模块，遍历模块，线索化模块。创建模块：利用双亲法创建一棵树。转换模块：将双亲法建立的树转换为二叉链表表示的孩子—兄弟表示法，转换为二叉树。遍历模块：将转换后的二叉树进行前序、中序和后序的非递归遍历。线索化模块：将转换后的二叉树进行

图1 功能模块图

2.1创建模块

利用双亲法创建一棵树的操作，流程如图2.1所示：

树与二叉树的转换

沈阳航空航天大学课程设计报告

第1章

概要设计

开始 NT.nodes[0].data!=NULL

YT.nodes[0].parent=-1;

i<MAX_TREE_SIZE

YDeQueue(q,);

N

k=1

r[k-1]!=' ';

Yscanf("%c",&r[k]);

N

k++ T.n=0;

j=0

j<k

Yr[j]==' '

N N

YT.nodes[i].data=NULL; T.nodes[i].data=r[j];

r[j]!=' '

YEnQueue(q,); i++

N

j++

-3-

树与二叉树的转换

图2.1 双亲法建树的流程图

2.2遍历模块

用非递归算法将转换后的二叉树进行先序、中序和后序的非递归遍历。其中先序遍历的流程如图2.21所示，中序遍历的流程图如图2.22所示，后序的非递归遍历流程图如图2.23所示。

树与二叉树的转换

图2.21 遍历模块中先序遍历的流程图

树与二叉树的转换

图2.22 遍历模块中中序遍历的流程图

树与二叉树的转换

沈阳航空航天大学课程设计报告 开始linkstack *S;

第 2 章 详细设计

p||!Emptystack(S)

Y

N

p!=q

N Yp

N Y

Push(S,p);

p->firstchild

Yp=p->firstchild;

Np=p->nextsibling

Emptystack(S)

Ybreak;

N

Gettop(S,q);

q->nextsibling==p

N

Yp=(CSTree)malloc(sizeof(CSNode)); p=q->nextsibling;

flag == p->data

N

Yp=(CSTree)malloc(sizeof(CSNode));

结束-7-

树与二叉树的转换

图2.23 遍历模块中后序遍历流程图

2.3转换模块

将用双亲法创建的树转化为二叉链表表示的二叉树，模块具体流程如图2.3所示。

图2.3 转换模块流程图

树与二叉树的转换

2.4线索化模块

将转换后的二叉树进行中序遍历线索化，即按照中序遍历顺序，若结点没有左孩子，则指向它的前驱，如果没有右孩子，就指向该结点的后继。具体流程图如图2.4所示。

树与二叉树的转换

图2.4 线索化模块流程图

2.5主模块

输出主菜单，根据需要输入菜单上对应功能的数字调用各个函数，实现各种功能。流程图如下图2.5.

树与二叉树的转换

沈阳航空航天大学课程设计报告

第 2 章 详细设计

K=5

YPostOrder(ct)

N

break

InOrder break

K=6

N Y

InThreading(ct) break

K=7

N Yprintf("\n\n 退出\n\n") printf("\n 序号不对\n")

break

break

结束

-11-

树与二叉树的转换

第3章 数据结构的描述

树是一种非线性的数据结构，树中的元素之间是一对多的层次关系。树有以

下三种常用的存储结构，即双亲表示法、孩子表示法和孩子兄弟表示法（二叉链表法）。本实验要实现的第一个功能就是将用双亲表示法建立的树转换为二叉树，即将树的双亲表示法转换为孩子兄弟表示法。 …… 此处隐藏：3144字，全部文档内容请下载后查看。喜欢就下载吧 ……