完全非遞歸方式解決二叉排序樹向雙向鏈表的轉換(標准注釋）

print?#include <iostream>  
#include <stack>  
using namespace std; 
//節點  
struct node 
{ 
    node *lchild,*rchild; 
    int value; 
}; 
 
//二元查找樹  
class list 
{ 
public: 
    list(); 
    void InOrder_transfer(); 
private: 
    node* root; 
}; 
 
void list::InOrder_transfer() 
{ 
    //如果根節點為空，則返回  
    if(root==NULL) 
        return; 
    //用棧的方式解決非遞歸中序遍歷問題  
    stack<node*> s; 
    bool head=0; 
    node* curr=root; 
    node* post=NULL; 
    while(1){ 
        while(curr){ 
            s.push(curr); 
            curr=curr->lchild; 
        } 
        if(s.empty()) 
            break; 
        curr=s.top(); 
        s.pop(); 
        //其實你想通了會發現，左節點指向的是前一個元素，右節點指向後一個元素  
        curr->lchild=post; 
        if(post) 
            post->rchild=curr; 
        //第一個節點為雙向鏈表頭節點  
        if(NULL==head){ 
            head=1; 
            root=curr; 
        } 
        //原先中序輸出節點的位置  
        //cout<<curr->value<<"  ";  
        post=curr; 
        curr=curr->rchild; 
    } 
    //輸出雙向鏈表節點  
    curr=root; 
    while(curr){ 
        cout<<curr->value<<"  "; 
        curr=curr->rchild; 
    } 
} 
 
list::list() 
{ 
    cout<<"請輸入您要輸入的節點,按'#'退出:"<<endl; 
    int i; 
    //用cin.fail(),cin.bad()判斷也行  
    if(cin>>i==NULL){ 
      cout<<"您的輸入有誤"<<endl; 
      exit(-1); 
    } 
    //創建根節點  
    root=new node; 
    root->value=i; 
    root->lchild=NULL; 
    root->rchild=NULL; 
    //建立兩個臨時節點，p開辟新節點，q為二元查找定位  
    node *p,*q; 
    while(cin>>i!=NULL){ 
        //開辟新節點  
        p=new node; 
        p->value=i; 
        p->lchild=NULL; 
        p->rchild=NULL; 
        //二元查找樹比較從q=root開始，小則轉左，大則轉右，如果有位置就插入  
        q=root; 
        while(1){ 
            //插入節點小於該節點比較值，左節點為空則插入，否則q=q->lchild繼續判斷  
            if(p->value<q->value){ 
                if(q->lchild) 
                    q=q->lchild; 
                else{ 
                    q->lchild=p; 
                    break; 
                } 
            } 
            //插入節點大於該節點比較值，右節點為空則插入，否則q=q->rchild繼續判斷  
            else if(p->value>q->value){ 
                if(q->rchild) 
                    q=q->rchild; 
                else{ 
                    q->rchild=p; 
                    break; 
                } 
            } 
            //如果兩節點相等，直接退出程序(有些暴力）  
            else{ 
                cout<<"node repeated!!"<<endl; 
                exit(-1); 
            } 
        } 
    } 
} 
 
void main() 
{ 
    list test; 
    //在中序遍歷中完成二叉排序樹到雙向鏈表的轉換  
    test.InOrder_transfer();     
    system("pause"); 
}