Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Binary tree implementation in C question as found in K&R

So I've been reading through the K&R C book and have a question.. in the 6th Chapter on structs on page 140-141, there is code that looks like this (I took out some of the more irrelevant parts)

/*
the program loops through a tree looking for some word
if it finds the word itll incremenet the count by 1 
if it doesnt itll add a new node
*/

 struct node {
    char *word;
    int count;
    struct node *left;
    struct node *right;
}

 main() {
    struct node *root;
    char word[1000];

    root = NULL;
    while(getword(word, MAXWORD) != EOF) /* getword just grabs 1 word at a time from a file of words */
        if(isalpha(word[0])) /* isalpha checks to see if it is a valid word */
            root = addNode(root, word);

    treeprint(root); /* prints the tree */
    return 0;
}

struct node *addNode(struct node *p, char *w) {
    int cond;

    if(p == NULL) {
        p = malloc(sizeof(struct node)); /* allocates memory for the new node */
        p -> word = strdup(w);
        p -> count = 1;
        p -> left = p -> right = NULL;
    }

    else if ((cond = strcmp(w, p -> word)) == 0)
        p -> count++;

    else if(cond < 0)
        p -> left = addNode(p -> left, w);

    else
        p -> right = addNode(p -> right, w);

    return p;
}

And my confusion is in the main() function at root = addNode(root, word)

If addNode returns a pointer to the newly added node (or to the node that word is at if its already int he tree), wouldn't that "lose" all the data above the tree? Shouldn't root stay as the root of the tree?

Thanks!

like image 287
adelbertc Avatar asked Jul 03 '11 07:07

adelbertc


People also ask

How to implement a binary tree in C?

A binary tree is called Full binary tree when each node of the tree has two children except the leafs (external nodes). Similarly like Linked Lists, you can implement a binary tree in C. We use structures to implement a binary tree in C. 1. Declaration of a binary tree:- First, you have to declare it before implementing it.

What is a special type of binary tree?

Special type of Binary Tree where every parent node or an internal node has either 2 or no child nodes. A Binary tree in which each internal node has exactly two children and all leaf nodes at same level. It is same as Full Binary Tree, but all leaf nodes must be at left and every level must have both left and right child nodes.

What is the difference between binary tree and leaf tree?

It is same as Full Binary Tree, but all leaf nodes must be at left and every level must have both left and right child nodes. And the last leaf node should not have the right child. It is the Binary Tree having a single child i.e. either left node or right node.

What is a binary search tree (BST)?

A binary search tree (BST) is a special type of binary tree in which each internal node contains a key. For a binary search tree, the rule is: a) A node can have a key that is greater than all the keys in the node’s left subtree. b) A node can have a key that is smaller than all the keys in the node’s right subtree.


1 Answers

root is always staying as root of the tree. root is passed as the first parameter of addNode which will only malloc if that is NULL, i.e. when root is passed for the first time. In later calls it won't change root, will only modify count, left or right. Note that in recursive addNode calls p is not passed, rather it's left or right child is passed. Try to go through the tree with a paper and pencil/pen and you will realize how the nodes are getting added.

like image 98
taskinoor Avatar answered Sep 27 '22 23:09

taskinoor