1

There seems to be no problem in the insertion process, but only the root node is output when printing. What is the problem? text error

  1. n = (node*)m(sizeof(node))
  2. print , scan

Data structure, tree

    struct node {
    int data;
    node* l, *r;
};

node* Insert(node* st, int item)
{
    node* n, * p; p = st;
    n = (node*)m(sizeof(node));
    n->data = item; n->l = NULL; n->r = NULL;

    if (st == NULL) {
        return n;
    }

    while (p != NULL) {
        if (p->data > item) {
            p = p->l;
        }
        else p = p->r;
    }
    p = n;

    return st;

}

node* st = NULL;
    node* a = NULL;
    while (1) {
        print("\n트리 1)삽입 2)삭제 3)전위순회 출력 4) 종료 "); scan("%d", &menu);
        if (menu == 4) break;

        switch (menu) {
        case 1:
            print("삽입할 값 입력 : "); scan("%d", &item);
            st = Insert(st, item);
            break;
        case 2:
            a = st;
            print("%d", a->data); a = a->l; print("%d", a->data); a = st->r; print("%d", a->data);
            break;
bombo
  • 47
  • 5
  • 1) n = (node*)m(sizeof(node)) -> n=(node*)malloc(sizeof(node)) 2) print -> printf , scan -> scanf – bombo Dec 18 '20 at 10:59
  • If you get a syntax error reported by your compiler, please show the exact message. – Gerhardh Dec 18 '20 at 11:03
  • No. There are no syntax errors caused by the compiler. When the code was uploaded to stackoverflow, an error occurred in typedef, variable name, etc. – bombo Dec 18 '20 at 11:06
  • You mean that "I don't know why that syntax is an error on here" is not related to a compilation error? – Gerhardh Dec 18 '20 at 11:08
  • Sorry, Main Question is "There seems to be no problem in the insertion process, but only the root node is output when printing. What is the problem?" – bombo Dec 18 '20 at 11:15
  • 1
    If there are no syntax errors, then why do you mention a syntax error in your question?? Please [edit] and make that clear – Jabberwocky Dec 18 '20 at 11:20
  • 1
    Do you **really** have a macro `m` to replace `malloc` and `print` ro replace `printf`? That is asking for trouble. Lots of trouble. – Gerhardh Dec 18 '20 at 11:25
  • Your code is not a [MCVE](https://stackoverflow.com/help/mcve) Please add the missing code to allow us compiling the relevant code. – Gerhardh Dec 18 '20 at 11:26

1 Answers1

1

Setting aside the syntax and style issues, I noticed a logical error in your Insert function. It appears you're implementing a binary search tree and you are walking the tree correctly. However, you're not actually inserting into the tree because the node p does not point into the tree; it's simply a copy of the node.

Consider what happens when we have the below tree:

     1
   /   \
 NULL  NULL

Let's insert 2 into the tree.

Insert(st, 2)
Step 1: p is a COPY of the root of st, which is node 1
     1 ==  p
   /   \
  NULL NULL

Step 2: Because p->data == 1 < 2, we move to the right and hit NULL
     1
   /   \
  NULL NULL == p

Now we assign p to the new node n:
     1
   /   \
  NULL  NULL; p = n

As you can see in the above, we didn't actually link the new node to the root; all we did was traverse to the correct location in the tree, but then assigned the new node n to p, which doesn't actually write into the tree; it just gives p the address of the node pointed to by n. It doesn't actually change the address of the node we'd like to change.

One solution (which seems to be your intention) is to have p be a pointer to a node pointer (node **). You can find more details about double pointers in this answer here.

Below is a visualization if we have p point to each node.

Insert(st, 2)
Step 1: Let p be a pointer to the root of st, which is node 1
     1 <- p
   /   \
  NULL NULL

Step 2: Because (*p)->data == 1 < 2, we move to the right (p = &((*p)->right)) and have *p == NULL
     1
   /   \
  NULL NULL <- p

Now we have p point to to the new node n: *p = n
     1
   /   \
  NULL  n

And have now added n into our tree successfully.
wLui155
  • 604
  • 4
  • 9