沉溺C++

记忆经典

C++博客 首页 新随笔 联系 聚合 管理
  3 Posts :: 4 Stories :: 2 Comments :: 0 Trackbacks
#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==0return 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 俊杰 阅读(233) 评论(2)  编辑 收藏 引用

Feedback

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

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

@alpc16
  回复  更多评论
  


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