二叉树得三种非递归遍历方法

二叉树得三种非递归遍历方法先根中根后根

二叉树得三种非递归遍历方法

先根

 1void nPreOrder(BinTree tree){
 2    Stack stack;
 3    BinTree cur;
 4    if(t == NULL){
 5        return ;
 6    }
 7    stack = createStack();
 8    push(stack,tree);
 9    while(!isEmptyStack(stack)){
10        cur = pop(stack);
11        if(cur != NULL){
12            visit(cur);
13            push(stack,cur->leftNode);
14            push(stack,cur->rightNode);         
15        }
16    }
17}

中根

 1void nInOrder(BinTree tree){
 2    Stack stack = createStack();
 3    BinTree cur = tree;
 4    if(cur == NULL){
 5        return ;
 6    }
 7    do{
 8        while(cur != NULL){
 9            push(stack,cur->leftNode);
10            cur = cur->leftNode;
11        }
12        cur = pop(stack);
13        visit(cur);
14        cur = cur->rightNode;   
15    }while(cur != NULL || !isEmptyStack(stack));
16}

后根

后根我也不太熟……

 1/*
 2    typedef struct{
 3        int tag;
 4        BinTree t;
 5    }Elem; 
 6*/ 
 7void nPostOrder(BinTree tree){
 8    Stack stack = createStack();
 9    Elem stnode;    
10    BinTree p = tree;
11    if(p == NULL){
12        return ;
13    }
14    do{
15        while(p != NULL){
16            stnode.t = p;
17            stnode.tag = 1;
18            push(stack,stnode);
19            p = p->leftNode;
20        }
21        while(!isEmptyStack(stack)){
22            stnode = pop(stack);
23            p = stnode.t;
24            if(stnode.tag == 1){
25                stnode.tag = 2;
26                push(stack,stnode);
27                p = p->rightNode;
28                break;
29            }else{
30                visit(p);
31            }
32        }
33    }while(!isEmptyStack(stack));
34}
35
36#优化
37void nPostOrder(BinTree tree){   
38    Stack stack = createStack();
39    BinTree p = tree;
40    while(p != NULL || !isEmptyStack(stack)){
41        while(p != NULL){
42            push(stack,p);
43            p = p->leftNode?p->leftNode:p->rightNode;
44        }
45        p = pop(stack);
46        visit(root(p));
47        if(!isEmptyStack(stack) && top(stack)->leftNode == p){
48            p = top(stack)->rightNode;
49        }else{
50            p = NULL;
51        }
52    }
53}