Making a linked list from a binary tree using Preorder Traversal

Question

I want to add elements to a Linked List while Preorder Traversaling on a Binary Tree. I do not want to destroy the BT, just make a copy of the elements in a linked list. This is my code snippet.

void Preorder(treeNode *node, Nodelist * head){
    if(node==NULL){
        return;
    }
    //printf("%d\n", node->data);
    head = List_insert(head, node->data);
    Preorder(node->left, head);
    Preorder(node->right, head);
}

Nodelist * List_insert(Nodelist * head, int v)
{
    Nodelist * p = Node_construct(v);
    p->depth = 2222;
    p -> next = head;
    return p;
}

void List_print(Nodelist * head)
{
    while (head != NULL)
    {
        printf("%d ", head -> value);
        printf("%d ", head -> depth);
        printf("\n");
        head = head -> next;
    }
    printf("\n\n");
}

treeNode * Insert(treeNode *node,int data)
{
        if(node==NULL)
        {
                treeNode *temp;
                temp = (treeNode *)malloc(sizeof(treeNode));
                temp -> data = data;
                temp -> left = temp -> right = NULL;
                return temp;
        }

        if(data >(node->data))
        {
                node->right = Insert(node->right,data);
        }
        else if(data < (node->data))
        {
                node->left = Insert(node->left,data);
        }
        return node;

}

int main(int argc, char**argv) {
        treeNode *root = NULL;
        root = Insert(root, 14);
        root = Insert(root, 15);
        root = Insert(root, 4);
        root = Insert(root, 9);
        root = Insert(root, 7);
        root = Insert(root, 18);
        root = Insert(root, 3);
        root = Insert(root, 5);
        root = Insert(root, 16);
        root = Insert(root, 20);
        root = Insert(root, 17); 

        Nodelist * head = NULL;
        Preorder(root, head);
        List_print(head);

    return 0;
}

The above code prints nothing. I think the problem is with the use of head = List_insert(head, node->data); in the preorder function. Any help with be appreciated.

If you wants to modify your BST into Linked list then traverse in postfix order, but that is different matter.. — Grijesh Chauhan
– Grijesh Chauhan, Commented Jan 12, 2013 at 5:09

perreal · Accepted Answer · 2013-01-12 04:25:02Z

2

You are passing NULL to the Preorder as the list head. This is passed by value and you cannot alter the head in the main function this way. Instead define Preorder like this:

void Preorder(treeNode *node, Nodelist **head)

So that you can do:

*head = Linst_insert....

inside the function to modify the list. Of course, you need to call preorder from the main function like this:

Preorder(root, &head);

answered Jan 12, 2013 at 4:25

perreal

98.7k23 gold badges159 silver badges187 bronze badges

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

Comments

Adeel Ahmed · Accepted Answer · 2013-01-12 05:14:18Z

Try this ... hope helps

Nodelist *Preorder(treeNode *node, Nodelist ** tail) { // use name 'tail' instead of 'head' because you are inserting on the tail, but this functions returns head..

    Nodelist *head;

    if(node==NULL){
        return;
    }
    //printf("%d\n", node->data);
    head = List_insert(tail, node->data);
    Preorder(node->left, tail);
    Preorder(node->right, tail);
    return head;
}

Nodelist * List_insert(Nodelist ** tail, int v)
{
    Nodelist * p = Node_construct(v);
    p->depth = 2222;
    p->next = NULL;
    if (!tail) {
        *tail = p;  // (*tail) is NULL, true when first time List_Insert called
    }
    else {
        (*tail)->next = p;
    }
    return p;
}

int main(int argc, char**argv) {
        treeNode *root = NULL;
        root = Insert(root, 14);
        root = Insert(root, 15);
        root = Insert(root, 4);
        root = Insert(root, 9);
        root = Insert(root, 7);
        root = Insert(root, 18);
        root = Insert(root, 3);
        root = Insert(root, 5);
        root = Insert(root, 16);
        root = Insert(root, 20);
        root = Insert(root, 17); 

        Nodelist * head = NULL;
        head = Preorder(root, &head);
        List_print(head);

    return 0;
}

Collectives™ on Stack Overflow

Making a linked list from a binary tree using Preorder Traversal

2 Answers 2

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related