数据结构与算法分析报告.docx

文档介绍：数据结构与算法分析实验报告
计算机学院
查找树算法实验报告
算法原理
在二叉排序树中进行查找的过程和二分查找类似,也是一个逐步缩小查找范围的过程。若查找成功,则是走了一条从根结点到待查结点的路径;若查找失败,则是走了一条根结点到某个叶子结点的路径。因此,查找过程中和关键字比较的次数不超过树的深度。
由于含有n个结点的二叉排序树不唯一,形态和深度可能不同。故含有n个结点的二叉排序树的平均查找长度和树的形态有关。
最好的情况是: 二叉排序树和二叉判定树形态相同。
最坏的情况是: 二叉排序树为单支树,这时的平均查找长度和顺序查找时相同。
最坏情况示例
就平均性能而言,二叉排序树上的查找和二分查找相差不大,并且二叉排序树上的插入和删除结点十分方便,无须大量移动结点。
复杂度
O(logN)
关键数据结构
class BinaryNode //节点类
{
public:
int data;
BinaryNode *l;
BinaryNode *r;
BinaryNode( int data , BinaryNode *l , BinaryNode *r )
{
this->data=data;
this->l=l;
this->r=r;
}
};
BinaryNode *root;
bool contains(int x ,BinaryNode *t)
{
if(t==NULL)
return false; //根节点为零,返回查找不到
else if(x<t->data) //与当前节点数据域比较,小则找左节点,大则找右节点,递归调用
return contains(x,t->l);
else if(t->data<x)
return contains(x,t->r);
else
return true;
}
void insert(int x ,BinaryNode * &t)
{
if(t==NULL) //插入过程与查找过程类似
t=new BinaryNode(x,NULL,NULL);
else if(x<t->data)
insert(x,t->l);
else if(t->data<x)
insert(x,t->r);
}
BinaryNode *findMax(BinaryNode *t)
{
if(t!=NULL)
while(t->r!=NULL)
t=t->r;
return t;
}
void printall(BinaryNode *&t)
{
if (t==NULL)
return;
else
{cout<<t->data<<endl;
printall(t->l);
printall(t->r);
}
程序源代码
#include<iostream>
#include<>
using namespace std;
class BinaryNode //节点类
{
public:
int data;
BinaryNode *l;
BinaryNode *r;
BinaryNode( int data , BinaryNode *l , BinaryNode *r )
{
this->data=data;
this->l=l;
this->r=r;
}
};
BinaryNode *root;
bool contains(int x ,BinaryNode *t)
{
if(t==NULL)
return false; //根节点为零,返回查找不到
else if(x<t->data) //与当前节点数据域比较,小则找左节点,大则找右节点,递归调用
return contains(x,t->l);
else if(t->data<x)
return contains(x,t->r);
else
return true;
}
void insert(int x ,BinaryNode * &t)
{
if(t==NULL) //插入过程与查找过程类似
t=new BinaryNode(x,NULL,NULL);
else if(x<t->data)
insert(x,t->l);
else if(t->data<x)
insert(x,t->r);
}
BinaryNode *findMax(BinaryNode *t)
{
if(t!=NULL)