Сложность Построение двоичного дерева из массива

Question

Я пытаюсь построить двоичное дерево из несортированного массива float для назначения, но я не могу это понять. Моя цель - отправить несортированный массив 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; 
     } 
    } 
    } 

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[], как массив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); 

, чтобы создать свой правый узел!