二叉查找樹（Binary Search Tree），也稱二叉排序樹（binary sorted tree），是指一棵空樹或者具有下列性質的二叉樹： 若任意節點的左子樹不空，則左子樹上所有結點的值均小於它的根結點的值 任意節點的右子樹不空，則右子樹上所有結點的值均大於它的根結點的值 任意節點的左、右子樹也分別為二叉查找樹 沒有鍵值相等的節點（no duplicate nodes） 二叉查找樹相比於其他數據結構的優勢在於查找、插入的時間復雜度較低。為O(log n)。 二叉查找樹是基礎性數據結構，用於構建更為抽象的數據結構，如集合、multiset、關聯數組等。 二叉查找樹的查找過程和次優二叉樹類似，通常采取二叉鏈表作為二叉查找樹的存儲結構。中序遍歷二叉查找樹可得到一個關鍵字的有序序列，一個無序序列可以通過構造一棵二叉 查找樹變成一個有序序列，構造樹的過程即為對無序序列進行查找的過程。每次插入的新的結點都是二叉查找樹上新的葉子結點，在進行插入操作時，不必移動其它結點，只需改動 某個結點的指針，由空變為非空即可。搜索,插入,刪除的復雜度等於樹高，期望O(log n),最壞O(n)(數列有序,樹退化成線性表). 雖然二叉查找樹的最壞效率是O(n),但它支持動態查詢,且有很多改進版的二叉查找樹可以使樹高為O(logn),如:SBT,AVL,紅黑樹等.故不失為一種好的動態查找方法. 基本操作實現： 1、二叉查找樹聲明 /*********二叉查找樹聲明 ********/ typedef struct tree_node *tree_prt; struct tree_node { element_type element; tree_ptr left; tree_prt right; }; typedef tree_ptr SEARCH_TREE; 2、查找操作 思路：若根結點的關鍵字等於查找的關鍵字，查找成功；否則，若小於根結點的關鍵字的值，遞歸查找左子樹，否則若大於根結點的關鍵字的值，遞歸查找右子樹，若子樹為空，則查找不成功 /*********查找算法 ********/ tree_ptr find(element_type x, SEARCH_TREE T) { if(T ==NULL) return NULL; if(x < T->element) return (find(x, T->left)); else if(x > T->element) return (find(x, T->right)); else return T; } 3、查找最大最小結點 /*********查找最大最小結點 ********/ tree_ptr find_min(SEARCH_TREE T) //遞歸 { if(T == NULL) return NULL; else if(T->left == NULL) return T; else return find_min(T->left); } tree_ptr find_max(SEARCH_TREE T) //非遞歸 { if(T != NULL) { while(T->right != NULL) { T = T->right; } } return T; } 4、插入操作 思路：首先執行查找算法，找出被插入結點的父結點，判斷被查結點是父結點的左孩子還是右孩子，將被插結點作為葉子結點插入，若二叉樹為空，則首先單獨生成根結點 /*********插入結點1 ********/ void insert(element_type x, SEARCH_TREE *T) { if(*T == NULL) { /* 空樹 */ *T = (SEARCH_TREE)malloc(sizeof(struct tree_node)); if(*T == NULL) { printf("Out of space!!!"); return; } else { (*T)->element = x; (*T)->left = (*T)->right = NULL; } } else if(x < (*T)->element) { insert(x, &((*T)->left)); } else { insert(x, &((*T)->right)); } } 當然也可以使用返回插入結點的方式： /*********插入結點2 ********/ tree_ptr insert(element_type x, SEARCH_TREE T) { if(T == NULL) { /* 空樹 */ T = (SEARCH_TREE)malloc(sizeof(struct tree_node)); if(T == NULL) { printf("Out of space!!!"); return; } else { T->element = x; T->left = T->right = NULL; } } else if(x < T->element) { T->left = insert(x, T->left)); } else { T->right = insert(x, T->right)); } return T; } 5、刪除操作 在二叉查找樹刪去一個結點，分三種情況討論： ① 若p是葉子結點： 直接刪除p，如圖(b)所示。 ② 若p只有一棵子樹(左子樹或右子樹)：直接用p的左子樹(或右子樹)取代p的位置而成為f的一棵子樹。即原來p是f的左子樹，則p的子樹成為f的左子樹；原來p是f的右子樹，則p的子樹成為f的右子樹，如圖(c)、 (d)所示。 ③ 若p既有左子樹又有右子樹 ：處理方法有以下兩種，可以任選其中一種。 ◆ 用p的直接前驅結點代替p。即從p的左子樹中選擇值最大的結點s放在p的位置(用結點s的內容替換結點p內容)，然後刪除結點s。s是p的左子樹中的最右邊的結點且沒有右子樹，對s的刪除同②，如圖(e)所示。 ◆ 用p的直接後繼結點代替p。即從p的右子樹中選擇值最小的結點s放在p的位置(用結點s的內容替換結點p內容)，然後刪除結點s。s是p的右子樹中的最左邊的結點且沒有左子樹，對s的刪除同②。 void delete(SEARCH_TREE *p) { SEARCH_TREE q, s; if((*p)->right == NULL) { q = *p; *p = (*p)->left; free(q); } else if((*p)->left == NULL) { q = *p; *p = (*p)->right; free(q); } else { q = *p; s = (*p)->left; while(s->right != NULL) { q = s; s = s->right; } (*p)->element = s->element; if(q != p) { q->right = s->left; } else { q ->left = s->left; } } free(s); } void deleteBST(SEARCH_TREE *T, element_type key) { if(!(*T)) { return; } else if ((*T)->element == key) { free(*T); } else if((*T)->element > key) { deleteBST((*)T->left, key); } else { deleteBST((*)T->right, key); } } 編程實踐 poj2418 Hardwood Species #include<stdio.h> #include<stdlib.h> #include<string.h> struct node { char name[31]; struct node *lchild, *rchild; int count; }tree; struct node *root; int n = 0; void mid_cal(struct node *root) { if(root != NULL) { mid_cal(root->lchild); printf("%s %.4lf\n", root->name, ((double)(root->count) / (double)n) * 100.0); mid_cal(root->rchild); } } void insertBST(struct node** root, char *s) { if(*root == NULL) { struct node *p = (struct node*)malloc(sizeof(tree)); strcpy(p->name, s); p->lchild = p->rchild = NULL; p->count = 1; *root = p; } else { if(strcmp(s, (*root)->name) == 0) { ((*root)->count)++; return; } else if(strcmp(s, (*root)->name) < 0) { insertBST(&((*root)->lchild), s); } else { insertBST(&((*root)->rchild), s); } } } int main() { char s[31]; while(gets(s)) { insertBST(&root, s); n++; } mid_cal(root); return 0;
