直到海角天涯
0%

二叉树及遍历

发表于 分类于

主要关于二叉树及几种遍历方式。

文件“tree.h”

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#ifndef _TREE_H_
#define _TREE_H_

struct treenode
{
    struct treenode *left;
    struct treenode *right;
    int data;

};

struct treenode *creat_node(int value);
struct treenode *addnode(struct treenode *tree,int value);
void preorder(struct treenode *tree);
void inorder(struct treenode *tree);
void postorder(struct treenode *tree);

void levelorder(struct treenode *root);

#endif

“tree.c”

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
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
#include <stdio.h>
#include <stdlib.h>
#include "tree.h"

struct treenode *creat_node(int value)
{
    struct treenode *node;

    node=(struct treenode *)malloc(sizeof(struct treenode));
    if(node==NULL)
    {
        printf("node malloc error\n");
        return NULL;
    }

    node->left=NULL;
    node->right=NULL;
    node->data=value;
    
    return node;
}

struct treenode *addnode(struct treenode *tree,int value)
{
    if(tree==NULL)
    {
        return creat_node(value);
    }

    if(value == tree->data)
    {
        return tree;
    }
    else if(value < tree->data)
    {
        if(tree->left==NULL)
        {
            tree->left=creat_node(value);
            return tree->left;
        }
        else
        {
            return addnode(tree->left,value);
        }
    }
    else if(value > tree->data)
    {
        if(tree->right==NULL)
        {
            tree->right=creat_node(value);
            return tree->right;
        }
        else
        {
            return addnode(tree->right,value);
        }
    }
}

/*
深度优先
*/
//前序遍历
void preorder(struct treenode *tree)
{
    if(tree==NULL)
    {
        //printf("preorder error\n");
        return;
    }

    printf("%d ",tree->data);
    preorder(tree->left);
    preorder(tree->right);
}

//中序遍历
void inorder(struct treenode *tree)
{
    if(tree==NULL)
    {
        //printf("inorder error\n");
        return;
    }

    inorder(tree->left);
    printf("%d ",tree->data);
    inorder(tree->right);
}

//后序遍历
void postorder(struct treenode *tree)
{
    if(tree==NULL)
    {
        //printf("postorder error\n");
        return;
    }

    postorder(tree->left);
    postorder(tree->right);
    printf("%d ",tree->data);
}

/*
广度优先，层序遍历
*/
#define TREENODE_QUEUE_SIZE 16
struct treenode treenode_queue[TREENODE_QUEUE_SIZE];
int treenode_write,treenode_read;
void queue_insert(struct treenode * node)
{
    if(node==NULL)
        return;
    if(treenode_write - treenode_read == TREENODE_QUEUE_SIZE)
        return;

    treenode_queue[treenode_write&(TREENODE_QUEUE_SIZE-1)]=*node;
    treenode_write++;
}

struct treenode *queue_poll(void)
{
    struct treenode * node=NULL;

    if(treenode_write == treenode_read)
        return NULL;

    node=&treenode_queue[treenode_read&(TREENODE_QUEUE_SIZE-1)];
    treenode_read++;
    return node;
}

void levelorder(struct treenode *root)
{
    struct treenode *node=NULL;

    if(root==NULL)
        return;

    queue_insert(root);
    while(1)
    {
        node=queue_poll();
        if(node!=NULL)
        {
            printf("%d ",node->data);
            if(node->left!=NULL)
                queue_insert(node->left);
            if(node->right!=NULL)
                queue_insert(node->right);
        }
        else
            break;
    }
}

文件”main.c”

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
#include <stdio.h>
#include <stdlib.h>
#include "tree.h"

int main(void)
{
    struct treenode *top=NULL;
    int arr[]={6,3,5,9,2,11,8,10};
    int i;

    top=creat_node(7);

    for(i=0;i<sizeof(arr)/sizeof(int);i++)
    {
        addnode(top,arr[i]);
    }

    printf("pre order:\n");
    preorder(top);

    printf("\nin order:\n");
    inorder(top);

    printf("\npost order:\n");
    postorder(top);

    printf("\nlevel order:\n");
    levelorder(top);

    printf("\n");
}

运行结果

25teLd.png