fork download
copy 
  1. /*=========================================================
  2. 	 6-7節 二元搜尋樹：建立,節點插入,節點搜尋,節點刪除
  3.  
  4.           *BstCreate()         建立二元搜尋樹
  5.           *BstInsert()         插入節點
  6.           *BstSearch()         搜尋節點
  7.           *BstDelete()         刪除節點
  8.  
  9.   =========================================================
  10. */
  11.  
  12. #include <cstdlib>
  13. #include <fstream>
  14. #include <iostream>
  15.  
  16. using namespace std;
  17.  
  18. typedef struct tagNode
  19.         {
  20.                 char left_thread;
  21.                 struct tagNode *left_c;
  22.                 int data;
  23.                 char right_thread;
  24.                 struct tagNode *right_c;
  25.         }TNode;
  26. TNode *listA;
  27.  
  28. TNode *BstCreate(void);
  29. TNode *BstInsert(TNode *,TNode *);
  30. TNode *BstSearch(TNode *t,int);
  31. TNode *BstDelete(TNode *t,int);
  32. void  InOrder(TNode *t);
  33.  
  34. int main(int argc, char *argv[])
  35. {
  36.     TNode *p;
  37.     int data,LoopFlag=1;
  38.     int choose=9;
  39.  
  40.     //listA=BstCreate();
  41.  
  42.     while(LoopFlag)
  43.     {
  44. 		if (choose!=9)
  45. 		{
  46.             cout << "\n 根: "<<listA->data<<"  BST中序: ";
  47.         	InOrder(listA);
  48. 		}
  49.         //cout << endl << "(1)插入資料\n(2)搜尋資料\n(3)刪除資料\n(0)結束=> ";
  50.         choose=9;
  51.         cin >> choose;
  52. 		cout <<"\n"<< choose;
  53.         switch(choose)
  54.         {
  55.             case 0:
  56. 				LoopFlag=0;
  57.                 break;                        /*結束程式*/
  58.             case 1:
  59.                 cout << " 請輸入欲建立之資料=> ";
  60.                 cin >> data;
  61.                 p=new TNode;
  62.                 p->data=data;
  63.                 listA=BstInsert(listA,p);
  64.             	break;
  65.             case 2:
  66.                 cout << " 請輸入欲搜尋之資料=> ";
  67.                 cin >> data;
  68.                 if(BstSearch(listA,data) == NULL)
  69.                     cout << "找不到資料" << endl;
  70.                 else
  71.                     cout << "找到!!!" << endl;
  72.                 break;
  73.             case 3:
  74.                 cout << " 請輸入欲刪除之資料=>";
  75.                 cin >> data;
  76.                 cout << data;
  77.  
  78.                 TNode *d;
  79.                 d = BstDelete(listA,data);
  80. 				if(d == NULL)
  81.                     cout << " 刪除資料錯誤失敗!!" << endl;
  82.                 else
  83.                 {
  84.                 	listA=d;
  85.                     cout << " 刪除完成!!" << endl;
  86.                 }
  87.                 break;
  88.             default:
  89.                 cout << "選項錯誤" << endl;
  90.                 LoopFlag=0;
  91.                 break;                        /*結束程式*/
  92.         }
  93.      }
  94.      //system("PAUSE");
  95. 	return EXIT_SUCCESS;
  96. }
  97.  
  98. void InOrder(TNode *p)
  99. {
  100.     if(p != NULL)
  101.     {
  102.         InOrder(p->left_c);
  103.         cout << p->data << " ";
  104.         InOrder(p->right_c);
  105.     }
  106. }
  107.  
  108. TNode *BstInsert(TNode *t,TNode *p)
  109. {
  110.     TNode *r,*q;
  111.     char direction;
  112.  
  113.     p->left_c=p->right_c=NULL;
  114.     if(t == NULL)
  115.     	t=p;
  116.     else
  117.     {
  118.         q=t;
  119.         while(q != NULL)
  120.         {
  121.             if(p->data < q->data)
  122.             {
  123.                 direction=1;
  124.                 r=q;
  125.                 q=q->left_c;
  126.             }
  127.             else if(p->data > q->data)
  128.             {
  129.                 direction=0;
  130.                 r=q;
  131.                 q=q->right_c;
  132.             }
  133.             else
  134.                 return(t);
  135.         }
  136.         if (direction==1)
  137.             r->left_c=p;
  138.         else
  139.             r->right_c=p;
  140.     }
  141.     return(t);
  142. }
  143.  
  144.  
  145. TNode *BstCreate(void)
  146. {
  147.     fstream datafile;
  148.     int data;
  149.     TNode *t,*p;
  150.  
  151.     datafile.open("BST.dat",ios::in);
  152.  
  153.     t=NULL;
  154. 	datafile >> data;
  155.     while(!datafile.eof())
  156.     {
  157.         p=new TNode;
  158.         p->data=data;
  159.         t=BstInsert(t,p);
  160. 		datafile >> data;
  161.     }
  162.     return(t);
  163. }
  164.  
  165.  
  166. TNode *BstSearch(TNode *t,int key)
  167. {
  168.     while(t != NULL)
  169.     {
  170.         if(key == t->data)
  171.             return(t);
  172.         else if(key < t->data)
  173.             t=t->left_c;
  174.         else
  175.             t=t->right_c;
  176.     }
  177.     return(NULL);
  178. }
  179.  
  180.  
  181. TNode *BstDelete(TNode *p,int key)
  182. {
  183.     int found=0,direction=0;
  184.     TNode *r,*q,*s,*t;
  185.  
  186.     r=q=s=NULL;
  187.     t=p;
  188.  
  189.     while(p!=NULL && !found)
  190.     {
  191.         if(key == p->data)
  192.             found=1;
  193.         else if(key < p->data)
  194.         {
  195.         	direction=1;
  196.             r=p;
  197.             p=p->left_c;
  198.         }
  199.         else
  200.         {
  201.             direction=0;
  202.             r=p;
  203.             p=p->right_c;
  204.         }
  205.     }
  206.     if(p == NULL)
  207.         return(NULL);
  208.     if(r == NULL)
  209.     {
  210.     	cout<<"\n rrr \n";
  211.         if(p->right_c == NULL)
  212.             return(p->left_c);
  213.         else if(p->left_c == NULL)
  214.             return(p->right_c);
  215.     }
  216.     if(p->right_c == NULL)
  217.     {
  218.     	cout<<"\n p-r \n";
  219.         if(direction == 1)
  220.             r->left_c=p->left_c;
  221.         else
  222.             r->right_c=p->left_c;
  223.     }
  224.     else if(p->left_c == NULL)
  225.     {
  226.     	cout<<"\n p-l \n";
  227.         if(direction == 1)
  228.             r->left_c=p->right_c;
  229.         else
  230.             r->right_c=p->right_c;
  231.     }
  232.     else
  233.     {
  234.     	cout<<"\n p------ \n";
  235.         s=p;
  236.         if (p->left_c != NULL)
  237.         {
  238.         	q=p->left_c;
  239.         	while(q->right_c != NULL)
  240.         	{
  241.             	s=q;
  242.             	q=q->right_c;
  243.         	}
  244.         	p->data=q->data;
  245.         	if(p == s)
  246.             	s->left_c=q->left_c;
  247.         	else
  248.             	s->right_c=q->left_c;
  249.         }
  250.         else if (p->right_c != NULL)
  251.         {
  252.         	q=p->right_c;
  253.         	while(q->left_c != NULL)
  254.         	{
  255.             	s=q;
  256.             	q=q->left_c;
  257.         	}
  258.         	p->data=q->data;
  259.         	if(p == s)
  260.             	s->right_c=q->right_c;
  261.         	else
  262.             	s->left_c=q->right_c;
  263.         }
  264.  
  265.     }
  266.     return(t);
  267. }
Success #stdin #stdout 0.01s 5380KB
comments (?)
stdin
copy 
1
50
1
80
1
70
1
90
1
60
1
75
1
95
1
65
3
70
stdout
copy 
1 請輸入欲建立之資料=> 
 根: 50  BST中序: 50 
1 請輸入欲建立之資料=> 
 根: 50  BST中序: 50 80 
1 請輸入欲建立之資料=> 
 根: 50  BST中序: 50 70 80 
1 請輸入欲建立之資料=> 
 根: 50  BST中序: 50 70 80 90 
1 請輸入欲建立之資料=> 
 根: 50  BST中序: 50 60 70 80 90 
1 請輸入欲建立之資料=> 
 根: 50  BST中序: 50 60 70 75 80 90 
1 請輸入欲建立之資料=> 
 根: 50  BST中序: 50 60 70 75 80 90 95 
1 請輸入欲建立之資料=> 
 根: 50  BST中序: 50 60 65 70 75 80 90 95 
3 請輸入欲刪除之資料=>70
 p------ 
 刪除完成!!

 根: 50  BST中序: 50 60 65 75 80 90 95 
9選項錯誤
https://ideone.com/NQGgPZ
language:
C++ (gcc 8.3)
created:
2 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!