Thread: BST Tree

  1. #1
    Unregistered
    Guest

    BST Tree

    How can I check to see if my program is building the tree correctly? I eventually want to
    add a preOrder() function, inOrder() function, postOrder() function, and a levelOrder()
    function transversals.

    #include<iostream>
    #include<iomanip>
    #include<fstream>
    #include <cctype> // defines isalpha() function
    #include<string>
    #include"TreeImplementation.cpp"

    using namespace std;


    int main()
    {

    node structnode;

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

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

    fin>>num;
    fin>>chr;
    while(fin)
    {
    bt.insert(num);
    bt.search(num);
    fout<<num;
    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;
    }

    #include"Treeheader.h"


    //Constructor
    ///////////////////////////////////////////////////////////////////////
    btree::btree()
    {
    root=NULL;
    }


    ///////////////////////////////////////////////////////////////////////
    /*btree::~btree()
    {
    destroy_tree(root);
    }
    */
    //Destriy tree function
    //////////////////////////////////////////////////////////////////////
    void destroy_tree(node *leaf)
    {
    if(leaf!=NULL)
    {
    destroy_tree(leaf->left);
    destroy_tree(leaf->right);
    delete leaf;
    }
    }

    //Insert Tree
    //////////////////////////////////////////////////////////////////////
    void btree::insert(int key, node *leaf)
    {
    if(key< leaf->key_value)
    {
    if(leaf->left!=NULL)
    insert(key, leaf->left);
    else
    {
    leaf->left=new node;
    leaf->left->key_value=key;
    leaf->left->left=NULL; //Sets the left child of the child node to null
    leaf->left->right=NULL; //Sets the right child of the child node to null
    }
    }
    else if(key>=leaf->key_value)
    {
    if(leaf->right!=NULL)
    insert(key, leaf->right);
    else
    {
    leaf->right=new node;
    leaf->right->key_value=key;
    leaf->right->left=NULL; //Sets the left child of the child node to null
    leaf->right->right=NULL; //Sets the right child of the child node to null
    }
    }
    }


    ///////////////////////////////////////////////////////////////////////

    node *btree::search(int key, node *leaf)
    {
    if(leaf!=NULL)
    {
    if(key==leaf->key_value)
    return leaf;
    if(key<leaf->key_value)
    return search(key, leaf->left);
    else
    return search(key, leaf->right);
    }
    else return NULL;
    }


    ///////////////////////////////////////////////////////////////////////

    void btree::insert(int key)
    {
    if(root!=NULL)
    insert(key, root);
    else
    {
    root=new node;
    root->key_value=key;
    root->left=NULL;
    root->right=NULL;
    }
    }


    //////////////////////////////////////////////////////////////////////

    node *btree::search(int key)
    {
    return search(key, root);
    }


    ///////////////////////////////////////////////////////////////////////

    /*void btree::destroy_tree(node *root)
    {
    if(root != NULL)
    destroy_tree(
    destroy_tree(root);
    }
    */

  2. #2
    Unregistered
    Guest
    Create a counter variable in your node struct or class and increment it as necessary for each child down the tree, then when you print the tree you can see if it was built properly by printing out that variable as well.

  3. #3
    Unregistered
    Guest
    I have never heard of a counter value in a struct or class.

  4. #4
    of Zen Hall zen's Avatar
    Join Date
    Aug 2001
    Posts
    1,007
    If you just want to know to check it's working properly you could run it through a debugger and watch where it is attaching the nodes.
    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, 06: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, 10:33 AM
  5. BST/Red and Black Tree
    By ghettoman in forum C++ Programming
    Replies: 0
    Last Post: 10-24-2001, 10:45 PM