沉溺C++

记忆经典
C++博客 首页 新随笔 联系 聚合 管理
  3 Posts :: 4 Stories :: 2 Comments :: 0 Trackbacks
NO_Recursive Travel
#include <iostream>
#include <stack>
using namespace std;
#define MAXNODENUM 20
typedef int  DataType; 
typedef struct node   
{
    DataType data;
    struct node *lchild,*rchild;
    int mark;
}CSNode,*CSTree;

CSTree createCSTree(CSTree T)
{
    int x;
    cin>>x;
    if (x==0) return 0 ;
    T=new CSNode;
    T->data=x;
    T->mark=0;
    T->lchild=createCSTree(T->lchild);
    T->rchild=createCSTree(T->rchild);
    return T;
}

void visit(CSNode *t)
{
    cout<<t->data<<" ";
}

void PreOder_NoRecursive(CSTree T)
{
    stack<CSNode*> ST;
    if (!T) return ;
    CSNode *p;
    p=T;
    ST.push(T);
    while (!ST.empty())
    {
        p=ST.top();
        visit(p);
        ST.pop();
        while (p->lchild)
        {
            visit(p->lchild);
            if (p->rchild)
            {
                ST.push(p->rchild);
            }
            p=p->lchild;
        }
    }
}
void InOrder_NoRecursive(CSTree T)
{
    stack<CSNode*> ST;
    if (!T) return ;
    CSNode *p;
    p=T;
    ST.push(T);
    while (!ST.empty())
    {
        p=ST.top();
        while (p->lchild&&!p->lchild->mark)
        {
            ST.push(p->lchild);
            p=p->lchild;
        }
        visit(p);
        p->mark=1;
        ST.pop();
        if (p->rchild)
        {
            ST.push(p->rchild);
        }
    }
}
void PostOrder_NoRecursive(CSTree T)
{
    stack<CSNode*> ST;
    if (!T) return ;
    CSNode *p;
    p=T;
    ST.push(T);
    while(!ST.empty())
    {
        p=ST.top();
        while (p->lchild&&!p->lchild->mark)
        {
            if (p->rchild)    ST.push(p->rchild);
            ST.push(p->lchild);
            p=p->lchild;
        }
        p=ST.top();
        visit(p);
        p->mark=1;
        ST.pop();
    }
}
int main()
{
    CSTree T;
    T=0;
    T=createCSTree(T);
//     PreOrderTravel(T);
//     cout<<endl;
//     PreOder_NoRecursive(T);
//     cout<<endl;
//     PostOrderTravel(T);
//     cout<<endl;
//     PostOrder_NoRecursive(T);
    InOrder_NoRecursive(T);
    return 0;
}
// 1 2 4 0 0 5 7 0 0 8 0 0 3 6 0 0 0
//1 2 4 0 9 0 0 5 7 
自己写的，课本如下：
void PreOrder_NoRecursive(CSTree T)
{
    stack<CSNode*> ST;
    if (!T) return ;
    CSNode *p;
    p=T;
    while (p!=NULL||!ST.empty())
    {
        while (p!=NULL)
        {
            visit(p);
            ST.push(p);
            p=p->lchild;
        }
        if (!ST.empty())
        {
            p=ST.top();
            ST.pop();
            p=p->rchild;
        }
    }
}



#include <iostream>
#include <stack>
using namespace std;
#define MAXNODENUM 20
typedef int  DataType; 
typedef struct node
{
    DataType data;
    struct node *lchild,*rchild;
    int  mark;
}CSNode,*CSTree;

void PostOrder_NoRecursive(CSTree T)
{
    stack<CSNode*> ST;
    if (!T) return ;
    CSNode *p;
    p=T;
    ST.push(p);
    while(!ST.empty())
    {
        p=ST.top();
        ST.pop();
        switch (p->mark)
        {
        case 0:
            p->mark=1;
            ST.push(p);
            if (p->lchild)
            {
                p=p->lchild;
                ST.push(p);
            }
            break;
        case 1:
            p->mark=2;
            ST.push(p);
            if (p->rchild)
            {
                p=p->rchild;
                ST.push(p);
            }
            break;
        case 2:
            visit(p);
        }
        
    }
}
省略了一部分代码，都是代码，请问课本的那个先序遍历的过程是怎样想出来的。是怎样的一个模拟的过程。
posted on 2008-09-12 02:44 俊杰 阅读(246) 评论(2)  编辑 收藏 引用

Feedback

# re: NO_Recursive Travel 2008-09-13 21:22 alpc16
看代码好累。。。  回复  更多评论
  

# re: NO_Recursive Travel 2008-09-14 01:10 俊杰
那你说下非递归的思想。。。
老大你在不

@alpc16
  回复  更多评论
  


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理