#1
  1. No Profile Picture
    Junior Member
    Devshed Newbie (0 - 499 posts)

    Join Date
    Sep 2003
    Posts
    1
    Rep Power
    0

    Angry binary search trees AGAIN!


    hi all, new to this forum! just wondering if u can help me out with a bit of code im workin on! may look a bit messy but im workin on it!

    #include <iostream>
    #include <string>
    #include <fstream>
    #define MAXSIZE 50

    using namespace std;

    // class for the order
    struct Order {
    int OrderNumber;
    int QoO;
    int RecNum;
    string CName;
    string DoO;
    string PCode;
    string OrDes;
    string DDA;
    string Stat;


    };

    Order Ord[MAXSIZE];

    // class for the tree
    typedef struct {
    string dataItem;
    int left, right;
    int label;
    } treeNode;




    treeNode tree[MAXSIZE];

    int nextfree, root, size;
    int xx = root;
    string CheckName;
    //string Delete;
    int RN=0;
    int flag=0;

    void init()
    {
    nextfree=0;
    root = -1;
    size = 0;

    for(int i=0;i<MAXSIZE; i++)
    {
    tree[i].left = i+1;
    tree[i].right = i+1;
    }
    tree[MAXSIZE-1].left = -1;
    tree[MAXSIZE-1].right = -1;
    }


    void BuildTree();
    void UpdateTree();
    void AddRec();
    void RemoveRec();
    void ViewRec();
    void BuildDb();
    void UpdateDb();
    void RemoveFromDb();
    void SearchDb();
    void displayrecords();

    int SearchTree();
    void init();

    // check whether tree is full
    bool isFull()
    { return (size == MAXSIZE); }

    // check whether tree is empty
    bool isEmpty()
    { return (size == 0); }

    void main()
    {
    int choice = 0;
    init();
    while (choice !=4)
    {
    cout << "\nMain Menu:\n1: Add Order.\n2: Remove Order.";
    cout << "\n3: Check Status of Order .\n4: show all records.\n5:Exit\n\n\n";
    cin >> choice;
    cin.get();

    switch (choice)
    {
    case 1 : AddRec();
    break;

    case 2 : RemoveRec();
    break;

    case 3 : ViewRec();
    break;
    case 4: displayrecords();
    break;

    case 5: cout << "\n\n Exit Selected.\n\n";
    break;

    default : cout << "\nInvalid Selection,\nPlease choose again\n\n";
    }
    }

    }

    void AddRec()
    {
    ifstream path1;
    path1.open("OrderTrack.txt",ios::in);
    RN = 1;
    while (!path1.eof())
    {
    // cout << Ord[RN].RecNum;
    // Ord[RN].RecNum = RN;
    //RN ++;


    Ord[RN].RecNum = RN;
    cout << "\nEnter Order Number:";
    cin >> Ord[RN].OrderNumber;
    cout << "\nEnter Client Name:";
    cin >> Ord[RN].CName;
    cout << "\nEnter Date of Order:";
    cin >> Ord[RN].DoO;
    cout << "\nEnter Product Code:";
    cin >> Ord[RN].PCode;
    cout << "\nEnter Order Description:";
    cin >> Ord[RN].OrDes;
    cout << "\nEnter Delivery Date Agreed:";
    cin >> Ord[RN].DDA;
    cout << "\nEnter Quantity Ordered:";
    cin >> Ord[RN].QoO;
    cout << "\nEnter Status:";
    cin >> Ord[RN].Stat;


    BuildDb();
    BuildTree();
    main();
    }
    cout << Ord[RN].RecNum;
    Ord[RN].RecNum = RN;
    RN ++;
    }

    void BuildTree()
    {
    if (!isFull())
    {
    //Enter data to be added to the tree
    tree[nextfree].label = Ord[RN].OrderNumber;
    tree[nextfree].dataItem = Ord[RN].CName;
    int newslot = nextfree;
    nextfree = tree[newslot].left;
    tree[newslot].left = -1;
    tree[newslot].right = -1;


    if (isEmpty())
    {
    root = newslot;
    }
    else
    {
    int current = root;
    int parent = current;
    bool goLeft;
    // find which node will be the parent of the new node in the binary search tree
    while (current != -1)
    {
    parent = current;
    if (tree[newslot].dataItem < tree[current].dataItem)
    {
    goLeft = true;
    current = tree[current].left;
    }
    else
    {
    goLeft = false;
    current = tree[current].right;
    }
    }

    // when parent is found get it to point to the new node
    // decide is the parent's left or right node to point to the new node
    if (goLeft)
    tree[parent].left = newslot;
    else
    tree[parent].right = newslot;

    }

    size++;
    }
    else
    cout << "\nIndex is full";
    }

    void ViewRec()
    {


    ifstream path1;


    flag = 0;
    path1.open("OrderTrack.txt",ios::in);
    cout << "\nEnter the Customer name to search for: ";
    cin >> CheckName;
    SearchTree();
    tree[xx].label = RN;
    cout << endl << endl;


    path1 >> Ord[RN].OrderNumber,'*';
    path1 >> Ord[RN].CName,'*';
    path1 >> Ord[RN].DoO,'*';
    path1 >> Ord[RN].PCode,'*';
    path1 >> Ord[RN].OrDes,'*';
    path1 >> Ord[RN].DDA,'*';
    path1 >> Ord[RN].QoO,'*';
    path1 >> Ord[RN].Stat,'*';

    cout << Ord[RN].OrderNumber << "\t" << Ord[RN].CName << "\t" << Ord[RN].DoO << endl;
    cout << Ord[RN].PCode << "\t" << Ord[RN].OrDes << "\t" << Ord[RN].DDA << endl;
    cout << Ord[RN].QoO << "\t" << Ord[RN].Stat << endl;


    if (flag = 100)
    {
    cout << endl << CheckName << " is not in the file\n";
    }

    path1.close();
    cout << endl;

    }


    int SearchTree()
    {
    while (xx=! size)
    {
    if(CheckName == tree[xx].dataItem)
    {
    return tree[xx].label;

    if(CheckName < tree[xx].dataItem)
    {
    xx = tree[xx].left;
    return tree[xx].label;
    }
    else
    {
    xx = tree[xx].right;
    return tree[xx].label;
    }
    }
    else return flag == 100;
    }
    }



    void RemoveRec()
    {
    ifstream path1;
    flag = 0;
    path1.open("OrderTrack.txt",ios::in);
    cout << "\nEnter the Customer name to be removed:";
    cin >> CheckName;
    SearchTree();
    tree[xx].label = RN;





    }

    void BuildDb()
    {
    //Ord[RN].RecNum ++;
    ofstream path1("OrderTrack.txt",ios::app);
    path1 << Ord[RN].RecNum << "*" << Ord[RN].CName << "*" << Ord[RN].DDA << "*" << Ord[RN].DoO<< "*" << Ord[RN].OrDes << "*" << Ord[RN].OrderNumber << "*" << Ord[RN].PCode << "*" << Ord[RN].QoO << "*" << Ord[RN].Stat << endl;
    path1.close();

    }



    void displayrecords()
    {int x=0;
    ofstream path1("OrderTrack.txt",ios::out);
    for(x=0;x=MAXSIZE;x++)
    {


    cout <<path1<< Ord[RN].OrderNumber << "\t" <<path1<< Ord[RN].CName << "\t" <<path1<< Ord[RN].DoO << endl;
    cout <<path1<< Ord[RN].PCode << "\t" <<path1<< Ord[RN].OrDes << "\t" <<path1<< Ord[RN].DDA << endl;
    cout <<path1<< Ord[RN].QoO << "\t" <<path1<< Ord[RN].Stat << endl;
    }
    path1.close();

    }


    anyway my problem is, that when I build the program, it comes up with the result 'SearchTree' : not all control paths return a value" plus the search doesnt work either, if neone can be bothered to read through it all, it would be much appreciated, if not no worries! nice one!
  2. #2
  3. No Profile Picture
    Contributing User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Sep 2003
    Location
    Europe
    Posts
    51
    Rep Power
    12
    Hi,

    I didn't read your code through, but I am replying since I am working now with binary trees too. You can find tree classes/templates in the Internet if you do some search. For example I found a nice multi-set representation as a binary tree at
    http://www.chips.navy.mil/archives/9...lymorphism.htm
    (they seem to have network problems today.)
    Here's a class that works on my MS Visual C++:

    class Node{
    friend ostream& operator << (ostream& o, const Node * rhs){
    o<<rhs->item;
    return o;
    };
    public:
    int item;
    Node * left;
    Node * right;
    Node(int n);
    void print(void);
    };

    Node::Node(int n){
    item=n;
    left=NULL;
    right=NULL;
    };

    class Tree{
    Node * root;
    Node * insert(int n, Node * nd);
    void print(Node * nd);
    void insert(int n);
    public:
    Tree(void);
    void insert(std::list<int> l);
    void print(void);
    };

    Tree::Tree(void){
    root = NULL;
    };

    Node * Tree::insert(int n, Node * nd){
    if(nd==NULL){
    return new Node(n);
    }else if(n<nd->item){
    nd->left=insert(n, nd->left);
    return nd;
    }else{
    nd->right=insert(n, nd->right);
    return nd;
    }
    };

    void Tree::insert(int n){
    root = insert(n, root);
    };

    void Tree::insert(std::list<int> l){
    if(!l.empty()){
    int n = l.front();
    l.pop_front();
    insert(n);
    insert(l);
    }
    };


    void Tree::print(Node * nd){
    if(nd!=NULL){
    print(nd->left);
    cout<<nd<<" ";
    print(nd->right);
    };
    };

    void Tree::print(void){
    print(root);
    };


    In my (newbie) opinion it's way more convenient to represent recursive data types with structs, because object constructor cannot return a NULL. I am writing classes just because I want to have private members. --Raokramer
    Last edited by raokramer; September 8th, 2003 at 09:09 AM.
  4. #3
  5. No Profile Picture
    Contributing User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Sep 2003
    Posts
    68
    Rep Power
    12
    >if neone can be bothered to read through it all, it would be much appreciated
    I read through enough to understand that you're doing things the hard way. Trying to write code for a binary tree that is implemented using an array and indices is silly. You lose one of the best aspects of a binary tree: unlimited size potential. You also have to work out the complicated index scheme. Pointers and dynamic memory allocation is so much easier and more intuitive.

IMN logo majestic logo threadwatch logo seochat tools logo