C-难以从数组中构建二进制树

Question

我试图从未分类的浮点数组中构建一个二进制树以进行分配，但我无法完全弄清楚。我的目标是将大小ndata的未分类数组xdata发送到函数build_tree()，该函数使用函数create_node（）创建一个新的节点。如果数组大小大于1，它将称为函数paritition_data()（效果很好，但我将其放在问题的底部以供参考），这将交换数组值的顺序，以便所有人值小于mid的左落在其左侧，并更大的值位于其右侧。该函数返回nleft，即mid左侧的值数。然后，我想递归致电partition_data()以创建新的left和right儿童节点。我认为在此步骤中，我的程序似乎失败了，尽管它编译了，但该程序似乎无限地将partition_data()调用，我不确定为什么。感谢任何帮助。

typedef struct treenode_struct {
  int n;
  float data;
  struct treenode_struct *left, *right;
} treenode;
treenode *create_node( ) {
  treenode *node;
  node = malloc(sizeof(treenode));
  if (node == NULL) {
    printf("Allocate Failed");
    exit(-1);
  }
  node->n = 0;
  node->right = NULL;
  node->left = NULL;
  tree_nodes++;
  return node;
}
treenode *build_tree( float xdata[], int ndata, float xmin, float xmax ) {
  treenode *node;
  int nleft;
  float mid = (xmin+xmax)/2.;
  node = create_node();
  node->n = ndata;
  if (ndata == 1) {  // Add code for this case
    node->data = xdata[0]; 
    node->left = NULL;
    node->right = NULL;
    return node;
  }
  if (ndata == 0){
    printf("Allocate failedn");
    exit(-1);
  }
 // More than one data point: use partition function
  if (ndata > 1) {
    nleft = partition_data(xdata,ndata,mid);
    int nright = ndata-nleft;
    // Add code to make a left child
    if(nleft != 0){
      node->left=build_tree(xdata,nleft,xmin,xdata[nleft-1]);
    }
    else{
      node->left = NULL;
    }
    // Add code to make a right child
    if(nright != 0){
      node->right=build_tree(xdata,nright,xdata[nleft],xmax);
    }
    else{
      node->right = NULL;
    }
    return node;
  }
}
int tree_nodes;
int main() {
  const int ndata = 16;
  float xdata[] = { 0.963,  0.003, 0.0251, 0.353, 0.667, 0.838, 0.335, 0.915,
            0.796, 0.833, 0.345, 0.871, 0.089, 0.888, 0.701, 0.735 };
  int i;
  float xmiddle = 0.5;
  printf("Input data:n");
  for (i=0;i<ndata;i++) printf("%f ",xdata[i]);
  printf("n");
 treenode *tree_root;
  float tree_xmin, tree_xmax;
  tree_nodes = 0;
  tree_xmin = 0;
  tree_xmax = 1;
  tree_root = build_tree( xdata, ndata, tree_xmin, tree_xmax );
  printf("Tree Built: nodes %dn",tree_nodes);
  printf("Tree Ordered data:n");
  for (i=0;i<ndata;i++) printf("%f ",xdata[i]);
  printf("nn");
}

这是partition_data()：

int partition_data( float xdata[], int ndata, float xmiddle ) {
  // Your code goes here
  int left = 0;
  int right = ndata-1;
  float temp;
  while(left < ndata){  //left loop
    if(xdata[left] < xmiddle){
      if(left == right){
    return left+1;
    break;
      }//DONE
      left = left + 1;
    }
    else{
      while(right<ndata){ //right loop, search for swappable Xright
    if(xdata[right] >= xmiddle){//X[right] is greater than/equal to xmiddle
      if(left == right){
        return left;
        break;
      }
      right=right-1;
    }
    else{ //found X[right] to swap
      temp = xdata[left];
      xdata[left] = xdata[right];//swap
      xdata[right]=temp;
      right = right-1;
      if(left == right) {
        return left+1;
        break;
      }
      left=left+1;
      break;
    }
    break;
      }
    }
  }

Answer 1

您的递归问题是由您的右节点的创建引起的。
您可以使用此代码创建正确的节点：

// Add code to make a right child
if(nright != 0){
  node->right=build_tree(xdata,nright,xdata[nleft],xmax);
}
else{
  node->right = NULL;
}

现在，如果您查看 build_tree功能，那么您拥有的是：

treenode *build_tree( float xdata[], int ndata, float xmin, float xmax )

让我们将其解释为：

从数组xdata[]创建树，其中所有元素都大于xmin，小于xmax

现在，没有将 xdata[]视为 array xdata[]，但请参见 xdata是我必须处理的第一个元素的指针。这将（希望）可以帮助您了解一点（实际上就是它，它只是指针）。在您的代码中创建您使用的正确节点：

 node->right=build_tree(xdata,nright,xdata[nleft],xmax);

但是，实际上，您实际上是作为右节点插入的，通过处理数组的第一个元素开始的数据将创建的树的根。那不是您想要的阵列的切片。您想要在右节点中拥有的切片是数组的正确部分，因此从索引ndata-nright开始的部分。因此，如果要更改数组的开始，只需将索引添加到数组的指针中即可。因此，在您的情况下，xdata + (ndata-nright)将代表以元素ndata-nright（或指向该元素的指针）开始的数组。所以你应该有：

  node->right=build_tree(xdata + (ndata-nright),mid,xdata[nleft],xmax);

创建您的右节点！