「树」专题 1:树与递归
- 树是理解「递归」和「分治」算法的很好的数据结构;
- 很多高级数据结构都是从「树」来的。
我们开始介绍「二叉树和递归」。递归,是使用计算机解决问题的一种重要的思考方式。而二叉树由于其天然的递归结构,使得基于二叉树的算法,均拥有着递归性质。使用二叉树,是研究学习递归算法的最佳入门方式。在这一章里,我们就来看一看二叉树中的递归算法。
在前面知识的学习中,我们看到了在基础算法以及系统设计中都用到了递归。深度优先遍历中也用到了递归。从这一部分开始,我们从另一个视角看递归。
从二叉树的角度看递归
二叉树天然具有递归的性质。二叉树的定义就是用二叉树定义二叉树。对于二叉树的定义来说,应该补充一点:空是一棵二叉树。
下面,我们来观察一个二叉树的前序遍历的递归方法。
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;
}
那么,我们可以再想想如何释放以 Node 为根结点的二叉树?