qq_43412960
2020-04-25 08:17
采纳率: 50%
浏览 144

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

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

  • 写回答
  • 好问题 提建议
  • 追加酬金
  • 关注问题
  • 邀请回答

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;
    }
    
    
    评论
    解决 无用 1
    打赏 举报
查看更多回答(3条)

相关推荐 更多相似问题