0

我正在尝试从未排序的浮点数组构建二叉树以进行分配，但我无法弄清楚。我的目标是将未排序xdata的大小数组发送ndata到函数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 failed\n");
    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 %d\n",tree_nodes);

  printf("Tree Ordered data:\n");
  for (i=0;i<ndata;i++) printf("%f ",xdata[i]);
  printf("\n\n");
}

这里是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;
      }
    }
  }
4

1 回答 1

0

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

// 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[]其视为数组 xdata[]，而是将xdata其视为指向我必须处理的第一个元素的指针。这将（希望）帮助您稍微理解它（实际上就是它，它只是一个指针）。在您的代码中创建您使用的正确节点：

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

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

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

创建您的正确节点！

于 2016-12-02T04:23:59.610 回答