BST代码无法大量使用 [英] BST code is not working with large number

问题描述

我的BST代码让我非常沮丧:

I have a very frustrated situation with my BST code:

vector<int> order;
BinarySearchTree tree;
for (int i=0; i<1000; ++i) {
  int j = rand()%1000;
  order.push_back(j);
}
for (int i = 0; i < 1000; ++i) {
  tree.insert(order[i]);
}
while(!tree.isEmpty()) {
  cout << tree.min() << endl;
  tree.remove(tree.min());
}

使用很小的i(例如10或100)，代码可以正常工作.但是，当i为1000时，它将停止工作.

the code is working perfectly fine with small number of i, say 10, or 100. However, it is stop working when i is 1000.

插入函数如下

void BinarySearchTree::insert(int d)
{
  tree_node* t = new tree_node;
  tree_node* parent;
  t->data = d;
  t->left = NULL;
  t->right = NULL;
  parent = NULL;

  // is this a new tree?
  if(isEmpty()) root = t;
  else
  {
    //Note: ALL insertions are as leaf nodes
    tree_node* curr;
    curr = root;
    // Find the Node's parent
    while(curr)
    {
      parent = curr;
      if(t->data > curr->data) curr = curr->right;
      else curr = curr->left;
    }

    if(t->data <= parent->data)
      parent->left = t;
    else
      parent->right = t;
  }
}

为回应这些评论，我将发布所有代码. :)

In response to the comments, i am going to post all the code. :)

void BinarySearchTree::remove(int d)
{
  //Locate the element
  bool found = false;
  if(isEmpty())
  {
    cout<<" This Tree is empty! "<<endl;
    return;
  }

  tree_node* curr;
  tree_node* parent;
  curr = root;
  //parent = root;

  while(curr != NULL)
  {
    if(curr->data == d)
    {
      found = true;
      break;
    }
    else
    {
      parent = curr;
      if(d>curr->data) curr = curr->right;
      else curr = curr->left;
    }
  }
  if(!found)
  {
    cout<<" Data not found! "<<endl;
    return;
  }


  // 3 cases :
  // 1. We're removing a leaf node
  // 2. We're removing a node with a single child
  // 3. we're removing a node with 2 children

  // Node with single child
  if((curr->left == NULL && curr->right != NULL)|| (curr->left != NULL
    && curr->right == NULL))
  {
    if(curr->left == NULL && curr->right != NULL)
    {
      if (curr == root) {
        root = curr->right;
        delete curr;
      }
      else {
        if(parent->left == curr)
        {
          parent->left = curr->right;
          delete curr;
        }
        else
        {
          parent->right = curr->right;
          delete curr;
        }
      }
    }
    else // left child present, no right child
    {
      if (curr==root) {
        root = curr->left;
        delete curr;
      }
      else {
        if(parent->left == curr)
        {
          parent->left = curr->left;
          delete curr;
        }
        else
        {
          parent->right = curr->left;
          delete curr;
        }
      }
    }
    return;
  }

  //We're looking at a leaf node
  if( curr->left == NULL && curr->right == NULL)
  {
    if (curr == root) {
      root = NULL;
      delete curr;
      return;
    }
    else {
      if(parent->left == curr) parent->left = NULL;
      else parent->right = NULL;
      delete curr;
      return;
    }
  }


  //Node with 2 children
  // replace node with smallest value in right subtree
  if (curr->left != NULL && curr->right != NULL)
  {
    tree_node* chkr;
    chkr = curr->right;
    if((chkr->left == NULL) && (chkr->right == NULL))
    {
      curr = chkr;
      delete chkr;
      curr->right = NULL;
    }
    else // right child has children
    {
      //if the node's right child has a left child
      // Move all the way down left to locate smallest element

      if((curr->right)->left != NULL)
      {
        tree_node* lcurr;
        tree_node* lcurrp;
        lcurrp = curr->right;
        lcurr = (curr->right)->left;
        while(lcurr->left != NULL)
        {
          lcurrp = lcurr;
          lcurr = lcurr->left;
        }
        curr->data = lcurr->data;
        delete lcurr;
        lcurrp->left = NULL;
      }
      else
      {
        tree_node* tmp;
        tmp = curr->right;
        curr->data = tmp->data;
        curr->right = tmp->right;
        delete tmp;
      }

    }
    return;
  }

}

和min()函数

int BinarySearchTree::min()
{
  tree_node *p=root;
  while (p->left != NULL)
    p=p->left;
  return (p->data);
}

推荐答案

最后四行看起来像是否定了for循环的逻辑. for循环说: 新值较大，向右走，向左走. 树的位置显示: 新值是在较大的地方，在左边的地方，在右边的地方.

Looks like the last four lines have negated logic of the for loop. The for loop says: new val is larger go right else left. The tree placement says: new val is larger place left else place right.

我也看不到您的删除代码，但是它可能会受到错误排序的影响.

Also I don't see your remove code, but the it may be affected by the wrong ordering.

还可以在使用前尝试初始化rand:

Also try initializing rand before using it:

srand (time(NULL));

这篇关于BST代码无法大量使用的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！