在学习分治算法的时候,分治算法经常要用到的就是递归了,但是嵌套递归让我感觉很迷茫,在学习树的遍历的时候,就花了很长时间看明白树的遍历方式.
并且自己用栈实现了树的非递归方式,如果读者也对嵌套递归表示茫然的话,非常建议先去看一下上面的知识.
这里我要讲的虽然是理解多重嵌套, 更重要的是理解分治算法,设计合适的递归方法来解决此类问题.
回到正题,树的遍历可以说是非常好的分治算法的例子了.
一颗树,有左子树和右子树,
左子树有 左子树和右子树
右子树有 左子树和右子树
左子树的左子树有 左子树和右子树..
......
我们来看一下递归遍历树的语句
void preorderTraverse(Tree tree){
if(tree==null)return; //这是递归终止条件 ,递归终止意味返回上一级递归, 语句1
visit(tree); //语句2
preorderTraverse(tree.leftchild);//递归遍历左子树 语句3
preorderTraverse(tree.rightchild);//语句4
}
先来分析一下树的前序遍历
设当前为(递归一)
- 根节点进入
- 语句1: 根不为空 //设当前程序为递归1
- 语句2:访问根节点 [根]
- 语句3:
递归2:遍历当前树的左子树 ,即A
(递归一(递归二)) - A节点进入
- 语句1: A不为空
- 语句2:访问A [根 A]
- 语句3:
递归3:遍历当前树的左子树 ,即B
(递归一(递归二(递归三))) - B节点进入
- 语句1: B不为空
- 语句2:访问B节点[根 A B]
- 语句3:
递归4:遍历当前树的左子树 ,即D
(递归一(递归二(递归三(递归四)))) - D节点进入
- 语句1: D不为空
- 语句2:访问D节点 [根 A B D]
- 语句3:
递归5:遍历当前树的左子树 ,即E
(递归一(递归二(递归三(递归四(递归五))))) - E节点进入
- 语句1: E不为空
- 语句2:访问E节点 [根 A B D E]
- 语句3:
递归6:遍历当前树的左子树 ,为NULL
(递归一(递归二(递归三(递归四(递归五(递归六))))) - NULL节点进入
- 语句1:NULL==NULL 返回 递归6结束 注意递归向上返回一级,,顺序执行下一句,
(递归一(递归二(递归三(递归四(递归五)))) - 此时返回到递归5,语句三结束, 此时执行的是递归五的最后一个语句
- 执行语句4,现在系统已经把五的信息加载进来了, 此时当前树是E
递归6遍历当前
树的右子树 NULL
(递归一(递归二(递归三(递归四(递归五{-递归六-}))))) - NULL节点进入,返回 向上返回一级
- 递归6结束
(递归一(递归二(递归三(递归四(递归五))))) - 由于递归五执行完毕,所以退出到 递归四
(递归一(递归二(递归三(递归四)))) - 当前节点是D,语句3结束
- 语句4 :'递归5' 递归遍历当前节点右子树 F 注意此时又是执行了当前递归四的最后一句
(递归一(递归二(递归三(递归四 {-递归五-} )))) - 语句1: F不为空
- 语句2:访问F节点 [根 A B D E F ]
- 语句3:
递归6:遍历当前树的左子树 ,为NULL
(递归一(递归二(递归三(递归四{- 递归五(递归六) -} )))) - NULL节点进入
- 语句1:NULL==NULL 返回 递归6结束 注意递归向上返回一级
(递归一(递归二(递归三(递归四(递归五)))))
语句四 '递归六' 访问当前节点右子树NULL注意此时执行开始执行了递归五的最后一句
(递归一(递归二(递归三(递归四{-递归五{-递归六-} -})))) - NULL=NULL 返回 递归六结束,同理 递归五最后一句执行完毕,递归四的最后一句执行完毕 ,直接推到递归三
(递归一(递归二(递归三)))
剩下的读者自己琢磨吧
我用{- -}区分了第二个递归,可以看到执行 {- -} 递归后,出来直接跳到最外边,因为{- -}内的递归是最后一句
image.png
可以看到当前是递归四,栈中保存了四个递归
点击递归三,你会看他递归三当前执行的语句是淡蓝色的 theFirstTraversal(root.getRightNode);也是是当前递归出栈会从这里开始向下执行.
这就是递归的机制,
用树的遍历来理解多重嵌套的递归,
同样,在设计分治算法的时候,用树了构造自己的算法是不是容易些呢? 这也是我准备做的事情.