二叉排序树的建立、先序/中序/后序遍历、查找
一、定義與性質(zhì)
定義?
二叉排序樹(Binary Sort Tree)又稱二叉查找(搜索)樹(Binary Search Tree)。其定義為：二叉排序樹或者是空樹.
性質(zhì)
（1） 二叉排序樹中任一結(jié)點(diǎn)x，其左(右)子樹中任一結(jié)點(diǎn)y(若存在)的關(guān)鍵字必小(大)于x的關(guān)鍵字。
（2） 二叉排序樹中，各結(jié)點(diǎn)關(guān)鍵字是惟一的。
? 注意：實(shí)際應(yīng)用中，不能保證被查找的數(shù)據(jù)集中各元素的關(guān)鍵字互不相同，所以可將二叉排序樹定義中BST性質(zhì)(1)里的"小于"改為"大于等于"，或?qū)ST性質(zhì)(2)里的"大于"改為"小于等于"，甚至可同時修改這兩個性質(zhì)。
（3） 按中序遍歷該樹所得到的中序序列是一個遞增有序序列。
二、插入與刪除
? ? ? ?插入與刪除操作是二叉排序樹中最常用也是最重要的兩個操作。
? ? ? ?插入過程是：
(a)若二叉排序樹T為空，則為待插入的關(guān)鍵字key申請一個新結(jié)點(diǎn)，并令其為根；
(b)若二叉排序樹T不為空，則將key和根的關(guān)鍵字比較：
???????? (i)若二者相等，則說明樹中已有此關(guān)鍵字key，無須插入。
???????? (ii)若key<T→key，則將key插入根的左子樹中。
???????? (iii)若key>T→key，則將它插入根的右子樹中。
子樹中的插入過程與上述的樹中插入過程相同。如此進(jìn)行下去，直到將key作為一個新的葉結(jié)點(diǎn)的關(guān)鍵字插入到二叉排序樹中，或者直到發(fā)現(xiàn)樹中已有此關(guān)鍵字為止。
? ? ?刪除過程：
? ? ?
(1) 進(jìn)行查找
????? 查找時，令p指向當(dāng)前訪問到的結(jié)點(diǎn)，parent指向其雙親(其初值為NULL)。若樹中找不到被刪結(jié)點(diǎn)則返回，否則被刪結(jié)點(diǎn)是*p。
(2) 刪去*p。
????? 刪*p時，應(yīng)將*p的子樹(若有)仍連接在樹上且保持BST性質(zhì)不變。按*p的孩子數(shù)目分三種情況進(jìn)行處理。
? ? ? ? ?刪除*p結(jié)點(diǎn)的三種情況
? ? ? ? ?a.*p是葉子(即它的孩子數(shù)為0)
????? 無須連接*p的子樹，只需將*p的雙親*parent中指向*p的指針域置空即可。
? ?
? ? ? ? ?b.*p只有一個孩子*child
????? 只需將*child和*p的雙親直接連接后，即可刪去*p。
? ? ? ? ? ? 注意：*p既可能是*parent的左孩子也可能是其右孩子，而*child可能是*p的左孩子或右孩子，故共有4種狀態(tài)。
? ? ? ? ? ? c.*p有兩個孩子
????? 先令q=p，將被刪結(jié)點(diǎn)的地址保存在q中；然后找*q的中序后繼*p，并在查找過程中仍用parent記住*p的雙親位置。*q的中序后繼*p一定是*q的右子樹中最左下的結(jié)點(diǎn)，它無左子樹。因此，可以將刪去*q的操作轉(zhuǎn)換為刪去的*p的操作，即在釋放結(jié)點(diǎn)*p之前將其數(shù)據(jù)復(fù)制到*q中，就相當(dāng)于刪去了*q。
三、代碼清單
#include<stdio.h> #include<stdlib.h> #define maxSize 20 #define maxWidth 20 typedef int KeyType; //假定關(guān)鍵字類型為整數(shù) typedef struct node { //結(jié)點(diǎn)類型KeyType key; //關(guān)鍵字項(xiàng)struct node *lchild,*rchild;//左右孩子指針 } BSTNode,BSTree; //typedef BSTNode *BSTree; //BSTree是二叉排序樹的類型//先序遍歷 void preOrder(BSTree *BT) { if(BT!= NULL) { printf("%d-",BT->key); preOrder(BT->lchild); preOrder(BT->rchild); } } //中序遍歷 void inOrder(BSTree *BT) { if(BT!= NULL) { inOrder(BT->lchild); printf("%d-",BT->key); inOrder(BT->rchild); } } //后序遍歷 void postOrder(BSTree *BT) { if(BT!= NULL) { postOrder(BT->lchild); postOrder(BT->rchild); printf("%d-",BT->key); } } //層次法打印二叉排序樹 /* 以先序遍歷的方式打印二叉排序樹 */ void dispTree(BSTree *BT) { BSTree *stack[maxSize],*p; int level[maxSize][2],top,n,i,width=4; if(BT!=NULL) { printf("Display a tree by hollow means.\n"); top=1; stack[top]=BT;//push root point to stack. level[top][0]=width; while(top>0) { p=stack[top]; n=level[top][0]; for(i=1;i<=n;i++) printf(" "); printf("%d",p->key); for(i=n+1;i<maxWidth;i+=2) printf("--"); printf("\n"); top--; if(p->rchild!=NULL) //右子樹先入棧，后出棧 { top++; stack[top]=p->rchild; level[top][0]=n+width; level[top][1]=2; } if(p->lchild!=NULL) //左子樹后入棧，先出棧{ top++; stack[top]=p->lchild; level[top][0]=n+width; level[top][1]=1; } //if} //while} //if } //dispTree() /* 向二叉排序樹中加入一個結(jié)點(diǎn) 要改變指針,需要傳遞指針的指針*/ /* return 0表示插入成功, return -1表示插入失敗 */ int InsertNode(BSTree **tree, KeyType key) {BSTNode *p= NULL, *parent = NULL;BSTNode *pNewNode = (BSTNode *)malloc(sizeof(BSTNode));if (pNewNode==NULL){return -1;}/* 新建結(jié)點(diǎn)賦值,特別是左右子結(jié)點(diǎn)指針要賦值為NULL，葉子節(jié)點(diǎn) *//* 二叉排序樹新插入的結(jié)點(diǎn)都是葉子節(jié)點(diǎn) */ pNewNode->key = key;pNewNode->lchild = NULL;pNewNode->rchild = NULL;/* 二叉排序樹是空樹 */if (*tree==NULL){*tree = pNewNode;return 0;}else{p = *tree;/* 尋找插入位置 */while (NULL != p) /* 待插入的結(jié)點(diǎn)以葉子節(jié)點(diǎn)方式插入 */{/* key值已在二叉排序樹中 */if (p->key == key){return 0;}else{parent = p;p = (p->key < key) ? p->rchild : p->lchild; //key是待插入結(jié)點(diǎn) }} //while，結(jié)束時NULL == p,此時已經(jīng)到了葉子節(jié)點(diǎn)位置 if (parent->key < key){parent->rchild = pNewNode;}else{parent->lchild = pNewNode;} //else return 0;} //else } //InsertNode //刪除節(jié)點(diǎn)/* 通過值查找并刪除一個結(jié)點(diǎn) */int delNode(BSTree **tree, KeyType key){BSTNode *p = NULL, *q = NULL, *parent = NULL, *child = NULL;p = *tree;/* parent為NULL表示根結(jié)點(diǎn)的父親為NULL */while (NULL != p){if (p->key == key) //此時找到待刪除的結(jié)點(diǎn)p {break;}else{ parent = p;p = (p->key < key) ? p->rchild : p->lchild;}} //while /* p為NULL時， 表示沒有找到結(jié)點(diǎn)值為key的結(jié)點(diǎn) */if (NULL == p) /* 到達(dá)葉子節(jié)點(diǎn)仍未查找到要刪除的結(jié)點(diǎn) */ {return -1;}/* p, q現(xiàn)在都是保存了待刪結(jié)點(diǎn)指針 */q = p; //此時p->key == key /* 待刪結(jié)點(diǎn)有兩個兒子結(jié)點(diǎn)，進(jìn)行一下轉(zhuǎn)化 */if (NULL != p->lchild && NULL != p->rchild){//找中序后繼，先右拐，然后左走到底parent = p;p = p->rchild; /* 進(jìn)入右子樹 */while (NULL != p->lchild){parent = p;p = p->lchild;}/* p中保存了待刪結(jié)點(diǎn)右子樹中最左下的結(jié)點(diǎn)指針， parent中就保存了該結(jié)點(diǎn)父親指針 */child = p->rchild;}else if(NULL == p -> lchild)child = p -> rchild;elsechild = p -> lchild; /* parent保存待刪結(jié)點(diǎn)的父親結(jié)點(diǎn)指針， child保存了待刪結(jié)點(diǎn)的兒子結(jié)點(diǎn)//實(shí)際刪除的是待刪節(jié)點(diǎn)的直接后繼，下面是刪除直接后繼的過程，（待刪結(jié)點(diǎn)至多只有一個兒子， 有兩個會轉(zhuǎn)化為0個或1個右結(jié)點(diǎn)）*/// 待刪結(jié)點(diǎn)是根結(jié)點(diǎn),且只有一個兒子if (NULL == parent){if(p->lchild!=NULL) *tree = p->lchild;else *tree = p->rchild;}else{/*待刪結(jié)點(diǎn)是父親結(jié)點(diǎn)的左兒子*/if (parent->lchild == p){parent->lchild = child;}else{parent->rchild = child;}//將實(shí)際刪除的節(jié)點(diǎn)的key值賦給原先要刪除的節(jié)點(diǎn)if (p != q){q->key = p->key;}}free(p);return 0;} //delNode//二叉排序樹查找 BSTNode* SearchBST(BSTree *T,KeyType key) { //在二叉排序樹T上查找關(guān)鍵字為key的結(jié)點(diǎn),成功時返回該結(jié)點(diǎn)位置,否則返回NUllif(T==NULL) //遞歸的終結(jié)條件return NULL; //T為空,查找失敗;if(key==T->key)//成功,返回找到的結(jié)點(diǎn)位置{printf("Got it!");return T;}if(key<T->key)return SearchBST(T->lchild,key);elsereturn SearchBST(T->rchild,key);//繼續(xù)在右子樹中查找 } //SearchBSTint main() {int n; BSTree *B=NULL;printf("Input number to initialize a BSTree:");while(1){scanf("%d",&n);if(n==0) break; //遇到0時停止輸入,0并不入樹 InsertNode(&B, n);} dispTree(B); printf("PreOrder：");preOrder(B);printf("\n");printf("Search a node:");scanf("%d",&n);SearchBST(B,n);printf("\n");printf("Delete a node:");scanf("%d",&n);delNode(&B,n);dispTree(B); printf("PreOrder：");preOrder(B);printf("\n");system("pause");return 1; }
四、程序運(yùn)行結(jié)果
出處：http://blog.csdn.net/silangquan/article/details/8065243
總結(jié)
以上是生活随笔為你收集整理的二叉排序树的建立、先序/中序/后序遍历、查找的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： 空类的sizeof为1
- 下一篇： 类的继承与sizeof