有关二叉排序树的毕业论文

/*以下是用c++ 实现的二叉排序树的源代码*/ #include<> typedef struct TreeNode { int... 二叉排序树****************/ BiSortTree::BiSortTree() { cout<<"建立一棵二叉排序树,请输入你要建...

一、定义二叉排序树，又叫二叉查找树，它或者是一棵空树；或者是具有以下性质的二叉树：1. 若它的左子树不空，则左子树上所有节点的值均小于它的根节点的值；2. 若它的右子树不空，则右子树上所有节点的值均大于它的根节点的值；3. 它的左右子树也分别为二叉排序树。二叉搜索树（BST）又称二叉查找树或二叉排序树。一棵二叉搜索树是以二叉树来组织的，可以使用一个链表数据结构来表示，其中每一个结点就是一个对象。一般地，除了key和卫星数据之外，每个结点还包含属性lchild、rchild和parent，分别指向结点的左孩子、右孩子和双亲（父结点）。如果某个孩子结点或父结点不存在，则相应属性的值为空（NIL）。根结点是树中唯一父指针为NIL的结点，而叶子结点的孩子结点指针也为NIL。

在 计算机科学中, 二叉搜索树(BST)，有时也被称为二叉排序树，是一种特殊类型的容器: 在内存中存储“项目”（例如数字，名称等）的数据结构。它们允许快速查找、添加和删除项目，并且可以用于实现动态项目集，或者允许通过其关键字查找项目的查找表(例如，通过名称查找人员的电话号码)。二叉排序树有序保存它们的关键字，以便查找和其他操作可以使用 二分的原则:当在树中寻找关键字(或插入新关键字的位置)时，他们从根到叶遍历树，与存储在树结点中的关键字进行比较，并根据比较结果决定继续在左或右子树中搜索。平均而言，这意味着每次比较都允许操作跳过树的大约一半结点，因此每次查找、插入或删除都需要存储在树中的项目数的对数级别的时间复杂度。这比在(未排序的)数组中按关键字查找项目需要的线性时间复杂的好多了 ，但比哈希表上的相应操作要慢。计算机科学出现了二叉排序树的几种变体；本文主要讨论基本类型，并在适当的时候引用更高级的类型。二叉排序树是带根结点的二叉树，其内部结点各自存储一个关键字(以及可选的相关值),并且各自具有两个可区分的子树，通常表示为左和右。该树还拥有二分搜索的属性，该属性声明每个结点中的关键字必须大于或等于左子树中存储的任何关键字，并且小于或等于右子树中存储的任何关键字。[1] 树的叶子(最终结点)不包含关键字，也没有结构来区分它们。通常，每个结点代表的信息是一条记录，而不是一个数据元素。 然而，出于排序的目的，结点是根据它们的关键字而不是它们相关记录的任何部分进行比较的。二叉排序树相对于其他数据结构的主要优势是在分类算法和 搜索算法比如有序遍历中非常有效；它们也很容易编码。二叉搜索树是用于构造更抽象的数据结构（如集合，多集合和关联数组）的基础数据结构。.当在二叉排序树中插入或搜索元素时，必须将每个被访问结点的关键字与要插入或找到的元素的关键字进行比较。二叉排序树的形状完全取决于插入和删除的顺序，并且可能退化。在长时间随机插入和删除的混合序列之后，树的预期高度接近关键字数量的平方根 √n，它的增长速度比 log n快得多。已经有许多研究来防止树的退化，这种退化导致最坏情况下的时间复杂度 O(n) (有关详细信息，请参见部分)。

二叉排序树的生成方法你要先了解,简单的说，最基本就是：1，第一个关键字做根结点。2，每个关键字都与根结点比较，如果小于根结点，就插入到左子树，否则插入到右子树。以序列（(34,76,45,18,26,54,92）为例：34/\1876\/\264592\54深度为：4。

晕了，真是好纠结，我在写完下面的代码后，才在网上找了找，居然发现和你的题目完全一样的代码，算了，我就直接发在网上找到的文档和代码给你吧，可怜我写了这么久代码呀。。。。。已发，请注意查收。代码写好了。VC下经测试通过。不过如果你还要论文之类的或者设计文档，我也比较难帮到你了。#include using namespace std;class node{public: node(int i):data(i),left(NULL),right(NULL){} void inorder(node *&root) //中序遍历，符合升序输出 { if(root!=NULL) { inorder(root->left); cout<data<<' '; inorder(root->right); } } void insert(node *&ptr,int item) //在查找树中插入元素 { if(ptr==NULL) ptr=new node(item); else if(itemdata) insert(ptr->left,item); else insert(ptr->right,item); } node *find(node *&ptr,int item) //在查找树中查找元素,找到返回所在结点指针，找不到返回空指针。 { if(ptr==NULL) return NULL; if(ptr->data==item) return ptr; else if(itemdata) find(ptr->left,item); else find(ptr->right,item); } node *&findy(node *&ptr,int item) //在查找树中查找肯定存在的元素,并返回其引用 { if(ptr->data==item) return ptr; else if(itemdata) findy(ptr->left,item); else findy(ptr->right,item); } node* rl(){return left;} node* rr(){return right;} void dele(node *&ptr) //删除值为item所在结点 { if(ptr->rl()==NULL&&ptr->rr()==NULL) ptr=NULL; else if(ptr->rr()==NULL) ptr=ptr->rl(); else ptr=ptr->rr(); }private: int data; node *left; //左孩子结点 node *right; //右孩子结点};int main(){ int t,i=0,j; cout<<"输入数字个数(结点个数):"; cin>>t; cout<<"输入"<>j; node *x=new node(j); for(;i>j; x->insert(x,j); } cout<<"中序遍历为:"; x->inorder(x); //作中序遍历 cout<<"\n输入操作(当输入-1时程序结束):"<>j; while(j!=-1) { node *t=x->find(x,j); //定位结点 if(t!=NULL) { node *&y=x->findy(x,j); x->dele(y); cout<<"中序遍历为:"; x->inorder(x); } else cout<<"无"<>j; } return 0;}附测试数据一组822 33 1 50 88 99 77 5533505155-1有什么不明的话可以M我或者留言我。