Code666 (代码贴、代码片段)

[C++] 二叉树的插入、删除、清空，更新等操作 →→→→→进入此内容的聊天室

来自 , 2020-05-24, 写在 C++, 查看 150 次.
URL http://www.code666.cn/view/33322217
  1. #include<iostream>
  2. #include<iomanip>
  3. using namespace std;
  4. typedef int T;
  5. class bst{
  6.         struct Node{
  7.                 T data;
  8.                 Node * L;
  9.                 Node * R;
  10.                 Node(const T&d):data(d),L(),R(){}
  11.                 Node(const T&d,Node *l,Node *r):data(d),L(l),R(r){}
  12.         };
  13.         Node *rp;
  14.         int n;
  15. public:
  16.         bst():rp(),n(){}
  17.         void insert(Node* &t,Node *p)//插入节点
  18.         {
  19.                 if(t==NULL) t=p;
  20.                 else if(p->data<t->data) insert(t->L,p);
  21.                 else insert(t->R,p);
  22.         }
  23.         void insert(const T&d){insert(rp,new Node(d));}
  24.  
  25.         Node *&find(Node *&t,const T&d)//查找指定元素
  26.         {
  27.                 if(t==NULL) return t;
  28.                 else if(d==t->data) return t;
  29.                 else if(d<t->data) return find(t->L,d);
  30.                 else return find(t->R,d);                      
  31.         }
  32.         Node *&find(const T&d){return find(rp,d);}
  33.        
  34.         void remove(const T&d)//删除节点
  35.         {
  36.                 Node *&t=find(d);
  37.                 if(t==NULL) return;
  38.                 Node *p=t;
  39.                 if(t->L!=NULL) insert(t->R,t->L);
  40.                 t=t->R;
  41.                 delete p;
  42.         }
  43.        
  44.         void clear(Node *&t)//清空二叉树
  45.         {
  46.                 if(t!=NULL)
  47.                 {
  48.                         clear(t->L);
  49.                         clear(t->R);
  50.                         delete t;
  51.                         t=NULL;//注意这里t要置空，否则输出时会是随机数
  52.                 }
  53.         }
  54.         void clear(){clear(rp);}
  55.        
  56.         int high(Node *t)//求树的高度
  57.         {
  58.                 if(t==NULL) return 0;
  59.                 int lh=high(t->L);
  60.                 int rh=high(t->R);
  61.                 return 1+(lh>rh?lh:rh); //每次通过这里不断的累加树的高度
  62.         }      
  63.         int high(){high(rp);}
  64.  
  65.         T &root()//查找根节点
  66.         {
  67.                 if(rp==NULL) throw "空";
  68.                 return rp->data;
  69.         }      
  70.        
  71.         void update(const T&olddata,const T&newdata)//更新一棵树
  72.         {
  73.                 remove(olddata);
  74.                 insert(newdata);
  75.         }
  76.  
  77.         void travel(Node *t)//遍历整棵树
  78.         {
  79.                 if(t!=NULL)
  80.                 {
  81.                         travel(t->L);
  82.                         cout<<t->data<<' ';
  83.                         travel(t->R);
  84.                 }
  85.         }
  86.         void travel(){travel(rp);cout<<endl;}
  87.  
  88.         void print(Node *t,int space,char sign)//打印一棵树
  89.         {
  90.                 if(t==NULL) return;
  91.                 cout<<setw(space+1)<<sign<<t->data<<endl;
  92.                 print(t->R,space+2,'\\');
  93.                 //cout<<setw(space+1)<<sign<<t->data<<endl;
  94.                 print(t->L,space,'/');
  95.                 //print(t->R,space+3,'\\');
  96.         }
  97.         void print(){print(rp,6,'*');}
  98. };
  99. int main()
  100. {
  101.         bst b;
  102.         b.insert(5);
  103.         b.insert(3);
  104.         b.insert(9);
  105.         b.insert(4);
  106.         b.insert(1);
  107.         b.travel();
  108.         cout<<"树的高度为:"<<b.high()<<endl;
  109.         cout<<"根节点是:"<<b.root()<<endl;
  110.         b.update(1,8);
  111.         b.travel();
  112.         b.print();
  113.         b.remove(4);
  114.         b.travel();
  115.         b.clear();
  116.         b.travel();
  117.         return 0;
  118. }
  119.  

回复 "二叉树的插入、删除、清空，更新等操作"

这儿你可以回复上面这条便签

captcha

贴代码片段 - Code666