0

只需一个简单的 BST 即可按顺序打印数字。无法弄清楚我做错了什么。

#include <iostream>
using namespace std;

class bst {
 private:
  bst* root;
  bst* left;
  bst* right;
  int value;

 public:
  bst(const int& numb) : root(NULL), left(NULL), right(NULL) {
    value = numb;
  }

  void insert(const int& numb) {
    if (numb < value) {
      if (left == NULL) {
        left = new bst(numb);
        left->root = left;
      } else { 
        left->insert(numb);
      }
    } else if (numb > value) {
      if (right == NULL) {
        right = new bst(numb);
        right->root = right;
      } else {
       left->insert(numb);  
      }
    } else if (numb == value) {
      cout << "duplicated value" << endl;
    }
  }

  void inorder() {
    if (left == NULL) cout << value << endl;
    else left->inorder();
    right->inorder();
  }
};


int main() {
  bst tree(5);
  tree.insert(7);
  tree.insert(1);
  tree.insert(3);
  tree.insert(2);
  tree.insert(9);
  tree.insert(10);
  return 0;
}
4

4 回答 4

3

第 29 行应为：

 right->insert(numb);

它目前的内容是：

 left->insert(numb);

我强烈建议研究 gdb 来解决这种情况。

于 2012-06-01T03:57:32.930 回答
1

inorder()应该：

if (left != NULL) left->inorder();
cout << value << endl;
if (right != NULL) right->inorder();

我认为其余的都是正确的。

于 2012-06-01T03:54:16.180 回答
1

至少在我看来，你的基本设计是有缺陷的。尽管我意识到许多教科书（等）将树描述为递归结构，其中每个节点都有两个子树，但我从未发现这是设计代码的好方法。

至少根据我的经验，在实际代码中，将树中节点的概念与整个树的概念分开会更好。只有树对外界可见；node应该藏在树里面，外面的世界看不到。

class bst {
    class node {
        int value;
        node *left;
        node *right;

        // ...

    };

    // ...

    node *root;   
};

然后我将insert分成两部分：一个接受一个值的公共函数，然后转发到以root为起点的第二个函数。第二个实际上是遍历这三个并插入新项目：

// public interface:
void insert(int v) {    
    insert(new node(v), root);
}

// private workhorse:
void insert(node *n, node *&pos) {
    if (pos == NULL)
        pos = n;
    else if (n->value < pos->value)
        insert(n,pos->left);
    else if (n->value > pos->value)
        insert(n,pos->right);
            else
                // duplicate value.
}

同样，inorder被分成公共和私有对，公共只提供一个接口，而私有的则做所有实际工作：

// public interface:
void inorder() {
    inorder(root);
}

// private worker
void inorder(node *n) {
    if (n==NULL)
        return;
    inorder(n->left);
    std::cout << n->value << endl;
    inorder(n->right);
}

对于它的价值：是的，我已经测试了这段代码，它至少可以与你在 you 中使用的输入一起工作main。不过它确实有缺点。例如，两者都insert递归inorder遍历树，因此一个大的、严重不平衡的树可能导致堆栈溢出。迭代插入相当容易，但在实际使用中，您通常只需切换到某种平衡树即可。

于 2012-06-01T04:45:15.943 回答
1

逻辑错误贯穿始终。

崩溃在这里：

  if (right == NULL) { 
    right = new bst(numb); 
    right->root = right; 
  } else { 
   left->insert(numb);   
  }

else case 使用右而不是左。

于 2012-06-01T04:00:40.180 回答