文档介绍：数据结构与算法分析实验报告计算机学院查找树算法实验报告算法原理在二叉排序树中进行查找的过程和二分查找类似,也是一个逐步缩小查找范围的过程。若查找成功,则是走了一条从根结点到待查结点的路径;若查找失败,则是走了一条根结点到某个叶子结点的路径。因此,查找过程中和关键字比较的次数不超过树的深度。由于含有门个结点的二叉排序树不唯一,形态和深度可能不同。故含有门个结点的二叉排序树的平均查找长度和树的形态有关。最好的情况是:二叉排序树和二叉判定树形态相同。最坏的情况是:二叉排序树为单支树,这时的平均查找长度和顺序查找时相同。最坏情况示例就平均性能而言,二叉排序树上的查找和二分查找相差不大,并且二叉排序树上的插入和删除结点十分方便,无须大量移动结点。复杂度O(logN)关键数据结构classBinaryNode 〃节点类{public:intdata;BinaryNode *1;BinaryNode *r;BinaryNode(intdata, BinaryNode{this->data=data;this->l=l;this->r=r;}};BinaryNode*root;BinaryNode*r)boolcontains(intx,BinaryNode*t){if(t==NULL)returnfalse;elseif(x<t->data)节点,递归调用returncontains(x,t・>l);elseif(t->data<x)returncontains(x,t・>r);elsereturntrue;〃根节点为零,返回查找不到〃与当前节点数据域比较,小则找左节点,大则找右}voidinsert(intx‘BinaryNode*&t){if(t==NULL)t=newBinaryNode(x,NULL,NULL);elseif(x<t->data)insert(x,t->l);elseif(t->data<x)insert(x,t->r);〃插入过程与查找过程类似BinaryNode*findMax(BinaryNode{if(t!=NULL)while(t->r!=NULL)returnt;voidprintall(BinaryNode*&t){if(t==NULL)return;else{cout«t->data«endl;printall(t->l);printall(t->r);}程序源代码#include<iostream>#include<>usingnamespacestd;classBinaryNode 〃节点类{public:intdata;BinaryNode *1;BinaryNode *r;BinaryNode(intdata,BinaryNode*1,BinaryNode*r){this・>data二data;this->l=l;this->r=r;}};BinaryNode*root;boolcontains(intx,BinaryNode*t){〃根节点为零,返回查找不到〃与当前节点数据域比较,小则找左节点,大则找右if(t==NULL)returnfalse;elseif(x<t->data)节点,递归调用returncontains(x,t->l);elseif(t->data<x)returncontains(x,t->r);elsereturntrue;}voidinsert(intx^inaryNode*&t){if(t==NULL) 〃插入过程与查找过程类似t=newBinaryNode(x,NULL,NULL);elseif(x<t->data)insert(x,t->l);else讦(t->data<x)insert(x,t->r);}BinaryNode*findMax(BinaryNode*t){if(t!=NULL)while(t->r!=NULL)t=t->r;returnt;}voidprintall(BinaryNode*&t){if(t==NULL)return;else{cout«t->data«endl;printall(t->l);printall(t->r);}}intmain(intargc,char*argv[])//inti=l,n=l;BinaryNode*t,*max;t=NULL;insert(98,t);insert(86zt);insert(l,t);insert(14zt);insert⑶t);insert(512zt);max=findMax(t);cout«H最大值是"«max->data«endl;if(contains(4,t))cout«"查找在树内"«endl;elsecout«"查找值不在树内”vvendl;cout«"节