计算机数据结构课设--二叉树课设论文

辽宁工业大学

课 程 设 计 说 明 书

题目： 数据结构课程设计 --二叉树

学院（系）： 电子与信息工程学院 专业班级： 计算机 学 号： 学生姓名： 指导教师： 姜悦岭 教师职称： 副 教 授 起止时间：

课程设计（论文）任务及评语

院（系）：电子与信息工程 教研室： 软件工程 学 号 课程设计（论文）题目 1．从十个题目中选择一个题目,，要求每个题目用标准的C语言程序实现，另外,完成思考 学生姓名 专业班级 计算机科学与技术 数据结构与算法课程设计 课程设计（论文）任务题一题，思考题须写出相应的类C算法即可。 2．每个题目编写源程序时，要求有主菜单,每个子功能定义为相应的子函数，在主函数中调用各子函数，程序结构清晰。 3． 根据题目,选择合适的逻辑结构和存储结构。 4． 输入的数据由键盘输入。 5． 分析算法的时间复杂度，要求算法的效率尽可能高。 6． 验证排序算法的稳定性。 指导教师评语及成绩 成绩： 指导教师签字： 2013 年 7 月 13 日

目 录

第1章 课程设计目的与要求 ................................................................................................... 1

1.1 课程设计目的 ............................................................................................................................... 1 1.2 课程设计的实验环境 ................................................................................................................... 1 1.3 课程设计的预备知识 ................................................................................................................... 1 1.4 课程设计要求 ............................................................................................................................... 1

第2章 课程设计内容 ............................................................................................................... 2

2.1题目的选择 .................................................................................................................................... 2 2.2 题目的具体实现 ........................................................................................................................... 2 2.3 思考题解析 ................................................................................................................................. 13

总 结 ......................................................................................................................................... 16 参考文献 ................................................................................................................................... 17

第1章 课程设计目的与要求

1.1 课程设计目的

本课程设计是计算机科学与技术专业的技术实践课。

本实践课的主要目的是：使学生学会利用在课堂中所学的理论知识，应用到实际中，解决相应的实际问题，深入理解和灵活掌握并应用所学的内容，培养学生理论结合实际的能力，培养学生发现问题分析问题解决问题的能力。同时，在实验步骤规范化程序设计方法等方面受到比较系统有力和规范的训练。通过实践设计使学生进一步加深对程序的规范性及对复杂程序设计步骤的理解。 1.2 课程设计的实验环境 Visual C++ 6.0 。 1.3 课程设计的预备知识 C语言程序设计、数据结构。 1.4 课程设计要求

（1） 了解并掌握数据结构预算法的设计方法，具备初步的分析和设计能力； （2） 初步掌握程序设计过程的问题分析，设计，程序编码，测试等基本方法和技

能；

（3） 提高综合运用所学的理论知识和方法分析和解决问题的能力； （4） 训练用系统的观点和程序开发一般规范进行程序开发，培养软件工作者所应;

具备的科学的工作方法和作风；

（5） 设计题目要求达到一定工作量（200行以上代码），并具有一定的深度和难度； （6） 编写出课程设计说明书，说明书不少于10页；

（7） 硬件：每个学生需配备计算机一台。操作系统： Windows. （8） 软件：Visual C++ 6.0；

（9） 将所选题目封装在一个主函数中。

1

第2章 课程设计内容

2.1题目的选择

9. 树的综合操作

2.2 题目的具体实现

（1）题目应实现的具体功能；

①创建二叉树的存储结构并保存（二叉链表）； ②非递归实现中序遍历二叉树； ③非递归实现先序遍历二叉树； ④递归实现先序遍历二叉树； ⑤求出二叉树的叶子结点数和层次数。 （2）题目所选择的数据结构及存储结构；

逻辑结构为树状结构,树的存储结构为链式存储结构 （3）需求分析：

1) 输入输出形式皆为字符（char）形式，输入是要输入一个完整的二叉树的先序遍历序列，才能成功建树（要注意空树的表达）。

2) 此程序能实现二叉树的创建，非递归先序，非递归中序遍历，递归层次遍历，求树的高度和叶子数功能。

3) 如果输入的不是一棵树的先序序列，则树无法建成，其他功能将无法实现。

2

（4）完整的源程序 # include # include # define stacksize 20 typedef struct lnode {

char data;

struct lnode *lchild,*rchild;

} lnode , *tree; typedef struct {

tree *base; tree *top; int size;

} seqstack; typedef struct qnode {

tree data; struct qnode *next;

}qnode,*queueptr; typedef struct {

queueptr front; queueptr rear;

}linkqueue;

void initqueue(linkqueue &q) //建队列 { }

3

q.front=q.rear=(queueptr)malloc(sizeof(qnode)); q.front->next=0;

void enqueue(linkqueue &q,tree &t) //入队列 { queueptr s;

s=(queueptr)malloc(sizeof(qnode)); s->data=t; s->next=0; q.rear->next=s; q.rear=s;

}

tree delqueue(linkqueue &q) { tree e; qnode *p; p=q.front->next; e=p->data;

q.front->next=p->next; if(q.rear==p)

q.rear=q.front;

free(p);

return(e); }

void creat(tree &t) //建树{ char ch; scanf(\"%c\ if(ch=='.') t=0; else {

t =(tree)malloc(sizeof(lnode));

//出队列4

}

}

t->data=ch; creat(t->lchild); creat(t->rchild);

void initstack(seqstack &s) //建立一个栈 { }

void push (seqstack &s,tree e) //入栈 { }

void pop(seqstack &s,tree &e) //出栈 { }

void preorder(tree t) //非递归先序遍历 {

seqstack s; initstack(s); tree p=t;

while (p!=0||!(s.base==s.top))

{ --s.top; e=*s.top; *s.top=e; ++s.top;

s.base=(tree *)malloc(stacksize * sizeof(tree)); s.top=s.base; s.size=stacksize;

while (p!=0) //遍历左子树

5

{

printf(\"%c \ push(s,p); p=p->lchild;

}

if (!(s.base==s.top)) //通过下一次循环中的内嵌while实现右子树遍历

{

pop(s,p);

p=p->rchild; }

}

}

void inorder (tree &t) {

seqstack s; initstack(s); tree p=t;

while(p!=0||!(s.top == s.base)) {

while(p!=0) {

push(s ,p ); p=p->lchild; }

if(!(s.top == s.base)) {

pop(s,p); printf(\"%c \ p=p->rchild; }

//非递归中序遍历 //栈不空 //遍历左子树 //入栈 //栈不空 //出栈 6

} }

int postorderdepth(tree t) //用后根遍历求树的层次数 {

int p,q,r; if (t!=0) {

p=postorderdepth( t->lchild ); //求左子树的深度 q=postorderdepth( t->rchild ); //求右子树的深度

r=p>q?p:q; //得到左、右子树深度较大者 return(r+1); //返回树的深度 }

else return(0); //如果为空，则返回0 }

int leaf(tree t) //求叶子个数 { if(!t) return(0);

else if (!t->lchild&&!t->rchild) return(1); else

return(leaf(t->lchild )+leaf(t->rchild )); }

void levelorder(tree t,linkqueue &q) //层次遍历 {

tree m;

if(t&&q.front!=q.rear) {

m=delqueue(q);

printf(\"%c \

7

}

}

t=m;

if(t->lchild) //将左孩子入队列 enqueue(q,t->lchild);

if(t->rchild) //将右孩子入队列 enqueue(q,t->rchild);

levelorder(t,q); //递归

void tips() //菜单 {

printf(\"please choose the way to visit：\\n\"); printf(\"<1> preorder\\n\"); printf(\"<2> inorder\\n\"); printf(\"<3> levelorder\\n\"); printf(\"<4> postorderdepth\\n\"); printf(\"<5> leaf\\n\"); printf(\"<0> exit\\n\"); }

void main() //主函数 {

tree t; linkqueue q; int m,n,a;

printf(\"please in put a lot of letters.\\n\"); creat(t);

tips();

scanf(\"%d\

while(a) {

switch(a)

8

{

case 1:

printf(\"the preorder is :\\n\");

preorder(t); printf(\"\\n\");

break;

case 2:

printf(\"the inorder is :\\n\");

inorder (t);

printf(\"\\n\");

break;

case 3:

printf(\"the levelorder is :\\n\"); initqueue(q);

enqueue(q,t);

levelorder(t,q); printf(\"\\n\");

break;

case 4:

printf(\"the postorderdepth is :\\n\"); m=postorderdepth (t);

printf(\"the depth of the tree is %d \\n\break;

case 5:

printf(\"the leaf is :\\n\");

n=leaf (t);

printf(\"the number of leaf is %d.\\n\break;

}

tips();

9

scanf(\"%d\ }

（4）程序的输入和输出

创建二叉树的操作：

输入树的先序遍历序列：abc..dh…ef…，完成建树。 }

printf(\"the end of the tree visit.\\n\");

10

按Enter键确定输入。

非递归先序遍历二叉树的操作：

在菜单中选择1 preorder，执行非递归先序遍历。输出遍历结果为：abcdhef。

非递归中序遍历二叉树的操作：

在菜单中选择2 inorder，执行非递归中序遍历。输出遍历结果为：cbhdafe。

递归层次遍历二叉树的操作：

在菜单中选择3 levelorder，执行递归层次遍历。输出遍历结果为：abecfdh。

11

求二叉树高度的操作：

在菜单中选择4 depth，执行用后续遍历方式求树的深度。输出遍历结果为：4.

求二叉树叶子结点的操作：

在菜单中选择5 leaf，执行求叶子个数。输出遍历结果为：5

结束树的操作：

在菜单中选择0 exit，推出对树的操作。

（5）调试程序中遇到的问题及解决方案

问题1：首先在创建二叉树的时候，要注意二叉树的输入，要用“.”代替空，否则程序不能正确运行；然后就是在求叶子的层次时从根结点出发，分别计算左孩子和右孩子，直到所求结点。

解决方案：建立二叉树时，按照先序遍历的方法，如果结点左孩子或右孩子为空则用“.”代替；要把空树全部输入，否则建树失败。

问题2：树的递归层次遍历较为困难，递归的逻辑思维比较难。

12

解决方案：递归层次遍历需要借助队列来实现，要先把树的根入队列，在出队列时一次把指针所指结点的左孩子和右孩子入队列，一次实现递归。同过出队列来实现树的递归层次遍历。

问题3：其中程序块比较多，其各种变量的格式可能不相匹配。

解决方案：梳理逻辑，通过自己的理解来使个变量的格式和变量名统一。 问题4：程序块太多，调试时很麻烦。

解决方案：程序块多可以小部分一起调试。应该先调试树的建立，然后一次调试先序，中序等功能。最后在主函数中做一个菜单目录，不要忘了在各个程序块上表明注视。

问题5：层次遍历入队列入队列出队列时，要保证树的根结点的地址。

解决方案：通过出队列返回m的值来保证t的值一直都在移动，从而实现将t的左右孩子入

队列的操作。

2.3 思考题解析

所选择的思考题：5.编写一个算法，构造一棵哈夫曼树，并求出其带权路径长度。 算法如下： typdef struct {

int weight;

int parent,lchild,rchild; }htnode,*huffmantree;

void creathuffmantree(huffmantree &ht ,int n)//建哈夫曼树

13

{ if(n<=1)

return;

m=2*n-1;

ht=(huffmantree)malloc((m+1)*sizeof(htnode)); for(i=n+1;i<=m;++i) {

select(ht,i-1,s1,s2); ht[s1].parent=i; ht[s2].parent=i; ht[i].lchild=s1; ht[i].rchild=s2;

ht[i].weight=ht[s1].weight+ht[s2].weight; }

void wpl(tree t, int h) //求WPL值 {

if(t!=NULL)

if(t->lchild==NULL&&t->rchild==NULL) m=n+t->wight*h;

14

else {

wpl(t->lchild,h+1); wpl(t->rchild,h+1); } }

程序分析：

该程序的逻辑结构为哈夫曼树的一个结点，存储结构是顺序存储结构。用左右孩子两个变量来储存树的权，其中双亲的权是孩子的权的和。通过顺序存储和数组的结构关系实现了对哈夫曼树的建立。

带权路径长度为哈夫曼树结点所带权数与路径长度的乘积的和。

15

总 结

数据结构注重逻辑思想，思维灵活，是计算机程序设计的重要理论技术基础。它不仅是计算机科学的核心课程，也是IT人员必须学好的一门课程。它兼顾了很多高级语言的特点，是一种典型的结构化程序设计语言，它处理能力强，使用灵活方便，应用面广，具有良好的可移植性。

在这两周的数据结构课程设计中,我选择的题目是：树的综合操作。这个题目对于我来说，比较有挑战性。在课程设计中，通过查阅资料、老师同学的帮助和自己的积极思考，终于在这个题目上有了很深刻的理解。在对这个题目的设计中，我对树的非递归先序，中序遍历、递归层次遍历、求叶子树和树的高度等问题上不再停留在理论阶段，深刻理解了这些问题在C语言中都是怎样操作怎样实现的。它不仅帮我们积累了调试程序的经验，也强化了我们的逻辑思维能力。通过对二叉树的综合应用的实践和理解，对课本中所学的数据结构理论知识也有了进一步的理解和掌握，学会了把学到的理论知识结合实际来解决问题，锻炼了自己动手的能力，培养了灵活运用所学过知识的能力。它带动了我们的思维模式， 改变了从前的刻板的思想。

通过这次课程设计，使我受益匪浅。深刻体会到了数据结构这门课的重要性，它的逻辑结构是最宝贵的。之前我们所学的知识都是局限于课本上和理论上，如今，通过这次课程设计，使我明确了数据结构的用途和用法。要学好一门学科，没有刻苦钻研的精神是不行的，只有在不断的尝试中，经历失败，从失败中总结经验，然后再不断的尝试，才能获得成功。

本人签字：

16

参考文献

[1]谭浩强.C程序设计.北京.清华大学出版社.2005年7月 [2]严蔚敏.数据结构.北京.清华大学出版社.2002年8月

[3]Brain W.Kernighan.The C program language.美国.机械工业出版社.2006年11月 [4] PrataS.. C PRIMER PLUS.美国.人民邮电出版社.2005年2月 [5]李春葆.数据结构教程.北京.清华大学出版社.2005年1月

17