數據結構之二叉 排序樹

1)二叉順序樹查找操作:(註釋內容來自《大話數據結構》)

 

 

2)二叉順序樹插入操作:

 

3)二叉順序樹刪除操作:

 

完整代碼如下:

 

  1 #include "stdafx.h"
  2 #include<iostream>
  3 using namespace std;
  4 typedef int Status;
  5 #define FALSE 0
  6 #define TRUE 1
  7 typedef struct BiTNode
  8 {
  9     int data;//結點數據
 10     struct BiTNode *lchild, *rchild; //左右孩子指針
 11 }BiTNode,*BiTree;
 12 
 13 //遞歸查找二叉排序樹T中是否存在key,
 14 //指針f指向T的雙親,其初始調用值為NULL
 15 //若查找成功,則指針p指向該數據元素結點,並返回TRUE 
 16 //否則指針p指向查找路徑上訪問的最後一個結點並返回FALSE
 17 Status SearchBST(BiTree T, int key, BiTree f, BiTree *p)
 18 {
 19     if (!T)                       //查找失敗
 20     {
 21         *p = f;
 22         return FALSE;
 23     }
 24     else if (key == T->data)      //查找成功
 25     {
 26         *p = T;
 27         return TRUE;
 28     }
 29     else if (key < T->data)
 30         return SearchBST(T->lchild, key, T, p);//在左子樹中繼續查找
 31     else
 32         return SearchBST(T->rchild, key, T, p);//在右子樹中繼續查找
 33 }
 34 
 35 Status InsertBST(BiTree *T, int key)
 36 {
 37     BiTree p, s;
 38     if (!SearchBST(*T, key, NULL, &p))//查找失敗
 39     {
 40         s = new BiTNode;
 41         s->data = key;
 42         s->lchild = s->rchild = NULL;
 43         if (!p)
 44             *T = s;               //插入s為新的根節點
 45         else if (key < p->data)
 46             p->lchild = s;        //插入s為左孩子
 47         else
 48             p->rchild = s;        //插入s為右孩子
 49     }
 50     else
 51         return FALSE;             // 樹中已有關鍵字相同的結點,不再插入
 52 }
 53 
 54 //從二叉排序樹中刪除結點p,並重接它的左或右子樹
 55 Status Delete(BiTree *p)
 56 {
 57     BiTree q, s;
 58     if ((*p)->rchild == NULL)     //右子樹空則只需重接它的左子樹(待刪結點是葉子也走此分支)
 59     {
 60         q = *p; 
 61         *p = (*p)->lchild; 
 62         free(q);
 63     }
 64     else if ((*p)->lchild == NULL) //只需重接它的右子樹
 65     {
 66         q = *p; 
 67         *p = (*p)->rchild; 
 68         free(q);
 69     }
 70     else                          //左右子樹均不空
 71     {
 72         q = *p; 
 73         s = (*p)->lchild;
 74         while (s->rchild)         //轉左,然後向右到盡頭(找待刪結點的前驅)
 75         {
 76             q = s;
 77             s = s->rchild;
 78         }
 79         (*p)->data = s->data;     //s指向被刪結點的直接前驅(將被刪結點前驅的值取代被刪結點的值)
 80         if (q != *p)
 81             q->rchild = s->lchild;//重接q的右子樹 
 82         else
 83             q->lchild = s->lchild;//重接q的左子樹
 84         free(s);
 85     }
 86     return TRUE;
 87 }
 88 
 89 //若二叉排序樹T中存在關鍵字等於key的數據元素時,則刪除該數據元素結點,
 90 //並返回TRUE;否則返回FALSE
 91 Status DeleteBST(BiTree *T, int key)
 92 {
 93     if (!*T)                      //不存在關鍵字等於key的數據元素
 94         return FALSE;
 95     else
 96     {
 97         if (key == (*T)->data)    //找到關鍵字等於key的數據元素
 98             return Delete(T);
 99         else if (key<(*T)->data)
100             return DeleteBST(&(*T)->lchild, key);
101         else
102             return DeleteBST(&(*T)->rchild, key);
103     }
104 }
105 
106 
107 int main()
108 {
109     int i;
110     int a[10] = { 62,88,58,47,35,73,51,99,37,93 };
111     BiTree T = NULL;
112 
113     for (i = 0; i<10; i++)
114     {
115         InsertBST(&T, a[i]);
116     }
117     DeleteBST(&T, 93);
118     DeleteBST(&T, 47);
119     cout<<"本樣例建議斷點跟蹤查看二叉排序樹結構";
120     return 0;
121 }

 

關鍵詞:gt key else return lchild 結點 rchild 數據 bitree 二叉

相關推薦:

(原創)像極了愛情的詳解排序二叉樹,一秒get

數據結構—樹與二叉樹

二叉排序樹

數據結構之平衡二叉樹

二叉搜索樹的查找、刪除、插入

二叉排序樹(查詢、插入、刪除)

數據結構之二叉樹