看到一个非递归交换一个二叉树的左右孩子的位置，于是想实现之，才发现非递归的先中后序遍历都忘记了……于是杂七杂八的写了一些，抄抄资料就实现了，然后实现非递归交换两个孩子的位置还是相当容易的。先直接上代码吧，其实这东西还是得自己写写过一遍的，印象才会更加深刻：

#include 
       
        #include 
        
         #include 
         
          #include 
          
           using std::cout;using std::endl;using std::cin;using std::ifstream;using std::stack;class BTree{private:    struct Node    {        Node* lChild;        char data;        Node* rChild;    };    Node* m_pRoot;        //pointer to tree root    void addNode(ifstream& fin, Node** ppNode);    void showNode(Node* pNode);        //递归中序遍历    void switchLRChild(Node* pNode);public:    explicit BTree(void) { m_pRoot = nullptr;}    void create(void);    void show(void);        //这是中序遍历    void switchLR(void);    void switchLR2(void);        //非递归实现交换节点的左右孩子    void preOrder(void);        //写着玩的非递归先序遍历    void inOrder(void);        //写着玩的非递归中序遍历    void aftOrder(void);        //写着玩的非递归后序遍历};void BTree::create(void){    ifstream fin("src.txt");    if(!fin)        cout<<"can not open the file!\n";    addNode(fin, &m_pRoot);}void BTree::addNode(ifstream& fin, Node** ppNode){    /* 手工读取    cout<<"Input node's value, blank to end:";    char ch;    cin.get(ch);    if(ch == '\n')        return;    while(cin.get() != '\n')        continue;    (*ppNode) = new Node;    (*ppNode)->data = ch;    (*ppNode)->lChild = nullptr;    (*ppNode)->rChild = nullptr;    cout<<"add left child:"<
           
            lChild));    cout<<"add right child:"<
            
             rChild));*/ //文件读取 std::string temp; getline(fin, temp); //这个函数以换行为标志读取一行，但是会丢弃换行符 if(temp.empty()) return; (*ppNode) = new Node; (*ppNode)->data = temp[0]; (*ppNode)->lChild = nullptr; (*ppNode)->rChild = nullptr; addNode(fin, &((*ppNode)->lChild)); addNode(fin, &((*ppNode)->rChild));}void BTree::show(void){ if(m_pRoot) { showNode(m_pRoot); cout<
             
              lChild); cout<
              
               data<<" "; showNode(pNode->rChild); } else { return; }}void BTree::switchLR(void){ switchLRChild(m_pRoot);}void BTree::switchLRChild(Node* pNode){ if (pNode && (pNode->lChild != nullptr || pNode->rChild != nullptr)) { Node* temp = pNode->lChild; pNode->lChild = pNode->rChild; pNode->rChild = temp; switchLRChild(pNode->lChild); switchLRChild(pNode->rChild); }}void BTree::switchLR2(void){ struct BNode { Node* pToNode; bool isFirst; }; BNode p = {m_pRoot, true}; stack
               
                 myStack; while(p.pToNode || !myStack.empty()) { while(p.pToNode) { myStack.push(p); p.pToNode = p.pToNode->lChild; p.isFirst = true; //重置 } p = myStack.top(); myStack.pop(); if (p.isFirst) { p.isFirst = false; myStack.push(p); p.pToNode = p.pToNode->rChild; p.isFirst = true; } else //节点第二次在栈顶了，那么此时交换它的左右节点 { Node* temp = p.pToNode->lChild; p.pToNode->lChild = p.pToNode->rChild; p.pToNode->rChild = temp; p.pToNode = nullptr; } } /* 这个和非递归的后序遍历的原理一样：先直接沿着左侧一路向下，把遇到的每个节点都入栈，直到没有了。 然后呢对于栈顶的节点，如果它是第一个出现在栈顶，那么还没有对它的右子树进行处理，所以切换到它的右子树 进行同样的处理。当它的右子树处理完了之后这个节点再次出现在栈顶，这个时候就可以交换它的左右子树了， 并且它的左右子树都已经完成了交换，这不就是递归吗？只不过是循环实现的就是啦。 */}void BTree::preOrder(void){ stack
                
                  myStack; Node* p = m_pRoot; while(p != nullptr || !myStack.empty()) { while(p != nullptr) //写的时候先写内层循环，再写外层循环 { cout<
                 
                  data<<" "; //先访问数据 myStack.push(p); //指针入栈 p = p->lChild; //指向左孩子 } if (!myStack.empty()) //到这里指针p肯定是空了 { p = myStack.top(); //节点出现在栈顶时，此节点已经访问过，并且其左孩子也被访问过，只有其右孩子还没有 myStack.pop(); p = p->rChild; } } cout<
                  
                    myStack; Node* p = m_pRoot; while(p || !myStack.empty()) //外层循环相当于实现了递归的作用 { while(p) { myStack.push(p); p = p->lChild; } if (!myStack.empty()) { p = myStack.top(); //节点出现在栈顶，则其左孩子已经被访问过，自己和右孩子都没有被访问过 myStack.pop(); cout<
                   
                    data<<" "; //访问数据 p = p->rChild; //对右子树也用同样的方法，这不是递归的思想吗？ } } cout<
                    
                      myStack; while(p.pToNode || !myStack.empty()) { while(p.pToNode) { myStack.push(p); p.pToNode = p.pToNode->lChild; p.isFirst = true; //注意这里每次切换的时候都要设置true或false，因为就那么一个变量，虽然放到栈里面都有true或false } if (!myStack.empty()) { p = myStack.top(); myStack.pop(); if (p.isFirst) //是第一次出现在栈顶 { p.isFirst = false; myStack.push(p); p.pToNode = p.pToNode->rChild; p.isFirst = true; } else //第二次出现在栈顶了 { cout<
                     
                      data<<" "; p.pToNode = nullptr; //这里其实就是让程序直接运行到下次出栈 } } } cout<
                     
                    
                   
                  
                 
                
               
              
             
            
           
          
         
        
       

1 C 2 T 3 G 4 V 5  6  7  8 W 9 10 11 M12 S13 14 15 N

注意：上面的第二份是数据，即先序遍历这个树所经过的节点顺序，总共17行的，但这里只有15行，不关我的事啊，我都Ctrl+A、Ctrl+C了，后面两行是是两个换行符，用来表示读入树结束。

---

---

---

　

　　首先是实现它的非递归的三种遍历啦，这个都是抄袭别人的啦，见附，这位博主确实写得好，排版还很漂亮，这个有加分的。

　　二叉树的非递归先序和中序遍历算容易的了，我用自己的语言写出来：从树根沿着左边的方向一直下，并入栈，如果是先序遍历的话还要在入栈前先访问一下；到了最左下角了，栈顶出栈，这是大概意思就是刚出栈节点的左孩子已经访问完了，看你怎么办。如果是中序遍历，这时候当然要访问它的数据啦，然后接着看刚出栈节点的右孩子，其实这里不就是递归的思想吗？直接对它的的右孩子同样处理不就可以了吗？

　　上面的思路已经很清晰了，转化为程序呢？先一个循环到最左下角，然后根据情况处理栈顶的东西。然后让指针指向栈顶的右孩子“递归”处理，这个“递归”还不能用递归，那也用循环代替啦：

//先序非递归大致结构：指针P = 树根；while (还没结束){    while(还没到最左下角)    {        访问P->数据；        P入栈；        p = p的左孩子；    }    p = 出栈；    p = p ->右孩子；        //然后继续循环啦}//中序非递归大致结构指针P = 树根；while (还没结束){    while(还没到最左下角)    {        P入栈；        p = p的左孩子；    }    p = 出栈；    访问P->数据；    p = p ->右孩子；        //然后继续循环啦}

　　下面是非递归实现后序遍历，详细的解释源代码中有注释：

//先序非递归大致结构：指针P = 树根；while (还没结束){    while(还没到最左下角)    {        P入栈；        p = p的左孩子；    }    p = 出栈；    if (P指向的节点是第一次出现在栈顶)        //表明它的右孩子还没有搞过，得先等等    {        设置P指向的标志位是访问过；        P入栈；        p = p->右孩子；    }     else    {        访问P->数据；        设置P为空以使下次循环直接让栈顶出栈；    }}

---

---

---

　　

　　这里面最漂亮的是什么呢？就是双重循环实现了类似递归的思想，虽然不是直接的递归调用。因为二叉树本身的定义就是递归定义的嘛，什么根节点左右两个子树，子树都是二叉树什么的，既然定义都是递归的，那么它的很多操作当然可以递归实现啦。

　　第二个问题不用解决了。

附：