会python真的可以为所欲为0(回)
353天前
这里还有人吗1(回)
538天前这里还有人吗0(回)
538天前
每天面对着电脑屏幕，敲打键盘。我所面对的并不只是代码，而是一种生活方式。0(回)
763天前到处都是羊，不想上班0(回)
843天前
鸽子
0(回)
847天前#include<iostream> |
#include<iomanip> |
using namespace std; |
typedef int T; |
class bst{ |
struct Node{ |
T data; |
Node * L; |
Node * R; |
Node(const T&d):data(d),L(),R(){} |
Node(const T&d,Node *l,Node *r):data(d),L(l),R(r){} |
}; |
Node *rp; |
int n; |
public: |
bst():rp(),n(){} |
void insert(Node* &t,Node *p)//插入节点 |
{ |
if(t==NULL) t=p; |
else if(p->data<t->data) insert(t->L,p); |
else insert(t->R,p); |
} |
void insert(const T&d){insert(rp,new Node(d));} |
Node *&find(Node *&t,const T&d)//查找指定元素 |
{ |
if(t==NULL) return t; |
else if(d==t->data) return t; |
else if(d<t->data) return find(t->L,d); |
else return find(t->R,d); |
} |
Node *&find(const T&d){return find(rp,d);} |
|
void remove(const T&d)//删除节点 |
{ |
Node *&t=find(d); |
if(t==NULL) return; |
Node *p=t; |
if(t->L!=NULL) insert(t->R,t->L); |
t=t->R; |
delete p; |
} |
|
void clear(Node *&t)//清空二叉树 |
{ |
if(t!=NULL) |
{ |
clear(t->L); |
clear(t->R); |
delete t; |
t=NULL;//注意这里t要置空，否则输出时会是随机数 |
} |
} |
void clear(){clear(rp);} |
|
int high(Node *t)//求树的高度 |
{ |
if(t==NULL) return 0; |
int lh=high(t->L); |
int rh=high(t->R); |
return 1+(lh>rh?lh:rh); //每次通过这里不断的累加树的高度 |
} |
int high(){high(rp);} |
T &root()//查找根节点 |
{ |
if(rp==NULL) throw "空"; |
return rp->data; |
} |
|
void update(const T&olddata,const T&newdata)//更新一棵树 |
{ |
remove(olddata); |
insert(newdata); |
} |
void travel(Node *t)//遍历整棵树 |
{ |
if(t!=NULL) |
{ |
travel(t->L); |
cout<<t->data<<' '; |
travel(t->R); |
} |
} |
void travel(){travel(rp);cout<<endl;} |
void print(Node *t,int space,char sign)//打印一棵树 |
{ |
if(t==NULL) return; |
cout<<setw(space+1)<<sign<<t->data<<endl; |
print(t->R,space+2,'\\'); |
//cout<<setw(space+1)<<sign<<t->data<<endl; |
print(t->L,space,'/'); |
//print(t->R,space+3,'\\'); |
} |
void print(){print(rp,6,'*');} |
}; |
int main() |
{ |
bst b; |
b.insert(5); |
b.insert(3); |
b.insert(9); |
b.insert(4); |
b.insert(1); |
b.travel(); |
cout<<"树的高度为:"<<b.high()<<endl; |
cout<<"根节点是:"<<b.root()<<endl; |
b.update(1,8); |
b.travel(); |
b.print(); |
b.remove(4); |
b.travel(); |
b.clear(); |
b.travel(); |
return 0; |
} |
