程式扎記: [C 範例代碼] 數據結構 : 二元樹 - 二元排序樹

標籤

2012年4月6日 星期五

[C 範例代碼] 數據結構 : 二元樹 - 二元排序樹

前言 : 
編成實現功能: 創建一棵二元排序樹, 創建完成後輸入要查找的數據並進行對二元排序樹搜尋, 並將搜尋次數與結果顯示出來. 

技術要點 : 
二元排序樹是一棵具有如下特徵的非空二元樹 : 
1. 若它的左子樹非空, 則左子樹上所有節點的值都小於根節點的值.
2. 若他的右子樹非空, 則右子樹上所有節點的值都大於根節點的值.
3. 左右子樹本身各是一棵二元排序樹.

範例代碼 : 
  1. #include   
  2. #include   
  3.   
  4. struct bnode{  
  5.     struct bnode *lchild;  
  6.     char data;  
  7.     struct bnode *rchild;  
  8. };  
  9. typedef bnode *bitree;  
  10.   
  11. int searchBTree(bitree root, int key) {  
  12.     int n=0;  
  13.     if(root == NULL)  
  14.         return -1;  
  15.     bitree tmp = root;  
  16.     while(tmp != NULL) {  
  17.         n++;  
  18.         if(tmp->data > key) {  
  19.             tmp = tmp->lchild;  
  20.         } else if(tmp->data == key) {  
  21.             return n;  
  22.         } else {  
  23.             tmp = tmp->rchild;  
  24.         }  
  25.     }  
  26.     return -1;  
  27. }  
  28.   
  29. void addNode(bitree *root, int val) {  
  30.     if(*root == NULL) {  
  31.         *root = (bitree) malloc(sizeof(bnode));  
  32.         (*root)->data = val;  
  33.         (*root)->lchild = NULL;  
  34.         (*root)->rchild = NULL;  
  35.     } else {  
  36.         bitree newtr = (bitree) malloc(sizeof(bnode));  
  37.         newtr->data = val;  
  38.         newtr->lchild = NULL;  
  39.         newtr->rchild = NULL;  
  40.         bitree tmp = *root;  
  41.         while(tmp != NULL) {  
  42.             if(tmp->data > val) { // 往左子樹               
  43.                 if(tmp->lchild != NULL) {  
  44.                     tmp = tmp->lchild;  
  45.                 } else {  
  46.                     tmp->lchild = newtr;  
  47.                     break;  
  48.                 }  
  49.             } else {  // 往右子樹  
  50.                 if(tmp->rchild != NULL) {  
  51.                     tmp = tmp->rchild;  
  52.                 } else {  
  53.                     tmp->rchild = newtr;  
  54.                     break;  
  55.                 }  
  56.             }             
  57.         }  
  58.     }  
  59. }  
  60.   
  61. void SC_113() {  
  62.     bitree root = NULL;  
  63.     int val = 0;  
  64.     while(val>=0) {  
  65.         printf("Please give val (-1 to leave): ");  
  66.         scanf("%d", &val);  
  67.         if(val>=0)  
  68.             addNode(&root, val);  
  69.     }  
  70.     printf("Please give search key: ");  
  71.     scanf("%d", &val);  
  72.     int n = searchBTree(root, val);  
  73.     if(n>0) {  
  74.         printf("Found in %d times!\n", n);  
  75.     } else {  
  76.         printf("Not found!");  
  77.     }  
  78.     free(root);  
  79. }  
執行結果 : 
Please give val (-1 to leave): 5
Please give val (-1 to leave): 9
Please give val (-1 to leave): 2
Please give val (-1 to leave): 6
Please give val (-1 to leave): 4
Please give val (-1 to leave): 3
Please give val (-1 to leave): 7
Please give val (-1 to leave): 10
Please give val (-1 to leave): -1 <離開建立搜尋二元樹>
Please give search key: 6
Found in 3 times!

補充說明 : 
[ 資料結構 小學堂 ] 樹狀結構導論 : 二元運算樹進階研究 - 二元排序樹

沒有留言:

張貼留言

網誌存檔

關於我自己

我的相片
Where there is a will, there is a way!