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条)

报告相同问题?

悬赏问题

  • ¥15 安装GroudingDINO RuntimeError: Error compiling objects for extension
  • ¥15 关于推送项目到github的问题
  • ¥15 急!C++指针编写相关的问题
  • ¥15 kerberos身份认证配置问题
  • ¥30 用python写一个多签情况下波场的代理资源和回收资源
  • ¥15 怎么在matlab中输出显示泵的流量-扬程和管路损失与流量均在一个表格里
  • ¥15 matlab学期例题代码答疑
  • ¥15 在线手电筒追加按钮JS
  • ¥15 调用函数时,无关变量的改变引起函数值的改变
  • ¥15 xy坐标转化为经纬度坐标