BST Tree

This is a discussion on BST Tree within the C++ Programming forums, part of the General Programming Boards category; I am trying to input these values into a BST but I am not sure where to start. Here is ...

  1. #1
    Unregistered
    Guest

    BST Tree

    I am trying to input these values into a BST but I am not sure where to start. Here is what I have:

    client file

    #include<iostream>
    #include<iomanip>
    #include<fstream>
    #include <cctype> // defines isalpha() function

    #include"t.cpp"

    using namespace std;


    int main()
    {

    btree bt;
    int num=0;
    char chr;
    int count=0;

    ifstream fin("input.txt");
    ofstream fout("output1.txt");

    fin>>num;
    fin>>chr;
    while(fin)
    {

    count++;
    fout<<"Step: "<<count<<" "<<"Data Value = "<<num<<" "<<"Activity Signal = "<<chr<<endl;


    fout<<"Preorder Transversal = "<<endl<<endl;
    fout<<"Inorder Transversal = "<<endl<<endl;
    fout<<"Post order Transversal = "<<endl<<endl;
    fout<<"Level by Level Transversal = "<<endl<<endl;
    fout<<"Total Number of nodes = "<<count<<endl<<endl;

    fin>>num;
    fin>>chr;
    }


    return 0;
    }

    Implementation file

    #include "t.h"
    #include <stddef.h> // For NULL

    struct TreeNode {
    char data; // Data member
    NodePtr lLink; // Pointer to left child
    NodePtr rLink; // Pointer to right child
    TreeNode( char, NodePtr, NodePtr ); // Constructor
    };

    TreeNode::TreeNode( /* in */ char someChar,
    /* in */ NodePtr leftPtr,
    /* in */ NodePtr rightPtr )
    //.................................................. ................
    // POST: data == someChar && lLink == leftPtr && rLink == rightPtr
    //.................................................. ................
    {
    data = someChar; lLink = leftPtr; rLink = rightPtr;
    }

    // Private members of CharTree class:
    // NodePtr rootPtr; Pointer to root node

    btree::btree()
    //.................................................. ................
    // POST: rootPtr == NULL
    //.................................................. ................
    {
    rootPtr = NULL;
    }

    bool btree::IsEmpty() const
    //.................................................. ................
    // POST: FCTVAL == (rootPtr == NULL)
    //.................................................. ................
    {
    return (rootPtr == NULL);
    }

    void btree::BuildRoot( /* in */ char someChar )
    //.................................................. ................
    // PRE: rootPtr == NULL
    // POST: rootPtr points to newly allocated node, call it N
    // && N.data == someChar && N.lLink == NULL && N.rLink == NULL
    //.................................................. ................
    {
    rootPtr = new TreeNode(someChar, NULL, NULL);
    }

    NodePtr btree::Root() const
    //.................................................. ................
    // POST: FCTVAL == rootPtr
    //.................................................. ................
    {
    return rootPtr;
    }

    void AppendLeft( /* in */ NodePtr ptr,
    /* in */ char someChar )
    //.................................................. ................
    // PRE: ptr != NULL && Assigned(someChar)
    // POST: ptr->lLink points to newly allocated node, call it LC
    // && LC.data == someChar && LC.lLink == NULL && LC.rLink == NULL
    //.................................................. ................
    {
    ptr->lLink = new TreeNode(someChar, NULL, NULL);
    }

    void AppendRight( /* in */ NodePtr ptr,
    /* in */ char someChar )
    //.................................................. ................
    // PRE: ptr != NULL && Assigned(someChar)
    // POST: ptr->rLink points to newly allocated node, call it RC
    // && RC.data == someChar && RC.lLink == NULL && RC.rLink == NULL
    //.................................................. ................
    {
    ptr->rLink = new TreeNode(someChar, NULL, NULL);
    }

    char Data( /* in */ NodePtr ptr )
    //.................................................. ................
    // PRE: ptr != NULL && Assigned(ptr->data)
    // POST: FCTVAL == ptr->data
    //.................................................. ................
    {
    return ptr->data;
    }

    void Store( /* in */ NodePtr ptr,
    /* in */ char someChar )
    //.................................................. ................
    // PRE: ptr != NULL && Assigned(someChar)
    // POST: ptr->data == someChar
    //.................................................. ................
    {
    ptr->data = someChar;
    }

    NodePtr LChild( /* in */ NodePtr ptr )
    //.................................................. ................
    // PRE: Assigned(ptr)
    // && (ptr != NULL) --> Assigned(ptr->lLink)
    // POST: FCTVAL == NULL, if ptr == NULL
    // == ptr->lLink, otherwise
    //.................................................. ................
    {
    return (ptr==NULL) ? NULL : ptr->lLink;
    }

    NodePtr RChild( /* in */ NodePtr ptr )
    //.................................................. ................
    // PRE: Assigned(ptr)
    // && (ptr != NULL) --> Assigned(ptr->rLink)
    // POST: FCTVAL == NULL, if ptr == NULL
    // == ptr->rLink, otherwise
    //.................................................. ................
    {
    return (ptr==NULL) ? NULL : ptr->rLink;
    }

    bool IsLeaf( /* in */ NodePtr ptr )
    //.................................................. ................
    // PRE: ptr != NULL
    // POST: FCTVAL == (ptr->lLink == NULL && ptr->rLink == NULL)
    //.................................................. ................
    {
    return (ptr->lLink == NULL && ptr->rLink == NULL);
    }

    void DeleteLeaf( /* inout */ NodePtr& ptr )
    //.................................................. ................
    // PRE: Assigned(ptr)
    // POST: *ptr deallocated
    //.................................................. ................
    {
    delete ptr;
    }

    Input file

    85 A
    14 A
    77 A
    46 A
    94 A
    18 A
    89 A
    42 A
    94 A
    75 A
    89 D
    97 A
    10 A
    92 A
    77 D
    90 A
    14 D
    121 A
    42 A
    85 D
    94 D

    How do I start or insert the numbers?

  2. #2
    zen
    zen is offline
    of Zen Hall zen's Avatar
    Join Date
    Aug 2001
    Posts
    1,007
    You need to write a function to tell you if the node you are trying to insert is greater or less than it's parent (where you are inserting it - probably from the root) so you can insert it a left or right child. Then check if there is a node already attached in the position you want to insert it. If there is repeat the process until you find an empty position (recursion can make the code simpler) .

    So if your numbers were entered in the order you have put them

    1) 85 would go into the root.

    2) Check 14 against the root. It's smaller so insert to the left. There's no existing node there so attach.

    3) Check 77 against the root. It's larger so insert to the right. There's no existing node there so attach.

    4) Check 46 against the root. It's smaller so insert to the left. There's a node to the left so compare 46 to the value of this node (14). It's larger so insert to the right. There's no existing node so attach.
    zen

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Interpreter.c
    By moussa in forum C Programming
    Replies: 4
    Last Post: 05-28-2008, 05:59 PM
  2. BST delete again, but this time I think I'm close
    By tms43 in forum C++ Programming
    Replies: 9
    Last Post: 11-05-2006, 05:24 PM
  3. Binary Search Trees Part III
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 16
    Last Post: 10-02-2004, 03:00 PM
  4. Request for comments
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 15
    Last Post: 01-02-2004, 09:33 AM
  5. BST/Red and Black Tree
    By ghettoman in forum C++ Programming
    Replies: 0
    Last Post: 10-24-2001, 10:45 PM

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