二叉树非递归中序遍历，思路是啥呢？
我想敲出代码来，但是想不通这种分叉的东西怎么写，也想不透怎么把根节点的位置顺序体现出来
浏览 142
已采纳
这是一个关于数据结构二叉树的遍历问题
- 写回答
- 赞 踩
- 关注问题
- 收藏
- 分享
- 邀请回答
微信扫一扫4条回答 默认 最新
- threenewbee 2020-04-25 14:30已采纳
拿 https://blog.csdn.net/qq_44556821/article/details/96423326 这个程序改了下。
#include <stack> #include <iostream> using namespace std; class TreeNode { private: char name_; public: int State;//状态值 TreeNode* leftNode; TreeNode* rightNode; public: TreeNode(char a):name_(a) { State = 0; leftNode = NULL; rightNode = NULL; } char getName() { return name_; } }; void MiddlePush(TreeNode& TreeTop); int main(){ //初始化树 TreeNode node1('A'); TreeNode node2('B'); TreeNode node3('C'); TreeNode node4('D'); TreeNode node5('E'); TreeNode node6('F'); TreeNode node7('G'); TreeNode node8('H'); TreeNode node9('I'); node1.leftNode = &node2; node1.rightNode = &node3; node2.leftNode = &node4; node2.rightNode = &node5; node3.rightNode = &node6; node4.leftNode = &node7; node4.rightNode = &node8; node6.leftNode = &node9; MiddlePush(node1); } void MiddlePush(TreeNode& TreeTop) { stack<TreeNode> STN; STN.push(TreeTop); while (STN.size()) { TreeNode Top = STN.top(); if (!Top.State) { STN.pop(); Top.State = 1; STN.push(Top); if (Top.rightNode) { STN.pop(); STN.push(*Top.rightNode); STN.push(Top); } if (Top.leftNode) { STN.push(*Top.leftNode); } } else { cout << Top.getName() << ends; STN.pop(); } } cout << endl; }已采纳该答案赞 踩 打赏 评论分享 - 502203305 2020-04-25 09:24
用栈呗，递归就是有记录的栈，你也模拟栈记录下来就行了。给你写个伪代码，具体细节自己实现。
struct Tree { int data; struct Tree * left,right; }; void midvisit(struct Tree * node) { stack<struct Tree*> treestack; struct Tree * temp = node; while (1) { if(NULL != temp) { treestack.push(temp); temp = temp->left; } else if(!treestack.empty()) { temp = treestack.pop(); cout>> temp->data; temp = temp -> right; } else { break; } } }赞 踩 打赏 评论分享 - 野草梦 2020-04-25 14:15
直接给你答案效果不大，推荐一本书
严蔚敏《数据结构》
里面有很详细的讲解。
自己学，自己领悟出来的更为深刻。赞 踩 打赏 评论分享 - noobmantest 2020-04-25 16:06
给你直接推荐一个视频吧，我觉得几行文字 可能给你讲不清楚。https://www.bilibili.com/video/BV1b7411N798?p=27 中序非递归代码可以直接从这个视频的11分钟开始看。
赞 踩 打赏 评论分享