首页 > 其他 > 详细

系统栈与二叉树递归调用

时间:2019-09-17 00:07:18      阅读:107      评论:0      收藏:0      [点我收藏+]

递归是计算机科学中一个非常重要的概念,对于斐波那契那种比较简单的递归,分析起来比较容易,但是由于二叉树涉及指针操作,所以模仿下遍历过程中系统栈的情况。
以二叉树中序遍历为例演示:

//二叉树定义
struct TreeNode {
    TreeNode* left;
    TreeNode* right;
    int val;
    TreeNode(int x) :val(x), left(NULL), right(NULL) {}
};

中序遍历的递归实现:
技术分享图片
假设二叉树如图所示:
技术分享图片
其中序遍历序列为\(2413\),可以在VS中用单步调试的方法跟踪相应的变量:
root==NULL(root指向2的左孩子)时,此时的系统栈(将1和2都压栈,因为中序遍历需要先访问左孩子):
技术分享图片
这时if不成立,执行83行的return语句,接着退栈,回到78行,此时的root指向2(因为此时程序已经来到了新的栈顶),并且向这个新栈顶返回了一个空的seq
技术分享图片
接着执行79行(因为这是上一个函数return的,所以不会再一次执行78行),将2存入seq中;
执行80行(root指向4),进而执行78行,root指向4的左孩子,此时的系统栈(很明显可以看到从栈底到栈顶依次存放根结点到当前root结点的路径上的结点):
技术分享图片
同样,执行return语句,退栈,将seq(里面只有2)返回到这一层,这一层的root指向4,接着将4存入seq
到80行,调用inOrder()使得root指向4的右孩子,右孩子为空,所以返回并退栈,root重新指向4,此时80行执行完毕,整个if执行完毕,返回seq并退栈,root返回到了2,以2为根结点的子树中序遍历完毕,系统栈:
技术分享图片
继续执行,return到78行,root指向1,将1存入seq,以此类推,就可以得到整个的遍历序列。

最关键的是:之所以要递归调用inOrder,就是因为现在还不想访问当前的结点(对于中序,要先找到最左边的结点),所以通过递归的方式将当前暂时不想访问的结点压入系统栈,找到了想访问的结点后,访问它并利用退栈操作返回父结点。

系统栈与二叉树递归调用

原文:https://www.cnblogs.com/EIMadrigal/p/11520701.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!