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

内蒙古科技大学本科生课程设计说明书题目：数据结构课程设计——二叉树的遍历和应用学生姓名：学号：专业：班级：指导教师：2013年5月29日内蒙古科技大学课程设计说明书内蒙古科技大学课程设计任务书I内蒙古科技大学课程设计说明书目录内蒙古科技大学课程设计任务书..............................................................错误！未定义书签。

目录 (II)第一章需求分析 (3)1.1课程设计目的 (3)1.2任务概述 (3)1.3课程设计内容 (3)第二章概要设计 (5)2.1设计思想 (5)2.2二叉树的遍历 (5)2.3运行界面设计 (6)第三章详细设计 (7)3.1二叉树的生成 (7)3.2二叉树的先序遍历 (7)3.3 二叉树的中序遍历 (8)3.4二叉树的后续遍历 (8)3.5主程序的设计 (8)第四章测试分析 (11)4.1二叉树的建立 (11)4.2二叉树的先序、中序、后序遍历 (11)第五章课程设计总结 (12)附录：程序代码 (13)致谢 ···········································································································错误！未定义书签。

实验5：二叉树的建立及遍历（第十三周星期三7、8节）一、实验目的1．学会实现二叉树结点结构和对二叉树的基本操作。

2．掌握对二叉树每种操作的具体实现，学会利用递归方法编写对二叉树这种递归数据结构进行处理的算法。

二、实验要求1．认真阅读和掌握和本实验相关的教材内容。

2．编写完整程序完成下面的实验内容并上机运行。

3．整理并上交实验报告。

三、实验内容1．编写程序任意输入二叉树的结点个数和结点值，构造一棵二叉树，采用三种递归遍历算法(前序、中序、后序)对这棵二叉树进行遍历并计算出二叉树的高度。

2 .编写程序生成下面所示的二叉树，并采用中序遍历的非递归算法对此二叉树进行遍历。

四、思考与提高1．如何计算二叉链表存储的二叉树中度数为1的结点数？2．已知有—棵以二叉链表存储的二叉树，root指向根结点，p指向二叉树中任一结点，如何求从根结点到p所指结点之间的路径?/*----------------------------------------* 05-1_递归遍历二叉树.cpp -- 递归遍历二叉树的相关操作* 对递归遍历二叉树的每个基本操作都用单独的函数来实现* 水上飘2009年写----------------------------------------*/// ds05.cpp : Defines the entry point for the console application.//#include "stdafx.h"#include <iostream>typedef char ElemType;using namespace std;typedef struct BiTNode {ElemType data;//左右孩子指针BiTNode *lchild, *rchild;}BiTNode, *BiTree;//动态输入字符按先序创建二叉树void CreateBiTree(BiTree &T) {char ch;ch = cin.get();if(ch == ' ') {T = NULL;}else {if(ch == '\n') {cout << "输入未结束前不要输入回车，""要结束分支请输入空格！" << endl;}else {//生成根结点T = (BiTNode * )malloc(sizeof(BiTNode));if(!T)cout << "内存分配失败！" << endl;T->data = ch;//构造左子树CreateBiTree(T->lchild);//构造右子树CreateBiTree(T->rchild);}}}//输出e的值ElemType PrintElement(ElemType e) { cout << e << " ";return e;}//先序遍历void PreOrderTraverse(BiTree T) { if (T != NULL) {//打印结点的值PrintElement(T->data);//遍历左孩子PreOrderTraverse(T->lchild);//遍历右孩子PreOrderTraverse(T->rchild);}}//中序遍历void InOrderTraverse(BiTree T) {if (T != NULL) {//遍历左孩子InOrderTraverse(T->lchild);//打印结点的值PrintElement(T->data);//遍历右孩子InOrderTraverse(T->rchild);}}//后序遍历void PostOrderTraverse(BiTree T) { if (T != NULL) {//遍历左孩子PostOrderTraverse(T->lchild);//遍历右孩子PostOrderTraverse(T->rchild);//打印结点的值PrintElement(T->data);}}//按任一种遍历次序输出二叉树中的所有结点void TraverseBiTree(BiTree T, int mark) {if(mark == 1) {//先序遍历PreOrderTraverse(T);cout << endl;}else if(mark == 2) {//中序遍历InOrderTraverse(T);cout << endl;}else if(mark == 3) {//后序遍历PostOrderTraverse(T);cout << endl;}else cout << "选择遍历结束！" << endl;}//输入值并执行选择遍历函数void ChoiceMark(BiTree T) {int mark = 1;cout << "请输入，先序遍历为1，中序为2，后序为3，跳过此操作为0：";cin >> mark;if(mark > 0 && mark < 4) {TraverseBiTree(T, mark);ChoiceMark(T);}else cout << "此操作已跳过！" << endl;}//求二叉树的深度int BiTreeDepth(BiTNode *T) {if (T == NULL) {//对于空树，返回0并结束递归return 0;}else {//计算左子树的深度int dep1 = BiTreeDepth(T->lchild);//计算右子树的深度int dep2 = BiTreeDepth(T->rchild);//返回树的深度if(dep1 > dep2)return dep1 + 1;elsereturn dep2 + 1;}}int _tmain(int argc, _TCHAR* argv[]){BiTNode *bt;bt = NULL; //将树根指针置空cout << "输入规则：" << endl<< "要生成新结点，输入一个字符，""不要生成新结点的左孩子，输入一个空格，""左右孩子都不要，输入两个空格，""要结束，输入多个空格（越多越好）,再回车！"<< endl << "按先序输入：";CreateBiTree(bt);cout << "树的深度为：" << BiTreeDepth(bt) << endl;ChoiceMark(bt);return 0;}/*----------------------------------------* 05-2_构造二叉树.cpp -- 构造二叉树的相关操作* 对构造二叉树的每个基本操作都用单独的函数来实现* 水上飘2009年写----------------------------------------*/// ds05-2.cpp : Defines the entry point for the console application.//#include "stdafx.h"#include <iostream>#define STACK_INIT_SIZE 100 //栈的存储空间初始分配量#define STACKINCREMENT 10 //存储空间分配增量typedef char ElemType; //元素类型using namespace std;typedef struct BiTNode {ElemType data; //结点值BiTNode *lchild, *rchild; //左右孩子指针}BiTNode, *BiTree;typedef struct {BiTree *base; //在栈构造之前和销毁之后，base的值为空BiTree *top; //栈顶指针int stacksize; //当前已分配的存储空间，以元素为单位}SqStack;//构造一个空栈void InitStack(SqStack &s) {s.base = (BiTree *)malloc(STACK_INIT_SIZE * sizeof(BiTree));if(!s.base)cout << "存储分配失败！" << endl;s.top = s.base;s.stacksize = STACK_INIT_SIZE;}//插入元素e为新的栈顶元素void Push(SqStack &s, BiTree e) {//栈满，追加存储空间if ((s.top - s.base) >= s.stacksize) {s.base = (BiTree *)malloc((STACK_INIT_SIZE+STACKINCREMENT) * sizeof(BiTree));if(!s.base)cout << "存储分配失败！" << endl;s.top = s.base + s.stacksize;s.stacksize += STACK_INIT_SIZE;}*s.top++ = e;}//若栈不空，则删除s的栈顶元素，并返回其值BiTree Pop(SqStack &s) {if(s.top == s.base)cout << "栈为空，无法删除栈顶元素！" << endl;s.top--;return *s.top;}//按先序输入字符创建二叉树void CreateBiTree(BiTree &T) {char ch;//接受输入的字符ch = cin.get();if(ch == ' ') {//分支结束T = NULL;} //if' 'endelse if(ch == '\n') {cout << "输入未结束前不要输入回车，""要结束分支请输入空格！（接着输入）" << endl;} //if'\n'endelse {//生成根结点T = (BiTNode * )malloc(sizeof(BiTree));if(!T)cout << "内存分配失败！" << endl;T->data = ch;//构造左子树CreateBiTree(T->lchild);//构造右子树CreateBiTree(T->rchild);} //Create end}//输出e的值，并返回ElemType PrintElement(ElemType e) {cout << e << " ";return e;}//中序遍历二叉树的非递归函数void InOrderTraverse(BiTree p, SqStack &S) {cout << "中序遍历结果：";while(S.top != S.base || p != NULL) {if(p != NULL) {Push(S,p);p = p->lchild;} //if NULL endelse {BiTree bi = Pop(S);if(!PrintElement(bi->data))cout << "输出其值未成功！" << endl;p = bi->rchild;} //else end} //while endcout << endl;}int _tmain(int argc, _TCHAR* argv[]){BiTNode *bt;SqStack S;InitStack(S);bt = NULL; //将树根指针置空cout << "老师要求的二叉树序列（‘空’表示空格）：""12空空346空空空5空空，再回车！"<< endl << "请按先序输入一个二叉树序列（可另输入，但要为先序），""无左右孩子则分别输入空格。

9.6.2 哈希函数的构造方法
构造哈希函数的目标：
哈希地址尽可能均匀分布在表空间上——均 匀性好； 哈希地址计算尽量简单。
考虑因素：
函数的复杂度； 关键字长度与表长的关系； 关键字分布情况； 元素的查找频率。
一、直接地址法 取关键字或关键字的某个线性函数值为哈希地址 即： H(key) = key 或： H(key) = a* key + b 其中，a， b为常数。 例：1949年后出生的人口调查表，关键字是年份 年份 1949 1950 1951 … 人数 … … … …
9.4 二叉排序树
1．定义：
二叉排序树(二叉搜索树或二叉查找树) 或者是一棵空树；或者是具有如下特性的二叉树
(1) 若它的左子树不空，则左子树上所有结点的 值均小于根结点的值；
(2) 若它的右子树不空，则右子树上所有结点 的值均大于等于根结点的值； (3) 它的左、右子树也都分别是二叉排序树。
例如:
H(key)
通常设定一个一维数组空间存储记录集合，则 H(key)指示数组中的下标。
称这个一维数组为哈希(Hash)表或散列表。 称映射函数 H 为哈希函数。 H(key)为哈希地址
例：假定一个线性表为： A = (18，75，60，43，54，90，46) 假定选取的哈希函数为
hash3(key) = key % 13
H(key) = key + (-1948) 此法仅适合于： 地址集合的大小 = = 关键字集合的大小
二、数字分析法
假设关键字集合中的每个关键字都是由 s 位数 字组成 (u1, u2, …, us)，分析关键字集中的全体， 并从中提取分布均匀的若干位或它们的组合作为 地址。 例如：有若干记录，关键字为 8 位十进制数， 假设哈希表的表长为100, 对关键字进行分析， 取随机性较好的两位十进制数作为哈希地址。

课程设计数据结构心得体会5篇（经典版）编制人：__________________审核人：__________________审批人：__________________编制单位：__________________编制时间：____年____月____日序言下载提示：该文档是本店铺精心编制而成的，希望大家下载后，能够帮助大家解决实际问题。

文档下载后可定制修改，请根据实际需要进行调整和使用，谢谢!并且，本店铺为大家提供各种类型的经典范文，如总结报告、演讲致辞、条据文书、策划方案、合同协议、应急预案、规章制度、教学资料、作文大全、其他范文等等，想了解不同范文格式和写法，敬请关注!Download tips: This document is carefully compiled by this editor. I hope that after you download it, it can help you solve practical problems. The document can be customized and modified after downloading, please adjust and use it according to actual needs, thank you!And, our store provides various types of classic sample essays for everyone, such as summary reports, speeches, policy documents, planning plans, contract agreements, emergency plans, rules and regulations, teaching materials, essay summaries, other sample essays, and so on. If you want to learn about different sample essay formats and writing methods, please stay tuned!课程设计数据结构心得体会5篇心得体会是我们用于记录自己感受的一种总结性文字，想要写出一篇有意义的心得体会，最关键的还是中心立意的明确，本店铺今天就为您带来了课程设计数据结构心得体会5篇，相信一定会对你有所帮助。