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