非递归遍历二叉树

#include<stdio.h>
#include<malloc.h>

typedef struct binode{
    char data;
    struct binode *lchild;
    struct binode *rchild;
}BiNode,*BiTree;
/****************************
 *输入创建二叉树： abd##ef###c##
 *其实输入按照先序顺序，#表示叶子节点
 *****************************/
void create(BiTree t){
    char ch=(char)getchar();
    if(ch=='#'){
        t->data='#';
        t->lchild=NULL;
        t->rchild=NULL;
    }
    else{
        t->data=ch;
        t->lchild=(BiTree)malloc(sizeof(BiNode));
        create(t->lchild);
        t->rchild=(BiTree)malloc(sizeof(BiNode));
        create(t->rchild);
    }  
}
//先序遍历
void preTraverse(BiTree t){
    BiTree p=t;
    BiTree stack[20]; //使用栈来替代递归方法
    int top=0;
    while(top>=0){
       while(p->data!='#'){
           printf("%c ",p->data);
           stack[top++]=p;
           p=p->lchild;
       }
       if(top>0)
          p=stack[--top]->rchild;
       else 
          top=-1;
       
    }
}
//中序遍历，和先序差不多
void midTraverse(BiTree t){
    BiTree p=t;
    BiTree stack[20];
    int top=0;
    while(top>=0){
        while(p->data!='#'){
           stack[top++]=p;
           p=p->lchild;
        }
        if(top>0){
           p=stack[--top];
           printf("%c ",p->data);
           p=p->rchild;
        }else
           top=-1;
    }
}
//后序遍历，稍微复杂一点
void afeTraverse(BiTree t){
    BiTree p=t,q=t;
    BiTree stack[20];
    int top=0;
    while(top>=0){
        while(p->data!='#'){
           stack[top++]=p;
           p=p->lchild;
        }
        if(q->rchild==p){
           printf("%c ",q->data);
           q->data='#'; //遍历完的节点直接做叶子标记
           --top; 
        }
        if(top>0){
           p=stack[top-1];
           q=p;
           p=p->rchild;
           
        }
    }
}
//测试
int main(){
    BiTree root=(BiTree)malloc(sizeof(BiNode));
    create(root);
    afeTraverse(root);
    printf("\n");
    return 1;
}

 

评论

6 楼 Heart.X.Raid 2009-11-02  

楼上兄弟写的不错，简单明了，学习了，谢谢

5 楼 liliuw 2009-11-01  

下面是我写的java代码
public class StarGraph {
public void mergeGraph(int size){
//小三角形的行数  
        int line=size; 
for(int i=0;i<line;i++){
for(int j=0;j<size*4-1;j++){
if(j>=(size*4-1)/2-i&&j<=(size*4-1)/2+i){  
System.out.print("*"); 
}else{
System.out.print(" ");
            }

}
System.out.println();
}
for(int i=0;i<line;i++){
for(int j=0;j<size*2-1;j++){
if(j>=(size*2-1)/2-i&&j<=(size*2-1)/2+i){  
System.out.print("*"); 
}else{
System.out.print(" ");
            } 
}
System.out.print(" ");
for(int j=0;j<size*2-1;j++){
if(j>=(size*2-1)/2-i&&j<=(size*2-1)/2+i){  
System.out.print("*"); 
}else{
System.out.print(" ");
            } 
}
System.out.println();
}
}
public static void main(String[] args) {
StarGraph g=new StarGraph();
g.mergeGraph(3);//传入小三角形的行数 ，小三角形的行数只能为奇数
}

}

4 楼 Heart.X.Raid 2009-11-01  

长见识了，上面两楼的兄弟果然厉害，在下佩服。不过不知道如果我想让100行的小三角形堆叠起来，对了最好堆叠100层。希望上面的兄弟能给我System.out.println();出来，而且还要求"结果正确"，"维护简单"，更要求“灵活多变”。

真长见识了....


2楼的兄弟，递归是个好办法，同意你的观点，但是希望不要嘴上说说，写个程序帖出来，让大家学习学习。现在很多程序员解答别人的问题的时候都喜欢说上一句，然后闪了，希望大家能认识到程序员的工作是什么：写程序，不是说算法。

3 楼 wubin98 2009-11-01  

renxiaoya0 写道

不折腾..

System.out.println("         *");
System.out.println("        ***");
System.out.println("       *****");
System.out.println("      *     *");
System.out.println("     ***   ***");
System.out.println("    ***** *****");

按楼上的做法比较好！需求明确，结果正确。代码易懂，维护简单，灵活多变

2 楼 renxiaoya0 2009-10-31  

不折腾..

System.out.println("         *");
System.out.println("        ***");
System.out.println("       *****");
System.out.println("      *     *");
System.out.println("     ***   ***");
System.out.println("    ***** *****");

1 楼 biAji 2009-10-31  

用递归不好么？