Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Code : Binary Search Tree C++

  1. Feb 4, 2008 #1
    #include <iostream.h>
    #include <conio.h>
    #include <stdio.h>
    void main()
    {
    struct znode // binary search tree node
    {
    int data; // data type is integer
    struct znode * left; // left subtree
    struct znode * right; // right subtree
    };

    struct znode * root = NULL; // root node, initially NULL

    void print_tree_inorder(struct znode* tree) // print tree in inorder (left -> parent -> right)
    {
    if (tree == NULL)
    printf("Tree is empty!\n");
    else
    {
    if (tree->left != NULL)
    print_tree_inorder(tree->left);
    printf("%d ", tree->data);
    if (tree->right != NULL)
    print_tree_inorder(tree->right);
    };
    }

    struct znode* insert(int insert_data, struct znode* tree) // node insert
    {
    if (tree == NULL) // if null, make new node
    {
    tree = (struct znode *)malloc(sizeof(struct znode));
    tree->data = insert_data;
    tree->left = NULL;
    tree->right = NULL;
    }
    else if (insert_data < tree->data) // insert data in left subtree
    tree->left = insert(insert_data, tree->left);
    else if (insert_data > tree->data)
    tree->right = insert(insert_data, tree->right); // insert data in right subtree
    else
    printf("Insert Error : item duplicated!\n"); // when the item already exists

    return tree;
    }

    struct znode* zremove_min(struct znode* tree) // delete minimum-valued node
    {
    struct znode* temp = tree;

    if (tree == NULL)
    printf("remove Minimum Error : null tree!\n");
    else if (tree->left != NULL)
    tree->left = zremove_min(tree->left); // traverse to left and left again
    else
    {
    tree = tree->right; // attach right subtree(or NULL) to parent
    free(temp); // and remove the old parent
    }

    return tree;
    }

    struct znode* zremove(int remove_data, struct znode* tree) // delete node
    {
    struct znode* temp = tree;

    if (tree == NULL)
    printf("remove Error : item not found!\n");
    else if (remove_data < tree->data) // delete data in left subtree
    tree->left = zremove(remove_data, tree->left);
    else if (remove_data > tree->data)
    tree->right = zremove(remove_data, tree->right); // delete data in right subtree
    else if (tree->left != NULL && tree->right != NULL)
    // if this has both left and rihgt subtree
    {
    temp = temp->right;
    while (temp->left != NULL)
    temp = temp->left; // find the minimum data of right subtree
    tree->data = temp->data; // and set it to the parent
    tree->right = zremove_min(tree->right); // and remove it in right subtree
    }
    else
    {
    tree = (tree->left != NULL) ? tree->left : tree->right;
    // attach one of two children to parent (tree or NULL)
    free(temp); // free the old parent
    }

    return tree;
    }

    int main()
    {
    FILE* fp;
    char buffer[11];

    fp = fopen("index.txt", "r");
    while (fgets(buffer, 10, fp) != NULL) // read one line from index.txt
    {
    printf("\ninsert %d : ", atoi(buffer));
    root = insert(atoi(buffer), root); // insert it
    print_tree_inorder(root); // and print the current tree shape
    }
    fclose(fp);

    fp = fopen("index.txt", "r"); // close and reopen
    while (fgets(buffer, 10, fp) != NULL)
    {
    printf("\ndelete %d : ", atoi(buffer));
    root = zremove(atoi(buffer), root); // delete a node
    print_tree_inorder(root); // and print
    }
    fclose(fp);

    getch();
    };
    };

    Compiling 0001.CPP:
    Error 0001.CPP 16: Declaration syntax error in function main()
    Warning 0001.CPP 119: 'root' is assigned a value that is never used in function main()



    Help Me !!


    Edit and modifier
     
  2. jcsd
  3. Feb 4, 2008 #2

    D H

    User Avatar
    Staff Emeritus
    Science Advisor

    In the future, please embed your code in code tags so that we can see the structure of your code.

    kind of like this:
    Code (Text):
    #include <iostream.h>
    #include <conio.h>
    #include <stdio.h>
    void main()
    {
    struct znode                        // binary search tree node
    {
           int data;                        // data type is integer
           struct znode * left;                        // left subtree
           struct znode * right;                        // right subtree
    };
    ...
    int main()
    {
    };
    };
     
    Why are you declaring main at the very top and wrapping all functions inside of main? You cannot embed a function within a function in C++.

    For a start, get rid of that initial "void main(){". I also suggest you switch to using C++ I/O rather than C I/O and C++ new/delete rather than malloc.
     
  4. Feb 4, 2008 #3

    jim mcnamara

    User Avatar
    Science Advisor
    Gold Member

    main() is never void; it returns an int. Always. That is the C and C++ standard.

    Plus, if this isn't an assignment, consider the standard library function bsearch().

    The STL aslo has a binary search.
     
    Last edited: Feb 4, 2008
  5. Feb 4, 2008 #4

    D H

    User Avatar
    Staff Emeritus
    Science Advisor

    The OP has problems much more basic than "void main" versus "int main". That that "void main" is pedantically incorrect is secondary to the fact that it is completely incorrect. The biggest problem, embedding one function definition inside another, is much worse than going against the standard. Many compilers will compile a program that declares main as void. I don't know any C compiler that will compile code in which a function is defined internal to some outer function (and if some compiler does do that the language is no longer C/C++).

    Besides, the OP does define a function "int main" (internal to the erroneous "void main" declaration).
     
  6. Feb 4, 2008 #5

    jim mcnamara

    User Avatar
    Science Advisor
    Gold Member

    I agree, DH, the OP's code has lots of problems. However start with what you learn on day one. Then go ahead from there.

    That one thing "pedantic" thing speaks volumes about how wrell the OP is learning or being taught to code. I didn't get past the void main().

    So in that sense I REALLY disagree with you. IMO, the OP may need to go back to Hello World. I think the the OP missed day one in class.. Your correcting what he posted will not help much, except maybe to get his coding assignment done. Wrong. There is nothing more basic than int main(). Period the end. YMMV.
     
  7. Feb 4, 2008 #6

    chroot

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    Void main functions are actually pretty common on Windows machines. Loosen your grip a little jim.

    The real problem here is that the OP is trying to put functions inside one another, when they should be peers.

    - Warren
     
  8. Apr 15, 2010 #7
    bu kod c++ değil c aga
     
  9. Apr 15, 2010 #8

    Mark44

    Staff: Mentor

    Amen to that Warren and D H.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?



Similar Discussions: Code : Binary Search Tree C++
  1. Binary Search Tree C++ (Replies: 1)

  2. Binary tree (Replies: 5)

Loading...