Ordered Binary Tree insert

Question

I have a problems in this code below, it's a part of a program for ordered binary trees. The problem is that when I enter numbers in the input, some elements are just lost and it happens all the times. I looked at the code and can't figure out why that happens. Can you help me out with this? Thanks.

void insert_ord(int number, struct treenode *currentNode){
   if(currentNode->flag == 0){
      currentNode->number = number;
      currentNode->flag = 1;                  
   }
   else{
      if(number <= currentNode->number){
         if(currentNode->left != NULL) insert_ord(number, currentNode->left);
         else {
            struct treenode *store = (struct treenode *)malloc(sizeof(struct treenode));
            currentNode->left = store;
            store->number = number;
            store->left = store->right = NULL;
            store->prev = currentNode;
         }
      }
      if(number > currentNode->number){
         if(currentNode->right != NULL) insert_ord(number, currentNode->right);
         else {
            struct treenode *store = (struct treenode *)malloc(sizeof(struct treenode));
            currentNode->right = store;
            store->number = number;
            store->left = store->right = NULL;
            store->prev = currentNode;
         }
      }
   }
}

"I have a problems in this code below, it's a part of a program for ordered binary trees." - the 'ordered' part is superfluous — Mitch Wheat
– Mitch Wheat, Commented Jun 6, 2011 at 2:04
@Mitch Wheat: no, a binary heap is not ordered in the sense I think you mean. You can also use a binary tree as a "concatenation structure", where the values at the vertices are not ordered in any way. — Rafe
– Rafe, Commented Jun 6, 2011 at 2:05
@Mitch: sorry, I assumed from your question you were assuming binary trees to be totally ordered. A heap is partially ordered and a concatenation tree is unordered. — Rafe
– Rafe, Commented Jun 6, 2011 at 6:49

caf · Accepted Answer · 2011-06-06 02:06:26Z

2

You aren't setting store->flag for the newly inserted nodes. Presumably it should be set to 1.

You should also restructure your code so that the new node creation isn't duplicated - the easiest way to do this with your current code is to separate that out into a new function:

struct treenode *new_node(struct treenode *parent, int number)
{
    struct treenode *store = malloc(sizeof(struct treenode));

    if (store) {
        store->number = number;
        store->left = store->right = NULL;
        store->prev = parent;
        store->flag = 1;
    }

    return store;
}

Then your insertion code just becomes:

if (currentNode->left)
    insert_ord(number, currentNode->left);
else
    currentNode->left = new_node(currentNode, number);

(and similar for the right node).

edited Jun 6, 2011 at 2:06

answered Jun 6, 2011 at 2:01

caf

241k42 gold badges344 silver badges479 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

Rafe · Accepted Answer · 2011-06-06 02:13:34Z

0

malloc returns uninitialised memory and you are not intialising the flag field of your malloced structures.

answered Jun 6, 2011 at 2:13

Rafe

5,3353 gold badges26 silver badges26 bronze badges

2 Comments

Mitch Wheat Over a year ago

isn't this essentially what @Caf posted some 13 minutes earlier?

Rafe Over a year ago

@Mitch, pretty much. I didn't see Caf's reply when I hit submit.

Collectives™ on Stack Overflow

Ordered Binary Tree insert

2 Answers 2

Comments

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related