数据结构课程设计树的应用

数据结构 课程设计报告

设计题目：树的应用

年 级 2010级 班 级 计科105 姓 名 聂永胜 赵攀攀 张姣姣 学 号 20101515506 20101515526 20101515511 指导教师 李晓辉 起止时间 12—9—24-----------9—28

2012--2013 年 一 学期

一．实习目的

更加深入的理解、掌握数据结构的一些算法并加以实现，提高自身的地动手实践能力，培养更好的团队合作能力。

二．问题描述（具体任务）

设计、创建一棵树，实现树与二叉树的互相转换以及对树的递归 非递归先序遍历，树的递归非递归后序遍历以及树的非递归层次遍历的操作。

三．需求分析

1、本演示程序中，可以输入任意个节点构造你想要的树，本程序构造时默认的是一个三度的树，也就是在创建树时所默认的是每个节点都有三个孩子，但是你可以通过键盘输入#号来让某些节点为空，以此来创建让您满意的树。

2、程序以用户和计算机对话的形式执行，即在计算机终端上显示“提示信息”之后，由用户在键盘上输入要创建树的节点值，然后通过程序执行输出结果。 3、程序的执行命令包括： （1）树的创建模块

（2）树与二叉树相互转换模块

（3）树的先序、后序、层次遍历（递归与非递归算法） 4、测试数据：

（1）测试数据由用户从键盘上任意输入。

四．算法设计思想及流程图

（1）根据老师所提供的课程设计题目及要求我们将程序分了9个模块，通过主程序调用相应的模块来实现课程的操作。

开始 创建树 树的递归先序遍历 树的递归后序遍历 树的非递归层次遍历 树转换为二叉树 二叉树非递归先序遍历 二叉树非递归中序遍历 二叉树非递归先序遍历 二叉树转换为树 按前序，后序，层次遍历此树 结束

五．C++语言源代码

#include using namespace std; #define m 3

typedef char ElemType; typedef struct Node {

ElemType data; struct Node* child[m];

}Node,*Tree;

typedef struct BiTNode{

ElemType data;

struct BiTNode*lchild,*rchild;

}BiTNode,*BiTree;

typedef struct stack { //栈结构定义

BiTree data[100]; //data 元素类型为 指针 int top; //栈顶指针 }seqstack;

// 按前序遍历 创建一棵度数为3的树的递归算法 void createtree(Tree &p) {

}

int i; char ch;

if((ch=getchar())=='#') p=NULL; //建立一棵空树 else { }

p=(Tree)malloc(sizeof(Node)); p->data=ch; for(i=0;icreatetree(p->child[i]);

//树转化为二叉树

BiTree TreetoBiTree(Tree &p) { int i; if(p==NULL)

return NULL;

BiTNode* q=(BiTNode*)malloc(sizeof(ElemType)) ;//创建根节点

------------------------------------------------------------

q->data =p->data; q->lchild=NULL; q->rchild=NULL;

if(p->child[0]!=NULL){

q->lchild=TreetoBiTree(p->child[0]);//把树的第一个孩子赋给二

叉树的左孩子 }

else if((p->child[1]!=NULL)){ BiTNode* r=q->lchild; if(p->child[1]!=NULL) { }

else if(p->child[2]!=NULL){ } else

return q;

r->rchild=TreetoBiTree(p->child [2]); r=r->rchild;

for(i=1;iif(p->child[i]!=NULL) { } else

return q;

r->rchild=TreetoBiTree(p->child [i]); r=r->rchild;

q->lchild=TreetoBiTree(p->child[1]); //把树的第二个孩子赋

给二叉树的左孩子 }

else if(p->child[2]!=NULL) {

q->lchild=TreetoBiTree(p->child[1]); //把树的第三个孩子赋BiTNode* r=q->lchild; if(p->child[2]!=NULL) { } else

return q;

r->rchild=TreetoBiTree(p->child [2]);

给二叉树的左孩子 }

//二叉树转换为树

Tree BiTreetoTree(BiTree &q) { int i;

if(q==NULL)return NULL;

Node* p=(Node*)malloc(sizeof(ElemType)); } return q;

}

p->data=q->data;//根赋值 for(i=0;iif(q->lchild!=NULL) { } return p;

p->child[0]=BiTreetoTree(q->lchild); BiTNode* r=q->lchild ; for(i=1;iif(r->rchild!=NULL) { }

p->child[i]=BiTreetoTree(r->rchild ); r=r->rchild ; p->child[i]=NULL;

void push(seqstack* s,BiTree p) { //进栈 s->data[++s->top]=p; }

BiTree pop(seqstack* s) { //出栈

if(s->top!=-1) { //非递归遍历中，top初始值为-1 s->top--;

return (s->data[s->top+1]); } else

return NULL; }

//二叉树中序遍历 (树的后序非递归遍历)非递归 算法

void inorder1(BiTree p) { seqstack s; s.top=-1;

while((p!=NULL)||(s.top!=-1)) { while(p) {

push(&s,p);

p=p->lchild; //子树根结点全部进栈 }

if(s.top!=-1) { p=pop(&s);

printf(\"%c\ //输出根结点，其实也就是左孩子或右孩子

(没有孩子的根结点是它父亲的左或右孩子） p=p->rchild; //进入右孩子访问 } } }

void visit(char ch) {cout<//二叉树先序遍历非递归算法 void PreOrderPrint(BiTree p) {

seqstack s;

s.top=-1; //top初始值为-1 while((p!=NULL)||(s.top!=-1)) { // 当前处理的子树 不为空，或栈不为空，则循环

while(p) {

visit(p->data); //访问当前子树根结点 s.top++;

s.data[s.top]=p; //当前子树根结点进栈(因为

还要访问右子树)

p=p->lchild; //访问此根结点 左孩子

} //循环直到遍历完当前子树根结点，和其左孩子

if(s.top>-1) {

p=pop(&s); //当前子树跟结点出栈 p=p->rchild; //访问其右孩子 } } }

//树的前序遍历递归算法

void preorder(Tree p) { //P为指向树根的指针 }

//树的后序遍历的递归算法 void postorder(Tree p) { int i;

if(p!=NULL) { int i;

if(p!=NULL) { //树不为空 }

printf(\"%c\ //输出根节点的值

for(i=0;ipreorder(p->child[i]);

}

}

for(i=0;ipostorder(p->child[i]);

printf(\"%c\ //输出根节点的值

//树的非递归层次遍历 void level(Tree t) {

Tree queue[20]; //存放等待访问的节点队列,每个元素都是指针型 int f=0,r=0,i; //f,r 分别是队头,队尾指针 Tree p; queue[0]=t; while(f<=r) { }

p=queue[f]; f++;

printf(\"%c\ //访问队头元素

for(i=0;iif(p->child[i]) { } ++r;

queue[r]=p->child[i];

}

void main() {

system(\"color 1F\"); //设置控制台的背景色为蓝色 printf(\"\\**********************************\\n\");

printf(\"\\ 第五组实验内容：树的应用 \\n\");

printf(\"\\ 组员：赵攀攀，张姣姣，聂永胜 printf(\"\\**********************************\\n\"); Tree T; Tree T1; BiTree p;

printf(\"=====输入要创建的树=====:\\n\"); createtree(T);//创建 一棵树 printf(\"\\n树的先序递归遍历:\"); preorder(T);

printf(\"\\n树的后序递归遍历:\"); postorder(T);

printf(\"\\n树的层序非递归遍历:\");

level(T);

printf(\"\\n\"); printf(\"\\n=====树转换为二叉树=====\\n\");

p=TreetoBiTree(T);

printf(\"\\n二叉树先序非递归遍历(树的先序非递归):\");

\\n\");

PreOrderPrint(p);

printf(\"\\n二叉树中序非递归遍历(树的后序非递归):\");

inorder1(p);

printf(\"\\n\");

printf(\"\\n=====二叉树转换为树=====\\n\");

T1=BiTreetoTree(p);

printf(\"\\n按先序递归遍历此树:\"); preorder(T1); printf(\"\\n\");

printf(\"\\n按后序递归遍历此树:\"); postorder(T1); printf(\"\\n\");

printf(\"\\n按层次非递归遍历此树:\"); level(T1); printf(\"\\n\"); return ; }

六．测试分析（运行结果）

比如说输入以下内容：

RAD###E####B###CFG###H###K##### 将会输出下面内容：

树的先序递归遍历：RADEBCFGHK

树的后序递归遍历：DEABGHKFCR 树的层次非递归遍历：RABCDEFGHK ====树转换为二叉树====

二叉树先序非递归遍历（树的先序非递归）：RADEBCFGHK 二叉树中序非递归遍历（树的后序非递归）：DEABGHKFCR ====二叉树转换为树====

按先序递归遍历此树：RADEBCFGHK 按按后序递归遍历此树：DEABGHKFCR 按按后序递归遍历此树: RABCDEFGHK

七．总结（收获及体会）

1、收获及体会；

在学习数据结构这门课的时候，对一些算法的设计和应用并不是

太理解，而且不知道怎么结合实际去实现这些算法，这次课程设计，我们通过各种途径去掌握了解树的应用各个分块的算法并加以实现，使我们对树的各种操作得到了很好的掌握，刚开始时一直在选用树的存储结构上产生了意见分歧，一直纠结徘徊在是用孩子兄弟法还是孩子法来创建，最后考虑到后面的遍历操作，我们统一了意见，决定采用孩子法。在编程过程中我们遇到了很多问题，最终都是通过资料的查询及小组成员的讨克了一个又一个的难题，在此期间我们充分认识到了团队合作的重要性，这对于以后我们的工作起到了一个很好的磨砺机会。这次的实习让我们收获到的不仅仅是知识的积累与巩固，更重要的是对团队合作的认识。

2、在此部分最后部分注明每位同学所做的具体工作。

对于此次课程设计，我们小组做了明确的分工，在程序的9个模

块中，聂永胜同学主要负责树的创建，树转换为二叉树及二叉树转换为树三个模块，张姣姣同学负责树的先序递归遍历，树的后序递归遍历以及主程序对各个模块的融合三个模块，赵攀攀同学负责树的先序，后序，层次的非递归遍历三个模块，在每个人将其工作任务完成后再将自己的编程思想讲授给另外两个同学，做到融会贯通。

八．参考文献

网上资料结合课本知识，再加上我们的不懈努力。