c語言實現(xiàn)二叉查找樹實例方法
以下為算法詳細(xì)流程及其實現(xiàn)。由于算法都用偽代碼給出，就免了一些文字描述。
/*******************************************
=================JJ日記=====================
作者: JJDiaries(阿呆)
郵箱：JJDiaries@gmail.com
日期: 2013-11-13
============================================
二叉查找樹，支持的操作包括：SERACH、MINIMUM、
MAXIMUM、PREDECESSOR、SUCCESSOR、INSERT、DELETE。
定理：對于一個高度為h的二叉查找樹，操作SERACH、MINIMUM、
MAXIMUM、PREDECESSOR、SUCCESSOR的運行時間均為O(h)
*******************************************/
/*================JJ日記=====================
作者: JJDiaries(阿呆)
郵箱：JJDiaries@gmail.com
日期: 2013-11-13
============================================*/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define WORDLEN 16
//定義一個節(jié)點，除了存放key值外，還包含了一個data字符數(shù)組用于存放一個單詞
struct node{
int key;
char data[WORDLEN];
struct node *parent;
struct node *left;
struct node *right;
};
typedef struct node * tree;
/*============================================
樹的中序遍歷
INORDER_TREE_WALK(x)
if x!=NIL
then INORDER_TREE_WALK(left[x])
print key[x]
INORDER_TREE_WALK(left[x])
============================================*/
void inorder_tree_walk(tree T)
{
if(T!=NULL){
inorder_tree_walk(T->left);
printf("key:%d words:%s\n",T->key,T->data);
inorder_tree_walk(T->right);
}
}
/*============================================
樹的搜索，返回含有關(guān)鍵字k的結(jié)點
TREE_SEARCH(x,k) //遞歸版本
if x=NIL or k =key[x]
then return x
if k<key[x]
then return TREE_SEARCH(left[x],k)
else return TREE_SEARCH(right[x],k)
TREE_SEARCH(x,k) //非遞歸版本
while x!=NIL and k!= key[x]
do if k<key[x]
then x <—— left[x]
else x <—— right[x]
return x
============================================*/
//遞歸版本
struct node* tree_search(tree T,int k)
{
if(T==NULL || k == T->key)
return T;
if(k < T->key)
return tree_search(T->left,k);
else
return tree_search(T->right,k);
}
//非遞歸版本
struct node* tree_search1(tree T,int k)
{
while(T!=NULL && T->key!=k)
if(k < T->key)
T=T->left;
else
T=T->right;
return T;
}
/*============================================
返回key值最小的結(jié)點
TREE_MINIMUM(x)
while left[x]!=NIL
do x <—— left[x]
return x
============================================*/
struct node* tree_minimum(tree T)
{
while(T->left != NULL)
T=T->left;
return T;
}
/*============================================
返回key值最大的結(jié)點
TREE_MAXMUM(x)
while right[x]!=NIL
do x <—— right[x]
return x
============================================*/
struct node* tree_maxmum(tree T)
{
while(T->right != NULL)
T=T->right;
return T;
}
/*============================================
中序遍歷下，返回某一結(jié)點的后繼結(jié)點
1）如果結(jié)點x有右子結(jié)點，則其后繼結(jié)點為右子樹中最小結(jié)點。
2）如果結(jié)點x沒有右子樹，且x有一個后繼y，則y是x的最低祖先結(jié)點
且y的左兒子也是x的祖先。
TREE_SUCCESSOR(x)
if right[x] != NIL
return TREE_MINIMUM(right[x])
y=p[x]
while y!=NIL and x=right[y] //如果x=left[y]，那么x的后繼就是y，跳出while循環(huán)，直接返回y即可
do x <—— y
y <—— p[y]
return y
============================================*/
struct node * tree_successor(struct node *T)
{
if(T->right!=NULL)
return tree_minimum(T->right);
struct node *y=T->parent;
while(y!=NULL && T == y->right){
T=y;
y=y->parent;
}
return y;
}
/*===========================================
插入操作
思路：從根節(jié)點一路往下尋找插入位置，用指針x跟蹤這條尋找路徑，并用指針y指向x的父結(jié)點
TREE_INSERT(T,z)
y=NIL
x=root[T]
while x!= NIL //直到x為空，這個空位置即為需要插入的位置
do y<—— x
if key[z]<key[x]
then x <—— left[x]
else x <—— right[x]
p[z]=y
if y=NIL
then root[T]=z //樹T為空時的情況
else if key[z] < key[y]
then left[y]=z //小于y的插在左邊，大于的插在右邊
else right[y]=z
============================================*/
void tree_insert(tree *PT,struct node *z)
{
if(*PT==NULL){//樹為空，則將z作為根結(jié)點返回
*PT=z;
return;
}
struct node *y=NULL;
struct node *x=*PT;
while(x!=NULL){
y=x;
if(z->key < x->key)
x=x->left;
else
x=x->right;
}
z->parent=y;
if(z->key < y->key)
y->left=z;
else
y->right=z;
}
/*===============================================
刪除操作
刪除操作分為三類情況：
1）若要刪除的節(jié)點z沒有子女，則只需修改z的父節(jié)點的該子女為NIL即可
2）若要刪除的節(jié)點z只有一個子女，則只需將z的這個子女與z的父節(jié)點連接起來即可
3）若要刪除的節(jié)點z有兩個子女，則需要先刪除z的后繼y，再用y的內(nèi)容替換z的內(nèi)容。
TREE_DELETE(T,z)
if left[z]=NIL || right[z]=NIL //把要刪除的節(jié)點先保存在y中
then y <—— z
else y <—— TREE_SUCCESSOR(z)
if left[y]!=NIL //將y的非空子女存放在x中
then X <—— left[y]
else x <—— right[y]
if x!=NIL
then p[x]=p[y] //將要刪除節(jié)點的子女連接到要刪除節(jié)點的父節(jié)點上
if p[y]=NIL //如果要刪除的節(jié)點為根節(jié)點
then root[T] <—— x
else if y=left[p[y]]//
then left[p[y]] <—— x
else right[p[y]] <—— x
if y!=z //第三種情況，需要用y的內(nèi)容替換z的內(nèi)容
then key[z] <—— key[y]
copy y's other data to z
return y
==============================================*/
struct node * tree_delete(tree *PT,struct node *z)
{
struct node *delnode,*sonnode;
if(z->left==NULL || z->right == NULL)//有一個子女或無子女，則要刪除的結(jié)點結(jié)尾z本身
delnode=z;
else //有兩個子女，則要刪除的結(jié)點為z的后繼結(jié)點
delnode=tree_successor(z);
if(delnode->left!=NULL)
sonnode=delnode->left;
else
sonnode=delnode->right;
if(sonnode!=NULL)
sonnode->parent=delnode->parent;
if(delnode->parent==NULL)
*PT=sonnode;
else if(delnode->parent->left==delnode)
delnode->parent->left=sonnode;
else
delnode->parent->right=sonnode;
if(delnode!=z){
z->key=delnode->key;
strcpy(z->data,delnode->data);
}
return delnode;
}
//初始化一棵樹
tree init_tree(int key)
{
struct node * t;
t=(tree)malloc(sizeof(struct node));
if(t==NULL)
return NULL;
t->key=key;
t->parent=t->left=t->right=NULL;
return t;
}
//釋放資源
void fini_tree(tree T)
{
if(T!=NULL){
fini_tree(T->left);
fini_tree(T->right);
printf("free node(%d,%s) now\n",T->key,T->data);
free(T);
}
}
//測試程序
int main()
{
tree myTree=init_tree(256);
if(myTree==NULL)
return 1;
strcpy(myTree->data,"JJDiaries");
struct record{
int key;
char word[WORDLEN];
};
struct record records[]={ {2,"Viidiot"},
{4,"linux-code"},
{123,"google"},
{345,"baidu"},
{543,"nsfocus"}
};
int i;
struct node *tmp;
for(i=0;i<5;++i){
tmp=(tree)malloc(sizeof(struct node));
if(tmp==NULL)
continue;
tmp->key=records[i].key;
strcpy(tmp->data,records[i].word);
tmp->left=tmp->right=tmp->parent=NULL;
tree_insert(&myTree,tmp);
}
inorder_tree_walk(myTree);
struct node *del;
del=tree_delete(&myTree,tree_search(myTree,345));
printf("Delete node(%d,%s)\n",del->key,del->data);
free(del);
inorder_tree_walk(myTree);
fini_tree(myTree);
}
程序運行結(jié)果：
jjdiaries@ubuntu>./search_tree
key:2 words:Viidiot
key:4 words:linux-code
key:123 words:google
key:256 words:JJDiaries
key:345 words:baidu
key:543 words:nsfocus
Delete node(345,baidu)
key:2 words:Viidiot
key:4 words:linux-code
key:123 words:google
key:256 words:JJDiaries
key:543 words:nsfocus
free node(123,google) now
free node(4,linux-code) now
free node(2,Viidiot) now
free node(543,nsfocus) now
free node(256,JJDiaries) now
相關(guān)文章
這篇文章主要介紹了關(guān)于C語言位運算的簡單示例，文中通過示例代碼介紹的非常詳細(xì)，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2020-12-12
這篇文章主要介紹了C++11 Unicode編碼轉(zhuǎn)換的相關(guān)資料，幫助大家更好的理解和學(xué)習(xí)c++11，感興趣的朋友可以了解下2020-08-08
這篇文章主要為大家詳細(xì)介紹了C語言實現(xiàn)簡單電子通訊錄，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價值，感興趣的小伙伴們可以參考一下2020-06-06
大家好，本篇文章主要講的是C++對象與繼承使用中一些問題介紹，感興趣的同學(xué)趕快來看一看吧，對你有幫助的話記得收藏一下，方便下次瀏覽2022-01-01
這篇文章主要介紹了C++實現(xiàn)多源最短路徑之Floyd算法,結(jié)合實例形式分析了多源最短路徑之Floyd算法的原理、實現(xiàn)方法及核心代碼,需要的朋友可以參考下2017-08-08
在C++編程中，異常處理和錯誤處理機(jī)制是非常重要的，它們可以幫助程序員有效地處理運行時錯誤和異常情況，本文就來介紹一下C++中的異常處理和錯誤處理機(jī)制吧2023-05-05
這篇文章主要給大家介紹了關(guān)于C++中sort函數(shù)的基礎(chǔ)入門使用的相關(guān)資料，文中通過示例代碼介紹的非常詳細(xì)，對大家學(xué)習(xí)或者使用C++具有一定的參考學(xué)習(xí)價值，需要的朋友們下面來一起看看吧2018-12-12
C語言函數(shù)是用來模塊化構(gòu)建程序的。如果你的功能少，你可以全都寫在mian函數(shù)中，但是當(dāng)實現(xiàn)功能多的時候，如果全寫在main的函數(shù)里，不僅代碼不美觀，而且函數(shù)實現(xiàn)的時候結(jié)構(gòu)復(fù)雜，代碼重復(fù)2022-05-05
這篇文章主要介紹了windows下vscode使用cmake的方法，文中通過示例代碼介紹的非常詳細(xì)，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2021-03-03
這篇文章主要為大家詳細(xì)介紹了C語言實現(xiàn)哈夫曼樹的構(gòu)建，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價值，感興趣的小伙伴們可以參考一下2020-04-04