数组BST的插入排序如何工作？

我试图做递归..父母的整数变量就像我，符合公式2*i +1为leftChild的和2*i +2的权利。数组BST的插入排序如何工作？

void BST::insert(const data &aData) 
{ 
    if (items[Parent].empty) 
    { 
     items[Parent].theData = aData; 
     items[Parent].empty = false; 
    } 
    else if (aData < items[Parent].theData) 
    { 
     Parent = 2 * Parent + 1; 
     if (Parent >= maxSize) this->reallocate(); 
     this->insert(aData); 
    } 
    else 
    { 
     Parent = (2 * rightChild++)+ 2; 
     if (Parent >= maxSize) this->reallocate(); 
     this->insert(aData); 
    } 
}

这将是比原来的父项... 时工作正常，但当我找到的东西，是较大的这一切搞砸了：X

void BST::reallocate() 
{ 
    item *new_array = new item[maxSize*2]; 

    for (int array_index = 0; array_index < maxSize; array_index++) 
    { 
     if (! items[array_index].empty) 
     { 
      new_array[array_index].theData = items[array_index].theData; 
     } 
    } 
    maxSize *= 2; 
    delete [] items; 

    items = NULL; 
    items = new_array; 
}

这里是我的构造函数等等没有人会再糊涂那么我：

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

上方插入函数实际上是最好的，我可以得到..

        R 
           /\ 
          / \ 
          / \ 
          L  X 
          /\ /\ 
          J V K T <--The only out of place node. 
         /\ \ 
         /NULL \ 
         G  /
           P

当插入：R, L, J, G, X, K, V, P, T的顺序

来源

2009-11-18 user40120

这只是一个递归定义的插入函数，试图完成。 – user40120 2009-11-18 00:45:19

T是插入的最后一项，是原因吗？ – user40120 2009-11-18 01:14:30

我会怀疑你的问题是在这条线：

Parent = (2 * rightChild++)+ 2;

你为什么要使用rightChild在这里，而不是(2 * Parent) + 2？

为了让事情更清晰，你可能想一些简单的内联函数添加到您的类计算左/右儿童和家长的指标，给出指数：

inline int getLeftChildIndex(int nodeNdx) { return (nodeNdx * 2) + 1; } 
inline int getRightChildIndex(int nodeNdx) { ... } 
inline int getParentIndex(int nodeNdx) { ... }

您可能还需要考虑使用类别search()或find()方法（我假设它有一个）来确定插入新节点的位置。搜索函数应该返回现有节点的索引（由您决定如何处理插入重复值）或者应该插入新值的索引。

来源

2009-11-24 00:08:38 sdtom

数组BST的插入排序如何工作？

回答

相关问题