非递归中序遍历非线索二叉树不用栈? 大家都很熟悉

大家都很熟悉用递归和堆栈来实现二叉树的遍历，比如，前序遍历，中序遍历，后序遍历。但Morris 遍历，使用无堆栈，O(1) 空间进行二叉树遍历。它的原理很简单，利用所有叶子结点的右指针，指向其后继结点，组成一个环，在第二次遍历到这个结点时，由于其左子树已经遍历完了，则访问该结点。算法伪码：MorrisInOrder()：while 没有结束如果当前节点没有左后代访问该节点转向右节点否则找到左后代的最右节点，且使最右节点的右指针指向当前节点转向左后代节点C++实现：void bst_morris_inorder(struct bst_node *root) { struct bst_node *p = root, *tmp; while (p) { if (p-\u0026gt;left == NULL) { printf("%d ", p-\u0026gt;key); p = p-\u0026gt;right; } else { tmp = p-\u0026gt;left; while (tmp-\u0026gt;right != NULL \u0026amp;\u0026amp; tmp-\u0026gt;right != p) tmp = tmp-\u0026gt;right; if (tmp-\u0026gt;right == NULL) { tmp-\u0026gt;right = p; p = p-\u0026gt;left; } else { printf("%d ", p-\u0026gt;key); tmp-\u0026gt;right = NULL; p = p-\u0026gt;right; } } } } 转自http://bbs.chinaunix.net/thread-4093579-1-1.html
■网友
Morris中序遍历。网上有完整的代码。自行搜之。

非递归中序遍历非线索二叉树不用栈?

推荐阅读

中国|银行业保险业整体运行稳健更大力度让利实体经济——中国银保监会新闻发言人答记者问

『篮郭先生』于情于理上分析，中超该不该降薪？，世界足坛兴起降薪潮

芒果都市|持A、B证驾驶员快看下你的证！长沙超4000驾驶人逾期未审验

网友|原创于小彤宣布与陈小纭分手？相差5岁姐弟恋终分手，网友表示不意外

环球网|美国确诊人数突破460万的这天，特朗普又去打高尔夫了

#批评#孩子犯错了，如何正确批评？

枕边文化■别担心！迈腾B7音响系统的改装，继续进步

集团|模塑科技：控股股东模塑集团约4000万股解除质押后再质押

当前热映电影票房榜，《飞驰人生2》跌至第二，你看过哪几部？

封麦|黄子华封麦2年后，开始想念说真话的人。｜百家故事

纯锡茶叶罐保养,锡罐茶叶罐简介

西部大英网|| 一组漫画，带你图解扫黑除恶宣传标语，扫黑除恶

锁骨是什么(为啥有人锁骨粗有的细)

味道|学会五香花生（空气炸锅），把餐厅味道搬回家

[整机质量部]整机质量部四月份优秀员工-王奉军

「娜娜细说」而且整容后的她颜值堪比杨颖，美炸了，凤姐居然整容了

『』2020高考：关于助考，聪明的父母会这3招，你学到了吗

行业|酒业这半年｜借力“真年份”，贵州醇是搅局者还是破局者

趣事趣谈：又会死去多少人？这数据简直太吓人了！，地球上每天出生多少人

百万有料|干脆一锅蒸吧，怎么包也包不好