0

请参阅下面的 BST 代码。它只输出“5”。我做错了什么？

#include <iostream>

class bst {
 public:
  bst(const int& numb) : root(new node(numb)) {}

  void insert(const int& numb) {
    root->insert(new node(numb), root);
  }

  void inorder() {
    root->inorder(root);
  }

 private:
  class node {
   public:
    node(const int& numb) : left(NULL), right(NULL) {
      value = numb;
    }

    void insert(node* insertion, node* position) {
      if (position == NULL) position = insertion;
      else if (insertion->value > position->value)
        insert(insertion, position->right);
      else if (insertion->value < position->value)
        insert(insertion, position->left);
    }

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

  node* root;
};

int main() {
  bst tree(5);
  tree.insert(4);
  tree.insert(2);
  tree.insert(10);
  tree.insert(14);
  tree.inorder();
  return 0;
}
4

3 回答 3

1

使用参考：

无效插入（节点*插入，节点* &位置）

无效中序（节点* &tree）{

于 2012-06-02T04:35:33.807 回答
1

这是因为您从未设置 的left和right字段的值root。

对于给定的节点，您必须在某处说n：

n->left = ...
n->right = ...

你从来没有这样做过。所以你最终得到了一个节点树。您的根有两个空子。

您也可以对此偷偷摸摸：如果您按照@user1431015 的建议进行操作，并通过引用传递子指针，那么对引用参数 ( position) 的赋值就可以解决问题。正如您所做的那样，通过值传递它们只会分配给局部变量，而不是树本身。

于 2012-06-02T04:41:02.260 回答
1

在大多数情况下，您的插入永远不会做任何事情。递归的基本情况是：

void insert(node* insertion, node* position) {
     if (position == NULL) position = insertion;

但是所有的“位置”都是局部范围的指针值。一旦你的函数退出，分配给它就没有效果了。

您需要做的是使位置参数成为对指针的引用。换句话说，使它成为 type node*&。然后，在您退出该功能后，分配将保持不变。

于 2012-06-02T04:41:12.837 回答