乐趣区

关于数据结构:先序建立二叉链表及先序中序遍历链栈非递归

#include<iostream>
using namespace std;
typedef struct BiNode{
    char data;
    struct BiNode *lchild,*rchild;
}BiTNode,*BiTree;
// 先序建设二叉链表
void CreateBiTree(BiTree &T){    
    char ch;
    cin >> ch;
    if(ch=='#')  T=NULL;
    else{                            
        T=new BiTNode;
        T->data=ch;
        CreateBiTree(T->lchild);
        CreateBiTree(T->rchild);
    }
}
// 链栈
typedef struct StackNode{
    BiTNode data;
    struct StackNode *next;
}StackNode,*LinkStack;
// 结构空栈 S
void InitStack(LinkStack &S){S=NULL;}
bool StackEmpty(LinkStack S){if(!S)
        return true;
    return false;
}
// 入栈 
void Push(LinkStack &S,BiTree e){
    StackNode *p=new StackNode;
    p->data=*e;
    p->next=S;
    S=p;
}
// 出栈 
void Pop(LinkStack &S,BiTree e){if(S!=NULL){    
        *e=S->data;
        StackNode *p=S;
        S=S->next;
        delete p;
    }
} 
// 中序遍历  
void In(BiTree T){ 
    LinkStack S; 
    BiTree p;
    BiTree q=new BiTNode;
    InitStack(S); p=T;
    while(p||!StackEmpty(S)){if(p){Push(S,p);                
            p=p->lchild;
        }       
        else{Pop(S,q);              
            cout<<q->data;
            p=q->rchild; 
        }
    }                                
}                                    
// 先序遍历  
void Pre(BiTree T){ 
    LinkStack S; 
    BiTree p;
    BiTree q=new BiTNode;
    InitStack(S); p=T;
    while(p||!StackEmpty(S)){if(p){Push(S,p);
            cout<<p->data;                
            p=p->lchild;
        }       
        else{Pop(S,q);              
            p=q->rchild; 
        }
    }                                
}
int main(){
    BiTree tree;
    cout<<"先序建设二叉链表:";
    CreateBiTree(tree);
    cout<<"先序遍历的后果为:"; 
    Pre(tree);
    cout<<endl;
    cout<<"中序遍历的后果为:";
    In(tree);
    cout<<endl;
}

退出移动版