完全非递归方式解决二叉排序树向双向链表的转换(标准注释）

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"); 
}&

补充：软件开发 , C++ ,