数据结构-C实现二叉查找树

树,源于元素之间的关系,通常子节点连向父节点,从整体上看就像一颗倒过来的树,根节点表示这种数据结构的起始元素。指针提供了一种维护三个节点之间关系的直观、动态的方式。我们可以动态分配节点内存,将其按需插入树中。
例如下的结构体节点

typedef struct _tree {
    void * data;//借助void指针指向任意数据
    struct _tree *left;//左节点
    struct _tree *right;//右节点
} TreeNode;

当我们按照特定的顺序向树中插入节点:插入新节点后,这个节点的所有左子节点的值都比父节点小,所有右子节点的值都比父节点的值大,这样的树就称为二叉查找树(利于查找操作)。
下面这个insertNode函数会把一个节点插入二叉查找树,这里利用COMPARE函数指针传递比较函数的地址。
定义一个雇员结构体

typedef struct _employee {
    char name[32];
    unsigned char age;
} Employee;

定义比较函数

typedef int(*COMPARE)(void *,void *);//定义一个函数指针

//比较函数
int compareEmployee(Employee *e1, Employee *e2) {
    return strcmp(e1->name, e2->name);
}

节点插入

//
void insertNode(TreeNode ** root, COMPARE compare, void * data) {
    TreeNode * node = (TreeNode*)malloc(sizeof(TreeNode));//申请内存,起始节点
    node->data = data;
    node->left = NULL;
    node->right = NULL;

    if (*root == NULL) {//起始节点不存在
        *root = node;
        return;
    }

    while (1){
        if (compare((*root)->data, data) > 0) {//判断节点值大小
            if ((*root)->left != NULL) {//左节点有值
                *root = (*root)->left;//将该节点作为父节点
            }else {//循环至根节点
                (*root)->left = node;//添加新的节点
                break;
            }
        }else {//右节点
            if ((*root)->right!= NULL) {
                *root = (*root)->right;
            }else{
                (*root)->right = node;
                break;
            }
        }
    }
}

就这样,我们就完成了一个二叉查找树的插入节点函数。下面初始化一个空的TreeNode,然后插入3个雇员结构体。

Employee * samuel = (Employee*)malloc(sizeof(Employee));
    samuel->age = 18;
    strcpy_s(samuel->name,32,"Samuel");

    Employee * sally = (Employee*)malloc(sizeof(Employee));
    sally->age = 25;
    strcpy_s(sally->name, 32,"Sally");

    Employee * susan = (Employee*)malloc(sizeof(Employee));
    susan->age = 22;
    strcpy_s(susan->name, 32, "Susan");

    TreeNode * tree = NULL;

    insertNode(&tree, (COMPARE)compareEmployee, samuel);
    insertNode(&tree, (COMPARE)compareEmployee, sally);
    insertNode(&tree, (COMPARE)compareEmployee, susan);

下图我们可以看到整个内存的结构状态


结构.png

后面再写二叉树的其他的操作了。
PS.参考书籍《深入理解C指针》

最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容

  • 树的概述 树是一种非常常用的数据结构,树与前面介绍的线性表,栈,队列等线性结构不同,树是一种非线性结构 1.树的定...
    Jack921阅读 4,491评论 1 31
  • 1 序 2016年6月25日夜,帝都,天下着大雨,拖着行李箱和同学在校门口照了最后一张合照,搬离寝室打车去了提前租...
    RichardJieChen阅读 5,173评论 0 12
  • B树的定义 一棵m阶的B树满足下列条件: 树中每个结点至多有m个孩子。 除根结点和叶子结点外,其它每个结点至少有m...
    文档随手记阅读 13,368评论 0 25
  • 基于树实现的数据结构,具有两个核心特征: 逻辑结构:数据元素之间具有层次关系; 数据运算:操作方法具有Log级的平...
    yhthu阅读 4,332评论 1 5
  • 就这样离开了吗? 也许吧,很多时候不都这样吗? 归去,也无风雨也无晴…… 回首凝望,依旧熟悉的校园, “悄悄的我走...
    文逸林阅读 476评论 0 2