![]() |
| | #1 |
| Registered User Join Date: Apr 2009
Posts: 48
| Inserting a node in a binary tree with a field for the parrent If I define a node like this Code: typedef struct treenode
{
int id;
struct node *Left, *Right;
} node;
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);
}
}
Code: typedef struct treenode
{
int id;
struct node *Left, *Right, *Dad;
} node;
please can someone help me Last edited by budala; 09-18-2009 at 10:51 AM. |
| budala is offline | |
| | #2 |
| and the Hat of Guessing Join Date: Nov 2007
Posts: 8,740
| 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. |
| tabstop is offline | |
| | #3 |
| Registered User Join Date: Apr 2009
Posts: 48
| 1. obviously I don't know 2. would you mind helping me a bit more? |
| budala is offline | |
| | #4 |
| and the Hat of Guessing Join Date: Nov 2007
Posts: 8,740
| 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. |
| tabstop is offline | |
| | #5 |
| Registered User Join Date: Oct 2008 Location: TX
Posts: 1,262
| 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. |
| itCbitC is offline | |
![]() |
| Tags |
| binary, node, parent, tree |
| Thread Tools | |
| Display Modes | |
|
Similar Threads | ||||
| Thread | Thread Starter | Forum | Replies | Last Post |
| Balancing A Binary Tree | mike_g | C Programming | 5 | 08-12-2008 04:01 PM |
| arrays vs lists? And containers in general! | clegs | C++ Programming | 22 | 12-03-2007 02:02 PM |
| Binary Search Trees Part III | Prelude | A Brief History of Cprogramming.com | 16 | 10-02-2004 03:00 PM |
| Big help in Astar search code... | alvifarooq | C++ Programming | 6 | 09-24-2004 11:38 AM |
| Binary Tree Search | C++Newbie | C++ Programming | 5 | 03-22-2002 12:38 PM |