Binary Tree implementation on C

Question

I am trying to implement tree in C but the thing is whenever i try to traverse it, it only shows the first three nodes of the tree and the rest are lost. like, if i enter 100, 200, 300, 400, 500, 600, 700 then only 100 ,200, 300 will be in the output. I think the problem is with insert function but i just can't figure it out.

#include<stdio.h>
#include<stdlib.h>
struct node
{
    int data;
    struct node *prev;
    struct node *next;
};
typedef struct node list;
list *head, *tail, *current, *newn;
void inorder(struct node *t)
{
    if(t != NULL)
    {

        inorder(t->prev);
        printf("%d->",t->data);
        inorder(t->next);
    }
}

struct node * insert(int key, struct node *t)
{
    if(t == NULL)
    {
        t = (list*)malloc(sizeof(list));
        t->data = key;
        t->prev = NULL;
        t->next = NULL;
    }
    else if(t->prev == NULL)
    {
        t->prev = insert(key,t->prev);
    }
    else if(t->next == NULL)
    {
        t->next = insert(key,t->next);
    }
    return(t);
}
int main()
{
    int x=1, y, z=1;
    current = (list*)malloc(sizeof(list));
    printf("Enter data:");
    scanf("%d",&current->data);
    current->next = NULL;
    current->prev = NULL;
    head = current;
    while(z == 1)
    {
        printf("Enter data:");
        scanf("%d",&y);
        current = insert(y,current);
        printf("want to insert more:");
        scanf("%d",&z);  
    }
    printf("\nInorder Traversal:");
    newn = head;
    inorder(newn);

}

Scanf (especially without checking the return value) is dangerous (http://sekrit.de/webdocs/c/beginners-guide-away-from-scanf.html). Try an experiment by hardcoding some ten node values instead of using scanf for them. Otherwise (agreeing with @lurker) https://ericlippert.com/2014/03/05/how-to-debug-small-programs/ and https://stackoverflow.com/questions/2069367/how-to-debug-using-gdb — Yunnosch, Aug 21 '17 at 21:00
Your `insert` isn't added when `root` has two non-`NULL` child elements. — BLUEPIXY, Aug 21 '17 at 21:04
You need to add processing if it is not `NULL` (`t->prev != NULL`, `t->next != NULL`). Or how about simply implementing a binary search tree? — BLUEPIXY, Aug 21 '17 at 21:08
@BLUEPIXY can you elaborate your answer or explain it more clearly, and i do't want to implement a binary search tree right now. — TrustTyler, Aug 21 '17 at 21:17
The thing that I first thought to work. but probably not good. I think for a while. Please give me some time. — BLUEPIXY, Aug 21 '17 at 21:27
@BLUEPIXY thanks a lot man! although i wanted it to be like the way i am already working on it but i just realized that a complete binary can't be implemented like this and will need balancing at the end. So, just write this as answer and i'll accept it. — TrustTyler, Aug 22 '17 at 08:28
It seems incredible to me that you'd have a binary tree node that has child nodes called `next` and `prev`. Typically they're called `right` and `left`. Calling them `next` and `prev` assumes that it's a binary search tree, and in that case the `prev` node isn't necessarily the in-order predecessor, but rather some node whose value is less than the parent node's value. — Jim Mischel, Aug 22 '17 at 17:14

score 2 · Accepted Answer · answered Aug 22 '17 at 10:34

only 100 ,200, 300 will be in the output.

at Insert function

if(t == NULL)
{
    ...
}
else if(t->prev == NULL)
{
    ...
}
else if(t->next == NULL)
{
    ...
}
return(t);

Because it is When t, t->prev and t->next are not all NULL Nothing (that is, inserting) is done.

When adding conditions and recursive calls like

else if(t->prev->prev == NULL)
{
    t->prev->prev = insert(key, t->prev->prev);
}

Insertion of the node is done, but since growth becomes like depth-first search, the growth of the tree becomes biased.
So, as an approach you need to search for the next insertion point like breadth first search.
I think there are some methods, As a method I propose, it is a way to keep it as a pool when creating a NULL node rather than searching.
A concrete implementation using a queue as a node pool is as follows(Please note that many checks are omitted And using global variables).

#include <stdio.h>
#include <stdlib.h>

struct node{
    int data;
    struct node *prev;
    struct node *next;
};
typedef struct node list;

void inorder(struct node *t){
    if(t != NULL){
        inorder(t->prev);
        printf("%d->",t->data);
        inorder(t->next);
    }
}
//node of queue 
typedef struct null_node {
    list **nodepp;
    struct null_node *next;
} node_pool;
//queue 
typedef struct queue {
    node_pool *head;
    node_pool *tail;
} queue;
//enqueue 
void push(queue *q, list **nodepp){
    node_pool *np = malloc(sizeof(*np));
    np->nodepp = nodepp;
    np->next = NULL;
    if(q->head == NULL){
        q->tail = q->head = np;
    } else {
        q->tail = q->tail->next = np;
    }
}
//dequeue 
list **pop(queue *q){
    node_pool *head = q->head;
    if(head == NULL)
        return NULL;

    q->head = q->head->next;
    if(q->head == NULL)
        q->tail = NULL;
    list **nodepp = head->nodepp;
    free(head);
    return nodepp;
}

void clear_queue(queue *q){
    while(pop(q));
}

list *Head;
queue Q;

struct node *insert(int key, struct node *root){
    list *t = malloc(sizeof(*t));
    t->data = key;
    t->next = t->prev = NULL;
    push(&Q, &t->prev);//enqueue a NULL node
    push(&Q, &t->next);

    if(root == NULL){
        return t;
    }
    list **null_nodep = pop(&Q);//dequeue the node
    *null_nodep = t;//Replace with new node
    return root;
}
int main(void){
    int /*x=1, unused x*/ y, z=1;

    Head = NULL;
    while(z == 1){
        printf("Enter data:");
        scanf("%d",&y);
        Head = insert(y, Head);
        printf("want to insert more:");
        scanf("%d",&z);  
    }
    printf("\nInorder Traversal:");
    inorder(Head);
    clear_queue(&Q);//Discard queued nodes
}

Binary Tree implementation on C

1 Answers1