二进制搜索树C++（Parents）

我只需要在我的BST上多一点帮助。这是我的BST看起来插入时这样的：二进制搜索树C++（Parents）

R，L，J，G

     R --Root at Index 0 
        /\ 
    L @ Index1  L NULL 
       /\ 
    J @ Index3 J NULL 
       /\ 
    G @ Index7 G NULL

这里，使得它发生的代码。

void BST::insert(const data &aData) 
{ 
    if (items[Parent].empty) 
    { 
     items[Parent].theData = aData; // insert at leaf. 
     items[Parent].empty = false; 
     size++; 

     return; 
    }   
    for (int i = 0; i <= size; i++) 
    { 
     if (aData < items[Parent].theData) 
     { 
      if (items[2*i+1].empty) 
      { 
      items[2*i+1].theData = aData; 
      items[2*i+1].empty = false; 
      } 
      else 
          { 
      // we must already have a left child to some root. 
           Parent++; So make the previous data the root??? 
      if (items[Parent].empty) 
      { 
       items[Parent].theData = items[2*i+1].theData; 
       items[Parent].empty = false; 
       Parent = (i-1)/2; 
      } 
          } 
     } 
     else 
     { ...// do the same for data greater than but with items[2*i+2] }

我的问题是，我什么时候需要做一个新的根？我什么时候需要创建一个新的根？为了重新比较？

这种方法是否正确？谢谢那些甚至两个看我的帖子:)

//构造函数的BST类和它的私人部分。

BST::BST(int capacity) : items(new item[capacity]), size(0), Parent(0), 
leftChild(0), rightChild(0) 
{ 
    items->empty = true; 
    maxSize = capacity; 
} 
private: 
    int size; // size of the ever growing/expanding tree :) 
    int Parent; 
    int maxSize;  
    int leftChild; 
    int rightChild; 
    struct item 
    { 
     bool empty; 
     data theData; 
    }; 
    item *items; // The tree array

来源

2009-11-17 user40120

您可以简化问题，因此包含完整的代码是可行的吗？或者把它写入（完整的）伪代码？没有指出像“item”，“Parent”，“data”等事情，这使得很难破译你正在做的事情。 – 2009-11-17 21:03:42

你为什么使用数组？ – 2009-11-17 21:06:58

我发布的构造函数，还有它的私人部分，我定义我的数据数组。对于那个很抱歉！ – user40120 2009-11-17 21:07:26

你的逻辑（相当模糊的，我必须说）似乎是错误的：什么样的“如果”顺序是什么？

if (items[2*i+1].empty) 
{ 
} 
else if (!items[2*i+1].empty) 
{ 
    if (items[2*i+1].empty) 
    { 
     // any code here is unreachable 
    } 
}

来源

2009-11-17 21:12:19 BostonLogan

我想知道我自己。它继续前进，所以我没有问题。 – user40120 2009-11-17 21:16:04

我认为如果我至少可以构建它。回去做好它会很容易。我很难第一次编写高效的代码。 – user40120 2009-11-17 21:17:50

我想我需要它做的是循环迭代 – user40120 2009-11-17 21:21:06

我建议你重新实现这个以递归方式工作。事情是这样的：

void BST::insert(const data& aData, int pos) { 
    if (items[pos].empty) { 
     // insert it here 
    } 
    else (aData < items[pos].theData) { 
     // go to left child 
     insert(aData, 2*pos + 1); 
    } 
    else { 
     // go to right child 
     insert(aData, 2*pos + 2); 
    } 
}

这不是真的清楚什么家长，leftChild和rightChild在你的类做，但是这是一个单独的问题。

来源

2009-11-17 21:46:39 Andrey

二进制搜索树C++（Parents）

回答

相关问题