qq_43412960 2020-04-25 08:17 采纳率: 78.6%
浏览 148
已采纳

这是一个关于数据结构二叉树的遍历问题

二叉树非递归中序遍历,思路是啥呢?
我想敲出代码来,但是想不通这种分叉的东西怎么写,也想不透怎么把根节点的位置顺序体现出来

  • 写回答

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;
    }
    
    
    本回答被题主选为最佳回答 , 对您是否有帮助呢?
    评论
查看更多回答(3条)

报告相同问题?

悬赏问题

  • ¥40 求一款能支持ios15以上的屏蔽越狱插件。比较好用的
  • ¥15 C++ QT对比内存字符(形式不定)
  • ¥30 C++第三方库libiconv 远程安装协助
  • ¥15 https://github.com/youlaitech/vue3-element-admin/blob/master/src/store/modules/user.ts 这2句代码如何理解
  • ¥15 duilib开发文本字串超过长度显示
  • ¥20 mysql的.ibd文件为啥那么多
  • ¥15 C++中采用栈和BFS算法求解迷宫问题
  • ¥15 关于#java#的问题:这是跳转失败出现的界面这是哪个出现问题的servlet(开发工具-ide)
  • ¥15 EBS R12费用采购跨月冲销
  • ¥15 python中用mplfinance如何做到多股同列?