Trees

This is a discussion on Trees within the C Programming forums, part of the General Programming Boards category; In my program i got the tree to print out side ways. Could someone help me print out the tree ...

  1. #1
    cis
    cis is offline
    Registered User
    Join Date
    Feb 2002
    Posts
    15

    Question Trees

    In my program i got the tree to print out side ways. Could someone help me print out the tree from top to bottom.

    I would like to print it out from top to bottom

    Like this

    ex.
    -----------------------------------------------------

    d
    / \
    b f
    / \ / \
    a c e g

    This is my code.
    ==============================

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

    //Structure Definition
    typedef struct node
    {
    int data;
    struct node *left;
    struct node *right;
    }*bptr;

    bptr root=NULL;


    int EnterRequest();
    void CreateTree(bptr *btree,int item);
    void Inorder(bptr btree);
    void Preorder(bptr btree);
    void Postorder(bptr btree);
    bptr Find(bptr btree,int key);
    void PrintTree(bptr btree,int i);
    bptr Bdelete(bptr btree,int key);
    void ExitPrg();

    int EnterRequest()
    {
    int request;

    printf("\nPlease enter the request\n");
    printf("\n");
    printf("1.CreaetTree\n");
    printf("2.PrintOrderTree\n");
    printf("3.Find a node\n");
    printf("4.PrintTree\n");
    printf("5.Delete a node\n");
    printf("6.Exit\n");
    printf("\n");
    printf("?");
    scanf("%d",&request);
    printf("\n");
    return request;
    }

    void CreateTree(bptr *btree ,int value)
    {
    if(*btree == NULL)
    {
    *btree=(node *) malloc(sizeof(struct node));

    if(*btree != NULL )
    {
    (*btree)->data = value;
    (*btree)->left = NULL;
    (*btree)->right = NULL;
    }
    else
    printf("%d not inserted. No memory available.\n", value);
    }
    else
    if(value < (*btree)->data)
    CreateTree( & ((*btree)->left),value);
    else if(value > (*btree)->data)
    CreateTree( & ((*btree)->right),value);
    else
    printf("(%d dupl.) ",value);
    }

    void Inorder(bptr btree)
    {

    if(btree!=NULL)
    {
    Inorder(btree->left);
    printf("%d ",btree->data);
    Inorder(btree->right);
    }

    }


    void Preorder(bptr btree)
    {
    if(btree!=NULL)
    {
    printf("%d ",btree->data);
    Preorder(btree->left);
    Preorder(btree->right);
    }

    }


    void Postorder(bptr btree)
    {
    if(btree!=NULL)
    {
    Postorder(btree->left);
    Postorder(btree->right);
    printf("%d ",btree->data);
    }
    }


    bptr Find(bptr btree,int key)
    {
    int i=0;
    if(btree==NULL)
    return NULL;
    else
    {
    while(btree->data!=key)
    {

    if(key>btree->data)
    { btree=btree->right;
    i++;
    }
    else
    { btree=btree->left;
    i++;
    }
    }
    }
    if(btree->left||btree->right)
    {
    printf("Value of the node is %d\n", btree->data);
    if(btree->left)
    {
    btree=btree->left;
    printf("And the children of the node is %d\n",btree->data);
    }
    else
    {
    btree=btree->right;
    printf("And the children of the node is %d\n",btree->data);
    }
    }
    else
    {
    printf("%d is a leaf\n",btree->data);
    }

    printf("Which is at the Level %d \n",i);
    return btree;
    }



    void PrintTree(bptr btree,int space)
    {
    int j;

    while(btree!=NULL)
    {
    PrintTree(btree->right,space+3);

    for(j=1;j<space;j++)
    {
    printf(" ");
    }
    printf("%d\n",btree->data);
    btree=btree->left;
    space+=3;
    }
    return;
    }


    bptr Bdelete(bptr btree,int key)
    {
    bptr p1,p2;

    if(!btree)
    return btree;

    if(btree->data==key)
    {
    if(btree->left==btree->right)
    {
    free(btree);
    return NULL;
    }

    else if(btree->right==NULL)
    {
    p1=btree->left;
    free(btree);
    return p1;

    }

    else if(btree->left==NULL)
    {
    p1=btree->right;
    free(btree);
    return p1;
    }
    else
    {
    p1=btree->right;
    p2=btree->right;

    while(p1->left)
    {
    p1=p1->left;
    p1->left=btree->left;
    free(btree);
    return p2;
    }
    }
    }
    if(btree->data<key)
    btree->right=Bdelete((btree->right),key);
    else
    btree->left=Bdelete(btree->left,key);
    return btree;

    }



    void ExitPrg()
    {
    clrscr();
    printf("\nHAVE A NICE DAY!");
    exit(0);
    }



    int main()
    {
    bptr res;

    int item,key,req,space=0,count;

    do
    {
    req=EnterRequest();

    switch(req)
    {
    case 1:
    count=1 ;
    root = NULL;
    srand(time( NULL ));
    while(count <=15 )
    {
    item = rand() %100;
    if(item >= 10)
    {
    CreateTree(&root,item);//calling the CreateTree Fn
    count++;
    }
    }
    Inorder(root);//calling the Inorder Fn inoder to dispaly the
    getch();//values being Inserted
    break;
    case 2:
    printf("\nInorder\n");
    Inorder(root);
    printf("\nPreorder\n");
    Preorder(root);
    printf("\nPostorder\n");
    Postorder(root);
    getch();
    break;
    case 3:
    printf("\nEnter the node to be searched for\n");
    scanf("%d",&key);
    if(key<10||key>100)
    {
    printf("Please Enter an appropriate value\n");
    req=EnterRequest();
    }
    else
    {
    clrscr();
    res=Find(root,key);
    printf("\nThe node is %d",res->data);
    }
    break;
    case 4:
    clrscr();
    printf("\nPrint's The Two-Dimesional Tree\n");
    PrintTree(root,space);
    getch();
    break;
    case 5:
    printf("\nEnter the node to be deleted\n");
    scanf("%d",&key);
    root=Bdelete(root,key);
    getch();
    clrscr();
    Inorder(root);
    break;
    case 6:ExitPrg();
    break;
    }
    } while(req!=6);

    getch();
    return(0);
    }

  2. #2
    cis
    cis is offline
    Registered User
    Join Date
    Feb 2002
    Posts
    15

    This is the code that creates a side view of the binary tree

    void PrintTree(bptr btree,int space)
    {
    int j;

    while(btree!=NULL)
    {
    PrintTree(btree->right,space+3);

    for(j=1;j<space;j++)
    {
    printf(" ");
    }
    printf("%d\n",btree->data);
    btree=btree->left;
    space+=3;
    }
    return;
    }

  3. #3
    Blank
    Join Date
    Aug 2001
    Posts
    1,034
    You can use a queue. The basic method is to do something like

    Code:
    queue q;
    
    q.push(root);
    while(!q.empty()) {
             n = q.pop();
             print(n);
             q.push(n->left);
             q.push(n->right);
    }

  4. #4
    Code Goddess Prelude's Avatar
    Join Date
    Sep 2001
    Posts
    9,796
    A simple if inefficient method is to use a height variable. To simulate a line order traversal, start with the root node (height 0) and print it, then go to the left leaf and increment height. Print the value and return to the root and repeat the process for the right leaf. When you print all possible values in a height level you increment the height variable and print the next line. By only printing the values at a certain height you can print the tree in line order very simply:
    Code:
    Height = 0:        d
    Height = 1:     /     \
    Height = 1:    b       f
    Height = 2:   / \     / \
    Height = 2:  a   c   e   g
    Height = 3: / \ / \ / \ / \
    Height = 3: * * * * * * * *
    -Prelude
    My best code is written with the delete key.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Trees
    By masterg in forum C++ Programming
    Replies: 2
    Last Post: 12-04-2008, 01:42 PM
  2. Binary Search Trees Part III
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 16
    Last Post: 10-02-2004, 04:00 PM
  3. Trees
    By samtay in forum C++ Programming
    Replies: 7
    Last Post: 03-28-2004, 09:35 AM
  4. Binary Trees...
    By SirCrono6 in forum C++ Programming
    Replies: 5
    Last Post: 11-25-2003, 04:54 PM
  5. AVL Trees
    By kwigibo in forum C Programming
    Replies: 2
    Last Post: 04-17-2002, 06:46 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21