数据结构-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指针》

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

推荐阅读更多精彩内容