Getting the parent of a node in a binary tree

This is a discussion on Getting the parent of a node in a binary tree within the C Programming forums, part of the General Programming Boards category; I need help with defining a node and inserting it in a binary tree. If I define a node like ...

  1. #1
    Registered User
    Join Date
    Apr 2009
    Posts
    74

    Inserting a node in a binary tree with a field for the parrent

    I need help with defining a node and inserting it in a binary tree.

    If I define a node like this

    Code:
    typedef struct treenode
    {
    	int id;
    	struct node *Left, *Right;
    } node;
    then I have no problem with insertion.

    Code:
    node* NewNode(int id)
    {
    	node *new = malloc(sizeof(node));
    	
    	new->id = id;
    	new->Left = NULL;
    	new->Right = NULL;
    	
    	return (new);
    }
    
    void Insert (node **root, int id)
    {
    	node *temp = *root;
    	if (temp == NULL) *root = NewNode(id);
    	else
    	{
    		if (temp->id == id) printf("DUPLICATE!!!");
    		else if (temp->id < id) Insert(&temp->Right, id);
    		else Insert(&temp->Left, id);
    	}
    }
    But I need a pointer to the parent of each node. so it should be defined like this
    Code:
    typedef struct treenode
    {
    	int id;
    	struct node *Left, *Right, *Dad;
    } node;
    and this is where the problems start.

    1. I don't know how to initialize the tree because it seems to me that the root should be initialized beforehand and then I would have problems with the line in Insert() if (temp == NULL) *root = NewNode(id);
    2. I don't know how to keep track of the recursive calls so I don't know how to link the new node with the parent


    please can someone help me
    Last edited by budala; 09-18-2009 at 10:51 AM.

  2. #2
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,185
    1. Why would that be a problem? Why would you want to initialize the root beforehand?

    2. Your tree-walking code needs to take account of the fact that the parent of the node is needed and "remember" it as it goes down. If you are doing this recursively, then you need another variable in your function call.

  3. #3
    Registered User
    Join Date
    Apr 2009
    Posts
    74
    1. obviously I don't know
    2. would you mind helping me a bit more?

  4. #4
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,185
    2. Without actually typing the entire code, I doubt it. You need to, when you insert a node, set a parent node pointer to the child (this is done for you by the fact that you pass the address of ->Left or ->Right to the function recursively) and you need to set the parent pointer in the child node, which means you need to be holding onto a pointer to the parent as you walk the tree. So you will need, not just a "where are we now" pointer (your root in the current example) but also a "where did we come from" pointer.

  5. #5
    Registered User
    Join Date
    Oct 2008
    Location
    TX
    Posts
    2,047
    So what is so hard about the advice tabstop gave you. Invoke NewNode() with two arguments; the second argument being the parent of the new node.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Binary Tree Search
    By C++Newbie in forum C++ Programming
    Replies: 7
    Last Post: 04-05-2011, 01:17 AM
  2. Balancing A Binary Tree
    By mike_g in forum C Programming
    Replies: 5
    Last Post: 08-12-2008, 04:01 PM
  3. arrays vs lists? And containers in general!
    By clegs in forum C++ Programming
    Replies: 22
    Last Post: 12-03-2007, 01:02 PM
  4. Binary Search Trees Part III
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 16
    Last Post: 10-02-2004, 03:00 PM
  5. Big help in Astar search code...
    By alvifarooq in forum C++ Programming
    Replies: 6
    Last Post: 09-24-2004, 11:38 AM

Tags for this Thread


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