Code666 (代码贴、代码片段)

[C++] 二叉排序树基本操作（初始化、查找和插入元素、删除元素、输出等） →→→→→进入此内容的聊天室

来自 , 2019-06-18, 写在 C++, 查看 104 次.
URL http://www.code666.cn/view/14cfdb59
  1. #include<iostream.h>
  2. #include<STRSTREAM.H>
  3. typedef int elemtype;
  4. struct bstnode
  5. {
  6.         elemtype data;
  7.         bstnode *lchild;
  8.         bstnode *rchild;
  9. };
  10.  
  11. void initbtree ( bstnode *&bst )
  12. { bst=NULL;}
  13.  
  14. int bstreeempty ( bstnode *bst )
  15. { return bst==NULL;}
  16.  
  17. int find ( bstnode *bst,elemtype &x )
  18. {
  19.         if ( bst==NULL )
  20.                 return 0;
  21.         else  if ( x==bst->data )
  22.         {
  23.                 x=bst->data;
  24.                 return 1;
  25.         }
  26.         else if ( x<bst->data )
  27.                 return find ( bst->lchild,x );
  28.         else
  29.                 return find ( bst->rchild,x );
  30. }
  31.  
  32. int update ( bstnode *bst,elemtype x )
  33. {
  34.         if ( bst==NULL )
  35.                 return 0;
  36.         else if ( x==bst->data )
  37.         {
  38.                 bst->data=x;
  39.                 return 1;
  40.         }
  41.         else if ( x<bst->data )
  42.                 return update ( bst->lchild,x );
  43.         else
  44.                 return update ( bst->rchild,x );
  45. }
  46.  
  47. void insert ( bstnode *&bst,elemtype x )
  48. {
  49.         if ( bst==NULL )
  50.         {
  51.                 bstnode *p=new bstnode;
  52.                 p->data=x;
  53.                 p->lchild=p->rchild=NULL;
  54.                 bst=p;
  55.         }
  56.         else if ( x<bst->data )
  57.                 insert ( bst->lchild,x );
  58.         else
  59.                 insert ( bst->rchild,x );
  60. }
  61.  
  62. int dele ( bstnode *&bst,elemtype x )
  63. {
  64.         bstnode *t=bst,*s=NULL;
  65.         while ( t!=NULL )
  66.         {
  67.                 if ( x==t->data )  break;
  68.                 else if ( x<t->data )
  69.                         { s=t; t=t->lchild;}
  70.                 else
  71.                         { s=t; t=t->lchild;}
  72.         }
  73.         if ( t==NULL )  return 0;
  74.         if ( t->lchild==NULL&&t->rchild==NULL )
  75.         {
  76.                 if ( t==bst )
  77.                         bst=NULL;
  78.                 else if ( t==s->lchild )
  79.                         s->lchild=NULL;
  80.                 else
  81.                         s->rchild=NULL;
  82.                 delete t;
  83.         }
  84.         else if ( t->lchild==NULL||t->rchild==NULL )
  85.         {
  86.                 if ( bst==t )
  87.                 {
  88.                         if ( t->lchild==NULL )
  89.                                 bst=t->rchild;
  90.                         else
  91.                                 bst=t->lchild;
  92.                 }
  93.                 else
  94.                 {
  95.                         if ( t==s->lchild&&t->lchild!=NULL )
  96.                                 s->lchild=t->lchild;
  97.                         else if ( t==s->lchild&&t->rchild!=NULL )
  98.                                 s->lchild=t->rchild;
  99.                         else if ( t==s->rchild&&t->lchild!=NULL )
  100.                                 s->rchild=t->lchild;
  101.                         else if ( t==s->rchild&&t->rchild!=NULL )
  102.                                 s->rchild=t->rchild;
  103.                 }
  104.                 delete t;
  105.         }
  106.         else if ( t->lchild!=NULL&&t->rchild!=NULL )
  107.         {
  108.                 bstnode *p=t,*q=t->lchild;
  109.                 while ( q->rchild!=NULL )
  110.                 {
  111.                         p=q;
  112.                         q=q->rchild;
  113.                 }
  114.                 t->data=q->data;
  115.                 if ( p==t ) t->lchild=q->lchild;
  116.                 else p->rchild=q->lchild;
  117.                 delete q;
  118.         }
  119.         return 1;
  120. }
  121.  
  122. void createbstree ( bstnode *&bst,elemtype a[],int n )
  123. {
  124.         bst=NULL;
  125.         for ( int i=0; i<n; i++ )
  126.                 insert ( bst,a[i] );
  127. }
  128.  
  129. void inorder ( bstnode *bst )
  130. {
  131.         if ( bst!=NULL )
  132.         {
  133.                 inorder ( bst->lchild );
  134.                 cout<<bst->data<<' ';
  135.                 inorder ( bst->rchild );
  136.         }
  137. }
  138.  
  139. int bstreedepth ( bstnode *bst )
  140. {
  141.         if ( bst==NULL )
  142.                 return 0;
  143.         else
  144.         {
  145.                 int dep1=bstreedepth ( bst->lchild );
  146.                 int dep2=bstreedepth ( bst->rchild );
  147.                 if ( dep1>dep2 )
  148.                         return dep1+1;
  149.                 else
  150.                         return dep2+1;
  151.         }
  152. }
  153.  
  154. int bstreecount ( bstnode *bst )
  155. {
  156.         if ( bst==NULL )
  157.                 return 0;
  158.         else
  159.                 return bstreecount ( bst->lchild ) +bstreecount ( bst->rchild ) +1;
  160.  
  161. }
  162.  
  163. int bstreeleafcount ( bstnode *bst )
  164. {
  165.         if ( bst==NULL )
  166.                 return 0;
  167.         else if ( bst->lchild==NULL&&bst->rchild==NULL )
  168.                 return 1;
  169.         else return bstreeleafcount ( bst->lchild ) +bstreeleafcount ( bst->rchild );
  170. }
  171.  
  172. void printbstree ( bstnode *bst )
  173. {
  174.         if ( bst==NULL )
  175.                 return;
  176.         else
  177.         {
  178.                 cout<<bst->data;
  179.                 if ( bst->lchild!=NULL||bst->rchild!=NULL )
  180.                 {
  181.                         cout<<'(';
  182.                         printbstree ( bst->lchild );
  183.                         if ( bst->rchild!=NULL )
  184.                                 cout<<',';
  185.                         printbstree ( bst->rchild );
  186.                         cout<<')';
  187.                 }
  188.         }
  189. }
  190.  
  191. void clearbstree ( bstnode *&bst )
  192. {
  193.         if ( bst!=NULL )
  194.         {
  195.                 clearbstree ( bst->lchild );
  196.                 clearbstree ( bst->rchild );
  197.                 delete bst;
  198.                 bst=NULL;
  199.         }
  200. }
  201.  
  202. void main()
  203. {
  204.         elemtype a[10]={30,50,20,70,25,54,80,23,92,40};
  205.         bstnode *bst=NULL;
  206.         createbstree ( bst,a,10 );
  207.         cout<<"output bstree:"<<endl;
  208.         printbstree ( bst );
  209.         cout<<endl;
  210.         cout<<"inorder list:"<<endl;
  211.         inorder ( bst );
  212.         cout<<endl;
  213.         elemtype x;
  214.         cout<<"input find is x:";
  215.         cin>>x;
  216.         if ( find ( bst,x ) )
  217.                 cout<<"ok!!!"<<endl;
  218.         else
  219.                 cout<<"fail!!!"<<endl;
  220.         insert ( bst,36 );
  221.         dele ( bst,30 );
  222.         dele ( bst,20 );
  223.         cout<<"op end inorder:"<<endl;
  224.         inorder ( bst );
  225.         cout<<endl;
  226.         cout<<"op end glist:"<<endl;
  227.         printbstree ( bst );
  228.         cout<<endl;
  229.         clearbstree ( bst );
  230. }
  231.  

回复 "二叉排序树基本操作（初始化、查找和插入元素、删除元素、输出等）"

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

captcha

贴代码片段 - Code666