C语言用指针支持树

树是很有用的数据结构，它的名字源于元素之间的关系。通常，子节点连接到父节点，从整体上看就像一颗倒过来的树，根节点表示这种数据结构的开始元素。

树可以有任意数量的子节点，不过，二叉树比较常见，它的每个节点能有0个、1个或是2个子节点。子节点要么是左子节点，要么是右子节点。没有子节点的节点称为叶子节点，就跟树叶一样。本节中的示例会阐明二叉树。

指针提供了一种维护三个节点之间关系的直观、动态的方式。我们可以动态分配节点，将其按需插入树中。这里使用下面的结构体作为节点，借助void指针可以处理我们需要的任意类型的数据：

typedef struct _tree {
    void *data;
    struct _tree *left;
    struct _tree *right;
} TreeNode;

按照特定顺序向树中插入节点是有意义的，这样可以让很多操作（比如搜索）变得容易。下面的顺序很常见：插入新节点后，这个节点的所有左子节点的值都比父节点小，所有右子节点的值都比父节点的值大，这样的树称为二叉查找树。

下面这个insertNode函数会把一个节点插入二叉查找树，不过，要插入节点，首先需要在新节点和已有节点之间做比较。我们用COMPARE函数指针来传递比较函数的地址，函数的第一部分为新节点分配内存并把数据赋给节点。因为新节点插入树后总是叶子节点，所以将左子节点和右子节点置为NULL：

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指针的指针的形式传递的，这是必要的，因为我们需要修改传入函数的指针，而不是指针指向的对象。

如果树非空，程序就进入一个无限循环，直到将新节点插入树中结束。每次循环迭代都会比较新节点和当前节点，根据比较结果，将局部root指针置为左子节点或者右子节点，这个root指针总是指向树的当前节点。如果左子节点或右子节点为空，那么就将新节点添加为当前节点的子节点，循环结束。

为了说明insertNode函数，我们会重用6.4节中创建的雇员实例。下面的代码片段初始化一个空的TreeNode，然后插入三个雇员结构体，程序栈的结果和堆的状态如下图所示。为了简化这个图，我们省略了某些指向雇员结构体的线，并调整了节点在堆中的位置，以反映树结构的顺序：

TreeNode *tree = NULL;

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

下说明了这棵树的逻辑结构。

二叉树可以满足多种需求，遍历二叉树的方式有三种：前序、中序和后序。三种技术步骤相同，但顺序不同。三个步骤如下：

• 访问节点
  处理节点
• 往左
  转移到左子节点
• 往右
  转移到右子节点

对我们来说，访问节点的目的是打印其内容。访问节点的三种顺序如下所示。

• 中序
  先往左，访问节点，再往右。
• 前序
  访问节点，往左，再往右。
• 后序
  先往左，再往右，最后访问节点。

函数的实现如下，所有的函数的参数都是树根和作为打印函数的一个函数指针，它们都是递归的。只要传入的根节点非空就会调用自身，不同点只在于执行三步操作的顺序：

void inOrder(TreeNode *root, DISPLAY display) {
    if (root != NULL) {
        inOrder(root->left, display);
        display(root->data);
        inOrder(root->right, display);
    }
}

void postOrder(TreeNode *root, DISPLAY display) {
    if (root != NULL) {
        postOrder(root->left, display);
        postOrder(root->right, display);
        display(root->data);
    }
}

void preOrder(TreeNode *root, DISPLAY display) {
    if (root != NULL) {
        display(root->data);
        preOrder(root->left, display);
        preOrder(root->right, display);
    }
}

下面的代码片段调用这些函数：

preOrder(tree, (DISPLAY) displayEmployee);
inOrder(tree, (DISPLAY) displayEmployee);
postOrder(tree, (DISPLAY) displayEmployee);

下表显示的是基于前面初始化的树每次函数调用的输出。

中序遍历会返回树成员的排序列表，前序和后序遍历跟栈和队列配合使用可以计算算术表达式。