生活随笔
收集整理的這篇文章主要介紹了
重学数据结构007——二叉查找树
小編覺得挺不錯的,現在分享給大家,幫大家做個參考.
? ? 之前的博客中提到過，我學習采用的參考書是《數據結構與算法分析——C語言描述》。這門書的組織安排與國內廣泛實用的教材《數據結構——C語言版》比較不同。這本書描述了一些樹和二叉樹的概念，舉例講解了什么是樹的三種遍歷之后，就開始重點講解二叉查找樹、平衡二叉樹、AVL樹、伸展樹、B數了。這一篇博客，重點學習二叉查找樹的概念和基本操作。
? ? 大家都知道，樹的定義本身就帶有遞歸性。因此，樹的很多操作都涉及到了遞歸。二叉查找樹的定義如下：
? ? 1.二叉查找樹首先是一棵二叉樹；
? ? 2.二叉查找樹除了是二叉樹外，還具有以下性質：對于樹中的任何一個節點X，其左子樹中的所有節點的關鍵字均小于X的關鍵字的值；而其右子樹中的所有關鍵字的值均大于X的關鍵字的值。下面兩棵二叉樹中，左邊的二叉樹是二叉查找樹而右邊的不是。
?
? ? 二叉查找樹的數據結構定義如下：
typedef?int?ElementType;?typedef?struct?TreeNode?*Position;?typedef?Position?BiSearchTree;?struct?TreeNode?{?????ElementType?Element;?????BiSearchTree?Left,Right;?};? ? ? 二叉查找樹的常用操作如下：
BiSearchTree?MakeEmpty(BiSearchTree?Tree);?Position?Find(ElementType?X,?BiSearchTree?T);?Position?FindMin(BiSearchTree?T);?Position?FindMax(BiSearchTree?T);?BiSearchTree?Insert(ElementType?X,BiSearchTree?T);?BiSearchTree?Delete(ElementType?X,?BiSearchTree?T);? ? ? 二叉排序樹的操作與之前學習的一些數據結構的操作相比，可能難理解一些。下面我們挑比較難的幾個一一講解。
? ? 1.二叉查找樹中查找指定的元素Find
? ? 二叉排序樹的性質是二叉排序樹很多操作的基本依據。既然要查找指定元素X，先比較X與根節點元素的關系，如果剛好相等，直接返回啦；如果X小于根節點的元素值，那么去根節點的左子樹中查找，也就是調用Find方法，只是傳遞的參數是X和根節點的左子樹；如果X大于根節點的元素值，那么去根節點的右子樹中查找，也就是調用Find函數，只是傳遞的參數是X和根節點的右子樹。
? ? 2.查找最小元素FindMin和最大元素FindMax
? ? 這兩個操作是類似的。采用迭代或者遞歸都可以實現，查找最小元素只需要沿著左子樹訪問下去，查找最大元素則相反。下面我們會分別采用遞歸和迭代實現這兩個操作。
? ? 3.插入操作Insert
? ? 插入操作其實類似于查找操作，插入過過程其實就是先得找到一個合適的位置。插入其實有下面幾個情況：
? ? (1)如果函數傳進來的是空樹，那么創建一棵樹，將其元素值設置為X。這種情況顯而易見；
? ? (2)如果不是空樹，那就比較根節點元素值和X的大小，如果X的值小于根節點的元素值，而此時的根節點的左子樹為空，那么根節點的左孩子就是X元素的歸宿啦；同樣的道理，如果X的值大于根節點的元素值，而此時根節點的右子樹為空，那么根節點的右孩子就是X元素的歸宿啦。把握住這一點其實基本上就能把握住這個操作了。文字描述可能比較抽象，下面看圖：
? ? 左邊的圖，如果要插入5，沿著樹一直找到節點4，這時5>4并且4的右孩子為空，那么5就是4的右孩子。右邊的圖，要想插入8，沿著樹找到9，發現8<9且9的左孩子為空，那么8就是9的左孩子。
? ? 當然，在實現這樣一個過程的時候可以使用遞歸。
? ? 4.刪除操作Delete
? ? 刪除操作是我認為最復雜最不好理解的一個操作。如果沒有仔細想明白整個過程，上來就看代碼的話可能會很暈。刪除操作分兩步：第一步是查找，找的過程就涉及元素值之間的比較。我們重點說找到之后的操作。假設我們找到了這個節點，現在要刪除，涉及三種情況：
? ? (1)該節點是葉子。這還有什么好說的，直接刪了一了百了；
? ? (2)該節點只有一個孩子節點。也不復雜，讓該節點的父節點直接指向其子節點就行了。當然，也別忘了回收該節點；
? ? (3)該節點有兩個孩子：找到該節點右子樹中最小的節點，將其元素值賦給該節點，然后刪除那個最小節點。這種情況看圖：
?
? ? 說了半天了，下面看看完整的代碼：
#include?<stdio.h>?#include?<stdlib.h>??typedef?int?ElementType;?typedef?struct?TreeNode?*Position;?typedef?Position?BiSearchTree;?struct?TreeNode?{?????ElementType?Element;?????BiSearchTree?Left,Right;?};???BiSearchTree?MakeEmpty(BiSearchTree?Tree)?{?????if(!Tree)?????{?????????MakeEmpty(Tree->Left);?????????MakeEmpty(Tree->Right);?????????free(Tree);?????}?????return?NULL;?}??Position?Find(ElementType?X,?BiSearchTree?T)?{?????if(T?==?NULL)?????{?????????return?NULL;?????}?????else?????{??????????????????if(X?<?T->Element)?????????{?????????????return?Find(X,T->Left);?????????}?????????else?if(X?>?T->Element)?????????{?????????????return?Find(X,T->Right);?????????}?????????else?????????{?????????????return?T;?????????}?????}?}??Position?FindMin(BiSearchTree?T)?{?????if(T?==?NULL)?????{?????????return?NULL;?????}?????else?????{?????????if(T->Left?==?NULL)??????????{?????????????return?T;?????????}else?????????{?????????????return?FindMin(T->Left);?????????}?????}?}???Position?FindMax(BiSearchTree?T)?{?????if(T->Right?!=?NULL)?????{?????????while(T->Right?!=?NULL)?????????{?????????????T?=?T->Right;?????????}?????}?????return?T;?}??BiSearchTree?Insert(ElementType?X,BiSearchTree?T)?{??????????if(T?==?NULL)?????{?????????T?=?malloc(sizeof(struct?TreeNode));?????????if(T?==?NULL)?????????{?????????????fprintf(stderr,"Out?of?Space!!!");?????????}?????????else?????????{?????????????T->Element?=?X;?????????????T->Left?=?NULL;?????????????T->Right?=?NULL;?????????}?????}??????????else?????{?????????if(X?<?T->Element)??????????{?????????????T->Left?=?Insert(X,T->Left);?????????}?????????else?if(X?>?T->Element)??????????{?????????????T->Right?=?Insert(X,T->Right);?????????}?????????else?????????{??????????????????????}?????}?????return?T;?}???BiSearchTree?Delete(ElementType?X,?BiSearchTree?T)?{?????Position?TmpCell;?????if(T==NULL)?????{?????????fprintf(stderr,"Element?does?not?exist!");?????}?????else?if(X?<?T->Element)?????{?????????T->Left?=?Delete(X,T->Left);?????}?????else?if(X?>?T->Element)?????{?????????T->Right?=?Delete(X,T->Right);?????}?????else?if(T->Left?&&?T->Right)?????{?????????TmpCell?=?FindMin(T->Right);?????????T->Element?=?TmpCell->Element;?????????T->Right?=?Delete(T->Element,T->Right);?????}?????else?????{?????????TmpCell?=?T;?????????if(T->Left?==?NULL)?????????{?????????????T?=?T->Right;?????????}?????????else?if(T->Right?==?NULL)?????????{?????????????T?=?T->Left;?????????}?????????free(TmpCell);?????}?????return?T;?}??int?main(void)?{?????BiSearchTree?T;?????int?index;?????int?arr[10]?=?{10,9,8,7,6,1,2,3,4,5};?????T?=?NULL;?????for(index=0;?index?<?10;?index++)?????{?????????T?=?Insert(arr[index],T);?????}?????T?=?Insert(18,T);?????T?=?Insert(15,T);?????printf("The?minimum?element?is?%d\n",FindMin(T)->Element);?????printf("The?maxmium?element?is?%d\n",FindMax(T)->Element);?????return?0;?}? ?
?
?
?
?
?
?
轉載于:https://blog.51cto.com/wawlian/722244
總結
以上是生活随笔為你收集整理的重学数据结构007——二叉查找树的全部內容，希望文章能夠幫你解決所遇到的問題。
如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。
