「树」专题 1：树与递归

专题 12：树

发布日期: 2017-11-16

树是理解「递归」和「分治」算法的很好的数据结构；
很多高级数据结构都是从「树」来的。

我们开始介绍「二叉树和递归」。递归，是使用计算机解决问题的一种重要的思考方式。而二叉树由于其天然的递归结构，使得基于二叉树的算法，均拥有着递归性质。使用二叉树，是研究学习递归算法的最佳入门方式。在这一章里，我们就来看一看二叉树中的递归算法。

在前面知识的学习中，我们看到了在基础算法以及系统设计中都用到了递归。深度优先遍历中也用到了递归。从这一部分开始，我们从另一个视角看递归。

从二叉树的角度看递归

二叉树天然具有递归的性质。二叉树的定义就是用二叉树定义二叉树。对于二叉树的定义来说，应该补充一点：空是一棵二叉树。

下面，我们来观察一个二叉树的前序遍历的递归方法。

Java 代码：

public void preorder(TreeNode node){
    if(node != null){
        System.out.print(node.val);
        preorder(node.left);
        preorder(node.right);
    } 
}

注意：这里 System.out.print(node.val); 这一行代码表示“处理这个结点的逻辑”。

在这里，我们先强调编写递归函数的第 1 个注意事项：首先明确这个函数要表达的任务（逻辑），明确参数的定义和返回值的意义。

接下来，我们将上面的代码改造一下。

Java 代码：

public void preorder(TreeNode node){

    // 先写递归终止条件
    if(node == null){
        return;
    } 

    // 再写递归过程
    System.out.print(node.val);
    preorder(node.left);
    preorder(node.right);
}

其实这样的写法更像递归结构，因为对于我们定义的每一个递归函数来说，应该包含下面两个部分：1、递归终止条件；2、设立递归过程，定义清楚函数的语义。

这就是我们编写一个递归函数应该注意的第 2 件事情。

接下来，我们再看一个方法：在一个二叉树中查看是否存在一个键值。写这个递归方法的步骤：想想（1）递归终止条件是什么？（2）递归过程是什么？参数 Node node 是什么意思？我们这里定义的参数 Node 对象，是在以 node 为根结点的二叉树中寻找指定的 key。于是，我们的逻辑是：如果 node 本身不是我们要找的结点的话，我们继续在 node 的左孩子和右孩子中继续查找。

Java 代码：

public boolean contain(Node node, int key) {
    // 首先我们要处理递归到底的情况
    if (node == null) {
        return false;
    }

    if (key == node.key) {
        return true;
    } 

    if (contain(node.left, key) || contain(node.right, key) {
        return true;
    } 
    return false;
}