Google Groups no longer supports new Usenet posts or subscriptions. Historical content remains viewable.
Dismiss
Binary Search Tree in C
144 views
Skip to first unread message
arnuld
Jan 8, 2018, 11:08:30 AM1/8/18
to
AIM: To implement a simple binary search tree without peeking into
section 6.5 of K&R2 :)
PROBLEM: how can I know that the printed tree really got Left and Right
in correct order (I mean How can I be sure, how can I see that all values
larger than root went to left leg and equal or smaller ones to right leg)
/* A Binary Search Tree implementation */
#include <stdio.h>
#include <stdlib.h>
enum { TOTAL_NODES = 10,
ROOT_NODE = 0
};
struct node
{
int num;
struct node* left;
struct node* right;
};
/* To keep track of root node, root node search will always be O(1) this
way */
struct myTree
{
struct node* rootNode;
};
struct myTree* allocTree(void);
void allocRoot(struct myTree*);
struct node* addChild(struct node*, int);
void printTree(struct node*);
int main(void)
{
struct myTree* s = allocTree();
int i, j;
allocRoot(s);
for(i = j = ROOT_NODE+1; i<=TOTAL_NODES; ++i, --j)
{
addChild(s->rootNode, i);
addChild(s->rootNode, j);
}
printTree(s->rootNode);
return 0;
}
struct node* addChild(struct node* pn, int n)
{
if(NULL == pn)
{
struct node* new_node = malloc(1 * sizeof(*new_node));
if(new_node)
{
new_node->num = n;
new_node->left = new_node->right = NULL;
}
else
{
printf("Out of memory. Can't add Node(%d)\n", n);
}
pn = new_node;
}
else if(n > pn->num)
{
pn->left = addChild(pn->left, n);
}
else
{
pn->right = addChild(pn->right, n);
}
return pn;
}
void printTree(struct node* pn)
{
if(pn)
{
printf("%d\n", pn->num);
printTree(pn->left);
printTree(pn->right);
}
}
void allocRoot(struct myTree* pt)
{
struct node* rt = pt->rootNode;
rt = malloc(1 * sizeof(*rt));
if(NULL == rt)
{
printf("Out of memory, can't create root node.\n... EXITing now....
\n\n");
exit(EXIT_FAILURE);
}
rt->num = ROOT_NODE;
rt->left = rt->right = NULL;
pt->rootNode = rt;
}
struct myTree* allocTree(void)
{
struct myTree* s = malloc(1 * sizeof(*s));
if(NULL == s)
{
printf("No memory to create Tree\n..\n..\n");
exit(EXIT_FAILURE);
}
s->rootNode = NULL;
return s;
}
======================== OUTPUT ===================================
[arnuld@arch64 programs]$ gcc -ansi -pedantic -Wall -Wextra tree.c
[arnuld@arch64 programs]$ ./a.out
0
1
2
3
4
5
6
7
8
9
10
1
0
-1
-2
-3
-4
-5
-6
-7
-8
[arnuld@arch64 programs]$
--
-- arnuld
http://lispmachine.wordpress.com/
section 6.5 of K&R2 :)
PROBLEM: how can I know that the printed tree really got Left and Right
in correct order (I mean How can I be sure, how can I see that all values
larger than root went to left leg and equal or smaller ones to right leg)
/* A Binary Search Tree implementation */
#include <stdio.h>
#include <stdlib.h>
enum { TOTAL_NODES = 10,
ROOT_NODE = 0
};
struct node
{
int num;
struct node* left;
struct node* right;
};
/* To keep track of root node, root node search will always be O(1) this
way */
struct myTree
{
struct node* rootNode;
};
struct myTree* allocTree(void);
void allocRoot(struct myTree*);
struct node* addChild(struct node*, int);
void printTree(struct node*);
int main(void)
{
struct myTree* s = allocTree();
int i, j;
allocRoot(s);
for(i = j = ROOT_NODE+1; i<=TOTAL_NODES; ++i, --j)
{
addChild(s->rootNode, i);
addChild(s->rootNode, j);
}
printTree(s->rootNode);
return 0;
}
struct node* addChild(struct node* pn, int n)
{
if(NULL == pn)
{
struct node* new_node = malloc(1 * sizeof(*new_node));
if(new_node)
{
new_node->num = n;
new_node->left = new_node->right = NULL;
}
else
{
printf("Out of memory. Can't add Node(%d)\n", n);
}
pn = new_node;
}
else if(n > pn->num)
{
pn->left = addChild(pn->left, n);
}
else
{
pn->right = addChild(pn->right, n);
}
return pn;
}
void printTree(struct node* pn)
{
if(pn)
{
printf("%d\n", pn->num);
printTree(pn->left);
printTree(pn->right);
}
}
void allocRoot(struct myTree* pt)
{
struct node* rt = pt->rootNode;
rt = malloc(1 * sizeof(*rt));
if(NULL == rt)
{
printf("Out of memory, can't create root node.\n... EXITing now....
\n\n");
exit(EXIT_FAILURE);
}
rt->num = ROOT_NODE;
rt->left = rt->right = NULL;
pt->rootNode = rt;
}
struct myTree* allocTree(void)
{
struct myTree* s = malloc(1 * sizeof(*s));
if(NULL == s)
{
printf("No memory to create Tree\n..\n..\n");
exit(EXIT_FAILURE);
}
s->rootNode = NULL;
return s;
}
======================== OUTPUT ===================================
[arnuld@arch64 programs]$ gcc -ansi -pedantic -Wall -Wextra tree.c
[arnuld@arch64 programs]$ ./a.out
0
1
2
3
4
5
6
7
8
9
10
1
0
-1
-2
-3
-4
-5
-6
-7
-8
[arnuld@arch64 programs]$
--
-- arnuld
http://lispmachine.wordpress.com/
Malcolm McLean
Jan 8, 2018, 11:30:44 AM1/8/18
to
On Monday, January 8, 2018 at 4:08:30 PM UTC, arnuld wrote:
> AIM: To implement a simple binary search tree without peeking into
> section 6.5 of K&R2 :)
>
> PROBLEM: how can I know that the printed tree really got Left and Right
> in correct order (I mean How can I be sure, how can I see that all values
> larger than root went to left leg and equal or smaller ones to right leg)
>
Print the tree out using brackets to denote the structure. So a node is
> AIM: To implement a simple binary search tree without peeking into
> section 6.5 of K&R2 :)
>
> PROBLEM: how can I know that the printed tree really got Left and Right
> in correct order (I mean How can I be sure, how can I see that all values
> larger than root went to left leg and equal or smaller ones to right leg)
>
open bracket
left children
comma
self
comma
right children
close bracket
this produces a tree on a few lines. It's not as readable as a tree
laid out as a graph, but the code to lay out trees nicely as graphs
is fairly complex whilst this is simple. It then allows you to check
a small tree by hand.
Ben Bacarisse
Jan 8, 2018, 12:37:04 PM1/8/18
to
arnuld <sun...@invalid.address> writes:
> PROBLEM: how can I know that the printed tree really got Left and Right
> in correct order (I mean How can I be sure, how can I see that all values
> larger than root went to left leg and equal or smaller ones to right leg)
Brackets have been suggested but you can also use indentation. The
> PROBLEM: how can I know that the printed tree really got Left and Right
> in correct order (I mean How can I be sure, how can I see that all values
> larger than root went to left leg and equal or smaller ones to right leg)
effect would be something like this:
25
21
20
16
15
0
-6
-8
-9
-13
-15
All the left nodes appear above the right nodes but the number is
printed preceded by spaces that corresponding to the depth of the node.
> /* To keep track of root node, root node search will always be O(1) this
> way */
> struct myTree
> {
> struct node* rootNode;
> };
about the tree. I'd simply represent a tree as a pointer to the root
node with no extra struct.
> void allocRoot(struct myTree* pt)
> {
> struct node* rt = pt->rootNode;
> rt = malloc(1 * sizeof(*rt));
> if(NULL == rt)
> {
> printf("Out of memory, can't create root node.\n... EXITing now....
> \n\n");
> exit(EXIT_FAILURE);
> }
>
> rt->num = ROOT_NODE;
> rt->left = rt->right = NULL;
> pt->rootNode = rt;
> }
know something about the distribution of the data? If this is a
general-purpose binary tree then I don't think this is a good idea.
--
Ben.
Ike Naar
Jan 8, 2018, 2:06:44 PM1/8/18
to
On 2018-01-08, arnuld <sun...@invalid.address> wrote:
> void printTree(struct node* pn)
> {
> if(pn)
> {
> printf("%d\n", pn->num);
> printTree(pn->left);
> printTree(pn->right);
> }
> }
If you want to print the tree in, say, ascending order,
> void printTree(struct node* pn)
> {
> if(pn)
> {
> printf("%d\n", pn->num);
> printTree(pn->left);
> printTree(pn->right);
> }
> }
then first print the right subtree, then the node, then the left subtree.
Scott Lurndal
Jan 8, 2018, 2:16:08 PM1/8/18
to
depend on the order of the three lines, above.
arnuld
Jan 9, 2018, 9:57:18 AM1/9/18
to
> On Mon, 08 Jan 2018 17:36:48 +0000, Ben Bacarisse wrote:
> Brackets have been suggested but you can also use indentation. The
> effect would be something like this:
> ... SNIP ...
> Brackets have been suggested but you can also use indentation. The
> effect would be something like this:
Well, I just put a single space instead of () but does not come out like
the way show.
> I can't work out what this comment means.
> I would not bother to do this unless I was keeping more information
> about the tree. I'd simply represent a tree as a pointer to the root
> node with no extra struct.
> This is very odd. Why do you always put a zero node in there? Do you
> know something about the distribution of the data? If this is a
> general-purpose binary tree then I don't think this is a good idea.
"general-purpose binary tree" and "not a good idea" meant.
/* A Binary Search Tree implementation
*
**/
#include <stdio.h>
#include <stdlib.h>
enum { TOTAL_NODES = 10,
};
struct node
{
int num;
struct node* left;
struct node* right;
};
struct node* allocRoot(void);
struct node
{
int num;
struct node* left;
struct node* right;
};
struct node* addChild(struct node*, int);
void printTree(struct node*);
int main(void)
{
struct node* rootNode = allocRoot();
void printTree(struct node*);
int main(void)
{
int i, j;
for(i = j = ROOT_NODE; i<=TOTAL_NODES; ++i, --j)
{
addChild(rootNode, i);
addChild(rootNode, j);
}
printTree(rootNode);
putchar('\n');
return 0;
}
struct node* addChild(struct node* pn, int n)
{
if(NULL == pn)
{
struct node* new_node = malloc(1 * sizeof(*new_node));
if(new_node)
{
new_node->num = n;
new_node->left = new_node->right = NULL;
}
else
{
printf("Out of memory. Can't add Node(%d)\n", n);
}
pn = new_node;
}
else if(n > pn->num)
{
pn->left = addChild(pn->left, n);
}
else
{
pn->right = addChild(pn->right, n);
}
return pn;
}
void printTree(struct node* pn)
{
if(pn)
{
printTree(pn->left);
printf("%d", pn->num);
printTree(pn->right);
putchar(')');
}
}
struct node* allocRoot(void)
{
struct node* rt = malloc(1 * sizeof(*rt));
if(NULL == rt)
{
printf("Out of memory, can't create root node.\n... EXITing now....
\n\n");
exit(EXIT_FAILURE);
}
rt->num = ROOT_NODE;
rt->left = rt->right = NULL;
return rt;
{
printf("Out of memory, can't create root node.\n... EXITing now....
\n\n");
exit(EXIT_FAILURE);
}
rt->num = ROOT_NODE;
rt->left = rt->right = NULL;
}
======================= OUTPUT =============================
[arnuld@arch64 programs]$ gcc -ansi -pedantic -Wall -Wextra tree.c
[arnuld@arch64 programs]$ ./a.out
((((((10)9)8)7)6)5(5(5(4(3(2(1(0))))))))
[arnuld@arch64 programs]$ ./a.out
Chad
Jan 9, 2018, 11:08:20 AM1/9/18
to
Uhhh...I'm not aware of any sane major research university nor tech firm that would want such a nutty output. Well, I take that back. Maybe if someone wants to be a dick about it. But still....
Manfred
Jan 9, 2018, 11:25:16 AM1/9/18
to
On 1/9/2018 3:56 PM, arnuld wrote:
> Well, I just put a single space instead of () but does not come out like
> the way show.
One issue is that you effectively add the ROOT_NODE three times.
> Well, I just put a single space instead of () but does not come out like
> the way show.
By the way, you may get rid of allocRoot() and replace it with
addChild(NULL, ROOT_NODE)
(I'll leave to Ben to answer to your other questions)
Malcolm McLean
Jan 9, 2018, 12:03:31 PM1/9/18
to
On Tuesday, January 9, 2018 at 2:57:18 PM UTC, arnuld wrote:
> > On Mon, 08 Jan 2018 17:36:48 +0000, Ben Bacarisse wrote:
>
> > This is very odd. Why do you always put a zero node in there? Do you
> > know something about the distribution of the data? If this is a
> > general-purpose binary tree then I don't think this is a good idea.
>
> Well, this function was called only once. I did not understand what
> "general-purpose binary tree" and "not a good idea" meant.
>
If you know that the data consists of roughly equal numbers of negative and
> > On Mon, 08 Jan 2018 17:36:48 +0000, Ben Bacarisse wrote:
>
> > This is very odd. Why do you always put a zero node in there? Do you
> > know something about the distribution of the data? If this is a
> > general-purpose binary tree then I don't think this is a good idea.
>
> Well, this function was called only once. I did not understand what
> "general-purpose binary tree" and "not a good idea" meant.
>
positive numbers, plus one zero (or zero is a special dummy or null case)
then it might make sense to reserve 0 for the root. However, whilst
there's nothing surprising about this distribution, it's not the only
possible distribution of the data.
Normally it's important that a binary tree be balanced, that is, have
approximately equal numbers of left and right descendants under the root,
and sub-trees also having that property. This is actually quite difficult
to achieve, but by randomising the data and choosing a random node
as root you will normally get a reasonable balance. You can improve
the distribution by choosing median as root, however taking the median
is itself an expensive function. I've leave you to think how you might
make the subtrees reasonably balanced.
arnuld
Jan 9, 2018, 11:34:53 PM1/9/18
to
> On Mon, 08 Jan 2018 16:08:06 +0000, arnuld wrote:
> ... SNIP ....
Just tried an iterative version of inserting elements but it does not
work and I can't figure out why:
/* A Binary Search Tree implementation
addChildIter(rootNode, j);
}
printTree(rootNode);
putchar('\n');
return 0;
}
struct node* addChild(struct node* pn, int n)
{
if(NULL == pn)
{
struct node* new_node = malloc(1 * sizeof(*new_node));
if(new_node)
{
new_node->num = n;
new_node->left = new_node->right = NULL;
}
else
{
printf("Out of memory. Can't add Node(%d)\n", n);
}
pn = new_node;
}
else if(n > pn->num)
{
pn->left = addChild(pn->left, n);
}
else
{
pn->right = addChild(pn->right, n);
}
return pn;
}
struct node* addChildIter(struct node* pn, int n)
{
struct node* new_node;
while(pn)
{
if(n > pn->num)
{
pn = pn->left;
}
else
{
pn = pn->right;
> ... SNIP ....
> struct node* addChild(struct node* pn, int n)
> {
> if(NULL == pn)
> {
> struct node* new_node = malloc(1 * sizeof(*new_node));
> ... SNIP ...
> {
> if(NULL == pn)
> {
> struct node* new_node = malloc(1 * sizeof(*new_node));
Just tried an iterative version of inserting elements but it does not
work and I can't figure out why:
/* A Binary Search Tree implementation
* just 2 operations: add and print
*
**/
*
**/
#include <stdio.h>
#include <stdlib.h>
enum { TOTAL_NODES = 10,
ROOT_NODE = 5
#include <stdlib.h>
enum { TOTAL_NODES = 10,
};
struct node
{
int num;
struct node* left;
struct node* right;
};
struct node
{
int num;
struct node* left;
struct node* right;
};
struct node* addChild(struct node*, int);
struct node* addChildIter(struct node* , int);
void printTree(struct node*);
int main(void)
{
struct node* rootNode = addChild(NULL, ROOT_NODE);
int main(void)
{
int i, j;
for(i = j = ROOT_NODE; i<=TOTAL_NODES; ++i, --j)
{
addChildIter(rootNode, i);
for(i = j = ROOT_NODE; i<=TOTAL_NODES; ++i, --j)
{
addChildIter(rootNode, j);
}
printTree(rootNode);
putchar('\n');
return 0;
}
struct node* addChild(struct node* pn, int n)
{
if(NULL == pn)
{
struct node* new_node = malloc(1 * sizeof(*new_node));
if(new_node)
{
new_node->num = n;
new_node->left = new_node->right = NULL;
}
else
{
printf("Out of memory. Can't add Node(%d)\n", n);
}
pn = new_node;
}
else if(n > pn->num)
{
pn->left = addChild(pn->left, n);
}
else
{
pn->right = addChild(pn->right, n);
}
return pn;
}
{
struct node* new_node;
while(pn)
{
if(n > pn->num)
{
pn = pn->left;
}
else
{
pn = pn->right;
}
}
new_node = malloc(1 * sizeof(*new_node));
if(new_node)
{
new_node->num = n;
new_node->left = new_node->right = NULL;
}
else
{
printf("Out of memory. Can't add Node(%d)\n", n);
}
pn = new_node;
}
new_node = malloc(1 * sizeof(*new_node));
if(new_node)
{
new_node->num = n;
new_node->left = new_node->right = NULL;
}
else
{
printf("Out of memory. Can't add Node(%d)\n", n);
}
pn = new_node;
return pn;
}
void printTree(struct node* pn)
{
if(pn)
{
}
void printTree(struct node* pn)
{
if(pn)
{
putchar('(');
printTree(pn->left);
printf("%d", pn->num);
printTree(pn->right);
putchar(')');
}
}
========================== OUTPUT =========================
printTree(pn->left);
printf("%d", pn->num);
printTree(pn->right);
putchar(')');
}
}
[arnuld@arch64 programs]$ gcc -ansi -pedantic -Wall -Wextra tree.c
[arnuld@arch64 programs]$ ./a.out
(5)
[arnuld@arch64 programs]$ ./a.out
arnuld
Jan 9, 2018, 11:37:30 PM1/9/18
to
> On Tue, 09 Jan 2018 17:24:56 +0100, Manfred wrote:
> One issue is that you effectively add the ROOT_NODE three times.
> By the way, you may get rid of allocRoot() and replace it with
> addChild(NULL, ROOT_NODE)
Yeah. I did replace allocRoot(). Now code looks so simple. I still did
> One issue is that you effectively add the ROOT_NODE three times.
> By the way, you may get rid of allocRoot() and replace it with
> addChild(NULL, ROOT_NODE)
not understand what you mean by "effectively adding ROOT_NODE 3 times".
If you mean number 5 added 3 times then I am fine with that. I am just
learning Data-Structures and Algorithms.
> (I'll leave to Ben to answer to your other questions)
Barry Schwarz
Jan 10, 2018, 12:35:50 AM1/10/18
to
On 10 Jan 2018 04:34:37 GMT, arnuld <sun...@invalid.address> wrote:
>Just tried an iterative version of inserting elements but it does not
>work and I can't figure out why:
"Does not work" doesn't tell us anything other than you are
>Just tried an iterative version of inserting elements but it does not
>work and I can't figure out why:
dissatisfied. In what way does it not work. Be as specific as
possible. Tell us what you have done to try to debug the issue.
Or you could look at the code and ask yourself where does addChildIter
connect the new node to the existing tree?
--
Remove del for email
arnuld
Jan 10, 2018, 1:37:58 AM1/10/18
to
> On Tue, 09 Jan 2018 21:35:33 -0800, Barry Schwarz wrote:
> "Does not work" doesn't tell us anything other than you are
> dissatisfied. In what way does it not work. Be as specific as
> possible. Tell us what you have done to try to debug the issue.
>
> Or you could look at the code and ask yourself where does addChildIter
> connect the new node to the existing tree?
Yeah. That's correct. It is not connecting new node to the tree. So all
> "Does not work" doesn't tell us anything other than you are
> dissatisfied. In what way does it not work. Be as specific as
> possible. Tell us what you have done to try to debug the issue.
>
> Or you could look at the code and ask yourself where does addChildIter
> connect the new node to the existing tree?
pointers are just pointing somewhere but not in the tree. I do not know
what first step to take to start understanding/debugging. It is kind of
as if I totally lack fundamentals of Data Structure or how it behaves in
C or both.
Manfred
Jan 10, 2018, 7:58:30 AM1/10/18
to
On 1/10/2018 5:37 AM, arnuld wrote:
> I still did
> not understand what you mean by "effectively adding ROOT_NODE 3 times".
> If you mean number 5 added 3 times then I am fine with that. I am just
> learning Data-Structures and Algorithms.
It means that you were adding ROOT_NODE (i.e. number 5) in the
> I still did
> not understand what you mean by "effectively adding ROOT_NODE 3 times".
> If you mean number 5 added 3 times then I am fine with that. I am just
> learning Data-Structures and Algorithms.
allocRoot() call, and then twice in the first 'for' iteration of addChild().
I pointed it out because from your code it did not look like this was
intentional.
Ben Bacarisse
Jan 10, 2018, 9:53:32 AM1/10/18
to
arnuld <sun...@invalid.address> writes:
>> On Tue, 09 Jan 2018 17:24:56 +0100, Manfred wrote:
<snip>
>> On Tue, 09 Jan 2018 17:24:56 +0100, Manfred wrote:
>> (I'll leave to Ben to answer to your other questions)
>
> I am waiting for him too :)
I considered the questions in your reply to me to have been answered by
>
> I am waiting for him too :)
other posts. Sorry if that was not the case. Do ask again if there is
something I said that has not been addressed.
--
Ben.
Mr. Man-wai Chang
Jan 10, 2018, 4:23:32 PM1/10/18
to
On 9/1/2018 00:08, arnuld wrote:
> AIM: To implement a simple binary search tree without peeking into
> section 6.5 of K&R2 :)
>
> PROBLEM: how can I know that the printed tree really got Left and Right
> in correct order (I mean How can I be sure, how can I see that all values
> larger than root went to left leg and equal or smaller ones to right leg)
It's also called "to flatten a tree/list".
> AIM: To implement a simple binary search tree without peeking into
> section 6.5 of K&R2 :)
>
> PROBLEM: how can I know that the printed tree really got Left and Right
> in correct order (I mean How can I be sure, how can I see that all values
> larger than root went to left leg and equal or smaller ones to right leg)
--
@~@ Remain silent! Drink, Blink, Stretch! Live long and prosper!!
/ v \ Simplicity is Beauty!
/( _ )\ May the Force and farces be with you!
^ ^ (x86_64 Ubuntu 9.10) Linux 2.6.39.3
不借貸! 不詐騙! 不援交! 不打交! 不打劫! 不自殺! 請考慮綜援 (CSSA):
http://www.swd.gov.hk/tc/index/site_pubsvc/page_socsecu/sub_addressesa
Barry Schwarz
Jan 11, 2018, 12:32:33 PM1/11/18
to
On 11 Jan 2018 16:44:58 GMT, r...@zedat.fu-berlin.de (Stefan Ram)
wrote:
>typedef size_t vertical;
>#define VERTICALFORMAT "%zu"
>
>#define MAX(a,b) ((a)>(b)?(a):(b))
>#define MIN(a,b) ((a)<(b)?(a):(b))
>
>typedef int number;
>#define NUMBERFORMAT "%d"
>
>struct box
>{ char * data;
> horizontal width;
Is this really easier to read or more informative than
size_t width;
> vertical height;
> horizontal anchorpos; };
>
>struct box * box_from_number( number const n )
>{ struct box * const box = malloc( sizeof * box );
> box->data = salfmt( NUMBERFORMAT, n );
Is this really easier to read or more informative than
box->data = salfmt( "%d", n );
It's certainly not easier to type.
wrote:
>typedef size_t vertical;
>#define VERTICALFORMAT "%zu"
>
>#define MAX(a,b) ((a)>(b)?(a):(b))
>#define MIN(a,b) ((a)<(b)?(a):(b))
>
>typedef int number;
>#define NUMBERFORMAT "%d"
>
>struct box
>{ char * data;
> horizontal width;
Is this really easier to read or more informative than
size_t width;
> vertical height;
> horizontal anchorpos; };
>
>struct box * box_from_number( number const n )
>{ struct box * const box = malloc( sizeof * box );
> box->data = salfmt( NUMBERFORMAT, n );
Is this really easier to read or more informative than
box->data = salfmt( "%d", n );
It's certainly not easier to type.
arnuld
Jan 11, 2018, 10:40:42 PM1/11/18
to
> On Wed, 10 Jan 2018 13:58:12 +0100, Manfred wrote:
> It means that you were adding ROOT_NODE (i.e. number 5) in the
> allocRoot() call, and then twice in the first 'for' iteration of
> addChild().
> I pointed it out because from your code it did not look like this was
> intentional.
Oh, that's correct. It was not intentional. Thanks for that :). I have
> It means that you were adding ROOT_NODE (i.e. number 5) in the
> allocRoot() call, and then twice in the first 'for' iteration of
> addChild().
> I pointed it out because from your code it did not look like this was
> intentional.
modified the code now, removed allocRott() and using addChild(NULL, i)
instead, so I think the problem is gone.
int main(void)
{
struct node* rootNode = addChild(NULL, ROOT_NODE);
int i, j;
for(i = j = ROOT_NODE; i<=TOTAL_NODES; ++i, --j)
{
addChild(rootNode, i);
addChild(rootNode, j);
}
printTree(rootNode);
putchar('\n');
return 0;
}
struct node* addChild(struct node* pn, int n)
{
if(NULL == pn)
{
struct node* new_node = malloc(1 * sizeof(*new_node));
if(new_node)
{
new_node->num = n;
new_node->left = new_node->right = NULL;
}
else
{
printf("Out of memory. Can't add Node(%d)\n", n);
}
pn = new_node;
}
else if(n > pn->num)
{
pn->left = addChild(pn->left, n);
}
else
{
pn->right = addChild(pn->right, n);
}
return pn;
}
for(i = j = ROOT_NODE; i<=TOTAL_NODES; ++i, --j)
{
addChild(rootNode, i);
addChild(rootNode, j);
}
printTree(rootNode);
putchar('\n');
return 0;
}
struct node* addChild(struct node* pn, int n)
{
if(NULL == pn)
{
struct node* new_node = malloc(1 * sizeof(*new_node));
if(new_node)
{
new_node->num = n;
new_node->left = new_node->right = NULL;
}
else
{
printf("Out of memory. Can't add Node(%d)\n", n);
}
pn = new_node;
}
else if(n > pn->num)
{
pn->left = addChild(pn->left, n);
}
else
{
pn->right = addChild(pn->right, n);
}
return pn;
}
Thiago Adams
Jan 12, 2018, 7:17:50 AM1/12/18
to
On Friday, January 12, 2018 at 1:40:42 AM UTC-2, arnuld wrote:
> > On Wed, 10 Jan 2018 13:58:12 +0100, Manfred wrote:
>
> > It means that you were adding ROOT_NODE (i.e. number 5) in the
> > allocRoot() call, and then twice in the first 'for' iteration of
> > addChild().
> > I pointed it out because from your code it did not look like this was
> > intentional.
>
> Oh, that's correct. It was not intentional. Thanks for that :). I have
> modified the code now, removed allocRott() and using addChild(NULL, i)
> instead, so I think the problem is gone.
>
How/where do you free nodes?
> > On Wed, 10 Jan 2018 13:58:12 +0100, Manfred wrote:
>
> > It means that you were adding ROOT_NODE (i.e. number 5) in the
> > allocRoot() call, and then twice in the first 'for' iteration of
> > addChild().
> > I pointed it out because from your code it did not look like this was
> > intentional.
>
> Oh, that's correct. It was not intentional. Thanks for that :). I have
> modified the code now, removed allocRott() and using addChild(NULL, i)
> instead, so I think the problem is gone.
>
Thiago Adams
Jan 12, 2018, 7:20:14 AM1/12/18
to
Don't you think the node allocation deserves a function
to avoid duplicate these lines in other places?
Manfred
Jan 12, 2018, 7:56:11 AM1/12/18
to
On 1/12/2018 4:40 AM, arnuld wrote:
>> On Wed, 10 Jan 2018 13:58:12 +0100, Manfred wrote:
>
>> It means that you were adding ROOT_NODE (i.e. number 5) in the
>> allocRoot() call, and then twice in the first 'for' iteration of
>> addChild().
>> I pointed it out because from your code it did not look like this was
>> intentional.
>
> Oh, that's correct. It was not intentional. Thanks for that :). I have
> modified the code now, removed allocRott() and using addChild(NULL, i)
> instead, so I think the problem is gone.
It looks like you are still adding ROOT_NODE three times..
>> On Wed, 10 Jan 2018 13:58:12 +0100, Manfred wrote:
>
>> It means that you were adding ROOT_NODE (i.e. number 5) in the
>> allocRoot() call, and then twice in the first 'for' iteration of
>> addChild().
>> I pointed it out because from your code it did not look like this was
>> intentional.
>
> Oh, that's correct. It was not intentional. Thanks for that :). I have
> modified the code now, removed allocRott() and using addChild(NULL, i)
> instead, so I think the problem is gone.
James R. Kuyper
Jan 12, 2018, 8:51:03 AM1/12/18
to
On 01/11/2018 10:40 PM, arnuld wrote:
>> On Wed, 10 Jan 2018 13:58:12 +0100, Manfred wrote:
>
>> It means that you were adding ROOT_NODE (i.e. number 5) in the
>> allocRoot() call, and then twice in the first 'for' iteration of
>> addChild().
>> I pointed it out because from your code it did not look like this was
>> intentional.
>
> Oh, that's correct. It was not intentional. Thanks for that :). I have
> modified the code now, removed allocRott() and using addChild(NULL, i)
> instead, so I think the problem is gone.
>
>
> int main(void)
> {
What value does the following line initialize the tree with?
>> On Wed, 10 Jan 2018 13:58:12 +0100, Manfred wrote:
>
>> It means that you were adding ROOT_NODE (i.e. number 5) in the
>> allocRoot() call, and then twice in the first 'for' iteration of
>> addChild().
>> I pointed it out because from your code it did not look like this was
>> intentional.
>
> Oh, that's correct. It was not intentional. Thanks for that :). I have
> modified the code now, removed allocRott() and using addChild(NULL, i)
> instead, so I think the problem is gone.
>
>
> int main(void)
> {
> struct node* rootNode = addChild(NULL, ROOT_NODE);
> int i, j;
>
> for(i = j = ROOT_NODE; i<=TOTAL_NODES; ++i, --j)
> {
following lines add to the tree?
> addChild(rootNode, i);
> addChild(rootNode, j);
Peter "Shaggy" Haywood
Jan 12, 2018, 3:38:45 PM1/12/18
to
Groovy hepcat arnuld was jivin' in comp.lang.c on Wed, 10 Jan 2018 5:37
pm. It's a cool scene! Dig it.
You're doing fine. You're almost there. You just need a way to record
a pointer to the parent node at each iteration. Just make sure you take
into account that this pointer will be null the first time through the
loop.
--
----- Dig the NEW and IMPROVED news sig!! -----
-------------- Shaggy was here! ---------------
Ain't I'm a dawg!!
pm. It's a cool scene! Dig it.
a pointer to the parent node at each iteration. Just make sure you take
into account that this pointer will be null the first time through the
loop.
--
----- Dig the NEW and IMPROVED news sig!! -----
-------------- Shaggy was here! ---------------
Ain't I'm a dawg!!
0 new messages