Thread: C++ Program Problem - Tree

  1. #1
    Registered User
    Join Date
    Sep 2011
    Posts
    25

    Question C++ Program Problem - Tree

    I have been having some difficulty with implementing a program that makes a LCRS Binary Tree from the users input. I need to have the program implement insertion, search, height, and preorder. So far I have gotten the insertion part to work, or at least it doesn't crash when inserting values . The problem is with my search function, it works if the value I'm looking for is the root node, but if it's deeper in the tree, it keeps returning false, earlier I was getting Access Errors, but I seemed to have resolved that bug. If anyone sees the error in my function, I would greatly appreciate the help. Thanks!

    [functions]
    Code:
    1. #include "BST.h"
    2. #include <cstdlib>
    3. #include <iostream>
    4. using namespace std;
    5. int Tree::command(string s) {
    6. if (s == "insert") return 1;
    7. if (s == "search") return 2;
    8. if (s == "preorder") return 3;
    9. if (s == "height") return 4;
    10. if (s == "quit") return 5;
    11. return -1;
    12. }
    13. bool Tree::insert(int value) {
    14. if (root == NULL) {
    15. root = new Node(value);
    16. cout<<"Root: "<<root->value<<endl;
    17. return true;
    18. } else
    19. return root->insert(value);
    20. }
    21. bool Node::insert(int value) {
    22. if (value = this->value) return true;
    23. else {
    24. if (this->child == NULL) {
    25. this->child = new Node(value);
    26. return true;
    27. } else {
    28. if (value < this->value) {
    29. if (this->value < this->child->value && this->child->sibling == NULL) {
    30. Node *s = new Node(value);
    31. s->sibling = this->child;
    32. this->child = s;
    33. return true;
    34. }
    35. if (this->value > this->child->value && this->child->sibling == NULL)
    36. return this->child->insert(value);
    37. if (this->child->sibling != NULL)
    38. return this->child->insert(value);
    39. }
    40. if (value > this->value) {
    41. if (this->value < this->child->value && this->child->sibling == NULL) {
    42. return this->child->insert(value);
    43. }
    44. if (this->value > this->child->value && this->child->sibling == NULL) {
    45. this->child->sibling = new Node(value);
    46. return true;
    47. }
    48. if (this->child->sibling != NULL) {
    49. return this->child->sibling->insert(value);
    50. }
    51. }
    52. }
    53. }
    54. }
    55. bool Tree::search(int value) {
    56. if (root == NULL)
    57. {
    58. cout<<"is null"<<endl;
    59. return false;
    60. }
    61. else{
    62. if(root->value == value) return true;
    63. else
    64. return root->search(value);
    65. }
    66. }
    67. bool Node::search(int value)
    68. {
    69. if (this->value == value) return true;
    70. else
    71. {
    72. if(this->child != NULL || this->sibling != NULL)
    73. {
    74. if(value > this->value && this->sibling != NULL)
    75. return this->sibling->search(value);
    76. if(value > this->value && this->sibling == NULL)
    77. return false;
    78. if(value < this->value && this->child != NULL)
    79. return this->child->search(value);
    80. if(value < this->value && this->child == NULL)
    81. return false;
    82. }
    83. else return false;
    84. }
    85. }
    [header]
    Code:
    1. #include <cstdlib>
    2. #include <string>
    3. using namespace std;
    4. class Node {
    5. public:
    6. int value;
    7. Node* child;
    8. Node* sibling;
    9. Node(int value) {
    10. this->value = value;
    11. child = NULL;
    12. sibling = NULL;
    13. }
    14. bool insert(int );
    15. bool search(int);
    16. };
    17. class Tree {
    18. private:
    19. Node* root;
    20. public:
    21. Tree() {
    22. root = NULL;
    23. }
    24. bool insert(int );
    25. int height(Tree *);
    26. bool search(int );
    27. void preorder(Tree *);
    28. int command(string);
    29. };

  2. #2
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,318
    Check line 22, there's an obvious bug there which will be the source of your problems.

    Note that you are shooting your self in the foot by not using proper indentation.
    Try and avoid using "this->" everywhere, it just clutters up the code. If you rename the local variables to not clash with the names of your member variables, then you can easily achieve this and it will make things so much nicer to read.
    Your insert function is also very large, It can be done in a lot less code that than, so you're probably overthinking it a little.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Help with a recursive expression tree program
    By TeamRival in forum C Programming
    Replies: 6
    Last Post: 03-25-2011, 07:27 PM
  2. Help Debugging my AVL tree program.
    By Nextstopearth in forum C Programming
    Replies: 2
    Last Post: 04-04-2009, 01:48 AM
  3. Problem with binary tree program
    By rsk8332 in forum C++ Programming
    Replies: 3
    Last Post: 04-09-2008, 07:08 PM
  4. How to program a data tree? (not binary)
    By Captain Penguin in forum C++ Programming
    Replies: 5
    Last Post: 12-30-2002, 03:25 PM

Tags for this Thread