二叉排序树查找的二叉排序树查找的程序实现:

急！急！求二叉排序树程序~

#include
//二叉排序树类的前视定义
template class BSTree;
//二叉排序树结点类的定义
template
class BSTreeNode
{friend class BSTree ;
private:
Type data; //数据域（在此为关键字）
BSTreeNode *leftChild, *rightChild;
public:
BSTreeNode():leftChild(NULL),rightChild (NULL){};//构造函数
BSTreeNode(const Type &d) : data (d), leftChild (NULL),rightChild (NULL) {} ; //构造函数
~BSTreeNode(){}; //析构函数
};

//二叉排序树的类定义
template
class BSTree
{
private:
BSTreeNode * root; //二叉排序树的根指针

void Insert ( const Type & x, BSTreeNode *&p );
//在p为根的二叉排序树上插入数据元素x
void Delete ( const Type & k, BSTreeNode *&p );

//在p为根的二叉排序树上删除关键字为k的结点
BSTreeNode * Min(BSTreeNode *p);
BSTreeNode * Find(const Type &k, BSTreeNode *p );
//在p为根的二叉排序树上查找关键字为k的结点
void InOrder(BSTreeNode *r);
public:
BSTree() : root (NULL) {}//构造函数
Type Find ( const Type &k ) {//查找
BSTreeNode* p=Find ( k, root );
if(p==NULL){
cout<<"There is not a node that equals "<<k<<endl;
return NULL;
}
return p->data;
}
void Insert(const Type &x) { Insert ( x, root ); } //插入
void Delete(const Type &k) { Delete ( k, root ); } //删除
void SortDisplay(){InOrder(root);cout<<endl;}

};

template
void BSTree::
Insert(const Type &x, BSTreeNode * &p) {
//在p为根的二叉排序树插入结点的递归算法
if ( p == NULL ) //空二叉树
p = new BSTreeNode(x); //创建数据元素x的结点
else if (xdata )
//在左子树插入
Insert ( x, p->leftChild );
else if ( x > p->data )
//在右子树插入
Insert ( x, p->rightChild );
else //结点x已存在
{
cout << "There has node x" << endl;
}
}
template
BSTreeNode * BSTree ::
Find (const Type &k, BSTreeNode *p) {
//在p为根的二叉排序树上进行查找的递归算法
if ( p == NULL ) return NULL; //查找失败
else if ( kdata )
//在左子树上递归查找
return Find (k,p->leftChild );
else if (k>p->data )
//在右子树上递归查找
return Find ( k, p->rightChild );
else return p; //相等,查找成功
}
template
void BSTree ::
Delete(const Type &k, BSTreeNode * &p){
//在p为根的二叉排序树上删除关键字为k的结点

if ( p != NULL ){
BSTreeNode * temp;
if ( k data )
Delete ( k, p->leftChild );
else if ( k > p->data )
Delete ( k, p->rightChild );
else if ( p->leftChild != NULL && p->rightChild != NULL ){
BSTreeNode * tparent=p;
temp=p->rightChild;
while(temp->leftChild!=NULL){
tparent=temp;
temp=temp->leftChild;
}
p->data = temp->data;
if(tparent==p)
Delete ( p->data,tparent->rightChild );
else Delete ( p->data,tparent->leftChild );
}
else {
temp = p;
if ( p->leftChild == NULL )
p = p->rightChild;
else if ( p->rightChild == NULL )
p = p->leftChild;
delete temp;
}
}
}
template
void BSTree::InOrder(BSTreeNode* r){
if(r!=NULL){
InOrder(r->leftChild);
coutdata<<" ";
InOrder(r->rightChild);
}
}
void main (){

BSTree a;
int x;
cout<<"输入序列："<<" ";
for(int i=0;;i++){
cin>>x;
if(x==-1)break;
a.Insert(x);
}
cout<<endl;
cout<<"输出中序遍历序列应为：";
a.SortDisplay();
cout<<endl;
cout<<"输入需要删除的整数："<<" ";
int y;
cin>>y;
cout<<endl;
cout<<"查找结果是:"<<a.Find(y)<<endl;
cout<<endl;
a.Delete(y);
cout<<"输出删除后的中序遍历序列应为："<<" ";
a.SortDisplay();

}

二叉排序树最重要的性质：对于每个节点a的左子树的根al的值一定比该节点值小，节点a右子树的根节点ar的值一定比a的值大，因此可以推出==>一个节点的左子树的所有节点的值都比它的值要小，一个节点的右子树的所有节点的值都比它大！对上面的这个序列进行分析，202是925的左子树根，所以202.911.240.912.245.363这些节点都必须要比925小，911是202右子树的根，所以911.240.912.245.363都要比202大，240是911的左子树根，所以240.912.245.363都要比911小才行，但是912比911要大是吧？所以912不应该是911左子树的节点，所以错了呗！应该够清楚了吧？再不懂就没辙了！记得给分哈^.^

5. 二叉排序树的删除:
假设被删结点是*p，其双亲是*f，不失一般性，设*p是*f的左孩子，下面分三种情况讨论：
⑴ 若结点*p是叶子结点，则只需修改其双亲结点*f的指针即可。
⑵ 若结点*p只有左子树PL或者只有右子树PR，则只要使PL或PR 成为其双亲结点的左子树即可。
⑶ 若结点*p的左、右子树均非空，先找到*p的中序前趋结点*s（注意*s是*p的左子树中的最右下的结点，它的右链域为空），然后有两种做法：
① 令*p的左子树直接链到*p的双亲结点*f的左链上,而*p的右子树链到*p的中序前趋结点*s的右链上。
② 以*p的中序前趋结点*s代替*p（即把*s的数据复制到*p中），将*s的左子树链到*s的双亲结点*q的左（或右）链上。
6. 删除算法演示 :
7. 二叉排序树的查找:
在二叉排序树中进行查找的过程和二分查找类似，也是一个逐步缩小查找范围的过程。若查找成功，则是走了一条从根结点到待查结点的路径；若查找失败，则是走了一条根结点到某个叶子结点的路径。因此，查找过程中和关键字比较的次数不超过树的深度。
由于含有n个结点的二叉排序树不唯一，形态和深度可能不同。故含有n个结点的二叉排序树的平均查找长度和树的形态有关。
最好的情况是： 二叉排序树和二叉判定树形态相同。
最坏的情况是： 二叉排序树为单支树，这时的平均查找长度和顺序查找时相同。
最坏情况示例
就平均性能而言，二叉排序树上的查找和二分查找相差不大，并且二叉排序树上的插入和删除结点十分方便，无须大量移动结点。

---

海盐县13422321615： 二叉排序树的查找(C语言)代码 - ？
凤治雪胆： #include #include #define INFMT ＂%d＂#define OUTFMT ＂%d ＂/* #define NULL 0L */#define BOOL int#define TRUE 1#define FALSE 0#define LEN 10000 typedef int ElemType; typedef struct BSTNode { ElemType data; struct BSTNode *...

海盐县13422321615： 数据结构实验,求用C语言编一个二叉排序树的创建和查找的程序 - ？
凤治雪胆： 这东西很多的这里给你一个#include <stdio.h>#include <stdlib.h> typedef struct np{int dat;struct np *left,*right;} node;node *create(void){return (malloc(sizeof(node)));}node *t(node *a,int d){if (a==NULL) { a=create(); a->left =a->right =NULL;a->dat=d;}...

海盐县13422321615： 二叉排序树的构造和查找方法 - ？
凤治雪胆： 二叉排序树的构造过程:按照给定序列,以此将结点插入二叉排序树中,在二叉排序树中插入新结点,要保证插入后的二叉树仍符合二叉排序树的定义. 插入过程:若二叉排序树为空,则待插入结点*S作为根结点插入到空树中; 当非空时,...

海盐县13422321615： C语言编程 二叉排序树查找 - ？
凤治雪胆： #include<stdio.h> #include<malloc.h> #define NULL 0 typedef struct node {int data;node *left;node *right; }node;node *CreateTree(node* root,int *p,int n) {int i=n;node *q,*r;while(i!=0){if(root==NULL){root=(node *)malloc(sizeof(node *)); ...

海盐县13422321615： 用C语言实现二叉排序树的查找、插入和删除 - ？
凤治雪胆： #include <stdio.h>#include <conio.h> #include <stdlib.h> typedef struct BitNode { char data; struct BitNode *lchild,*rchild; }BitNode,*BiTree; void CreateBiTree(BiTree &); //生成一个二叉树 void FirstOrder(BiTree); //先序递归遍历二叉树 void ...

海盐县13422321615： 4.给定无序表D={18,88,15,93,35,51,60,17,22},用二叉排序树查找法在D中查找51.现要求:(1)试画出二叉排序树,并画出查找过程;(3分)(2)求出其... - ？
凤治雪胆：[答案] (1)树如下(查找过程已标红): 18 15/ \88 \17 35/ \93 22/\51 \60 (2) 查找长度: ASL=(1*1+2*2+3*3+4*2+5*1)/9=3

海盐县13422321615： 依次输入元素:10,8,16,5,20,7,12,19,试生成一棵二叉排序树.(1) 画出建立的二叉排序树.(2) 假定每个元素的查找概率相等,计算查找成功时的平均查找... - ？
凤治雪胆：[答案] 你是要算法还是本题答案? 本题答案为 10 8 16 5 12 20 7 19 算法为: 步骤:若根结点的关键字值等于查找的关键字,成功. 否则,若小于根结点的关键字值,递归查左子树. 若大于根结点的关键字值,递归查右子树. 若子树为空,查找不成功. 平均情...

海盐县13422321615： 二叉树的查找 - ？
凤治雪胆： LZ好,// tree.cpp : 定义控制台应用程序的入口点.//#include <stdio.h>#include <tchar.h>#include ＂binary_tree.h＂ int _tmain(int argc, _TCHAR* argv[]) {//初始化二叉树类 Binary_Tree * pBTree = new Binary_Tree();//创建一个二叉树 while(1...

海盐县13422321615： 实现二叉排序树的生成,完成二叉排序树的遍历、查找. 要求: - ？
凤治雪胆： 利用c语言,代码如下仅供参考: 说明:为了保证输入的数据按要求构造出想要的、唯一确定的二叉树的形状,这里输入要求利用广义表的形式,虽然会显得繁琐一点,但足以保证严谨性.否则只是单纯一串数字,树形就能千变万化,不一定的...

海盐县13422321615： 急!急!求二叉排序树程序 - ？
凤治雪胆： #include <iostream.h>//二叉排序树类的前视定义 template<class Type> class BSTree; //二叉排序树结点类的定义 template<class Type> class BSTreeNode {friend class BSTree <Type>; private:Type data; //数据域(在此为关键字) ...