二叉树

二叉树是一种特殊形式的树，它的每个节点最多只有两个孩子。右边是一个一般形式的二叉树，它由一个根节点root和左右两个子树\(T_{left}, T_{right}\)构成。 实际上，这是一种嵌套的结构，它的左右两个子树分别具有相同的形式，并且其根节点是root的左右两个孩子。

一般我们提到二叉树，都是所谓的二叉查找树(binary search tree, BST)。对于二叉查找树中的任何一个节点，其左子树中的所有节点的键值都小于该节点的键值， 而右子树中的所有节点的键值都大于该节点的键值。并且二叉查找树中的任何子树都是二叉查找树。给定键值查找节点的过程，就相当于一个二分查找的过程。 平均情况下，对于一个有\(n\)个节点的查找树，其查找的时间复杂度是\(O(\log(n))\)的，这相比于线性表\(O(n)\)的平均查找效率要快了很多。

在最差的情况下，二叉树的所有节点都只有一个子节点。此时二叉树就退化成为了一个顺序的线性表，其查找复杂度就是\(O(n)\)。 在Linux内核中，定义和实现了一种特殊的二叉树——红黑树。红黑树的插入和删除操作相对复杂一些， 但是能够在一定程度上维持一个平衡的二叉树，可以避免二叉查找树的最差情况。

此外，在编译器的领域中，二叉树也是一种使用率很高的数据结构。有很多运算符都是双目的，比如说“加减乘除与或”等。我们以运算符作为键值，左右操作数分别作为两个子树。 那么就可以用一颗树的形式描述一个表达式。而且通过中序、先序、后序遍历树，我们可以获得编译过程中可能用到的中缀、前缀、后缀表达式。

本文中，我们以类似Linux中的链表的套路实现一套C语言的二叉树接口。

1. 二叉树的定义与构建

我们沿用Linux中的链表的思想，将二叉树节点嵌入到实际的结构体中。下面左侧代码定义了一个精简的数据结构， 只有三个指针。其中parent用于指示当前节点的父节点，如果当前节点是根节点则不存在父节点，parent指向当前空地址。如果它没有左孩子或者右孩子，那么left或者right将指向空地址。 初始化过程如下面右侧的代码所示。

        struct binary_tree_node {
            struct binary_tree_node *parent;
            struct binary_tree_node *left;
            struct binary_tree_node *right;
        };

        void init_binary_tree_node(struct binary_tree_node* node) {
            node->parent = NULL;
            node->left = NULL;
            node->right = NULL;
        }

根据在文章之初给出的二叉树一般形式，构建一棵二叉树需要三个要素：根节点、左子树、右子树，其中根节点是必须的。下面的函数create_btree就是用来构建二叉树的函数， 它有三个参数，其中root是将要构建的二叉树的根节点，lroot和rroot分别是左右两个子树的根节点。在该函数中，我们先判定root不为空。接着分别判定左右子树是否存在， 若存在则将它们添加到root上。

        void create_btree(struct btree_node *root, struct btree_node *lroot, struct btree_node *rroot) {
            assert(NULL != root);
            if (NULL != lroot) {
                root->left = lroot;
                lroot->parent = root;
            }
            if (NULL != rroot) {
                root->right = rroot;
                rroot->parent = root;
            }
        }

2. 二叉树的遍历

对于二叉树，根据根节点的访问顺序有先序、中序和后序三种遍历方式。所谓的先序遍历就是处理节点本身，再依次访问节点的左子树和右子树，即节点->左子树->右子树的访问顺序。 中序遍历的顺序则是左子树->节点->右子树，后序则是左子树->右子树->节点。

下面三段伪代码分别是以递归的形式描述的三种遍历方式。递归的形式实现起来很简洁，但是效率上有些问题。递归的实现需要一直调用函数，直到访问到一个叶子节点才会沿着调用路径依次返回， 如果树的深度很高，就需要用到大量的栈空间(这里所说的栈是指系统的栈空间， 不是数据结构栈。)；而且函数调用与返回也会额外的耗费一些计算资源和时间。

preorder_traversal(node)
    handle(node)
    if (nil != node.left)
        preorder_traversal(node.left)
    if (nil != node.right)
        preorder_traversal(node.right)

inorder_traversal(node)
    if (nil != node.left)
        inorder_traversal(node.left)
    handle(node)
    if (nil != node.right)
        inorder_traversal(node.right)

postorder_traversal(node)
    if (nil != node.left)
        postorder_traversal(node.left)
    if (nil != node.right)
        postorder_traversal(node.right)
    handle(node)

我们完全可以以非递归的形式实现这三种遍历操作，但是需要借助一个栈来实现。入栈的顺序不一样，决定了遍历方式的不同。

2.1 先序遍历

下面是先序遍历的实现，它有两个参数， 其中root指示了遍历目标树的根节点。pdeque则是一个双端队列，如果我们只在一端操作它就是一个栈。 第一次调用该函数的时候，应当保证pdeque为空。调用该函数它都只会返回一个二叉树节点，返回对象的顺序是对二叉树先序遍历的顺序。

        struct btree_node * btree_preorder_traversal(struct btree_node *root, deque_btree_node_ptr *pdeque) {
            struct btree_node *re;

接下来，我们根据输入的栈是否为空来判定是否是首次调用该函数。如果栈为空表明当前是首次调用该函数，应当从根节点开始处理，所以在第5行中令re指向了根节点。 如果栈不空，说明之前已经调用过该函数，栈中已经记录了先序遍历的中间结果，在第7行中从栈中拿出一个节点进行处理。当我们从栈中取出一个空指针时说明已经遍历结束， 返回空指针。

            int size = deque_btree_node_ptr_size(pdeque);
            if (0 == size) {
                re = root;
            } else {
                deque_btree_node_ptr_pop_back(pdeque, &re);
                if (NULL == re)
                    return NULL;
            }

然后先后检测右子树和左子树是否存在，如果存在则将它们入栈。

            if (NULL != re->right)
                deque_btree_node_ptr_push_back(pdeque, re->right);
            if (NULL != re->left)
                deque_btree_node_ptr_push_back(pdeque, re->left);

在返回当前节点之前，我们先检查一下栈的大小。如果为空，说明已经遍历了整棵树，下次调用该函数的时候需要返回空指针以结束遍历。所以我们在第16行中，向入栈了一个空指针。

            if (0 == deque_btree_node_ptr_size(pdeque))
                deque_btree_node_ptr_push_back(pdeque, NULL);
            return re;
        }

2.2 中序遍历

下面是中序遍历的实现，它同样有两个参数，其中root指示了遍历目标树的根节点。pdeque则是一个用作栈的双端队列。

        struct btree_node * btree_inorder_traversal(struct btree_node *root, deque_btree_node_ptr *pdeque) {
            struct btree_node *re;

我们仍然根据栈是否为空来判定是否首次调用该函数。如果是首次调用，我们将在第6到9行的while循环中沿着左子树展开，并依次将途经的节点入栈。该循环结束之后， re就得到了树中最左边的节点。

            int size = deque_btree_node_ptr_size(pdeque);
            if (0 == size) {
                re = root;
                while (NULL != re->left) {
                    deque_btree_node_ptr_push_back(pdeque, re);
                    re = re->left;
                }
            }

如果栈不空，说明已经将树中的节点沿左子树展开了。此时从栈中取出一个节点，如果为空指针，则说明已经遍历结束。

            else {
                deque_btree_node_ptr_pop_back(pdeque, &re);
                if (NULL == re)
                    return NULL;
            }

如果没有遍历结束，并且当前节点有右孩子，我们就需要对这个右孩子沿左子树展开，如下面代码所示。这样我们就能够保证栈中所保存的节点的左子树都已经展开。

            if (NULL != re->right) {
                deque_btree_node_ptr_push_back(pdeque, re->right);
                root = re->right;
                while (NULL != root->left) {
                    deque_btree_node_ptr_push_back(pdeque, root->left);
                    root = root->left;
                }
            }

当所有节点的左子树都展开之后，就意味着遍历结束，此时栈将变空。我们入栈一个空指针，下次调用该函数的时候就会通知调用者遍历结束。

            if (0 == deque_btree_node_ptr_size(pdeque))
                deque_btree_node_ptr_push_back(pdeque, NULL);
            return re;
        }

2.3 后序遍历

相比于先序和中序遍历，后序遍历的非递归形式相对复杂了一点点。主要是因为需要先分别展开左右子树，再处理根节点，如果只是把子树的根节点入栈，很容易形成死循环。 需要一个机制来判定当前节点是否已经展开。下面是后序遍历的实现，它同样有两个参数，其中root指示了遍历目标树的根节点。 pdeque则是一个用作栈的双端队列。

        struct btree_node * btree_postorder_traversal(struct btree_node *root, deque_btree_node_ptr *pdeque) {
            struct btree_node *re, *tmp;

在初次调用该函数的时候，我们把根节点入栈两次。

            int size = deque_btree_node_ptr_size(pdeque);
            if (0 == size) {
                deque_btree_node_ptr_push_back(pdeque, root);
                deque_btree_node_ptr_push_back(pdeque, root);
            }

然后，我们从栈中取出一个节点。如果该节点是一个空指针，说明遍历结束。如果从栈中取出一个节点之后，栈变空了说明已经将所有的节点展开过了，下次调用就应当返回空指针了。

            deque_btree_node_ptr_pop_back(pdeque, &re);
            if (NULL == re)
                return NULL;
            if (0 == deque_btree_node_ptr_size(pdeque))
                deque_btree_node_ptr_push_back(pdeque, NULL);

peek_back函数用于查看当前双端队列队尾的数据，而不将之从队列中取出。我们通过该函数窥视一下栈顶中的数据，如果当前节点与栈顶中的节点是同一个，说明尚未展开过该节点。 我们将在下面的while循环中，依次展开右子树和左子树，每个展开的节点都在栈中保存两次，这样就能方便的判定当前节点是否展开过。

这里之所以使用一个while循环而不是简单的条件语句，是因为在后序遍历的展开过程中，我们需要沿着左子树和右子树依次向下搜索直到一个叶子节点为止，优先搜索左子树。

            deque_btree_node_ptr_peek_back(pdeque, &tmp);
            while (tmp == re) {
                if (NULL != re->right) {
                    deque_btree_node_ptr_push_back(pdeque, re->right);
                    deque_btree_node_ptr_push_back(pdeque, re->right);
                }
                if (NULL != re->left) {
                    deque_btree_node_ptr_push_back(pdeque, re->left);
                    deque_btree_node_ptr_push_back(pdeque, re->left);
                }
                deque_btree_node_ptr_pop_back(pdeque, &re);
                deque_btree_node_ptr_peek_back(pdeque, &tmp);
            }

最后我们将展开后的节点返回。

            return re;
        }

2.4 调用方式

假设我们有一个嵌入binary_tree_node节点的整型二叉树节点int_btree_node:

        struct int_btree_node {
            int key;
            struct btree_node n;
        };

我们可以通过如下的形式，通过while和for循环完成二叉树的三种形式的遍历。每次调用遍历函数都会按照遍历顺序返回一个指针，如果遍历结束将返回一个空指针，作为循环的结束条件。 这里通过宏定义ContainerOf来获取嵌入二叉树节点的对象本身。

        deque_btree_node_ptr deque;
        deque_btree_node_ptr_init(&deque);
        // 先序遍历
        struct btree_node *tmp = btree_preorder_traversal(&(root.n), &deque);
        while (NULL != tmp) {
            printf("%d\n", ContainerOf(tmp, struct int_btree_node, n)->key);
            tmp = btree_preorder_traversal(&(root.n), &deque);
        }
        // 中序遍历
        deque_btree_node_ptr_clear(&deque);
        for (tmp = btree_inorder_traversal(&(root.n), &deque); NULL != tmp; tmp = btree_inorder_traversal(&(root.n), &deque))
            printf("%d\r\n", ContainerOf(tmp, struct int_btree_node, n)->key);

3. 二叉搜索树

二叉搜索树是一种以二叉树形式构建的搜索树，其中的每个节点都满足一个规则：左子树的所有节点的键值都小于该节点的键值，右子树的所有节点键值都不小于该节点的键值。 一般有插入(insert)、删除(remove)、查找(search)一个节点的操作，有时还会求取搜索树中的最小键值(minimal)和最大键值(maximal)的节点， 对于每个节点还可以求取它在树中的前驱(predecessor)和后继(successor)节点。

根据二叉搜索树的性质，我们知道其中保存的数据存在顺序关系。由于我们希望提供一个比较通用的数据结构，所以我们并不清楚用户的键值是什么数据类型，更不可能直接对比两个键值。 需要用户自己提供一个用于对比两个节点的函数，为此我们定义了一个函数指针类型btree_compare_func。

        typedef int (*btree_compare_fun)(const struct btree_node *a, const struct btree_node *b);

它有两个参数分别指向了需要对比的两个节点，在使用过程中，如果该函数返回值小于0，则表示节点a的键值小于节点b的键值；大于0，则说明a的键值大于b的键值；等于0则两者相等。 用户需要根据这一规则提供一个对比函数，比如说对于刚刚定义的int_btree_node，我们可以提供如下的对比函数:

        int compare_fun(const struct btree_node *a, const struct btree_node *b) {
            struct int_btree_node *p_a = ContainerOf(a, struct int_btree_node, n);
            struct int_btree_node *p_b = ContainerOf(b, struct int_btree_node, n);
            return p_a->key - p_b->key;
        }

该函数具有与btree_compare_fun相同的参数列表。在函数的一开始，我们就通过宏ContainerOf获取嵌入二叉树节点的数据对象，分别用p_a和p_b指示。然后直接返回两个键值的差， 显然这个差值的符号就满足对比函数输出接口的要求。

3.1 最小节点和最大节点

这里所谓的最小节点和最大节点是指键值最小和键值最大的连个节点。根据二叉搜索树的性质，不难证明树中最左边的节点就是其最小节点，最右边的节点则是其最大节点。 下面分别是求取树中最小节点和最大节点的函数，我们从根节点开始分别沿左子树或者右子树依次向下搜索，直到空节点为止。

struct btree_node *btree_minimum(struct btree_node *root) {
    if (NULL == root)
        return NULL;
    while (NULL != root->left)
        root = root->left;
    return root;
}

struct btree_node * btree_maximum(struct btree_node *root) {
    if (NULL == root)
        return NULL;
    while (NULL != root->right)
        root = root->right;
    return root;
}

3.2 前驱和后继

对于二叉搜索树中的一个节点而言，它的前驱是指第一个键值小于该节点键值的节点，后继则是第一个大于的节点。实际上如果我们对目标二叉树进行中序遍历，就可以从小到大的访问数中的每个元素。 所以前驱和后继可以说是中序遍历条件下，当前节点的前一个节点和后一个节点。

下面左右两个函数分别用于求取目标节点的前驱和后继。若求取给定节点的前驱，有两种情况需要讨论。如果给定节点存在左子树，那么它的前驱就是左子树中的最大节点。 否则，我们需要沿着左子树依次向上查找到第一个非左子树的祖先节点，该节点就是我们要找的前驱。 对于第二种情况的讨论我们可以换个思路，假设节点y是目标节点node的前驱，那么反过来，node是y的后继，又由于node是y的后代，这意味着node一定在y的右子树上， 所以node就是y的右子树的最小节点。我们反转求取最小节点的操作过程，就可以得到node的前驱y。

struct btree_node *btree_predecessor(struct btree_node *node) {
    if (NULL != node->left)
        return btree_maximum(node->left);
    struct btree_node *y = node->parent;
    while ((NULL != y) && (node == y->left)) {
        node = y;
        y = y->parent;
    }
    return y;
}

struct btree_node *btree_successor(struct btree_node *node) {
    if (NULL != node->right)
        return btree_minimum(node->right);
    struct btree_node *y = node->parent;
    while ((NULL != y) && (node == y->right)) {
        node = y;
        y = y->parent;
    }
    return y;
}

求取后继的操作与前驱的操作是对称的，我们只需要将左改为右，求取最大节点改为最小节点，就可以得到上面右边所示的求取后继的函数。

3.3 插入、查找、删除

二叉搜索树是一个动态的数据结构，我们需要提供插入和删除元素的接口，查找操作则是二叉搜索树的基本操作之一。下面是插入操作的接口实现， 它有三个参数，其中root是插入目标搜索树根节点，node是将要插入的节点，compare则是本节一开始提到的对比函数。如果成功执行了插入操作，将返回插入的节点node， 否则返回空指针。在函数的一开始，我们需要确认目标搜索树存在。

        struct btree_node * btree_insert(struct btree_node *root, struct btree_node *node, btree_compare_fun compare) {
            if (NULL == root)
                return NULL;

接着我们定义了两个临时变量x和y，用于定位插入节点的位置。在while循环中，我们从根节点开始依次与目标节点对比。 如果目标节点小于当前节点，就向下查找左子树，否则就查找右子树，直到访问到一个空节点为止。x指示当前节点，y指示了当前节点的父节点。

            struct btree_node *y = NULL;
            struct btree_node *x = root;
            while (NULL != x) {
                y = x;
                if (compare(node, x) < 0)
                    x = x->left;
                else
                    x = x->right;
            }

在循环结束之后，y就记录了插入操作之后目标节点的父节点。我们需要再次对比目标节点和y，以确定目标节点应当放置在y的左子树上还是右子树上。最后返回退出。 如上面的右图所示，我们将要插入一个键值为13的节点，依次对比了12、18、15之后，发现应当将之插入到15的左子树上。

            node->parent = y;
            if (compare(node, y) < 0)
                y->left = node;
            else
                y->right = node;
            return node;
        }

本质上，上述的插入操作就是先执行一次查找操作之后，再将目标节点挂到二叉树上。下面的函数具体给出了一个二叉搜索树的查找接口，同样的它有三个参数， 其中root是目标二叉搜索树的根节点，嵌入node的数据对象的键值则是我们想要查找的数据，compare则是用户提供的对比函数。在函数中，我们从根节点开始搜索， 如果键值小于目标值则搜索左子树，如果大于目标值则搜索右子树，直到两者键值相等或者搜索到叶子节点为止。

        struct btree_node *btree_find(struct btree_node *root, struct btree_node *node, btree_compare_fun compare) {
            while (NULL != root) {
                int com = compare(node, root);
                if (com < 0)
                    root = root->left;
                else if (com > 0)
                    root = root->right;
                else
                    break;
            }
            return root;
        }

有时我们还需要把一个节点从树中移除，有三种情况需要处理：

• 如果目标节点是一个叶子节点，我们直接用空节点代替该节点。
• 如果目标节点只有一个孩子，我们就用它的孩子来代替该节点。
• 如果目标节点有两个孩子，我们就用该节点的后继来代替该节点。

对于前两种情况我们可以很容易理解，它们所对应的操作不会改变二叉搜索树的特性。对于第三种情况，我们可以断定目标节点的后继的键值，一定大于其左子树的所有节点。 而其后继一定是其右子树中的最小节点，所以用它来代替目标节点则一定能够保证变换后右子树的键值特性。

下面是移除节点的函数实现，它有两个参数，其中root是一个指向二叉树根节点的二重指针，node则是待删除的节点。在调用该函数的时候，用户需要保证node一定是root所指二叉树中的节点。 有时待移除的节点可能也是根节点，此时移除node之后树的根节点就会变化，所以这里root是一个二重指针用于记录移除节点之后二叉树的根。

        struct btree_node * btree_remove(struct btree_node **root, struct btree_node *node) {

针对第二种情况，我们分别检测左子树和右子树是否存在，如果不存在就用另一个子树替代该节点。这两个判定条件同时也包含了第一种情况。如果目标节点是一个叶子节点， 意味着左右两个子树都是空。如果左子树为空，我们就直接用右子树替代之，而对于叶子节点而言替代的右子树实际上就是一个空节点。

            if (NULL == node->left)
                btree_replace_subtree(root, node, node->right);
            else if (NULL == node->right)
                btree_replace_subtree(root, node, node->left);

如果左右两个孩子都存在，就对应着第三种情况，此时我们需要用目标节点的后继来替代该节点。目标节点的后继就是其右子树的最小节点，这里通过调用函数btree_minimum来获得，并用指针n来标记。 最小节点有一个特性就是它的左子树一定为空，所以我们需要对其右子树做一些特殊的处理。如果n的父节点不是要删除的对象，那么我们就需要通过用n的右子树替代n，先将n从二叉树中移除， 再用之替代目标节点。如果n的父节点就是node，我们就可以直接用以n为根节点的子树替代删除对象。

            else {
                struct btree_node *n = btree_minimum(node->right);
                if (node != n->parent) {
                    btree_replace_subtree(root, n, n->right);
                    n->right = node->right;
                    n->right->parent = n;
                }
                btree_replace_subtree(root, node, n);
                n->left = node->left;
                n->left->parent = n;
            }
        }

在移除节点的过程中，我们反复调用了一个btree_replace_subtree的函数，该函数用以v为根节点的二叉树来替换u节点。它还有一个二重指针root用于指示u所在的二叉树根节点， 这里使用二重指针也是考虑到节点u可能就是一个根节点，以至于该函数调用结束后能够通过root反应这种根节点变换。在函数的一开始，我们检查u不能是空节点，否则没有意义。

        void btree_replace_subtree(struct btree_node **root, struct btree_node *u, struct btree_node *v) {
            if (NULL == u)
                return;

我们依次查看u的父节点是否为空，是其父节点的左子树还是右子树，来调整根节点和父节点。

            if (NULL == u->parent && NULL != root)
                *root = v;
            else if (u == u->parent->left)
                u->parent->left = v;
            else
                u->parent->right = v;

最后更新替换子树根节点的父节点。

            if (NULL != v)
                v->parent = u->parent;
        }

4. 完

本文中，我们定义了一套C语言形式的二叉树接口。介绍了如何定义和构建一棵二叉树，然后借助栈结构实现了非递归形式的先序、中序和后序遍历操作。最后，我们还提供了构建二叉搜索树的接口， 实现了求取树中最小节点和最大节点，指定节点的前驱和后继，插入、查找、删除指定节点的方法。