trees

[rithish]

hii i finished these topics 1.linked list 2.stack and queues.how much time will it take me to finish trees 1.binary tee 2.avl tree 3.b-tree 4.binary search 5.threaded binary tree??? actualy ill try through linked list will it be easy???

[rithish]

insert(int key, struct node **leaf)
{
    if( *leaf == 0 )
    {
        *leaf = (struct node*) malloc( sizeof( struct node ) );
        (*leaf)->key_value = key;
        /* initialize the children to null */
        (*leaf)->left = 0;    
        (*leaf)->right = 0;  
    }
    else if(key < (*leaf)->key_value)
        {
            insert( key, &(*leaf)->left );
        }


    else if(key > (*leaf)->key_value)
    {
        insert( key, &(*leaf)->right );
    }
}

this is a insertion coding for binary trees. i have a confusion in insertion where

else if(key < (*leaf)->key_value)
            {
                insert( key, &(*leaf)->left );
            }


        else if(key > (*leaf)->key_value)
        {
            insert( key, &(*leaf)->right );
        }
    }

where if a element is less than root value is kept in left node and greater is kept in right side.but code confuses me bcoz in linked list if we insert a new node it will b like this

*last;
newnode=malloc(size of(struct node);
last->link=newnode;
last=last->link;

but this code i dont understand wats happening

[rithish]

my question is how the key value gets inserted in node?????????????please some one help i understand the concept but difficult to implement it through linked list couldn't understand properly

[Gonbe]

It does it recursively. It goes down the correct path until it reaches the correct position. (at which point *leaf will be NULL)

You seem to implement a binary search tree although you cannot insert the same value more than once. I do not know if this is desired but for the example below I assume that this is a mistake and values equal to the root are pushed down the right side.

Say you have the following tree:

        5
       /  \
      3    8
      /\   /\
     2 4  6  9
    /      \
   1        7

And you want to insert another 4. Your function will first attempt to insert it into the tree as a whole. The supplied node dereferenced is not 0 and 4 < 5 meaning it is inserted into the left section. So basically the problem is reduced to inserting the key into the following tree:

      3    
      /\  
     2 4
    /    
   1    

The function is called again, but now 4 >= 3 so 4 is inserted to the left side. Reducing the problem to inserting 4 into the following tree:

4

Again the right side of this node is taken as 4 >= 4. it does not have any children however so the memory address contains a NULL pointer. So now the problem is reduced to inserting 4 into this following tree:

<none>

This is the recursion base case and a new node is constructed for the key on the supplied memory adres which currently contains a NULL pointer. After creation the total tree would look like:

        5
       /  \
      3    8
      /\   /\
     2 4  6  9
    /   \  \
   1     4  7

Regarding your first question: I cannot tell how long it takes you to implement the other trees as I don't know you. The most difficult one you mentioned is the AVL-Tree where you sometimes have to do multiple rotations in order to maintain the properties of that tree. The other trees are relatively easy.

[rithish]

ok i udentified wer my problem is and wer i got struck.actually i didnt understand full concepts of recursion please some one explain or give me a link for easy understanding.ok ill illustrate where my problem is now.have a look at towers of hanoi problem

    #include<stdio.h>
    #include<conio.h>
    #include<math.h>
    void hanoi(int x, char from,char to,char aux)
    {
    if(x==1)
    {
    printf("Move Disk From %c to %c\n",from,to);
    }
    else
    {
    hanoi(x-1,from,aux,to);
    printf("Move Disk From %c to %c\n",from,to);
    hanoi(x-1,aux,to,from);
    }
    }
    void main()
    {
    int disk;
    int moves;
    clrscr();
    printf("Enter the number of disks you want to play with:");
    scanf("%d",&disk);
    moves=pow(2,disk)-1;
    printf("\nThe No of moves required is=%d \n",moves);
    hanoi(disk,'A','C','B');
    getch();
    }

here my problem is over here

hanoi(x-1,from,aux,to);
printf("Move Disk From %c to %c\n",from,to);
hanoi(x-1,aux,to,from);

the recursion i dont understand please give me a link to understand or explain

[rithish]

but recursion using stack i understand but i dont understand these kind of recursions like tis

    insert(int key, struct node **leaf)
    {
    if( *leaf == 0 )
    {
    *leaf = (struct node*) malloc( sizeof( struct node ) );
    (*leaf)->key_value = key;
    /* initialize the children to null */
    (*leaf)->left = 0;
    (*leaf)->right = 0;
    }
    else if(key < (*leaf)->key_value)
    {
    insert( key, &(*leaf)->left );
    }
    else if(key > (*leaf)->key_value)
    {
    insert( key, &(*leaf)->right );
    }
    }

[Gonbe]

I'm not sure what there is not to understand about it. You start with a bigger problem then you express that into a smaller problem until you reach a base case.

The base case here would be reaching a node that is null and reducing the problem happens because insert(n) would reduce to either insert(left-child-of-n) or insert(right-child_of-n) if n is not null which is always a smaller problem.

[rithish]

void inorder(struct tree *p)
{
if(p!=NULL)
{
inorder(p->lchild);
printf("%d ",p->data);
inorder(p->rchild);
}
}

for example over here inorder traversal step by step ill say wat ever i understand
1.initially it will be in d root node it keeps on traversing
2.the function inorder(p->lchild); executes and confusion is over here it will be keep on executing at a stage p will be null and print the data.
3.how can this inorder(p->rchild); execute bcoz now pointer will be last left node and how it will point to right node tats my problem

[rithish]

ok gonbe u may leave this topic jus explain or give me link to understand these kind of recursions

void inorder(struct tree *p)
{
if(p!=NULL)
{
inorder(p->lchild);
printf("%d ",p->data);
inorder(p->rchild);
}
}

[Gonbe]

That function prints the elements of the tree from low to high. Try to not think about what happens in the recursion but think of it as reducing the problem.

If basically says this:

If you have a node to look at:

1. First print it's left subtree in order.
2. then print the current node
3. Finally print it's right subtree in order.

This will result in a sorted output because everything left is smaller than the node's value and everything to the right is bigger or equal. The "p!=NULL" condition ensures it performs no more recursive calls when you don't have a node anymore.

If you want a more non-recursive viewing point you could replace the recursive calls with their definitions. Say you call "inorder" with this tree: (So '5' is the node you pass)

        5
       /  \
      3    8
      /   
     2

I will write this as:

inorder(5-3-8-2)

The definition for that would be (excluding the stop condition):

inorder(3-2);
print 5
inorder(8);

The first inorder call would result in:

inorder(2);
print 3

(There is no right, so it would result in a recursive call with a NULL parameter which wouldn't do anything so I omit it here)

Replacing that in what we had we have:

inorder(2);
print 3
print 5
inorder(8);

Both the remaining "inorder" calls do not have any children so their recursive calls wouldn't do anything so these would just print their number. So now we have:

print 2
print 3
print 5
print 8

Which is what we wanted. The values present in the binary search tree, ordered from lowest till biggest.

-edit-

About links, you should be able to find them yourself as it's a very widely documented topic. There's also not that much to understand about it, you just need to master the way of thinking about problems, I guess. If you want some practice at it maybe try programming in a functional language such as Haskell.

[rithish]

ok but how does a pointer know that the node has been visited tats my doubt here while using recursion?????

[Gonbe]

It doesn't need to know because solving a big problem is solved by solving subproblems in recursion. You might get confused because there's a print statement between two recursive calls.

Try to visualize what the recursive steps look like. For example:

inorder(p->lchild);

When would this recursive call print something? The first print statement would take place on the lowest node in the tree because every recursive call makes this call before printing it's node value and then processing the right side.