二叉排序树的实现_二叉排序树的三种特性_二叉排序树的应用

电脑杂谈  发布时间:2017-02-14 07:35:08  来源:网络整理

二叉排序树的应用_二叉排序树的实现_二叉排序树的三种特性

课程设计任务书题 目: 二叉排序树的建立及遍历的实现初始条件:理论:学习了《数据结构》课程,掌握了基本的数据结构和常用的算法;实践:计算机技术系实验室提供计算机及软件开发环境。要求完成的主要任务: (包括课程设计工作量及其技术要求,以及说明书撰写等具体要求)1、系统应具备的功能:(1)建立二叉排序树;(2)中序遍历二叉排序树并输出排序结果;2、数据结构设计;3、主要算法设计;4、编程及上机实现;5、撰写课程设计报告,包括:(1)设计题目;(2)摘要和关键字;(3)正文,包括引言、需求分析、数据结构设计、算法设计、程序实现及测试、设计体会等;(4)结束语;(5)参考文献。二叉排序树的实现时间安排: 2007年7月2日-7日 (第18周)7月2日 查阅资料7月3日 系统设计,数据结构设计,算法设计7月4日-5日 编程并上机调试7月6日 撰写报告7月7日 验收程序,提交设计报告书。指导教师签名: 2007年7月2日系主任(或责任教师)签名: 2007年7月2日排序二叉树的建立及其遍历的实现摘要:我所设计的课题为排序二叉树的建立及其遍历的实现,它的主要功能是将输入的数据组合成排序二叉树,并进行,先序,中序和后序遍历。

设计该课题采用了C语言程序设计,简洁而方便,它主要运用了建立函数,调用函数,建立递归函数等等方面来进行设计。 关键字:排序二叉树,先序遍历,中序遍历,后序遍历0.引言我所设计的题目为排序二叉树的建立及其遍历的实现。排序二叉树或是一棵空树;或是具有以下性质的二叉树:(1)若它的左子树不空,则作子树上所有的结点的值均小于它的根结点的值;(2)若它的右子树不空,则右子树上所有结点的值均大于它的根结点的值; 3)它的左,右子树也分别为二叉排序树。对排序二叉树的建立需知道其定义及其通过插入结点来建立排序二叉树,遍历及其输出结果。该设计根据输入的数据进行建立排序二叉树。对排序二叉树的遍历,其关键是运用递归调用,这将极大的方便算法设计。1.需求分析建立排序二叉树,主要是需要建立节点用来存储输入的数据,需要建立函数用来创造排序二叉树,在函数内,需要进行数据比较决定数据放在左子树还是右子树。在遍历二叉树中,需要建立递归函数进行遍历。该题目包含两方面的内容,一为排序二叉树的建立;二为排序二叉树的遍历,包括先序遍历,中序遍历和后序遍历。排序二叉树的建立主要运用了循环语句和递归语句进行,对遍历算法运用了递归语句来进行。

二叉排序树的三种特性_二叉排序树的实现_二叉排序树的应用

2.数据结构设计本题目主要会用到建立结点,构造指针变量,插入结点函数和建立排序二叉树函数,求深度函数,以及先序遍历函数,中序遍历函数和后序遍历函数,还有一些常用的输入输出语句。对建立的函明确其作用,先理清函数内部的程序以及算法在将其应用到整个程序中,在建立排序二叉树时,主要用到建立节点函数,建立树函数,深度函数,在遍历树是,用到先序遍历函数,中序遍历函数和后序遍历函数。结点结构体定义:typedef struct tnode /*建立节点*/ int data; struct tnode *lchild,*rchild;TNODE;3.算法设计在进行算法设计时,应将题目分为两部分,排序二叉树的建立,排序二叉树的遍历。3.1 定义结点typedef struct tnode /*建立节点*/ int data;struct tnode *lchild,*rchild;TNODE;TNODE *q; /*构造指针变量*/TNODE *bt;3.2 插入结点函数insert Void insert TNODE **b,TNODE *s/*排序二叉树中插入节点*/ if *b NULL *b s; else if s- data *b - data return; else if s- data *b - data insert & *b - lchild ,s ; else if s- data *b - data insert & *b - rchild ,s ; 3.3 创建树函数creatvoid creat TNODE *b /*建立排序二叉树*/ int x; TNODE *s; b NULL; /*初始化二叉数*/ scanf "%d",&x ; s TNODE * malloc sizeof TNODE ; q s; /*将根结点指针地址赋值给q*/while x! -1 /*反复读入节点,直至-1结束*/ s- data x; s- lchild NULL; s- rchild NULL; insert &bt,s ; scanf "%d",&x ; /*节点插入排序二叉树中*/ s TNODE * malloc sizeof TNODE ; n n+1; 3.4 求排序二叉树的深度int deep TNODE *t /*求排序二叉树的深度 */ int rd;int ld;if !t return 0; else ld deep t- lchild ; rd deep t- rchild ; if ld rd return ld+1; else return rd+1; 3.5 建立先序遍历函数void preorder TNODE *p /*先序遍历二叉树*/ if p printf "%4d",p- data ; preorder p- lchild ; preorder p- rchild ; 3.6 中序遍历void inorder TNODE *p /*中序遍历二叉树*/ if p inorder p- lchild ; printf "%4d",p- data ; inorder p- rchild ; 3.7 后序遍历void postorder TNODE *p /*后序遍历二叉树*/ if p postorder p- lchild ; postorder p- rchild ; printf "%4d",p- data ; 这三个函数都应用了递归调用。


本文来自电脑杂谈,转载请注明本文网址:
http://xinshanjie.com/a/jisuanjixue/article-32330-1.html

相关阅读
发表评论  请自觉遵守互联网相关的政策法规,严禁发布、暴力、反动的言论

热点图片
拼命载入中...