Problems implementing a binary tree

This is a discussion on Problems implementing a binary tree within the C Programming forums, part of the General Programming Boards category; I am not understanding why the following code is not working. I am assuming the problem is in the InsertNode ...

  1. #1
    * noops's Avatar
    Join Date
    Jun 2008
    Posts
    108

    Problems implementing a binary tree

    I am not understanding why the following code is not working. I am assuming the problem is in the InsertNode function.

    Code:
    #include <stdio.h>
    #include <stdlib.h>
    
    typedef struct Node {
    	int value;
    	struct Node* left;
    	struct Node* right;
    } Node;
    
    Node* InitNode(int value);
    void InsertNode(Node* node, Node* newnode);
    void PrintTree(Node* node);
    
    Node* InitNode(int value)
    {
    	Node* node = (Node*)malloc(sizeof(Node));
    	node->value = value;
    	node->left = NULL;
    	node->right = NULL;
    	return(node);
    }
    
    void InsertNode(Node* node, Node* newnode)
    {
    	if (node == NULL)
    	{
    		node = newnode;
    		return;
    	}
    	if (newnode->value < node->value)
    		InsertNode(node->left, newnode);
    	else
    		InsertNode(node->right, newnode);
    }
    
    void PrintTree(Node* node)
    {
    	if (node == NULL)
    		return;
    	PrintTree(node->left);
    	printf(" %3d", node->value);
    	PrintTree(node->right);
    }
    
    int main()
    {
    	Node* root = InitNode(5);
    	Node* left = InitNode(4);
    	Node* right = InitNode(6);
    
    	InsertNode(root, left);
    	InsertNode(root, right);
    
    	PrintTree(root);
    
    	return(0);
    }

  2. #2
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,185
    When you do node=newnode, you are changing the values passed in to the function -- which means that those changes are not reflected in the main program (hence no node is actually inserted). (We've gone around this bit a couple times in the last few days, so read some recent threads.)

  3. #3
    * noops's Avatar
    Join Date
    Jun 2008
    Posts
    108
    My problem stems from assuming by passing a pointer that I can change the location of where the pointer points to. I carried this over from my experience with integers where I would pass in a pointer to the int, modify that, and when the function was done, the changes persisted.

    Apparently, for pointers, I needed to be passing in a pointer to the pointer. It actually does make sense the more I think about it. When passing a value to a function that you want the change to persist you need to pass a pointer to that value (even if it is already a pointer).

    Here is my modified insert function which now works:
    Code:
    void InsertNode(Node** node, Node* newnode)
    {
    	if ((*node) == NULL)
    	{
    		*node = newnode;
    		return;
    	}
    	if (newnode->value < (*node)->value)
    		InsertNode(&(*node)->left, newnode);
    	else
    		InsertNode(&(*node)->right, newnode);
    }

  4. #4
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,304
    Quote Originally Posted by noops View Post
    When passing a value to a function that you want the change to persist you need to pass a pointer to that value (even if it is already a pointer).
    That's exactly it!
    Answering your own questions like that suggests that you have great potential as a software developer.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Tutorial review
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 11
    Last Post: 03-22-2004, 08:40 PM
  2. Binary tree search efficiency
    By ExCoder01 in forum A Brief History of Cprogramming.com
    Replies: 8
    Last Post: 10-23-2003, 10:11 PM
  3. Templated Binary Tree... dear god...
    By Nakeerb in forum C++ Programming
    Replies: 15
    Last Post: 01-17-2003, 01:24 AM
  4. binary tree node structure
    By Kirsten in forum C Programming
    Replies: 2
    Last Post: 04-26-2002, 08:02 PM
  5. read records fron file into a binary tree
    By Kirsten in forum C Programming
    Replies: 1
    Last Post: 04-23-2002, 02:48 PM

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