数据结构之二叉树的基本操作（C++）

100 阅读 0 评论 66 点赞

我是靠谱客的博主俏皮小馒头，最近开发中收集的这篇文章主要介绍数据结构之二叉树的基本操作（C++），觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

#include<iostream>
using namespace std;
typedef struct bstnode{
   int data;
   bstnode *lchild,*rchild;
}bstnode,*linkbst;
class bst{
public:
bstnode *t;
   bst(){t=NULL;}
   void inorder(bstnode *t);//中序遍历二叉树
   void insert(bstnode *&t,int key);//插入关键字key
   bool exist(bstnode *t,int key);//判断key是否在二叉树t中
   bstnode *search(bstnode *t,int key);//查找关健词key
    void createbitree(int d[ ],int n); //n个数据在数组d中，t为二叉排序树根
   void DeleteBST(bstnode* &T,int key);//删除data为key的结点
void deletex( bstnode *&p);
   int countx(bstnode *t,int key);//计算关键字key的深度
};
void bst::insert(bstnode *&t, int key){
//在二叉排序树中插入查找关键字key
if(t==NULL){
t=new bstnode;
t->lchild=t->rchild=NULL;
t->data=key;
return;
}
if(key<t->data) insert(t->lchild,key);
else insert(t->rchild, key );
}
void bst::createbitree(int d[ ],int n){
t=NULL;
for(int i=0;i<n;i++)
insert(t,d[i]);
}
void bst::inorder(bstnode *t){
   if(t){
       inorder(t->lchild);
       cout<<t->data<<' ';
       inorder(t->rchild);
   }
}

bool bst::exist(bstnode *t,int key){
    if(t==NULL)   return false;
    else if(key<t->data)   return exist(t->lchild,key);
   else if(key>t->data)   return exist(t->rchild,key);
   else   return true;
}

bstnode *bst::search(bstnode *t,int key){
if(t==NULL||key==t->data) return t;
else if(key<t->data)
return search(t->lchild,key);
else return search(t->rchild,key);
}

void bst::DeleteBST(bstnode* &T,int key){
   if(!T) return;
   else{
       if(key==T->data) deletex(T);
       else if(key<T->data) DeleteBST(T->lchild,key);
       else DeleteBST(T->rchild,key);
   }
}
void bst::deletex(bstnode *&p){
   if(!p)return;
   bstnode *s,*q;
   if(p->rchild==NULL){
       q=p;
p=p->lchild;
delete q;
   }
else if(p->lchild==NULL)
{ q=p; p=p->rchild;
delete q;
}
else {
q=p; s=p->lchild;
while(s->rchild!=NULL)
{q=s; s=s->rchild;}
p->data=s->data;
if(q!=p) q->rchild=s->lchild;
else q->lchild=s->lchild;

delete s;
       }
   }
int bst::countx(bstnode *t,int key){
    if(exist(t,key)==false)   return 0;
    else{
   if(t==NULL)return 0;
   else if(key<t->data)return 1+countx(t->lchild,key);
   else if(key>t->data) return 1+countx(t->rchild,key);
       else return 1;
   }
}

int main(){
   bst bt;
   int a[]={40,10,60,9,25,34,5,78,90,2};
   bt.createbitree(a,sizeof(a)/sizeof(int));
   bt.inorder(bt.t);
   cout<<endl;
   bt.insert(bt.t,70);
   bt.inorder(bt.t);
   cout<<endl;
cout<<bt.search(bt.t,40)->data<<endl;
   bt.DeleteBST(bt.t,40);
   bt.inorder(bt.t);
   cout<<endl;
   cout<<bt.countx(bt.t,78);
}