二叉搜索树的添加、删除、查找、层次遍历(小白必看)
前面,我们介绍了树的基本操作,这几篇都是数据结构小白必会的东西,今天再分享一篇
#include <iostream>
#include <stdlib.h>
using namespace std;
typedef int ElemType;
struct Tree
{ElemType elem;Tree *lchild;Tree *rchild;
};
struct Node
{Tree *elem;Node *next;
};
struct Queue
{Node *front;Node *rear;
};
Tree *CreatBinaryTree();
void PrintBinaryTree(Tree *t);
Queue CreatQueue();
bool isEmpty(Queue *Q);
void AddQueue(Queue *Q,Tree *N);
Tree *DeleteQueue(Queue *Q);
//二叉搜索树
Tree *Find(Tree *BST,ElemType elem);
Tree *FindMax(Tree *BST);
Tree *FindMin(Tree *BST);
Tree *Insert(Tree *BST,ElemType elem);
Tree *Delete(Tree *BST,ElemType elem);
int main()
{int opt;ElemType elem;Tree *position=NULL;Tree *BST=NULL;while(opt!=7){puts("1搜索 2搜索最大值 3搜索最小值");puts("4添加元素 5打印 6删除");cin>>opt; switch(opt){case 1:{cout<<"请输入元素"<<endl;cin>>elem;position=Find(BST,elem);if(position==NULL)cout<<"搜索失败"<<endl;else{cout<<"搜索成功!"<<endl<<"其左孩子值为:"<<position->lchild->elem<<" 其右孩子的值为:"<<position->rchild->elem<<endl; } break;}case 2:{position=FindMax(BST);if(position!=NULL)cout<<"最大值为:"<<position->elem<<endl; break;}case 3:{position=FindMin(BST);if(position!=NULL)cout<<"最小值为:"<<position->elem<<endl; break;}case 4:{
// cout<<"请输入你要添加的元素"<<endl;cin>>elem;BST=Insert(BST,elem);break;}case 5:{PrintBinaryTree(BST);cout<<endl;break;}case 6:{
// cout<<"请输入删除的元素"<<endl;cin>>elem;BST=Delete(BST,elem);break;} } }return 0;
}Tree *CreatBinaryTree()//先序创建
{Tree *t;ElemType elem;cin>>elem;//1 2 4 0 0 5 0 0 3 6 0 0 7 0 0if(elem==0){t=NULL; }else{t=(Tree *)malloc(sizeof(Tree));t->elem=elem;t->lchild=CreatBinaryTree();t->rchild=CreatBinaryTree();}return t;
}
void PrintBinaryTree(Tree *t)//层次遍历
{Queue Q=CreatQueue();AddQueue(&Q,t);while(!isEmpty(&Q)){t=DeleteQueue(&Q); cout<<t->elem<<" ";if(t->lchild)AddQueue(&Q,t->lchild);if(t->rchild)AddQueue(&Q,t->rchild);}
}
Queue CreatQueue()
{Queue Q;Q.front=Q.rear=(Node*)malloc(sizeof(Node));Q.front->next=NULL;return Q;
}
bool isEmpty(Queue *Q)
{return Q->front->next==NULL;
}
void AddQueue(Queue *Q,Tree *elem)
{if(elem){Q->rear->next=(Node*)malloc(sizeof(Node));Q->rear=Q->rear->next;Q->rear->elem=elem;Q->rear->next=NULL;}
}
Tree *DeleteQueue(Queue *Q)
{if(!isEmpty(Q)){Tree*t;Node *p=Q->front->next;if(p==Q->rear)Q->rear=Q->front;Q->front->next=p->next;t=p->elem;free(p);return t;}else return NULL;
}Tree *Find(Tree *BST,int elem)
{/*if(!BST) return NULL;if(elem<BST->elem){return Find(BST->lchild,elem);}else if(elem>BST->elem){return Find(BST->rchild,elem);}else {return BST;}*/while(BST){if(elem<BST->elem){BST=BST->lchild; }else if(elem>BST->elem){BST=BST->rchild;}else{return BST;}}return NULL;
}
Tree *FindMax(Tree *BST)
{
/* if(BST){if(BST->rchild==NULL)return BST;else return FindMax(BST->rchild); }else return NULL;
*/ if(BST) while(BST->rchild){BST=BST->rchild;}return BST;
}
Tree *FindMin(Tree *BST)
{if(BST==NULL) return NULL;else {if(BST->lchild==NULL)return BST;else return FindMin(BST->lchild);}
/* if(BST)while(BST->lchild){BST=BST->lchild;}return BST;
*/
}
Tree *Insert(Tree *BST,ElemType elem)
{if(!BST){BST=(Tree*)malloc(sizeof(Tree));BST->elem=elem;BST->lchild=BST->rchild=NULL;}if(elem<BST->elem)//左 {BST->lchild=Insert(BST->lchild,elem); }if(elem>BST->elem)//右 {BST->rchild=Insert(BST->rchild,elem);} return BST;
}Tree *Delete(Tree *BST,ElemType elem)
{Tree *Tmp;if(BST!=NULL){if(elem<BST->elem){BST->lchild=Delete(BST->lchild,elem);}else if(elem>BST->elem){BST->rchild=Delete(BST->rchild,elem);}else{if(BST->lchild&&BST->rchild){Tmp=FindMin(BST->rchild);BST->elem=Tmp->elem;BST->rchild=Delete(BST->rchild,BST->elem);}else{Tmp=BST;if(BST->lchild!=NULL)BST=BST->lchild;if(BST->rchild!=NULL)BST=BST->rchild;free(Tmp);}}}return BST;
}
二叉搜索树的添加、删除、查找、层次遍历(小白必看)
前面,我们介绍了树的基本操作,这几篇都是数据结构小白必会的东西,今天再分享一篇
#include <iostream>
#include <stdlib.h>
using namespace std;
typedef int ElemType;
struct Tree
{ElemType elem;Tree *lchild;Tree *rchild;
};
struct Node
{Tree *elem;Node *next;
};
struct Queue
{Node *front;Node *rear;
};
Tree *CreatBinaryTree();
void PrintBinaryTree(Tree *t);
Queue CreatQueue();
bool isEmpty(Queue *Q);
void AddQueue(Queue *Q,Tree *N);
Tree *DeleteQueue(Queue *Q);
//二叉搜索树
Tree *Find(Tree *BST,ElemType elem);
Tree *FindMax(Tree *BST);
Tree *FindMin(Tree *BST);
Tree *Insert(Tree *BST,ElemType elem);
Tree *Delete(Tree *BST,ElemType elem);
int main()
{int opt;ElemType elem;Tree *position=NULL;Tree *BST=NULL;while(opt!=7){puts("1搜索 2搜索最大值 3搜索最小值");puts("4添加元素 5打印 6删除");cin>>opt; switch(opt){case 1:{cout<<"请输入元素"<<endl;cin>>elem;position=Find(BST,elem);if(position==NULL)cout<<"搜索失败"<<endl;else{cout<<"搜索成功!"<<endl<<"其左孩子值为:"<<position->lchild->elem<<" 其右孩子的值为:"<<position->rchild->elem<<endl; } break;}case 2:{position=FindMax(BST);if(position!=NULL)cout<<"最大值为:"<<position->elem<<endl; break;}case 3:{position=FindMin(BST);if(position!=NULL)cout<<"最小值为:"<<position->elem<<endl; break;}case 4:{
// cout<<"请输入你要添加的元素"<<endl;cin>>elem;BST=Insert(BST,elem);break;}case 5:{PrintBinaryTree(BST);cout<<endl;break;}case 6:{
// cout<<"请输入删除的元素"<<endl;cin>>elem;BST=Delete(BST,elem);break;} } }return 0;
}Tree *CreatBinaryTree()//先序创建
{Tree *t;ElemType elem;cin>>elem;//1 2 4 0 0 5 0 0 3 6 0 0 7 0 0if(elem==0){t=NULL; }else{t=(Tree *)malloc(sizeof(Tree));t->elem=elem;t->lchild=CreatBinaryTree();t->rchild=CreatBinaryTree();}return t;
}
void PrintBinaryTree(Tree *t)//层次遍历
{Queue Q=CreatQueue();AddQueue(&Q,t);while(!isEmpty(&Q)){t=DeleteQueue(&Q); cout<<t->elem<<" ";if(t->lchild)AddQueue(&Q,t->lchild);if(t->rchild)AddQueue(&Q,t->rchild);}
}
Queue CreatQueue()
{Queue Q;Q.front=Q.rear=(Node*)malloc(sizeof(Node));Q.front->next=NULL;return Q;
}
bool isEmpty(Queue *Q)
{return Q->front->next==NULL;
}
void AddQueue(Queue *Q,Tree *elem)
{if(elem){Q->rear->next=(Node*)malloc(sizeof(Node));Q->rear=Q->rear->next;Q->rear->elem=elem;Q->rear->next=NULL;}
}
Tree *DeleteQueue(Queue *Q)
{if(!isEmpty(Q)){Tree*t;Node *p=Q->front->next;if(p==Q->rear)Q->rear=Q->front;Q->front->next=p->next;t=p->elem;free(p);return t;}else return NULL;
}Tree *Find(Tree *BST,int elem)
{/*if(!BST) return NULL;if(elem<BST->elem){return Find(BST->lchild,elem);}else if(elem>BST->elem){return Find(BST->rchild,elem);}else {return BST;}*/while(BST){if(elem<BST->elem){BST=BST->lchild; }else if(elem>BST->elem){BST=BST->rchild;}else{return BST;}}return NULL;
}
Tree *FindMax(Tree *BST)
{
/* if(BST){if(BST->rchild==NULL)return BST;else return FindMax(BST->rchild); }else return NULL;
*/ if(BST) while(BST->rchild){BST=BST->rchild;}return BST;
}
Tree *FindMin(Tree *BST)
{if(BST==NULL) return NULL;else {if(BST->lchild==NULL)return BST;else return FindMin(BST->lchild);}
/* if(BST)while(BST->lchild){BST=BST->lchild;}return BST;
*/
}
Tree *Insert(Tree *BST,ElemType elem)
{if(!BST){BST=(Tree*)malloc(sizeof(Tree));BST->elem=elem;BST->lchild=BST->rchild=NULL;}if(elem<BST->elem)//左 {BST->lchild=Insert(BST->lchild,elem); }if(elem>BST->elem)//右 {BST->rchild=Insert(BST->rchild,elem);} return BST;
}Tree *Delete(Tree *BST,ElemType elem)
{Tree *Tmp;if(BST!=NULL){if(elem<BST->elem){BST->lchild=Delete(BST->lchild,elem);}else if(elem>BST->elem){BST->rchild=Delete(BST->rchild,elem);}else{if(BST->lchild&&BST->rchild){Tmp=FindMin(BST->rchild);BST->elem=Tmp->elem;BST->rchild=Delete(BST->rchild,BST->elem);}else{Tmp=BST;if(BST->lchild!=NULL)BST=BST->lchild;if(BST->rchild!=NULL)BST=BST->rchild;free(Tmp);}}}return BST;
}
发布评论