现在的位置: 首页 > 综合 > 正文

二叉排序树

2013年07月28日 ⁄ 综合 ⁄ 共 3185字 ⁄ 字号 小 中 大 ⁄ 评论关闭
Code:
  1. // 链树.cpp : 定义控制台应用程序的入口点。    
  2. #include "stdafx.h"    
  3.     
  4. #include <iostream>  
  5. using namespace std;  
  6.   
  7.   
  8. typedef int ElemType;  
  9.   
  10. typedef struct Bitnode  
  11.   {  
  12.      ElemType data;  
  13.     struct Bitnode *lchild,*rchild;  
  14.   }Bitnode,*BitTree;  
  15. /********search    第一个为遍历查找  第二个为二叉排序查找  ************/  
  16.  int fd=0;  
  17. void Search_Elem2(BitTree T,ElemType e,BitTree &p,BitTree &f)//  
  18. {  
  19.  if(T&&!fd)  
  20.  if(T->data==e)  
  21.  {p=T;fd=1;}  
  22.  else{ if(!fd){f=T;  
  23.  Search_Elem2(T->lchild,e,p,f);}  
  24.        if(!fd){ f=T;  
  25.        Search_Elem2(T->rchild,e,p,f);}  
  26.        }  
  27. }  
  28. void Search(BitTree T,ElemType e,BitTree*F,BitTree*P)//Search(T,e,&F,&P)  
  29. {  
  30.  while(T)  
  31.      if(e==T->data){*P=T;break;}  
  32.      else if(T->data>e){*F=T;T=T->lchild;}  
  33.      else{*F=T;T=T->rchild;}  
  34. }  
  35. /********               插入节点             ************/  
  36. int Insert(BitTree &T,ElemType e)//有了&就牛逼了  
  37. {BitTree F=NULL,P=NULL,S;//!!!  
  38.  Search(T,e,&F,&P);  
  39.  if(P)return 0;  
  40.  S=new Bitnode;  
  41.  S->data=e;  
  42.  S->lchild=NULL;  
  43.  S->rchild=NULL;  
  44.  if(F==NULL)T=S;  
  45.  else if (F->data<e)F->rchild=S;  
  46.  else F->lchild=S;  
  47.  return 1;  
  48.     }  
  49. /********        中序  遍历              ************/  
  50. void In_Order_Traverse(BitTree T)  
  51. {if(T)  
  52.     {  
  53.      In_Order_Traverse(T->lchild);  
  54.      cout<<T->data;  
  55.      In_Order_Traverse(T->rchild);  
  56. }  
  57. }  
  58. /********         删除节点 中序不变     ************/  
  59. void Delete_Elem(BitTree &T,ElemType e)//*  
  60.     {  
  61.     BitTree s,q,p=NULL,f=NULL;  
  62.   
  63.     cout<<endl<<e<<" :";  
  64.   
  65. Search(T,e,&f,&p);//fd=0;Search_Elem2(T,e,p,f);  
  66.  if(p==NULL)cout<<"The target elem no  exist orthe tree is  empty "<<endl;//1  
  67.  else{  
  68.      if(p->lchild==NULL&&p->rchild==NULL)//leaf  
  69.          {if(f==NULL)T=NULL;//pbuxing  
  70.               else{ delete(p);  
  71.                     if(f->lchild==p)f->lchild=NULL;  
  72.                     else f->rchild=NULL;}//  
  73.          }  
  74.   
  75.   
  76.      else if(p->lchild==NULL)//2  
  77.          {//cout<<f;cout<<T->data;cout<<T->rchild->data<<"   ";  //  
  78.              if(f==NULL)  
  79.              {T=p->rchild;delete(p);  
  80.               }  
  81.              else{if(f->lchild==p)f->lchild=p->rchild;  
  82.                   else f->rchild=p->rchild;}  
  83.           }  
  84.   
  85.      else if(p->rchild==NULL)//22  
  86.      {  
  87.      if(f==NULL)  
  88.          {T=p->lchild;delete(p);  
  89.          }  
  90.      else{if(f->lchild==p)f->lchild=p->lchild;  
  91.           else f->rchild=p->lchild;}  
  92.      }  
  93.   
  94.   
  95.   
  96.      else {q=p;  
  97.          s=q->lchild;  
  98.          while(s->rchild!=NULL){q=s;s=s->rchild;}  
  99.          p->data=s->data;  
  100.          if(q->lchild==s)q->lchild=s->lchild;  
  101.          else q->rchild=s->lchild;  
  102.          delete(s);  
  103.      }  
  104.  }  
  105. }  
  106.   
  107.   
  108.   
  109.   
  110. int main()  
  111. {  
  112.  BitTree T=NULL;  
  113. //输入124三个空格357两个空格8两个空格6两个空格  
  114.   
  115. Insert(T,1);  
  116. Insert(T,2);  
  117. Insert(T,3);  
  118. Insert(T,4);  
  119. Insert(T,5);  
  120. Insert(T,6);  
  121.   
  122. Delete_Elem(T,1);  
  123. In_Order_Traverse(T);  
  124. Delete_Elem(T,2);  
  125. In_Order_Traverse(T);  
  126. Delete_Elem(T,3);  
  127. In_Order_Traverse(T);  
  128. Delete_Elem(T,4);  
  129. In_Order_Traverse(T);  
  130. Delete_Elem(T,5);  
  131. In_Order_Traverse(T);  
  132. Delete_Elem(T,6);  
  133. In_Order_Traverse(T);  
  134. Delete_Elem(T,7);  
  135. In_Order_Traverse(T);  
  136. Delete_Elem(T,8);  
  137. In_Order_Traverse(T);  
  138. Delete_Elem(T,9);  
  139. In_Order_Traverse(T);  
  140. Delete_Elem(T,0);  
  141. In_Order_Traverse(T);  
  142.   
  143.   
  144.   
  145.   
  146.   
  147.  int m;  
  148.  cin>>m;  
  149.   
  150.     return 1;  
  151. }  

 

 

返回
【上篇】
【下篇】

作者:

抱歉!评论已关闭.

返回首页

Copyright © 2013-2018 学步园  保留所有权利.
软文销售 QQ客服：2265327166 点击这里给我发消息（其他合作也可洽谈）
必威体育
必威电竞