二叉排序树的实现

河南城建学院 数据结构 课程设计说明书 题目:   　二叉排序树的实现　  院    系：      专业班级：  计算机科学与技术专业  学    号：              学生姓名：                  同 组 人：                  指导教师：                  2010年 06 月 25 日 目录 1、需求分析    1 2、概要设计    2 3、详细设计    3 3.1 程序源代码    3 3.2 调试结果分析    12 4、总结    14 参考文献    15 1、需求分析 1． 基本要求 a) 以回车('\n')为输入结束标志,输入数列L，生成一棵二叉排 序树T； b) 对二叉排序树T作中序遍历，输出结果； c) 输入元素x,查找二叉排序树T,若存在含x的结点,则删除该结点,并作中序遍历(执行操作2)；否则输出信息“无x”； 2． 数据类型 要实现二叉排序数，必须先定义数据类型，本设计的输入数据为整型，输出的数据也为整型。 3． 题目功能详细说明 要生成一棵二叉排序数T，元素类型为ElemType 在二叉排序树中查找其关键字等于给定值的结点是否存在 在二叉排序树中插入一个新结点，中序遍历所建二叉排序树，将得到一个按关键字有序的元素序列 二叉排序树的查找，可多次查找，并输出查找的结果 4．最后对输出结构进行分析 2、概要设计 2.1 功能设计： 要生成一棵二叉排序树T，元素类型为ElemType 在二叉排序树中查找其关键字等于给定值的结点是否存在 在二叉排序树中插入一个新结点，中序遍历所建二叉排序树，将得到一个按关键字有序的元素序列 二叉排序树的查找，可多次查找，并输出查找的结果 最后对输出结构进行分析 2.2 . 抽象数据类型的定义 #define  MAX-TREE-SIZE 100  //二叉树的最大结点数 Typedef TELem type sqbitree[MAX-TREE-SIZE];//0号单元存储根结点 结点X的双亲PARENT(T,E) if(!t)  {*p=f;return (0);}        /*查找不成功*/ else    if(key==t->data)    {*p=t;return (1);} /*查找成功*/ else    if(keydata)  searchBST(t->lchild,key,t,p);  /*在左子树中继续查找*/ else    searchBST(t->rchild,key,t,p); /*在右子树中继续查找*/ calculateASL(node *t,int *s,int *j,int i) /*计算平均查找长度*/ { if(*t){ i++;  /*i记录当前结点的在当前树中的深度*/ *s=*s+i;  /*s记录已遍历过的点的深度之和*/ if(calculateASL(&(*t)->lchild,s,j,i))/*计算左子树的ASL*/ 2.3 数据

流程

快递问题件怎么处理流程河南自建厂房流程下载关于规范招聘需求审批流程制作流程表下载邮件下载流程设计

图： 数据流程图 3、详细设计 3.1 程序源代码 /*以下是用c++ 实现的二叉排序树的源代码*/ #include typedef struct TreeNode { int key; struct TreeNode *left; struct TreeNode *right; }treeNode; class BiSortTree { public: BiSortTree(void); void desplayTree(void);//显示这个树 void insertTree(int key);//在树中插入一个值 deleteTree(int key);//在树中删除一个值 treeNode* searchTree(int key);//在树中查找一个值 ~BiSortTree(); private: treeNode*  buildTree(treeNode* head,int number);//建立一个树 treeNode*  search(treeNode* head ,int key);//查找 treeNode* BiSortTree::searchParent(treeNode* head,treeNode* p);//查找出p的父亲节点的指针 treeNode* BiSortTree::searchMinRight(treeNode* head);//找到右子树中最小的节点 void showTree(treeNode* head);//显示 void destroyTree(treeNode* head);//删除 treeNode *Head; }; /**************以下是建立一个二叉排序树****************/ BiSortTree::BiSortTree() { cout<<"建立一棵二叉排序树,请输入你要建树的所有数(以-1 作为结束标志!): "<>number; while(number!=-1) { Head=buildTree(Head,number); cin>>number; } } treeNode* BiSortTree::buildTree(treeNode* head,int number) { treeNode *p;  p=new treeNode; p->key=number; p->left =p->right=NULL; if(head==NULL) { return p; } else { if(p->key key) head->left=buildTree(head->left,number); else head->right=buildTree(head->right,number); return head; } } /*****************以下是在一棵二叉排序树插入一个数***********************************/ void BiSortTree::insertTree(int key) { Head=buildTree(Head,key); } /*****************以下是在一个二叉排序树查找一个数是否存在*************************/ treeNode*  BiSortTree::searchTree(int key) { return search(Head,key); } treeNode* BiSortTree::search(treeNode* head ,int key) { if(head==NULL) return NULL; if(head->key==key) return head; else { if(keykey ) return search( head->left,key); else return search(head->right,key); } } /************以下是在一个二叉排序树删除一个给定的值*********************************/ BiSortTree::deleteTree(int key) { treeNode *p; p=NULL; p=search(Head,key); if(p==NULL) { cout<<"Don't find the key"; } if(p==Head) { Head=NULL; } else { treeNode* parent; parent=searchParent(Head,p); if(p->left==NULL&&p->right==NULL)//叶子节点 { if(parent->left==p) { parent->left=NULL; } else { parent->right=NULL; } } else//非叶子节点 { if(p->right==NULL)//该节点没有右孩子 { if(parent->left==p) { parent->left=p->left ; } else { parent->right=p->left; } } else//该点有左右孩子 { treeNode * rightMinSon,* secondParent;//secondParent为右子树中的最小节点的父亲 rightMinSon=searchMinRight(p->right); secondParent=searchParent(p->right ,rightMinSon); secondParent->left=rightMinSon->right; if(p->right==rightMinSon)//右子树中的最小节点的父亲为p { p->right=rightMinSon->right ; } p->key=rightMinSon->key ; } } } } treeNode* BiSortTree::searchParent(treeNode* head,treeNode* p) { if(head->left==p||head->right==p||head==p||head==NULL) return head; else { if(p->keykey) return searchParent(head->left ,p); else return searchParent(head->right ,p); } } treeNode* BiSortTree::searchMinRight(treeNode* head)//找到右子树中最小的节点 { if(head->left ==NULL||head==NULL) { return head; } else { return searchMinRight(head->left); } } /*****************以下是显示一个二叉排序树****************************************/ void BiSortTree::desplayTree(void) { showTree(Head); cout<left ) ; cout<key<<' ' ; showTree(Head->right) ; } } /*****************以下是删除一棵整二叉排序树************************************/ BiSortTree::~BiSortTree() { cout<<"已经消除了一棵树!!!!"<left ); destroyTree(head->right ); delete head; } } /*********************/ void print() { cout<>choiceNumber; switch(choiceNumber) { case 1:  tree.desplayTree();break; case 2: cout<<"请插入一个数: "<>number; tree.insertTree(number); tree.desplayTree(); break; case 3: cout<<"请插入你要找数: "<>number;  if(tree.searchTree(number)==NULL) { cout<<"没有发现"<>number; tree.deleteTree(number); tree.desplayTree(); break; default: break; } cout<<"你是否要继续(Y/N)?"<>flag; if(flag=='N'||flag=='n') break; } } 3.2 调试结果分析 1、开始界面 2、菜单选项 3、对二叉排序树T作中序遍历 4、插入一个节点 5、寻找一个节点 6、删除一个节点 4、总结 在本次课程设计中间，遇到了很多问题。首先是界面问题，由于对MFC界面编程接触较少，导致刚开始设计时很迷茫，甚至想直接用DOS界面。但是后来仔细研究之后终于克服了困难，确定了采用界面编程。之后是添加航班信息的困难，第一次设计的时候并没有设计添加模块，查询的航班信息就是预先存储的8组数据，主要是因为二分查找的前提是有序

表

关于同志近三年现实表现材料材料类招标技术评分表图表与交易pdf视力表打印pdf用图表说话 pdf

，在学习了排序之后困难就迎刃而解。还有显示航班信息的问题，找到了航班之后要如何告知用户，我采用简单消息框，这就势必导致在输出前要先完成格式的编写，在多次试验之后，终于完成了任务。其实在这次课程设计是遇到的困难还有很多，但是只要用心去想，去做，就都解决了。 本程序虽然已经完成了课程设计的需求，但是就应用上来说还是不完整的。由于时间仓促，故只提出一些改进的思想。待以后改进。将航班信息保存到一个文本文件或者二进制文件中。方便使用；将8个查询按钮“合并”为一个查询按钮；简化界面；将查抄代码封装在类里，使用时调用，简化代码；设计GUI，美化界面。 通过课程设计，我加深了对数据结构这门课的认识，数据结构课程主要是研究非数值计算的程序设计问题中所出现的计算机操作对象以及它们之间的关系和操作的学科。数据结构是介于数学、计算机软件和计算机硬件之间的一门计算机专业的核心课程，它是计算机程序设计、数据库、操作系统、编译原理及人工智能等的重要基础，广泛的应用于信息学、系统工程等各种领域。通过本次课程设计，我的思维能力、综合应用能力和专业素质得到提高。 参考文献 [1] 严蔚敏. 数据结构(C语言版). 北京: 清华大学出版社,2007