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
|
#include <stdlib.h>
#include <string.h>
#include <stdio.h>
typedef struct node {
char *name;
struct node *left;
struct node *right;
} treenode;
typedef struct queue {
int front,back;
treenode **data;
} queue;
inorder(t)
treenode *t;
{
if (!t) return;
inorder(t->left);
printf("%s\n",t->name);
inorder(t->right);
}
addNode(n,v,q)
treenode **n;
char *v;
queue *q;
{
treenode *nxt;
nxt = malloc(sizeof(treenode));
memset(nxt, 0, sizeof(nxt));
nxt->name = v; /* safe - caller creates new storage for each */
enqueue(nxt,q);
}
enqueue(t,q)
treenode *t;
queue *q;
{
q->data[(q->front)++] = t;
}
main (argc, argv, envp)
int argc;
char **argv, **envp;
{
/*
prompt the user for a series of names and add them
in the order given to create a complete binary tree
the user enters
giselle
magda
aviva
ahnk
havi
minna
monique
^d
you build:
giselle
/ \
magda aviva
/ \ / \
ahnk havi minna monique
then print it out inorder
this should work for any number of name entered.
(consider using a queue)
*/
treenode *t = 0;
char buf[1024];
queue q;
q.back = 0;
q.front = 0;
q.data = calloc(100,sizeof(treenode*));
while (gets(buf))
addNode(&t, strdup(buf),&q);
printf("q.back %d q.front %d", q.back, q.front);
while(q.back < q.front){
printf("bulid tree pass %d %x\n", q.back,q.data[q.back]);
q.data[q.back]->left = q.data[((2 * q.back) +1)];
q.data[q.back]->right = q.data[((2 * q.back) + 2)];
q.back++;
}
t = q.data[0];
inorder(t);
}
|
