本文对常用数据结构中的二叉树、二叉搜索树、平衡树进行简单介绍。

1 树

       树的出现一部分是为了解决数组和链表的性能问题，因为数组和链表的操作复杂度普遍在O(N)甚至是O(N²)；一部分是现实应用中对该数据结构的需要，比如操作系统的目录结构，就可以很好的表示成树。

       一棵树是一些结点的集合，这个集合要么为空，如果不为空则具备如下特点：

       1） 有且只有一个根结点root；
       2） root具有任意多个（含0个）与其相连的结点，并且每个结点都是一棵树的根结点。

       与root相连的结点称为root的子结点，root是其子结点的父结点，以root的子结点为根结点的树称为root的子树。从以上树的特点的描述可以看出树的操作多数可以使用递归来实现，因为该描述本身就是一个递归（每棵子树同时是一棵树）。

       下图是一棵树的示意图：

图1.1 树示意图

       在上图中结点1是树的根结点，结点2是结点1的子结点，结点4有两个子结点8和9，结点3没有子结点，在树中没有子结点的结点被称为叶子结点或叶结点。

2 相关概念

       树相关的概念包括根结点、叶结点、父结点、子结点、兄弟结点、堂兄弟结点、祖先结点、层、深度、子树、树的高度等。根结点、叶结点、父结点、子结点、子树前面已经介绍了，这里不再赘述。

       兄弟结点：具有同一个父结点的结点，如上图中的结点2、3、4、5、6；

       堂兄弟结点：其父结点具有同一个父结点的结点，如上图中的结点7、8、10；

       祖先结点：对于任意结点N_i，从根结点root到N_i的路径上所经过的所有结点均称为结点N_i的祖先结点；

       深度：对于任意结点N_i，其深度是从根结点root到N_i的路径的长度，因此根结点的深度为0；

       层：结点N_i的深度即为N_i在树中层数；

       高度：对于任意结点N_i，其高度是从结点N_i到其叶结点的最长路径的长度；

       树的高度：根结点root的高度。

3 二叉树

       二叉树是一种特殊的树，其任意结点至多存在一左一右两个子结点。一棵典型的二叉树如下：

图3.1 二叉树

       根据二叉树结点的情况又有集中比较特殊的二叉树类型，如满二叉树、完全二叉树、二叉搜索树等；其中满二叉树是指除叶结点外的所有结点都有左右两个子结点的二叉树，上图把结点8、9删掉就是一个满二叉树（保留8、9也是满二叉树，只是其更特殊）；完全二叉树是除叶结点外所有结点都有左右两个子结点，且叶结点都在同一层（这一层一定是树的最底层）的二叉树，从描述可知完全二叉树首先是满二叉树，上图就是一棵完全二叉树；二叉搜索树后面还会介绍这里先不表述。

       二叉树作为一种特殊的树，其优点是由于限定了每个结点最多只有两个子结点，因此使用方便，同时由于其天然按照父结点将所有子结点分成了两部分，因此其多数操作的平均时间复杂度是O(logN)。

4 二叉树的遍历

4.1 遍历类型

       根据根结点和子结点在遍历时的顺序二叉树遍历分为三种类型：前序遍历、中序遍历、后序遍历。

       前序遍历：遍历顺序根左右，即对于一个结点来说先遍历其本身，然后遍历左子树，然后是右子树。

       中序遍历：遍历顺序左根右，即对于一个结点来说先遍历左子树，然后遍历其本身，然后是右子树。

       后序遍历：遍历顺序左右根，即对于一个结点来说先遍历左子树，然后遍历右子树，然后是其本身。

       从以上描述可以看出前中后序遍历中的前中后针对的是根结点在遍历中的位置。除了前中后序遍历外，还有一种遍历方式是将二叉树一层一层的从左到右遍历，这种遍历称为层次遍历。

       对于一棵如下图的树：

图4.1 二叉树遍历

       其各种遍历的结果为：

       前序遍历：1245367

       中序遍历：4251637

       后序遍历：4526731

       层次遍历：1234567

4.2 代码实现

       要实现二叉树的遍历，我们先来定义二叉树结点对应的数据结构，从二叉树的定义看，结点具有一个结点值、一个左子结点、一个右子结点，其中左右子结点可能为空，因此我们定义结点的结构如下：

Java：

public class TreeNode {
    public int val;
    public TreeNode left;
    public TreeNode right;

    public TreeNode(int val) {
        this.val = val;
    }
}

       PS：为了演示方便这里所有的成员变量和属性都定义成了public的，实际应用中不建议这样使用，其可见性以及是否需要getter/setter请根据实际情况设置。

C：

struct TreeNode {
    int val;
    struct TreeNode* left;
    struct TreeNode* right;
};

       从树的定义及三种遍历类型的定义来看，很显然树的前中后序遍历适合使用递归来实现，而层次遍历从描述来看就很适合使用广度优先搜索来实现，如下是代码示例。

4.2.1 Java代码

    /**
     * 前序遍历
     * @param root
     */
    public void preorderTraversal(TreeNode root) {
        if (root == null) {
            return;
        }
        System.out.print(root.val + ", ");
        preorderTraversal(root.left);
        preorderTraversal(root.right);
    }

    /**
     * 中序遍历
     * @param root
     */
    public void inorderTraversal(TreeNode root) {
        if (root == null) {
            return;
        }
        inorderTraversal(root.left);
        System.out.print(root.val + ", ");
        inorderTraversal(root.right);
    }

    /**
     * 后序遍历
     * @param root
     */
    public void postorderTraversal(TreeNode root) {
        if (root == null) {
            return;
        }
        postorderTraversal(root.left);
        postorderTraversal(root.right);
        System.out.print(root.val + ", ");
    }

    /**
     * 层次遍历
     * @param root
     */
    public void levelOrderTraversal(TreeNode root) {
        if (root == null) {
            return;
        }

        Queue<TreeNode> queue = new ArrayDeque<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                TreeNode node = queue.poll();
                System.out.print(node.val + ", ");
                if (node.left != null) {
                    queue.offer(node.left);
                }
                if (node.right != null) {
                    queue.offer(node.right);
                }
            }
        }
    }

4.2.2 C代码

#include <queue.h>

/**
 * 功能描述
 * @author Leander
 * @version [版本号, 2019/11/6]
 * @date 2019/11/6
 * @see []
 * Copyright (c) 2019 Leander All rights reserved.
 */

/**
 * 前序遍历
 * @param root
 */
void preorderTraversal(struct TreeNode* root) {
    if (root == NULL) {
        return;
    }
    printf("%d, ", root->val);
    preorderTraversal(root->left);
    preorderTraversal(root->right);
}

/**
 * 中序遍历
 * @param root
 */
void inorderTraversal(struct TreeNode* root) {
    if (root == NULL) {
        return;
    }
    inorderTraversal(root->left);
    printf("%d, ", root->val);
    inorderTraversal(root->right);
}

/**
 * 后序遍历
 * @param root
 */
void postorderTraversal(struct TreeNode* root) {
    if (root == NULL) {
        return;
    }
    postorderTraversal(root->left);
    postorderTraversal(root->right);
    printf("%d, ", root->val);
}

typedef struct item {
    struct TreeNode* node;
    struct item* prev;
    struct item* next;
} Item;

Item* queue = NULL;

void levelOrderTraversal(struct TreeNode* root) {
    if (root == NULL) {
        return;
    }
    Item* item = (Item*) malloc(sizeof(Item));
    item->node = root;
    QUEUE_OFFER(queue, item);

    while (!QUEUE_EMPTY(queue)) {
        int size;
        Item* tmp;
        QUEUE_COUNT(queue, tmp, size);
        for (int i = 0; i < size; ++i) {
            QUEUE_POLL(queue, tmp);
            struct TreeNode* node = tmp->node;
            printf("%d, ", node->val);
            if (node->left != NULL) {
                item = (Item*) malloc(sizeof(Item));
                item->node = node->left;
                QUEUE_OFFER(queue, item);
            }
            if (node->right != NULL) {
                item = (Item*) malloc(sizeof(Item));
                item->node = node->right;
                QUEUE_OFFER(queue, item);
            }
        }
    }
    printf("\n");
}

       其中用到的queue.h，这个是用C实现的简单队列，后附到附录中，这个简单队列实现了队列的入队、出队、计数、判空、获取队首元素等操作的宏。

5 二叉搜索树（BST）

       二叉搜索树（BST）是一种特殊的二叉树，对于任意结点N满足如下性质：X的左子树中所有结点的值均小于X的值，X右子树中所有结点的值均大于X的值。如下是一颗典型的二叉搜索树：

图5.1 二叉搜索树示意图

       根据二叉搜索树的性质可以得出，如果按照中序遍历的方式对其进行遍历，可以得到一个排序的序列；这是二叉搜索树的一个重要特点，据此可以实现平均O(logN)的搜索，对于要搜索的任何值V，如果结点X的值大于V，则搜索N的左子树，如果结点X的值小于V，则搜索X的右子树，直到结点的值等于V。

       二叉搜索树的基本操作跟二叉树是一样的，只是其具有可以排序的特征，因此不再对其遍历的等操作做过多介绍。

6 平衡树（AVL）

       二叉搜索树的平均操作时间为O(logN)，但是存在最坏情况是O(N)的可能，比如对于如下的二叉搜索树，其操作时间复杂度即为O(N)，该二叉搜索树是一种很糟糕的二叉搜索树，因其左子树每个节点都只有左子结点，右子树每个结点都只有左子结点，因此去查找的时候需要进行N/2次操作才行。还有比在这更坏的情况即根结点也只有左子树或右子树，比如下图将结点1、2、3删除。

图6.1 糟糕的二叉搜索树

       这样在最坏情况下二叉搜索树的时间复杂度表现较差，于是平衡树就产生了，平衡树通过对二叉搜索树进行一定的限制，能够确保其最坏情况下也是O(logN)的时间复杂度。如果一棵二叉搜索树满足如下条件，则其是一棵平衡树：树的每个结点的左右子树的高度差最大为1。

7 附录

7.1 求二叉树的高度

Java代码：

    public int depth(TreeNode root) {
        if (root == null) {
            return 0;
        }

        return 1 + Math.max(depth(root.left), depth(root.right));
    }

C代码：

int depth(struct TreeNode* root) {
    if (root == NULL) {
        return 0;
    }

    int leftDepth = depth(root->left);
    int rightDepth = depth(root->right);
    return 1 + (leftDepth > rightDepth ? leftDepth : rightDepth);
}

7.2 C队列简单实现

/**
 * 功能描述
 * @author Leander
 * @version [版本号, 2019/11/6]
 * @date 2019/11/6
 * @see []
 * Copyright (c) 2019 Leander All rights reserved.
 */
#include "stdbool.h"

#ifndef QUEUE_H
#define QUEUE_H

#define QUEUE_PEEK(head) (head)
#define QUEUE_EMPTY(head) ((head) == NULL)
#define QUEUE_OFFER(head, add)      \
do {                                \
    if ((head) != NULL) {           \
        (add)->prev = (head)->prev; \
        (head)->prev->next = (add); \
        (head)->prev = (add);       \
        (add)->next = NULL;         \
    } else {                        \
        (head) = (add);             \
        (head)->prev = (head);      \
        (head)->next = NULL;        \
    }                               \
} while (false)

#define QUEUE_POLL(head, result)        \
do {                                    \
    (result) = (head);                  \
    (head) = (head)->next;              \
    if ((head) != NULL) {               \
        (head)->prev = (result)->prev;  \
    }                                   \
    (result)->prev = NULL;              \
    (result)->next = NULL;              \
} while (false)

#define QUEUE_COUNT(head,el,counter)    \
do {                                    \
    (counter) = 0;                      \
    for ((el) = (head); (el) != NULL;(el) = (el)->next) {   \
        (counter)++;                                        \
    }                                                       \
} while (false)

#endif // !QUEUE_H