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

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

复制代码 代码如下:

/*******************************************
=================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
//定义一个节点，除了存放key值外，还包含了一个data字符数组用于存放一个单词
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);
    }
}

/*============================================
树的搜索，返回含有关键字k的结点
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值最小的结点
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值最大的结点
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;
}
/*============================================   
中序遍历下，返回某一结点的后继结点
1）如果结点x有右子结点，则其后继结点为右子树中最小结点。
2）如果结点x没有右子树，且x有一个后继y，则y是x的最低祖先结点
且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循环，直接返回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;
}

/*===========================================
插入操作
思路：从根节点一路往下寻找插入位置，用指针x跟踪这条寻找路径，并用指针y指向x的父结点
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作为根结点返回
        *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）若要删除的节点z没有子女，则只需修改z的父节点的该子女为NIL即可
2）若要删除的节点z只有一个子女，则只需将z的这个子女与z的父节点连接起来即可
3）若要删除的节点z有两个子女，则需要先删除z的后继y，再用y的内容替换z的内容。
TREE_DELETE(T,z)
    if left[z]=NIL || right[z]=NIL  //把要删除的节点先保存在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]    //将要删除节点的子女连接到要删除节点的父节点上
    if p[y]=NIL     //如果要删除的节点为根节点
        then root[T] <—— x
        else if y=left[p[y]]//
            then left[p[y]] <—— x
            else right[p[y]] <—— x
    if y!=z  //第三种情况，需要用y的内容替换z的内容
        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)//有一个子女或无子女，则要删除的结点结尾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) 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);
}

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

时间： 2024-12-06 00:10:54

c语言实现二叉查找树实例方法_C 语言的相关文章

C语言泛型编程实例教程_C 语言

本文实例讲述了C语言泛型编程的方法,分享给大家供大家参考之用.具体分析如下: 首先,泛型编程让你编写完全一般化并可重复使用的算法,其效率与针对某特定数据类型而设计的算法相同.在C语言中,可以通过一些手段实现这样的泛型编程.这里介绍一种方法--通过无类型指针void* 看下面的一个实现交换两个元素内容的函数swap,以整型int为例: void swap(int* i1,int* i2){ int temp; temp = *i1; *i1 = *i2; *i2 = temp; } 当你想交换两个

C语言冒泡排序法心得_C 语言

记得以前在大学里学习c语言的时候,刚开始是很吃力的. 入门级别的算法中有个叫冒泡排序法,也有称为气泡排序法.那时候刚接触它就对它的名字特别感兴趣,因为觉得很有意思.好了,废话不多说了,我们先一起简单回忆下这个冒泡排序法.  一.打印行和列一般是这样的一个简单代码,输出4行4列*: for(int i = 1,i < 5,i++){ for(int j = 1,j < 5,j++){ printf("*"); } printf("n\"); }  二.打印

C语言字符串大小比较_C 语言

C语言字符串大小比较 #include <stdio.h> #include <string.h> int fun(char *a,char *b) { int i = 0,j = 0; while(a[i]&&b[j]) { if(a[i]-b[j]>0) return 1; else if(a[i]-b[j]<0) return -1; i++,j++; } if(strlen(a)==i&&strlen(b)==j) return

12个关于C语言的有趣问答_C 语言

本文汇总了12个关于C语言的问答,对于加深对C语言程序设计的难点理解很有帮助,读者可参考一下: 1.gets() 方法 问:以下代码有个被隐藏住的问题,你能找到它吗? 答:这个不显眼的问题就是使用了 gets() 方法.此方法接受一个string类型参数,但是却没有检测此数值是否 有足够的空间来拷贝数据.所以这里我们一般用 fgets() 方法将来的更好. #include<stdio.h> int main(void) { char buff[10]; memset(buff,0,sizeo

浅谈C语言的字符串分割_C 语言

说起来很有意思,自认为对C语言理解得还是比较深刻的.但居然到今天才知道有个strtok函数,试用了一下突然感慨以前做了多少重复劳动.每次需要解析配置文件,每次需要分割字符串,居然都是自己去分割字符串,既累人又容易出错.感概技术学得不够全面啊!这里引用一段strtok用法: The strtok() function returns a pointer to the next "token" in str1, where str2 contains the delimiters that

原创的C语言控制台小游戏_C 语言

最开始左上色块被感染,通过切换颜色,不断感染同色色块.亮点是可以切换图案,设置方块个数和最大限制次数.整体还是比较满意,希望大神指教. #include <stdio.h> #include <windows.h> #include <conio.h> #include <time.h> #include <stdlib.h> int DIFFICULT=44; int count=0 ; int TYPE_SHAPE=2 ; int flag=

C语言 数据类型详细介绍_C 语言

C 数据类型 在 C 语言中,数据类型指的是用于声明不同类型的变量或函数的一个广泛的系统.变量的类型决定了变量存储占用的空间,以及如何解释存储的位模式. C 中的类型可分为以下几种: 序号 类型与描述 1 基本类型: 它们是算术类型,包括两种类型:整数类型和浮点类型. 2 枚举类型: 它们也是算术类型,被用来定义在程序中只能赋予其一定的离散整数值的变量. 3 void 类型: 类型说明符 void 表明没有可用的值. 4 派生类型: 它们包括:指针类型.数组类型.结构类型.共用体类型和函数类型.

C语言实现冒泡排序算法_C 语言

BubblSort.c #include<stdio.h> void BubbleSort(int a[],int len) { int i; int j; int h; int temp; for(i=0;i<len-1;++i) { for(j=len-1;j>i;--j) { if(a[j]<a[j-1]) { temp=a[j]; a[j]=a[j-1]; a[j-1]=temp; } } for(h=0;h<len;h++) { printf(" %

6个变态的C语言Hello World程序_C 语言

下面的六个程序片段主要完成这些事情: 输出Hello, World 混乱C语言的源代码 下面的所有程序都可以在GCC下编译通过,只有最后一个需要动用C++的编译器g++才能编程通过. hello1.c #define _________ } #define ________ putchar #define _______ main #define _(a) ________(a); #define ______ _______(){ #define __ ______ _(0x48)_(0x65