今夜午後 8 時 CDT が期限のプログラミング クラスの割り当てがあり、これに問題があります。ファイルを読み取って、次の番号のリストを取得します。
9 30 20 40 35 22 48 36 37 38
それらを配列に配置し (簡単です)、C を使用してこれらを二分探索木に読み込みます。リストの最初の数字は、ツリー内の要素の数です。残りは次の構造体に配置されます。
typedef struct node_struct {
int data;
struct node_struct* left;
struct node_struct* right;
} Node;
私は最初の部分をパットしたと思います。fscanf を使用して (私はこの方法を使用することを選択しませんでした。fgets の方が好きです)、配列の各メンバーで挿入関数を呼び出し、挿入関数内で「createNode」関数を呼び出します。
問題は、BST に 1 人のメンバーしか入れていないことです。さらに、BST は条件を満たさなければなりませんnode->left->data <= node->data < node->right->data...つまり、ノードはツリー内で順番に並んでいる必要があります。
これが私がこれまでに持っているものです：
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
// def BST node struct
typedef struct node_struct {
int data;
struct node_struct* left;
struct node_struct* right;
} Node;
// prototypes
Node* createNode(int data);
Node* bstInsert(Node* root, int data);
// helper function prototypes
void padding(char ch, int n);
void displayTree(Node* root, int depth);
int main(int argc, char **argv)
{
FILE *in = NULL;
int num_read, count=0, array_size = 0;
if(argc != 2){
printf("hw3 <input-file>\n");
return 1;
}
in = fopen(argv[1], "r");
if(in == NULL){
printf("File can not be opened.\n");
return 2;
}
// read in the first line to get the array size
fscanf(in, "%d", &array_size);
// declare the array
int array[array_size];
// read from the second line to get each element of the array
while(!feof(in)){
fscanf(in, "%d", &num_read);
array[count] = num_read;
count++;
}
fclose(in);
if (array_size != count) {
printf("data error. Make sure the first line specifies the correct number of elements.");
return 3;
}
Node *root1 = NULL, *root2 = NULL, *root3 = NULL;
int i;
// task1: construct a bst from the unsorted array
printf("=== task1: construct a bst from the unsorted array ===\n");
for (i = 0; i < array_size; i++) {
root1 = bstInsert(root1, array[i]);
}
displayTree(root1, 0);
return 0;
}
Node* bstInsert(Node* root, int data) {
if(root == NULL){
root = createNode(data);
if(root != NULL){
root= createNode(data);
}
else{
printf("%d not inserted, no memory available.\n", data);
}
}
Node* current, previous, right;
current = root;
previous = root->left;
next = root->right;
else{
if(previous->data <= current->data){
}
}
return root;
}
Node* createNode(int data) {
// TODO
Node* aRoot;
if(!data)
return NULL;
aRoot = malloc(sizeof(Node));
if(!aRoot){
printf("Unable to allocate memory for node.\n");
return NULL;
}
aRoot->data = data;
aRoot->left = NULL;
aRoot->right = NULL;
return aRoot;
}
/* helper functions to print a bst; You just need to call displayTree when visualizing a bst */
void padding(char ch, int n)
{
int i;
for (i = 0; i < n; i++)
printf("%c%c%c%c", ch, ch ,ch, ch);
}
void displayTree(Node* root, int depth){
if (root == NULL) {
padding (' ', depth);
printf("-\n");
}
else {
displayTree(root->right, depth+1);
padding(' ', depth);
printf ( "%d\n", root->data);
displayTree(root->left, depth+1);
}
}
main、createNode、displayTree、そしてpadding大丈夫だと思います。bstInsert困っているところです。有効なツリーを作成するために物事を注文する方法がわかりません。
編集：
bstInsert を編集し、さらにロジックを挿入しました。ツリーにもっと多くの葉が表示されるはずですが、残念ながら「30」という数字しか表示されません。こちらが新機能。
Node* bstInsert(Node* root, int data) {
if(root == NULL){
root = createNode(data);
if(root != NULL){
root= createNode(data);
}
else{
printf("%d not inserted, no memory available.\n", data);
}
}
else{
if(data < root->data){
bstInsert(root->left, data);
}
else if(data > root->data || data == root->data){
bstInsert(root->right, data);
}
}
return root;
}