对于这个程序，我必须读取大约 50 个数字的文本文件，然后我必须将它们分解(BST 的结尾由 -1 表示)。所以我很确定我使用链表来表示实际的树编号，然后使用 BST 来表示实际的树。不过，我的 while 循环遇到了一些麻烦，当数字为 -1 时，要分解树。示例输出如下。
Tree 1: 5 8 14 15 17 19 20 30
Tree 2: 28 60 65 80 83 86 90
Tree 3: 33 40 41 42 43 45 49
Tree 4: 1 4 13 21 47 72
Tree 5: 16 55 69 77 111
文本文件是......
15
8
14
5
19
20
17
30
-1
80
65
60
86
83
90
28
-1
42
45
49
40
43
33
41
-1
13
47
21
72
1
4
-1
55
16
69
77
111
-1
#include<stdio.h>
#include<stdlib.h>
#define MAX_LINE_SIZE 20
typedef struct BST {
int value;
int treeNum;
struct BST* left;
struct BST* right;
}BST;
typedef struct rootList {
struct BST* root;
struct rootList* next;
}rootList;
void insert_BST(BST** root, int insertValue, int treeNum);
BST* createTreeNode(int nodeValue, int treeNum);
void printTrees(rootList* listHead);
void free_BSTs(BST* root);
void insert_rootList(rootList** listHead, BST* root);
void print_BST_inorder(BST* root);
int main (int argc, char* argv[]){
if (argc != 2){
printf("Incorrect number of command args\n");
return 1;
}
FILE *input = fopen(argv[1], "r");
while(input == NULL){
char file[100];
printf("Unable to open file, enter a new name: ");
scanf("%99s", file);
input = fopen(file, "r");
}
int value;
int treeNum = 1;
BST **root;
rootList **listHead;
while (fscanf(input, "%d", &value) != EOF){
while(value != -1){
insert_BST(root, value, treeNum);
}
treeNum++;
insert_rootList(listHead,(*root));
}
return 0;
}
/*createTreeNode
* * parameters: int value to be inserted in the binary search tree
* * returns: pointer to a newly created binary search tree node (BST*)
* * -> createTreeNode simply creates a new tree node using the value passed as the
* * parameter.*/
BST* createTreeNode(int nodeValue, int treeNum){
BST *new_bst = (BST*)malloc(sizeof(BST));
new_bst->value = nodeValue;
new_bst->treeNum = treeNum;
new_bst->right = new_bst->left = 0;
return new_bst;
}
/* insert_BST
* * parameters: the reference of the root (BST**) and the int value to be inserted.
* * returns: void
* *
* * -> This function recursively finds the right position in the binary search tree
* * for the new value and inserts the node containing the new value in that position.
* * */
void insert_BST(BST** root, int insertValue, int treeNum){
*root = createTreeNode(insertValue, treeNum);
if(root != 0){
if(insertValue < (*root)->value)
insert_BST((*root)->right, insertValue, treeNum);
else if (insertValue > (*root)->value)
insert_BST((*root)->left, insertValue, treeNum);
return;
}
}
/*insert_rootList
* * parameters: the reference of the head pointer to the list (BST**) and pointer to the root of the new binary search tree
* * returns: void
* *
* * -> This function inserts the new binary search tree at the BACK of the linked
* * list containing pointers to the roots of the binary search trees.
* * */
void insert_rootList(rootList** listHead, BST* new_root){
rootList *temp = (rootList*)malloc(sizeof(rootList));
temp->root = new_root;
temp->next = NULL;
if((*listHead)->next == NULL){
(*listHead)->next = temp;
}
else
{
rootList *current = *listHead;
while((*listHead)->next != NULL){
if(current->next == NULL)
{
current->next = temp;
break;
}
current = current->next;
}
}
return;
}
/* printTrees
* * parameters: pointer to the head of the linked list
* * returns: void
* *
* * -> This Function prints all the binary search trees in the linked list
* * */
void printTrees(rootList* listHead){
while(listHead != NULL){
print_BST_inorder(*listHead);
}
}
/* print_BST_inorder
* * parameters: pointer to the root of the tree
* * returns: void
* *
* * -> This Function prints the binary search tree using inorder traversal
* * */
void print_BST_inorder(BST* root){
print_BST_inorder(root->left);
printf("%d", root->value);
print_BST_inorder(root->right);
}
这些是我编译时遇到的错误
homework3.c: In function ‘insert_BST’:
homework3.c:101: warning: passing argument 1 of ‘insert_BST’ from incompatible pointer type
homework3.c:95: note: expected ‘struct BST **’ but argument is of type ‘struct BST *’
homework3.c:103: warning: passing argument 1 of ‘insert_BST’ from incompatible pointer type
homework3.c:95: note: expected ‘struct BST **’ but argument is of type ‘struct BST *’
homework3.c: In function ‘printTrees’:
homework3.c:157: warning: passing argument 1 of ‘print_BST_inorder’ from incompatible pointer type
homework3.c:28: note: expected ‘struct BST *’ but argument is of type ‘struct rootList *’
最佳答案
将 insert_BST 函数替换为:
insert_BST(&(*root)->right, insertValue, treeNum);
和
insert_BST(&(*root)->left, insertValue, treeNum);
将 print_BST_inorder 的调用更改为:
print_BST_inorder(listHead->root);
说明:
(*root)->right 和 (*root)->left 的类型为 struct BST*，但是 insert_BST 函数采用 struct BST**，因此您只需取消引用它们即可。
listHead 的类型为 rootList*，因此 *listHead 是一个 rootList，而 print_BST_inorder 函数需要一个 BST*，它是该结构的成员 root。
关于c - 如何读取文本文件并将值存储到多个二叉树中，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/23161757/