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
|
/* trees.c
*
* Trees
*
*/
#include "trees.h"
/* adds a node containing token, at or below p */
struct tnode *bintree_insert(struct tnode *p, char *t)
{
int cond;
if (p == NULL)
{
p = (struct tnode *) malloc(sizeof(struct tnode));
p->text = t;
p->count = 1;
p->left = p->right = NULL;
}
else if ((cond = strcmp(t, p->text)) == 0)
p->count++;
else if (cond < 0) /* go to the left subtree */
p->left = bintree_insert(p->left, t);
else /* go to the right subtree */
p->right = bintree_insert(p->right, t);
return p;
}
/* CLR: pre-order / prefix tree print */
void treeprint_prefix(struct tnode *p)
{
if (p != NULL)
{
printf("%4d %s\n", p->count, p->text);
treeprint_prefix(p->left);
treeprint_prefix(p->right);
}
}
/* LCR: in-order / infix tree print */
void treeprint_infix(struct tnode *p)
{
if (p != NULL)
{
treeprint_infix(p->left);
printf("%4d %s\n", p->count, p->text);
treeprint_infix(p->right);
}
}
/* LRC: post-order / postfix tree print */
void treeprint_postfix(struct tnode *p)
{
if (p != NULL)
{
treeprint_postfix(p->left);
treeprint_postfix(p->right);
printf("%4d %s\n", p->count, p->text);
}
}
int main(int argc, char **argv)
{
struct tnode *root = NULL;
char *tokens[] = { "Anything", "that", "can", "go", "wrong", "will",
"binary", "trees", "are", "useful",
"dreaming", "in", "digital", "living", "in", "realtime",
"thinking", "in", "binary", "talking", "in", "ip"};
int i;
for (i = 0; i < sizeof(tokens) / sizeof(char *); i++)
root = bintree_insert(root, tokens[i]);
treeprint_infix(root);
return 0;
}
|
