读书笔记: 树的遍历(前序,中序,后序) Tree Traversal(preorder,inorder,postorder)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
#include <stdio.h>
#include "type_stack_queue.h"

void preorder(tree_pointer ptr);
void inorder(tree_pointer ptr);
void postorder(tree_pointer ptr);

//迭代,为了模拟递归过程,必须建立自己的栈结构
void iter_inorder(tree_pointer node){
    Stack S;
    InitStack(&S);
    for(;;){
        for(;node;node=node->left_child){
            Stack_push(&S, node);
        }
        node = Stack_pop(&S);
        if(!node) break; // empty stack
        printf("%s ",node->data);
        node=node->right_child;
    }
}

int main (int argc, const char * argv[])
{

    tree_pointer node1,node2,node3;
    node1 = create_tree_pointer("node1");
    node2 = create_tree_pointer("node2");
    node3 = create_tree_pointer("node3");
    node1->left_child = node2;
    node1->right_child = node3;

    iter_inorder(node1);
    return 0;
}

void preorder(tree_pointer ptr){
    if(ptr){
        printf("%s",ptr->data);
        preorder(ptr->left_child);
        preorder(ptr->right_child);
    }
}

void inorder(tree_pointer ptr){
    if(ptr){
        inorder(ptr->left_child);
        printf("%s",ptr->data);
        inorder(ptr->right_child);
    }
}

void postorder(tree_pointer ptr){
    if(ptr){
        postorder(ptr->left_child);
        postorder(ptr->right_child);
        printf("%s",ptr->data);
    }
}
//

//
//#define MAX_QUEUE_SIZE 10
////层序遍历,用队列
//void level_order(tree_pointer ptr){
//    int front=0,rear=0;
//    tree_pointer queue[MAX_QUEUE_SIZE];
//    if(!ptr) return; // empty tree
//    queue_add(front,&rear,ptr);
//    for(;;){
//        ptr = queue_delete(&front,rear);
//        if(ptr){
//            printf("%d",ptr->data);
//            if(ptr->left_child)
//                queue_add(ptr->left_child);
//            if(ptr->right_child)
//                queue_add(ptr->right_child);
//        } else {
//            break;
//        }
//    }
//}