数据结构学习系列之二叉树的遍历

• 二叉树的遍历：
• 前序遍历：
• 先访问根结点，再访问左子树，最后访问右子树，简记：“根左右”；
• 中序遍历：
• 先访问左子树，再访问根结点，最后访问右子树，简记：“左根右”；
• 后序遍历：
• 先访问左子树，再访问右子树，最后访问根结点，简记：“左右根”；
• 创建二叉树：
• 采用前序遍历和递归的思想，原因：先有根结点，才有左子树和右子树；
• 销毁二叉树：
• 采用后序遍历和递归的思想，原因：先销毁左子树，再销毁右子树，最后销毁根结点，可以有效防止内存的泄露；
• 实例要求：
• 输入：

A
B
D
#
#
E
#
#
C
#
#
1
2
3
4
5
6
7
8
9
10
11

• 输出：

前序遍历结果：ABDEC
中序遍历结果：DBEAC
后序遍历结果：DEBCA
1
2
3

• 示例代码：

#include 
#include 
#include 

//二叉树结构体
typedef struct  BiTree{

    char data;
    struct BiTree *lchild;
    struct BiTree *rchild;

}node_t;

//创建二叉树
int create_bin_tree(node_t **root){

    if(NULL == root){

        printf("入参为NULL\n");
        return -1;

    }

    char val = 0;
    scanf("%c",&val);
    getchar(); //清理垃圾字符
    if('#' == val){

        return 0;
    }
    *root = (node_t *)malloc(sizeof(node_t));
    if(NULL == *root){

        printf("内存分配失败\n");
        return -1;
    }

    //创建根结点

    (*root)->data = val;
    (*root)->lchild = NULL;
    (*root)->rchild = NULL;

    //创建左子树
    create_bin_tree(&((*root)->lchild));

    //创建右子树

    create_bin_tree(&((*root)->rchild));

    return 0;
}

//前序遍历
int preorder_tree(node_t *root){

    if(NULL == root){

        return -1;
    }
    printf("%c",root->data);
    preorder_tree(root->lchild);
    preorder_tree(root->rchild);
}
//中序遍历
int inorder_tree(node_t *root){

    if(NULL == root){

        return -1;
    }
    inorder_tree(root->lchild);
    printf("%c",root->data);
    inorder_tree(root->rchild);

}
//后序遍历
int postorder_tree(node_t *root){

    if(NULL == root){

        return -1;
    }

    postorder_tree(root->lchild);
    postorder_tree(root->rchild);
    printf("%c",root->data);

    
}

//销毁二叉树

int destory_bin_tree(node_t **root){

    if(NULL == root || NULL == *root){

        return -1;
    }

    destory_bin_tree(&((*root)->lchild));
    destory_bin_tree(&((*root)->rchild));
    free(*root);

    *root = NULL;

    return 0;
}

int main(int argc, char const *argv[]){
   
    node_t *root = NULL;

    create_bin_tree(&root);

    printf("root = %p\n",root);

    printf("前序遍历结果：");
    preorder_tree(root);
    puts("");
    
    printf("中序遍历结果：");
    inorder_tree(root);
    puts("");

    printf("后序遍历结果：");
    postorder_tree(root);
    puts("");

    destory_bin_tree(&root);

    printf("root = %p\n",root);

    return 0;
}

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
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136

• 运行结果：

A
B
D
#
#
E
#
#
C
#
#
root = 0x560198a85670
前序遍历结果：ABDEC
中序遍历结果：DBEAC
后序遍历结果：DEBCA
root = (nil)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16