c语言实现二叉查找树实例方法

以下为算法详细流程及其实现。由于算法都用伪代码给出，就免了一些文字描述。

复制代码 代码如下:

#include
#include
#include
#define WORDLEN 16
//定义一个节点，除了存放key值外，还包含了一个data字符数组用于存放一个单词
struct node{
    int key;
    char data[WORDLEN];
    struct node *parent;
    struct node *left;
    struct node *right;
};
typedef struct node * tree;

   
void inorder_tree_walk(tree T)
{
    if(T!=NULL){
        inorder_tree_walk(T->left);
        printf("key:%d   words:%sn",T->key,T->data);
        inorder_tree_walk(T->right);
    }
}

//递归版本
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;
}

   
struct node* tree_minimum(tree T)
{
    while(T->left != NULL)
        T=T->left;
    return T;
}

struct node* tree_maxmum(tree T)
{
    while(T->right != NULL)
        T=T->right;
    return T;
}
   
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;
}

   
void tree_insert(tree *PT,struct node *z)
{
    if(*PT==NULL){//树为空，则将z作为根结点返回
        *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;
}

struct node * tree_delete(tree *PT,struct node *z)
{
    struct node *delnode,*sonnode;
    if(z->left==NULL || z->right == NULL)//有一个子女或无子女，则要删除的结点结尾z本身
        delnode=z;
    else                                 //有两个子女，则要删除的结点为z的后继结点
        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) nown",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);
}

程序运行结果：
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