二叉查找树算法
㈠ c++二叉搜索树算法
#include<iostream>
usingnamespacestd;
typedefstruct_node
{
intdata;
struct_node*pLeftPtr;
struct_node*pRightPtr;
}BTreeNode;
classBinarySearchTree
{
public:
BinarySearchTree();
~BinarySearchTree();
boolCreate(int*pIntArray,intarrLength);
boolInsert(intdata);
//查找节点，searchLength为搜索长度，返回值为true表示指定的数据存在，否则不存在
boolFind(intdata,int*searchLength);
//中序输出二叉树
voidMidOutput();
//释放内存
voidDestroy();
voidDelete(intdata);
protected:
boolInsert(BTreeNode*pRoot,intdata);
boolFind(BTreeNode*pRoot,intdata,int*searchLength);
voidDelete(BTreeNode*&pRoot,intdata);
voidMidOutput(BTreeNode*pRoot);
voidDestroy(BTreeNode*pRoot);
private:
BTreeNode*m_pRoot;//二叉搜索树根节点
};
BinarySearchTree::BinarySearchTree()
{
m_pRoot=NULL;
}
BinarySearchTree::~BinarySearchTree()
{
Destroy();
}
boolBinarySearchTree::Create(int*pIntArray,intarrLength)
{
for(inti=0;i<arrLength;i++)
{
if(!Insert(*(pIntArray+i)))
returnfalse;
}
returntrue;
}
boolBinarySearchTree::Insert(BTreeNode*pRoot,intdata)
{
BTreeNode*pNewNode=newBTreeNode;
if(pNewNode==NULL)
returnfalse;
pNewNode->data=data;
pNewNode->pLeftPtr=NULL;
pNewNode->pRightPtr=NULL;
BTreeNode*pCurrentNode=pRoot;
BTreeNode*pParentNode=pCurrentNode;//保存父节点的指针
intflag=0;//标记插入节点的位置
if(pCurrentNode==NULL)
{
m_pRoot=pNewNode;
}else{
while(pCurrentNode)
{
if(data<pCurrentNode->data)
{
pParentNode=pCurrentNode;
pCurrentNode=pCurrentNode->pLeftPtr;
flag=0;
}elseif(data>pCurrentNode->data){
pParentNode=pCurrentNode;
pCurrentNode=pCurrentNode->pRightPtr;
flag=1;
}
}
if(flag==0)
{
pParentNode->pLeftPtr=pNewNode;
}else{
pParentNode->pRightPtr=pNewNode;
}
}
returntrue;
}
boolBinarySearchTree::Insert(intdata)
{
returnInsert(m_pRoot,data);
}
boolBinarySearchTree::Find(BTreeNode*pRoot,intdata,int*searchLength)
{
if(pRoot==NULL)
{
*searchLength=0;
returnfalse;
}
BTreeNode*pCurrentNode=pRoot;
staticintlength=0;
while(pCurrentNode!=NULL)
{
if(data==pCurrentNode->data)
{
*searchLength=length;
cout<<"数字"<<data<<"存在二叉树中,查找长度为:"<<endl<<length<<endl;
returntrue;
}elseif(data<pCurrentNode->data)
{
length++;
pCurrentNode=pCurrentNode->pLeftPtr;
}else{
length++;
pCurrentNode=pCurrentNode->pRightPtr;
}
}
*searchLength=length;
cout<<"数字"<<data<<"不在二叉树中,查找长度为:"<<endl<<length<<endl;
length=0;//每次查找结束，重新赋值为0
returnfalse;
}
boolBinarySearchTree::Find(intdata,int*searchLength)
{
returnFind(m_pRoot,data,searchLength);
}
voidBinarySearchTree::Destroy(BTreeNode*pRoot)
{
BTreeNode*pCurrentNode=pRoot;
if(pCurrentNode==NULL)
return;
Destroy(pCurrentNode->pLeftPtr);
Destroy(pCurrentNode->pRightPtr);
deletepCurrentNode;
m_pRoot=NULL;
}
voidBinarySearchTree::Destroy()
{
Destroy(m_pRoot);
}
voidBinarySearchTree::MidOutput(BTreeNode*pRoot)
{
if(pRoot)
{
MidOutput(pRoot->pLeftPtr);
cout<<pRoot->data<<"";
MidOutput(pRoot->pRightPtr);
}
}
voidBinarySearchTree::MidOutput()
{
MidOutput(m_pRoot);
}
voidBinarySearchTree::Delete(intdata)
{
Delete(m_pRoot,data);
}
voidBinarySearchTree::Delete(BTreeNode*&pRoot,intdata)
{
if(!pRoot)
return;
elseif(data==pRoot->data){
if(pRoot->pLeftPtr==NULL&&pRoot->pRightPtr==NULL)//叶子节点
{
deletepRoot;
pRoot=NULL;
}elseif(pRoot->pLeftPtr!=NULL&&pRoot->pRightPtr==NULL){//只有左子树
BTreeNode*pNode=pRoot->pLeftPtr;
deletepRoot;
pRoot=pNode;
}elseif(pRoot->pLeftPtr==NULL&&pRoot->pRightPtr!=NULL){//只有右子树
BTreeNode*pNode=pRoot->pRightPtr;
deletepRoot;
pRoot=pNode;
}else{//有左右子树
//找到左子树的最大节点
BTreeNode*pCurrentNode=pRoot->pLeftPtr;
BTreeNode*pParentNode=NULL;
while(pCurrentNode->pRightPtr!=NULL)
{
pParentNode=pCurrentNode;
pCurrentNode=pCurrentNode->pRightPtr;
}
pRoot->data=pCurrentNode->data;
if(pParentNode)
{
pParentNode->pRightPtr=pCurrentNode->pLeftPtr;
}else{
pRoot->pLeftPtr=pCurrentNode->pLeftPtr;
}
deletepCurrentNode;
}
}elseif(data<pRoot->data)
Delete(pRoot->pLeftPtr,data);
else
Delete(pRoot->pRightPtr,data);
}
voidmain()
{
intdata[8];
cout<<"请输入整形数据,数据用空格隔开,回车键结束输入"<<endl;
for(inti=0;i<8;i++)
cin>>data[i];
//intdata[8]={13,15,6,20,14,5,7,18};
BinarySearchTreetree;
tree.Create(data,sizeof(data)/sizeof(data[0]));
cout<<"插入数据后的二叉树为:"<<endl;
tree.MidOutput();
cout<<endl;
intlen_1=0;
intlen_2=0;
tree.Find(14,&len_1);
tree.Find(21,&len_2);
tree.Delete(20);
cout<<"删除数字20后的二叉树结果:"<<endl;
tree.MidOutput();
cout<<endl;
tree.Delete(15);
cout<<"删除数字15后的二叉树结果:"<<endl;
tree.MidOutput();
cout<<endl;
}
㈡ 二叉排序树定义
二叉排序树（Binary Sort Tree），又称二叉查找树（Binary Search Tree），亦称二叉搜索树。是数据结构中的一类。在一般情况下，查询效率比链表结构要高。
定义一：
一棵空树，或者是具有下列性质的二叉树：
（1）若左子树不空，则左子树上所有结点的值均小于它的根结点的值；
（2）若右子树不空，则右子树上所有结点的值均大于它的根结点的值；
（3）左、右子树也分别为二叉排序树；
（4）没有键值相等的结点。
定义二：
一棵空树，或者是具有下列性质的二叉树：
（1）若左子树不空，则左子树上所有结点的值均小于它的根结点的值；
（2）若右子树不空，则右子树上所有结点的值均大于或等于它的根结点的值；
（3）左、右子树也分别为二叉排序树。
定义三：
一棵空树，或者是具有下列性质的二叉树：
（1）若左子树不空，则左子树上所有结点的值均小于或等于它的根结点的值；
（2）若右子树不空，则右子树上所有结点的值均大于它的根结点的值；
（3）左、右子树也分别为二叉排序树；
【注】：以上的三种定义在不同的数据结构教材中均有不同的定义方式 但是都是正确的 在开发时需要根据不 同的需求进行进行选择。
插入删除：
与次优二叉树相对，二叉排序树是一种动态树表。其特点是：树的结构通常不是一次生成的，而是在查找过程中，当树中不存在关键字等于给定值的结点时再进行插入。新插入的结点一定是一个新添加的叶子结点，并且是查找不成功时查找路径上访问的最后一个结点的左孩子或右孩子结点。
㈢ 二叉查找树算法
#include <iostream>using namespace std;typedef struct _node{ int data; struct _node *pLeftPtr; struct _node *pRightPtr;}BTreeNode;class BinarySearchTree{public: BinarySearchTree(); ~BinarySearchTree(); bool Create(int* pIntArray,int arrLength); bool Insert(int data); // 查找节点，searchLength为搜索长度，返回值为true表示指定的数据存在，否则不存在 bool Find(int data, int* searchLength); // 中序输出二叉树 void MidOutput(); // 释放内存 void Destroy(); void Delete(int data);protected: bool Insert(BTreeNode* pRoot, int data); bool Find(BTreeNode* pRoot,int data, int *searchLength); void Delete(BTreeNode* &pRoot, int data); void MidOutput(BTreeNode* pRoot); void Destroy(BTreeNode* pRoot);private: BTreeNode* m_pRoot; //二叉搜索树根节点};BinarySearchTree::BinarySearchTree(){ m_pRoot = NULL;}BinarySearchTree::~BinarySearchTree(){ Destroy();}bool BinarySearchTree::Create(int* pIntArray,int arrLength){ for(int i=0; i<arrLength; i++) { if(!Insert(*(pIntArray+i))) return false; } return true;}bool BinarySearchTree::Insert(BTreeNode* pRoot, int data){ BTreeNode* pNewNode = new BTreeNode; if(pNewNode == NULL) return false; pNewNode->data = data; pNewNode->pLeftPtr = NULL; pNewNode->pRightPtr = NULL; BTreeNode* pCurrentNode = pRoot; BTreeNode* pParentNode = pCurrentNode;// 保存父节点的指针 int flag = 0;// 标记插入节点的位置 if(pCurrentNode == NULL) { m_pRoot = pNewNode; }else{ while(pCurrentNode) { if(data < pCurrentNode->data) { pParentNode = pCurrentNode; pCurrentNode = pCurrentNode->pLeftPtr; flag = 0; }else if(data > pCurrentNode->data){ pParentNode = pCurrentNode; pCurrentNode = pCurrentNode->pRightPtr; flag = 1; } } if(flag == 0) { pParentNode->pLeftPtr = pNewNode; }else{ pParentNode->pRightPtr = pNewNode; } } return true; }bool BinarySearchTree::Insert(int data){ return Insert(m_pRoot,data);}bool BinarySearchTree::Find(BTreeNode* pRoot,int data, int *searchLength){ if(pRoot == NULL) { *searchLength = 0; return false; } BTreeNode* pCurrentNode = pRoot; static int length = 0; while(pCurrentNode != NULL) { if(data == pCurrentNode->data) { *searchLength = length; cout<<"数字"<<data<<"存在二叉树中,查找长度为: "<<endl<<length<<endl; return true; }else if(data < pCurrentNode->data) { length ++; pCurrentNode = pCurrentNode->pLeftPtr; }else{ length ++; pCurrentNode = pCurrentNode->pRightPtr; } } *searchLength = length; cout<<"数字"<<data<<"不在二叉树中,查找长度为: "<<endl<<length<<endl; length = 0; // 每次查找结束，重新赋值为0 return false;}bool BinarySearchTree::Find(int data, int* searchLength){ return Find(m_pRoot,data,searchLength);}void BinarySearchTree::Destroy(BTreeNode* pRoot){ BTreeNode* pCurrentNode = pRoot; if(pCurrentNode == NULL) return; Destroy(pCurrentNode->pLeftPtr); Destroy(pCurrentNode->pRightPtr); delete pCurrentNode; m_pRoot = NULL;}void BinarySearchTree::Destroy(){ Destroy(m_pRoot);}void BinarySearchTree::MidOutput(BTreeNode* pRoot){ if(pRoot) { MidOutput(pRoot->pLeftPtr); cout<<pRoot->data <<" "; MidOutput(pRoot->pRightPtr); }}void BinarySearchTree::MidOutput(){ MidOutput(m_pRoot);}void BinarySearchTree::Delete(int data){ Delete(m_pRoot,data);}void BinarySearchTree::Delete(BTreeNode* &pRoot, int data){ if(!pRoot) return; else if(data == pRoot->data){ if(pRoot->pLeftPtr == NULL && pRoot->pRightPtr == NULL) // 叶子节点 { delete pRoot; pRoot = NULL; }else if(pRoot->pLeftPtr != NULL && pRoot->pRightPtr == NULL){ // 只有左子树 BTreeNode* pNode = pRoot->pLeftPtr; delete pRoot; pRoot = pNode; }else if(pRoot->pLeftPtr == NULL && pRoot->pRightPtr != NULL){ // 只有右子树 BTreeNode* pNode = pRoot->pRightPtr; delete pRoot; pRoot = pNode; }else{ // 有左右子树 // 找到左子树的最大节点 BTreeNode* pCurrentNode = pRoot->pLeftPtr; BTreeNode* pParentNode = NULL; while(pCurrentNode->pRightPtr != NULL) { pParentNode = pCurrentNode; pCurrentNode = pCurrentNode->pRightPtr; } pRoot->data = pCurrentNode->data; if(pParentNode) { pParentNode->pRightPtr = pCurrentNode->pLeftPtr; }else{ pRoot->pLeftPtr= pCurrentNode->pLeftPtr; } delete pCurrentNode; } }else if(data < pRoot->data) Delete(pRoot->pLeftPtr, data); else Delete(pRoot->pRightPtr, data);}void main(){ int data[8]; cout<<"请输入整形数据, 数据用空格隔开, 回车键结束输入"<<endl; for(int i=0; i<8; i++) cin>>data[i]; // int data[8] = {13,15,6,20,14,5,7,18}; BinarySearchTree tree; tree.Create(data,sizeof(data)/sizeof(data[0])); cout<<"插入数据后的二叉树为: "<<endl; tree.MidOutput(); cout<<endl; int len_1=0; int len_2=0; tree.Find(14,&len_1); tree.Find(21,&len_2); tree.Delete(20); cout<<"删除数字20后的二叉树结果: "<<endl; tree.MidOutput(); cout<<endl; tree.Delete(15); cout<<"删除数字15后的二叉树结果: "<<endl; tree.MidOutput(); cout<<endl;}
㈣ 实验四 二叉排序树查找
#include<iostream.>
using namespace std;
typedef int KeyType;
typedef struct tree//声明树的结构
{
struct tree *left; //存放左子树的指针
struct tree *right; //存放又子树的指针
KeyType key; //存放节点的内容
} BSTNode, * BSTree; //声明二叉树的链表
BSTree insertBST(BSTree tptr,KeyType key)// 在二叉排序树中插入结点
{ //若二叉排序树tptr中没有关键字为key的结点，则插入，否则直接返回
BSTree f,p=tptr; //p的初值指向根结点
while(p) //查找插入位置，循环结束时，p是空指针，f指向待插入结点的双亲
{
if(p->key==key) //树中已有key，无须插入
return tptr;
f=p; //f保存当前查找的结点，即f是p的双亲
p=(key<p->key)?p->left:p->right;
}
p=(BSTree )malloc(sizeof(BSTNode)); //生成新结点
p->key=key; p->left=p->right=NULL;
if(tptr==NULL) //原树为空，新插入的结点为新的根
tptr=p;
else
if(key<f->key)
f->left=p;
else
f->right=p;
return tptr;
}
BSTree createBST()//建立二叉树
{
BSTree t=NULL; //根结点
KeyType key;
cin>>key;
while(key!=-1)
{
t=insertBST(t,key);
cin>>key;
}
return t;
}
void inorder_btree(BSTree root)// 中序遍历打印二叉排序树
{
BSTree p=root;
if(p!=NULL){
inorder_btree(p->left );
cout<<" "<<p->key<<" ";
inorder_btree(p->right );
}
}
int searchBST(BSTree t,KeyType key)//查找
{
if(key==t->key)
return 1;
if(t==NULL)
return 0;
if(key<t->key)
return searchBST(t->left,key);
else
return searchBST(t->right,key);
}
BSTree deleteBST(BSTree tptr,KeyType key)//删除
{
BSTree p,tmp,parent=NULL;
p=tptr;
while(p)
{
if(p->key==key)
break;
parent=p;
p=(key<p->key)?p->left:p->right;
}
if(!p) return NULL;
tmp=p;
if(!p->right&&!p->left) /*p的左右子树都为空*/
{
if(!parent) //要删根，须修改根指针
tptr=NULL;
else if(p==parent->right)
parent->right=NULL;
else
parent->left=NULL;
free(p);
}
else if(!p->right) //p的右子树为空，则重接p的左子树
{
p=p->left;
if(!parent) //要删根，须修改根指针
tptr=p;
else if(tmp==parent->left)
parent->left=p;
else
parent->right=p;
free(tmp);
}
else if(!p->left) //的左子树为空，则重接p的左子树
{
p=p->right;
if(!parent) //要删根，须修改根指针
tptr=p;
else if(tmp==parent->left)
parent->left=p;
else
parent->right=p;
free(tmp);
}
else if(p->right&&p->left) //p有左子树和右子树，用p的后继覆盖p然后删去后继
{ //另有方法：用p的前驱覆盖p然后删去前驱||合并p的左右
parent=p; //由于用覆盖法删根，则不必特殊考虑删根
p=p->right;
while(p->left)
{
parent=p;
p=p->left;
}
tmp->key=p->key;
if(p==parent->left)
parent->left=NULL;
else
parent->right=NULL;
free(p);
}
return tptr;
}
int main()
{
KeyType key;
int flag,test;
char cmd;
BSTree root;
do
{
cout<<"\n\n"<<endl;
cout<<"\t\t*******请选择你要执行的操作:********"<<endl;
cout<<"\n"<<endl;
cout<<"\t\t C.创建一棵二叉排序树\n";
cout<<"\t\t E.结束本程序\n";
cout<<"\n\n\t\t************************************"<<endl;
flag=0;
do
{
if(flag!=0)
cout<<"选择操作错误！请重新选择！\n";
fflush(stdin);
cin>>cmd;
flag++;
}while(cmd!='c'&&cmd!='C'&&cmd!='a'&&cmd!='A');
if(cmd=='c'||cmd=='C')
{
cout<<"请输入你所要创建的二叉树的结点的值，以-1结束：\n";
root=createBST();
do
{
flag=0;
cout<<"\n\n中序遍历二叉树："<<endl;
inorder_btree(root);
cout<<"\n"<<endl;
cout<<"\t\t************请选择你要对这棵二叉树所做的操作:**************"<<endl;
cout<<"\t\t** **"<<endl;
cout<<"\t\t** S......查找你想要寻找的结点 **"<<endl;
cout<<"\t\t** I......插入你想要插入的结点 **"<<endl;
cout<<"\t\t** D......删除你想要删除的结点 **"<<endl;
cout<<"\t\t** Q......结束对这棵二叉树的操作 **"<<endl;
cout<<"\t\t** **"<<endl;
cout<<"\t\t***********************************************************"<<endl;
do{
if(flag!=0)
cout<<"选择操作错误！请重新选择！\n";
fflush(stdin);
scanf("%c",&cmd);
flag++;
}while(cmd!='s'&&cmd!='S'&&cmd!='i'&&cmd!='I'&&cmd!='d'&&cmd!='D'&&cmd!='q'&&cmd!='Q');
switch(cmd)
{
case 's':
case 'S':
cout<<"请输入你要查找结点的关键字：\n";
cin>>key;
test=searchBST(root,key);
if(test==0)
cout<<"\n对不起，你所查找的结点 "<<key<<"不存在!";
else
cout<<"\n成功找到结点\n"<<key<<" ";
break;
case 'i':
case 'I':
cout<<"请输入你要插入结点的关键字：\n";
cin>>key;
root=insertBST(root,key); //注意必须将值传回根
break;
case 'd':
case 'D':
cout<<"请输入你要删除结点的关键字：\n";
cin>>key;
root=deleteBST(root,key); //注意必须将值传回根
if(root==NULL)
cout<<"\n对不起，你所删除的结点 "<<key<<" 不存在!\n";
else
cout<<"\n成功删除结点 "<<key<<" ";
break;
}
}while(cmd!='q'&&cmd!='Q');
}
}while(cmd!='e'&&cmd!='E');
return 0;
}
㈤ 二叉搜索树的基本操作
哈哈，居然有人来提问了，城院的
我刚奋斗了2小时做了下，你看看对不？
Test5.cpp:
#include<iostream.h>
#include<stdlib.h>
typedefdoubleElemType;
#defineMaxsize100
#include"BSTree.h"
voidmain()
{
inti,n;
ElemTypex;
ElemTypea[Maxsize];
BTreeNode*bst;
InitBSTree(bst);
cout<<"请输入你所要测试的二叉搜索树的结点的个数:";
cin>>n;
cout<<"请输入你要测试的二叉搜索树:"<<endl;
for(i=0;i<n;i++){
cin>>a[i];
}
CreateBSTree(bst,a,n);
cout<<"你输入的二叉搜索树的广义表形式为:";
PrintBSTree(bst);
cout<<endl;
cout<<"输入一个待插入结点的整数值:";
cin>>x;
Insert(bst,x);
cout<<"插入结点后的二叉搜索树的广义表形式为:";
PrintBSTree(bst);
cout<<endl;
cout<<"输入一个待删除结点的值:";
cin>>x;
if(Delete(bst,x))cout<<"删除元素"<<x<<"成功!"<<endl;
elsecout<<"删除元素"<<x<<"失败!"<<endl;
PrintBSTree(bst);
cout<<endl;
cout<<"该二叉搜索树中的最大值为:"<<MaxBSTree(bst)<<endl;
}
BSTree.h:
structBTreeNode{
ElemTypedata;
ElemTypecount;
BTreeNode*left;
BTreeNode*right;
};
voidInitBSTree(BTreeNode*&bst)//初始化二叉搜索树
{
bst=NULL;
}
voidPrintBSTree(BTreeNode*bst)//以广义表形式输出二叉搜索树
{
if(bst!=NULL){
cout<<bst->data;
cout<<'['<<bst->count<<']';
if(bst->left!=NULL||bst->right!=NULL){
cout<<'(';
PrintBSTree(bst->left);
if(bst->right!=NULL)
cout<<',';
PrintBSTree(bst->right);
cout<<')';
}
}
}
voidInsert(BTreeNode*&bst,ElemTypeitem)
{
BTreeNode*t=bst,*parent=NULL;
while(t!=NULL){
parent=t;
if(item<t->data)t=t->left;
elseif(item>t->data)t=t->right;
else{
t->count++;
break;
}
}
if((t==NULL)||item!=parent->data){
BTreeNode*p=newBTreeNode;
p->data=item;
p->count=1;
p->left=p->right=NULL;
if(parent==NULL)bst=p;
elseif(item<parent->data)parent->left=p;
elseparent->right=p;
}
}
voidCreateBSTree(BTreeNode*&bst,ElemTypea[],intn)//建立二叉搜索树（用非递归算法实现)
{
bst=NULL;
for(inti=0;i<n;i++)
Insert(bst,a[i]);
}
boolDelete(BTreeNode*&bst,ElemTypeitem)
{
BTreeNode*t=bst,*parent=NULL,*m,*n;
while((t!=NULL)&&(t->data!=item)){
if(item==t->data)break;
else{
if(item<t->data){
parent=t;
t=t->left;
}
else{
parent=t;
t=t->right;
}
}
}
if(t->count>1){
t->count--;
returntrue;
}
elseif(t==NULL){
cout<<"没有找到待删除结点!"<<endl;
returnfalse;
}
else{
if((t->left==NULL)&&(t->right==NULL)){
if(t==bst)
bst=NULL;
else{
if(t==parent->left)
parent->left=NULL;
else
parent->right=NULL;
}
}
elseif((t->left==NULL)||(t->right==NULL)){
if(t==bst){
if(t->left==NULL)
bst=t->right;
else
bst=t->left;
}
else{
if((t==parent->left)&&(t->left!=NULL))
parent->left=t->left;
elseif((t==parent->left)&&(t->right!=NULL))
parent->left=t->right;
elseif((t==parent->right)&&(t->left!=NULL))
parent->right=t->left;
elseif((t==parent->right)&&(t->right!=NULL))
parent->right=t->right;
}
}
else{
if((t->left!=NULL)&&(t->right!=NULL)){
m=t;
n=t->left;
while(n->right!=NULL){
m=n;
n=n->right;
}
t->data=n->data;
if(m==t)
t->left=n->left;
else
m->right=n->left;
t=n;
}
}
free(t);
returntrue;
}
}
ElemTypeMaxBSTree(BTreeNode*bst)//求二叉搜索树的最大结点值（用非递归算法实现）
{
ElemTypemax;
if(bst==NULL){
cout<<"该二叉搜索树为空！"<<endl;
exit(1);
}
max=bst->data;
while(bst!=NULL){
if(max<bst->data)
max=bst->data;
bst=bst->right;
}
returnmax;
}
你试试吧，应该对的，选我做答案哈~
㈥ 二叉树查找树算法实现
#include<stdio.h>
#include<stdlib.h>
#define OK 1
#define ERROR 0
#define OVERFLOW -1
#define EQ(a,b) ((a)==(b))
#define LT(a,b) ((a)<(b))
typedef int ElemType;
typedef int Status;
typedef struct TElemType{
int key;
int num;
}TElemType;
typedef struct BiTNode{
TElemType data;
struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree;
Status SearchBST(BiTree T,int key,BiTree f,BiTree &p){
if(!T) { p=f; return ERROR;}
else if(EQ(T->data.key,key)) { p=T; return OK; }
else if(LT(key,T->data.key))
return SearchBST(T->lchild,key,T,p);
else return SearchBST(T->rchild,key,T,p);
}
Status SearchBST1(BiTree T,int key,BiTree f,BiTree &p){
if(!T) { p=f; return ERROR;}
else if(EQ(T->data.key,key)) {
printf("%d %d",p->data.key,p->data.num);
p=T; return OK; }
else if(LT(key,T->data.key))
return SearchBST(T->lchild,key,T,p);
else return SearchBST(T->rchild,key,T,p);
}
Status InsertBST(BiTree &T,TElemType e){
BiTree s,p;
if(!SearchBST(T,e.key,NULL,p)){
s=(BiTree)malloc(sizeof(BiTNode));
s->data=e;
s->lchild=s->rchild=NULL;
if(!p) T=s;
else if(LT(e.key,p->data.key)) p->lchild=s;
else p->rchild=s;
return OK;
}
}
Status Output(TElemType e){
printf("%d ",e.key);
printf("%d\n",e.num);
}
Status PreOrderTraver( BiTree T){//二叉树先序遍历
if(T==NULL) return ERROR;
else{
Output(T->data);
PreOrderTraver(T->lchild);
PreOrderTraver(T->rchild);}
return OK;
}
int main()
{
BiTree T,f=NULL,q;
TElemType a;
int i,n,b;
printf("请输入你要创建的二叉排序树的结点个数:\n");
scanf("%d",&n);
for(i=0;i<n;i++){
scanf("%d",a.key);
scanf("%d",a.num);
InsertBST(T,a);
}
printf("请输入你要查找的关键字: ");{
scanf("%d",b);
if(SearchBST1(T,b,f,q)) printf("查找成功！\n");
else printf("查找失败！\n");}
printf("二叉树的先序遍历:\n");
PreOrderTraver(T);
system("pause");
return 0;
}
这个就是！希望可以帮助你！
㈦ 题目3． 平衡二叉树算法查找树中某节点的时间复杂度是多少
平均查找的时间复杂度为O(log n)。
平衡树的查找过程和排序树的相同。在查找过程中和给定值进行比较关键字个数不超过树的深度。
如果二叉树的元素个数为n，那么不管是对树进行插入节点、查找、删除节点都是log(n)次循环调用就可以了。它的时间复杂度相对于其他数据结构如数组等是最优的。
是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。常用算法有红黑树、AVL、Treap、伸展树等。
(7)二叉查找树算法扩展阅读：
二叉树也是递归定义的，其结点有左右子树之分，逻辑上二叉树算法有五种基本形态：
(1)空二叉树——(a)
(2)只有一个根结点的二叉树——(b);
(3)右子树为空的二叉树——(c);
(4)左子树为空的二叉树——(d);
(5)完全二叉树——(e)
注意：尽管二叉树与树有许多相似之处，但二叉树不是树的特殊情形。
㈧ 二叉搜索树的算法实现
1 二叉排序树的查找算法
2 在二叉排序树插入结点的算法
3 在二叉排序树删除结点的算法
4 二叉排序树性能分析 在二叉排序树b中查找x的过程为：
若b是空树，则搜索失败，否则：
若x等于b的根结点的数据域之值，则查找成功；否则：
若x小于b的根结点的数据域之值，则搜索左子树；否则：
查找右子树。
Status SearchBST(BiTree T, KeyType key, BiTree f, BiTree &*p){
//在根指针T所指二叉排序树中递归地查找其关键字等于key的数据元素，若查找成功，
//则指针p指向该数据元素结点，并返回TRUE，否则指针指向查找路径上访问的最后
//一个结点并返回FALSE，指针f指向T的双亲，其初始调用值为NULL
if(!T){ p=f; return FALSE;} //查找不成功
else if EQ(key, T->data.key) {P=T; return TRUE;} //查找成功
else if LT(key,T->data.key)
return SearchBST(T->lchild, key, T, p); //在左子树中继续查找
else return SearchBST(T->rchild, key, T, p); //在右子树中继续查找
pascal语言实现
type
Link = ^tree;
Tree = record
D :longint;
Left :link;
Right :link;
End;
function search(n :longint;t :link):boolean;
Begin
If t^.d < n then begin
If t^.right = nil then exit(false) else exit(search(n,t^.right));
End;
If t^.d > n then begin
If t^.left = nil then exit(false) else exit(search(n,t^.left));
End;
Exit(true);
End; 向一个二叉排序树b中插入一个结点s的算法，过程为：
若b是空树，则将s所指结点作为根结点插入，否则：
若s->data等于b的根结点的数据域之值，则返回，否则：
若s->data小于b的根结点的数据域之值，则把s所指结点插入到左子树中，否则：
把s所指结点插入到右子树中。
/*当二叉排序树T中不存在关键字等于e.key的数据元素时，插入e并返回TRUE，否则返回FALSE*/
Status InsertBST(BiTree &T, ElemType e)
{
if(!SearchBST(T, e.key, NULL,p)
{
s=(BiTree *)malloc(sizeof(BiTNode));
s->data = e; s->lchild = s->rchild = NULL;
if(!p) T-s;
//被插结点*s为新的根结点
else if LT(e.key, p->data.key) p->lchld = s;
//被子插结点*s为左孩子
else ->rchild = s;
//被插结点*s为右孩子
return TRUE;
}
else
return FALSE;
//树中已有关键字相同的结点，不再插入
}
pascal代码:
procere push(n :longint;var t:link);
Var P,q :link;
Begin
If t^.d < n then begin
If t^.right = nil then begin
New(p);
P^.d := n;
P^.right := nil;
P^.left := nil;
T^.right := p;
End else push(n,t^.right);
End else begin
If t^.left = nil then begin
New(p);
P^.d := n;
P^.right := nil;
P^.left := nil;
T^.left := p;
End else push(n,t^.left);
End;
End; 在二叉排序树删去一个结点，分三种情况讨论：
若*p结点为叶子结点，即PL(左子树)和PR(右子树)均为空树。由于删去叶子结点不破坏整棵树的结构，则只需修改其双亲结点的指针即可。
若*p结点只有左子树PL或右子树PR，此时只要令PL或PR直接成为其双亲结点*f的左子树或右子树即可，作此修改也不破坏二叉排序树的特性。
若*p结点的左子树和右子树均不空。在删去*p之后，为保持其它元素之间的相对位置不变，可按中序遍历保持有序进行调整，可以有两种做法：其一是令*p的左子树为*f的左子树，*s为*f左子树的最右下的结点，而*p的右子树为*s的右子树；其二是令*p的直接前驱（或直接后继）替代*p，然后再从二叉排序树中删去它的直接前驱（或直接后继）。在二叉排序树上删除一个结点的算法如下：
Status DeleteBST(BiTree &T, KeyType key){
//若二叉排序树T中存在关键字等于key的数据元素时，则删除该数据元素，并返回
//TRUE；否则返回FALSE
if(!T) return FALSE; //不存在关键字等于key的数据元素
else{
if(EQ(key, T->data.key)) {return Delete(T)}; 找到关键字等于key的数据元素
else if(LT(key, T->data.key)) return DeleteBST(T->lchild, key);
else return DeleteBST(T->rchild, key);
}
}
Status Delete(BiTree &p){
//从二叉排序树中删除结点p，并重接它的左或右子树
if(!p->rchild){ //右子树空则只需重接它的左子树
q=p; p=p->lchild; free(q);
}
else if(!p->lchild){ //左子树空只需重接它的右子树
q=p; p=p->rchild; free(q);
}
else{ //左右子树均不空
q=p;
s=p->lchild;
while(s->rchild){
q=s;
s=s->rchild
} //转左，然后向右到尽头
p->data = s->data; //s指向被删结点的“前驱”
if(q!=p)
q->rchild = s->lchild; //重接*q的右子树
else
q->lchild = s->lchild; //重接*q的左子树
free(s);
}
return TRUE;
}
㈨ 求个二叉排序树查找的递归算法
#include<iostream> #include<string> #include<cstring> using namespace std; class BinaryTreeNode {public: string data; int w; BinaryTreeNode *leftchild; BinaryTreeNode *rightchild; BinaryTreeNode *parent; int pos[50]; BinaryTreeNode(string a,int postion) { data=a; w=1; leftchild=NULL; rightchild=NULL; parent=NULL; pos[0]=postion; } }; class BSTree {public: BinaryTreeNode *root; BSTree(){root=NULL;} void Insert(string a,int postion); void Delete(string key); BinaryTreeNode *Search(string key,BinaryTreeNode*& pr,BinaryTreeNode *&parent); void InOrder(BinaryTreeNode *&root); void PreOrder(BinaryTreeNode *&root); }; void BSTree::InOrder(BinaryTreeNode *&root) { if(root) { InOrder(root->leftchild); cout<<root->data; cout<<" "<<root->w<<endl; InOrder(root->rightchild); } } void BSTree::PreOrder(BinaryTreeNode*& root) { if(root) { cout<<root->data; cout<<" "<<root->w<<endl; PreOrder(root->leftchild); PreOrder(root->rightchild); } } BinaryTreeNode *BSTree::Search(string key,BinaryTreeNode*& pr,BinaryTreeNode*& parents) { BinaryTreeNode *p=root; pr=root; while(p) { parents=p; if(key<p->data) { pr=p; p=p->leftchild; } else if(key>p->data) { pr=p; p=p->rightchild; } else return p; } return NULL; } void BSTree::Insert(string a,int postion) { BinaryTreeNode *pr,*p,*pp=NULL; p=Search(a,pr,pp); if(p!=NULL) { p->w++; p->pos[p->w-1]=postion; return; } BinaryTreeNode *r=new BinaryTreeNode(a,postion); if(!root) root=r; else if(a<pp->data) pp->leftchild=r; else pp->rightchild=r; } void BSTree::Delete(string key) { BinaryTreeNode *p,*pr,*pp; p=Search(key,pp,pr); if(p==NULL) return; if(p->leftchild&&p->rightchild) { BinaryTreeNode *s=p->rightchild,*ps=p; while(s->leftchild) { ps=s; s=s->leftchild; } p->data=s->data; p->w=s->w; for(int i=0;i<s->w;i++) { p->pos[i]=s->pos[i]; } pp=ps; p=s; } if(p->leftchild) { if(pp->leftchild==p) { pp->leftchild=p->leftchild; p->leftchild->parent=pp; } else { pp->rightchild=p->leftchild; p->leftchild->parent=pp; } } else if(p->rightchild) { if(pp->leftchild
㈩ 二叉树算法有哪些应用场景
二叉树常被用于实现二叉查找树和二叉堆。
在计算机科学中，二叉树是每个结点最多有两个子树的树结构。通常子树被称作“左子树”和“右子树”。
根据不同的用途可分为：
1、完全二叉树——若设二叉树的高度为h，除第 h 层外，其它各层 (1～h-1) 的结点数都达到最大个数，第h层有叶子结点，并且叶子结点都是从左到右依次排布，这就是完全二叉树。
2、满二叉树——除了叶结点外每一个结点都有左右子叶且叶子结点都处在最底层的二叉树。
3、平衡二叉树——平衡二叉树又被称为AVL树（区别于AVL算法），它是一棵二叉排序树，且具有以下性质：它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。
(10)二叉查找树算法扩展阅读
深度为h的二叉树最多有个结点(h>=1)，最少有h个结点。对于任意一棵二叉树，如果其叶结点数为N0，而度数为2的结点总数为N2，则N0=N2+1。
有N个结点的完全二叉树各结点如果用顺序方式存储，则结点之间有如下关系为若I为结点编号则 如果I>1，则其父结点的编号为I/2。如果2*I<=N，则其左孩子（即左子树的根结点）的编号为2*I。若2*I>N，则无左孩子。如果2*I+1<=N，则其右孩子的结点编号为2*I+1。