从数组构造二叉树的困难

Question

我正在尝试从未排序的浮点数组构建二叉树以进行赋值，但我不太明白。我的目标是将大小为 ndata 的未排序数组 xdata 发送到函数 build_tree()，它使用函数 create_node() 创建一个新节点。在数组大小大于1的情况下，它会调用函数paritition_data()（效果很好，但我把它放在问题的底部以供参考），这将交换数组的顺序值，以便所有小于 mid 的值都落在它的左边，而更大的值落在它的右边。函数returnsnleft，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;
      }
    }
  }

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 )

我们将其解释为：

create a tree from the array xdata[] where all elements are greater than xmin and less than xmax

现在不再将 xdata[] 视为数组 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);

创建适合您的节点！

从数组构造二叉树的困难

Difficulty Constructing Binary Tree from Array

c

arrays

sorting

binary-tree

bsp-tree