以下是我正在學習的編程課程的作業：
以下是我到目前為止撰寫的代碼。我已經對其進行了調整以將整數包含在一個陣列中，而無需從另一個檔案中讀取它們，以便您輕松使用。下面我將解釋為什么它沒有成功創建二叉樹，然后是我的問題。這是代碼：
/* A program that should use integers in an array to make binary trees
using the integers, then prints the integers from the tree inorder.
By John
*/
#include <stdio.h>
#include <stdlib.h>
typedef struct NODE
{
int data;
struct NODE *left;
struct NODE *right;
} NODE;
typedef NODE *BTREE;
//allocate memory for the node
BTREE create_node(BTREE t)
{
t = (BTREE)malloc(sizeof(NODE));
return t;
}
//initialize the node
BTREE init_node(int number, BTREE p1, BTREE p2)
{
BTREE t = NULL;
t = create_node(t);
t->data = number;
if (p1->data <= t->data)
{
t->left = p1;
}
else if (p1->data > t->data)
{
t->right = p1;
}
if (p2->data <= t->data)
{
t->left = p2;
}
else if (p2->data > t->data)
{
t->right = p2;
}
return t;
}
//create the tree from the integers stored in the array
BTREE create_tree(int num_array[], int i, int size)
{
if (i >= size)
{
return NULL;
}
else
{
return (init_node(num_array[i],
create_tree(num_array, 2*i 1, size),
create_tree(num_array, 2*i 2, size)));
}
}
//printing the integers stored in the trees inorder
void print_inorder(BTREE t)
{
if (t != NULL)
{
print_inorder(t->left);
printf("%d :", t->data);
print_inorder(t->right);
}
}
int main(void)
{
BTREE t = NULL;
int data[] = { 9, 11, 4, 5 }; //pointer to integers array
int i = 0; //represents indexes of the integers array
int number = 0; //number of integers to be read into array
t = create_tree(data, i, number);
print_inorder(t);
free(t);
return 0;
}
I get a segmentation fault, because I have a bad (dangling?) pointer, to my understanding (and please correct me if I'm wrong). When init_node which is being returned by the create_tree function is finally called, the i value being passed to the init_node function is == 3 , which refers to the last integer in my num_array. Hence, in the init_node function, if(p1 -> data <= t -> data) is an invalid statement because p1 itself cannot exist, since it would've needed an int that's taken from the num_array, but I had already reached the end of the num_array before attempting to create p1, hence p1 is a bad / dangling pointer.
My problem is in the return value of the create_tree function:
BTREE create_tree(int num_array[], int i, int size)
{
if (i >= size)
{
return NULL;
}
else
{
return (init_node(num_array[i],
create_tree(num_array, 2*i 1, size),
create_tree(num_array, 2*i 2, size)));
}
}
The point of this:
return (init_node(num_array[i],
create_tree(num_array, 2*i 1, size),
create_tree(num_array, 2*i 2, size)));
is to create NODE p1 and NODE p2 to be used by the init_node function to create a tree, that assigns p1 to the left pointer and p2 to the right pointer. p1 should contain one integer, then p2 should contain the integer contained at the very next index in the num_array. What ended up happening was that when we get to the execution of create_tree(num_array, 2*i 1, size), it recurses, and with the recursions i takes the values 0, 1, 3, then i becomes == 7, hence NULL is returned to the create_tree function, and the i value passed to create_tree(num_array, 2*i 2, size) is already == 3, so the create_tree function in this case returns NULL, and then the init_node function starts executing.
What I wanted by the create_tree recursions in the returned init_node function, was to use the integer at index i == 0 of the num_array in create_tree(num_array, 2*i 1, size), then use the integer at index i == 1 in create_tree(num_array, 2*i 2, size), and for the init_node function to be called to create the trees, and then for the alternation between the first and second create_tree function calls to continue using i == 2 and i == 3 consecutively. How can I fix my code to make it do that?
(The professor teaching the course actually implemented the code the way I did it, meaning he wrote the create_tree function the way I did, except that he used a char array containing chars a, b, c, d, e instead of an int array containing ints, and somehow his program executed properly, and mines does not, which is also very confusing.)
Below is a snippet from my course, showing generally the same logic that I used, used by the professor for his init_node and create_tree functions. He then runs the compiled program and it works just fine, and I cannot understand how that worked for him.
Thank you for all your help!
uj5u.com熱心網友回復：
我在您的示例代碼中發現了兩個關鍵缺陷。第一個可能僅在示例中，而不是您的原始版本：
int data[] = { 9, 11, 4, 5 }; //pointer to integers array
int i = 0; //represents indexes of the integers array
int number = 0; //number of integers to be read into array
t = create_tree(data, i, number);
該number變數需要設定為陣列的大小，因此它的零值將阻止代碼做太多事情。但真正的問題是init_node()功能。
在您教授的示例中，t->leftand無條件t-right設定為引數and ，可能是。但是您的代碼會進行一些條件測驗，例如when might be 。同樣對于. 而且，它可能會離開和/或未初始化。讓我們重做代碼，測驗指標的有效性：p1p2NULLif (p1->data ...p1NULLp2t->leftt->right
#include <stdio.h>
#include <stdlib.h>
typedef struct NODE
{
int data;
struct NODE *left;
struct NODE *right;
} NODE;
typedef NODE *BTREE;
BTREE create_node(void)
{
BTREE t = malloc(sizeof(NODE));
if (t == NULL)
{
perror("NODE can't be allocated!");
exit(EXIT_FAILURE);
}
return t;
}
BTREE init_node(int number, BTREE p1, BTREE p2)
{
BTREE t = create_node();
t->data = number;
t->left = NULL;
t->right = NULL;
if (p1 != NULL)
{
if (p1->data <= t->data)
{
t->left = p1;
}
else
{
t->right = p1;
}
}
if (p2 != NULL)
{
if (p2->data <= t->data)
{
t->left = p2;
}
else
{
t->right = p2;
}
}
return t;
}
BTREE create_tree(int num_array[], unsigned i, size_t size)
{
if (i >= size)
{
return NULL;
}
return init_node(num_array[i], create_tree(num_array, 2*i 1, size), create_tree(num_array, 2*i 2, size));
}
void print_inorder(BTREE t)
{
if (t != NULL)
{
printf("(");
print_inorder(t->left);
printf(" %d ", t->data);
print_inorder(t->right);
printf(")");
}
}
int main(void)
{
BTREE t = NULL;
int data[] = { 9, 11, 4, 5 }; // pointer to integers array
size_t number = sizeof(data)/sizeof(*data); // number of integers to be read into array
t = create_tree(data, 0, number);
print_inorder(t);
printf("\n");
return EXIT_SUCCESS;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qiye/455063.html
標籤：c recursion tree binary-tree
上一篇：如何從（雙重）遞回函式輸出？
下一篇：這個numba函式的錯誤是什么？