二叉查找树中序遍历非递归解法
2023-03-14 09:44:43 时间
对于树的访问先是从根节点开始进行的,递归左子树和右子树,对于左子树和右子树又可以看成是一棵子树继续递归下去,访问根节点的时候它不是直接处理根节点的而是需要等待它的左子树调用完之后那么才进行处理的,左子树也是一样,当访问到它的左子树的时候也需要等待它的左子树处理完毕才处理自己。
这也就是先访问,后出现的特点,与一种数据结构的特点是类似的,那就是栈,栈也是 "先进后出" 的特点,其实递归来说其实就是一种隐式的栈,所以当我们采用非递归形式的时候我们可以自己声明一个栈,模仿递归求解的过程来进行处理。
代码:
1 import java.util.Stack; 2 import java.util.function.Consumer; 3 4 5 public class BST中序遍历非递归 { 6 private void inorder2(TreeNode<Integer> p, Consumer<Integer> con) { 7 Stack<TreeNode<Integer>> stack = new Stack<>(); 8 TreeNode<Integer> curr = p; 9 // curr不为空或者栈不为空,都可以继续处理 10 while (curr != null || !stack.isEmpty()) {// 没有生产也没有消费,就退出循环了 11 // 沿左支线一撸到底,全部入栈 12 while (curr != null) { 13 stack.push(curr); 14 curr = curr.left; 15 } 16 // 处理栈顶 17 if (!stack.isEmpty()) { 18 TreeNode<Integer> pop = stack.pop(); 19 con.accept(pop.val); 20 // curr指向pop的右子树,继续外层循环 21 curr = pop.right;// 有可能为空,为空,只消费栈中内容,不为空,就要向栈中生产若干内容 22 } 23 } 24 } 25 26 public static class TreeNode<T> { 27 28 public T val; 29 public TreeNode<T> left = null; 30 public TreeNode<T> right = null; 31 public TreeNode<T> parent = null; 32 33 public TreeNode(T val) { 34 this.val = val; 35 } 36 37 } 38 }
相关文章
- 在 Go 里用 CGO?这 7 个问题你要关注!
- 9款优秀的去中心化通讯软件 Matrix 的客户端
- 求职数据分析,项目经验该怎么写
- 在OKR中,我看到了数据驱动业务的未来
- 火山引擎云原生大数据在金融行业的实践
- OpenHarmony富设备移植指南(二)—从postmarketOS获取移植资源
- 《数据成熟度指数》报告:64%的企业领袖认为大多数员工“不懂数据”
- OpenHarmony 小型系统兼容性测试指南
- 肯睿中国(Cloudera):2023年企业数字战略三大趋势预测
- 适用于 Linux 的十大命令行游戏
- GNOME 截图工具的新旧截图方式
- System76 即将推出的 COSMIC 桌面正在酝酿大变化
- 2GB 内存 8GB 存储即可流畅运行,Windows 11 极致精简版系统 Tiny11 发布
- 迎接 ecode:一个即将推出的具有全新图形用户界面框架的现代、轻量级代码编辑器
- loongarch架构介绍(三)—地址翻译
- Go 语言怎么解决编译器错误“err is shadowed during return”?
- 敏捷:可能被开发人员遗忘的部分
- Denodo预测2023年数据管理和分析的未来
- 利用数据推动可持续发展
- 在 Vue3 中实现 React 原生 Hooks(useState、useEffect),深入理解 React Hooks 的