qq_43412960
2020-04-25 08:17
采纳率: 79.1%
浏览 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分钟开始看。

    打赏 评论

相关推荐 更多相似问题