我一直在努力写那个；
我将从一个文本文件中接收到一定数量的输入，它会一直持续到 -1 -1(第一个是学生 ID，第二个是学生成绩)
例如;
121 40
456 50
445 60
123 70
677 80
546 90
我的输出将是学生成绩及其 ID 的排序列表(我这样做了。)
我的程序还应按以下方式打印二叉搜索树(第一个数字代表学生 ID，第二个数字显示年级，括号中的数字显示父节点。L 代表左 child ，R 代表右 child )。
这意味着输出将是;
123 70
456 50 (70 L) 546 90 (70 R)
121 40 (50 L) 445 60 (50 R) 677 80 (90 L)
我写了这段代码，但有些东西我无法修复。 printParent() 函数应该是固定的。它应该在树的每一层打印“\n”。
#include <stdlib.h>
#include <stdio.h>
struct node{
struct node *left;
int ID;
int Grade;
struct node *right;
};
struct node* newNode(int,int);
struct node* insertNode(struct node *node,int id,int grade);
void printTree(struct node *node);
void printParent(struct node*);
int main() {
struct node *head = NULL;
FILE *file = fopen("input.txt","r");
int stdID,grade;
while (!feof(file)) {
fscanf(file,"%d %d",&stdID,&grade);
if (stdID && grade == -1){
break;}
else
head = insertNode(head,stdID,grade);
}
printTree(head);
printf("\n");
printf("%d %d\n",head->ID,head->Grade);
printParent(head);
printf("\n");
fclose(file);
return 0;
}
struct node* newNode(int id,int grade){
struct node *newnode = malloc(sizeof(struct node));
newnode->ID = id;
newnode->Grade = grade;
newnode->left = newnode->right = NULL;
return newnode;
}
struct node* insertNode(struct node *node,int id,int grade){
if (node == NULL)
return newNode(id,grade);
if ( grade < node->Grade)
node->left = insertNode(node->left,id,grade);
else if ( grade >= node->Grade)
node->right = insertNode(node->right,id,grade);
return node;
}
void printTree(struct node *node){
if (node == NULL)
return;
printTree(node->left);
printf("%d %d\n", node->ID,node->Grade);
printTree(node->right);
}
void printParent(struct node *node){
struct node *temp = node;
if (temp == NULL)
return;
if (temp->left != NULL){
printf("%d %d (%d L) ",temp->left->ID,temp->left->Grade,temp->Grade);
}
if (temp->right != NULL){
printf("%d %d (%d R) ",temp->right->ID,temp->right->Grade,temp->Grade);
}
printParent(temp->left);
printParent(temp->right);
}
最佳答案
如评论中所述，我认为您需要进行广度优先搜索 (BFS)，跟踪级别，以便在级别之间转换时可以输出换行符。
这里是相当稳健地完成工作的代码。它使用一个 FIFO 队列来记录哪些节点需要处理。队列适度健壮，但如果要求添加一个没有空间的元素，它会突然停止。解决这个问题是可行的，但有点繁琐(动态内存分配，但困难的部分是在队列数组增长但队列中的索引不在开始时处理正确的复制，这通常是这种情况)。
#include <assert.h>
#include <inttypes.h>
#include <stdio.h>
#include <stdlib.h>
struct node
{
struct node *left;
int ID;
int Grade;
struct node *right;
};
struct node *newNode(int, int);
struct node *insertNode(struct node *node, int id, int grade);
void printTree(struct node *node);
void printParent(struct node *);
int main(int argc, char **argv)
{
const char *name = "input.txt";
if (argc == 2)
name = argv[1];
struct node *head = NULL;
FILE *file = fopen(name, "r");
if (file == 0)
{
fprintf(stderr, "%s: failed to open file %s for reading\n", argv[0], name);
return 1;
}
printf("File: %s\n", name);
int stdID, grade;
while (fscanf(file, "%d %d", &stdID, &grade) == 2)
{
if (stdID == -1 && grade == -1)
break;
printf("Read: %d %d\n", stdID, grade);
head = insertNode(head, stdID, grade);
//printf("Tree:\n");
//printTree(head);
}
fclose(file);
printf("Completed tree:\n");
printTree(head);
printf("\n");
printf("%3d %3d\n", head->ID, head->Grade);
printf("Parent tree:\n");
printParent(head);
printf("\n");
return 0;
}
struct node *newNode(int id, int grade)
{
struct node *newnode = malloc(sizeof(struct node));
newnode->ID = id;
newnode->Grade = grade;
newnode->left = newnode->right = NULL;
return newnode;
}
struct node *insertNode(struct node *node, int id, int grade)
{
if (node == NULL)
return newNode(id, grade);
if (grade < node->Grade)
node->left = insertNode(node->left, id, grade);
else if (grade >= node->Grade)
node->right = insertNode(node->right, id, grade);
return node;
}
void printTree(struct node *node)
{
if (node == NULL)
return;
printTree(node->left);
printf("%3d %3d (0x%.12" PRIXPTR ": 0x%.12" PRIXPTR " - 0x%.12" PRIXPTR ")\n",
node->ID, node->Grade,
(uintptr_t)node, (uintptr_t)node->left, (uintptr_t)node->right);
printTree(node->right);
}
/* Structures to manage BFS - breadth-first search */
struct bfs_node
{
struct node *parent;
struct node *child;
char side[4]; /* "L" or "R" plus padding */
int level;
};
enum { MAX_QUEUE_SIZE = 100 };
struct bfs_queue
{
struct bfs_node q[MAX_QUEUE_SIZE];
size_t q_head;
size_t q_tail;
};
static void bfs_add(struct bfs_queue *q, struct node *parent, struct node *child, int level, char side)
{
assert(q != 0 && parent != 0 && child != 0);
assert(parent->left == child || parent->right == child);
assert(side == 'L' || side == 'R');
assert(q->q_head < MAX_QUEUE_SIZE && q->q_tail < MAX_QUEUE_SIZE);
size_t next = (q->q_head + 1) % MAX_QUEUE_SIZE;
if (next == q->q_tail)
{
fprintf(stderr, "Queue is full\n");
exit(EXIT_FAILURE);
}
q->q[q->q_head] = (struct bfs_node){ .parent = parent, .child = child,
.level = level, .side = { side, '\0' } };
q->q_head = next;
}
static inline void bfs_init(struct bfs_queue *q)
{
assert(q != 0);
q->q_head = q->q_tail = 0;
}
static inline int bfs_empty(const struct bfs_queue *q)
{
assert(q != 0);
return (q->q_head == q->q_tail);
}
static struct bfs_node *bfs_remove(struct bfs_queue *q)
{
if (q->q_tail == q->q_head)
{
fprintf(stderr, "cannot remove anything from an empty queue\n");
exit(EXIT_FAILURE);
}
assert(q->q_head < MAX_QUEUE_SIZE && q->q_tail < MAX_QUEUE_SIZE);
size_t curr = q->q_tail;
q->q_tail = (q->q_tail + 1) % MAX_QUEUE_SIZE;
return &q->q[curr];
}
void printParent(struct node *node)
{
if (node == 0)
{
printf("Empty tree\n");
return;
}
int level = 0;
struct bfs_queue q;
bfs_init(&q);
if (node->left)
bfs_add(&q, node, node->left, level + 1, 'L');
if (node->right)
bfs_add(&q, node, node->right, level + 1, 'R');
printf("Level %d: %3d %3d", level, node->ID, node->Grade);
while (!bfs_empty(&q))
{
struct bfs_node *data = bfs_remove(&q);
assert(data != 0);
if (data->level != level)
{
assert(data->level == level + 1);
putchar('\n');
level = data->level;
printf("Level %d:", level);
}
struct node *child = data->child;
assert(child != 0);
if (child->left)
bfs_add(&q, child, child->left, level + 1, 'L');
if (child->right)
bfs_add(&q, child, child->right, level + 1, 'R');
//printf(" %3d %3d (%3d %s)", child->ID, child->Grade, data->parent->ID, data->side);
printf(" %3d %3d (%3d %s)", child->ID, child->Grade, data->parent->Grade, data->side);
}
putchar('\n');
}
请注意，读取数据的代码已进行了相当大的修改，避免了 feof() 函数，并且还接受命令行文件名而不仅仅是固定文件名——但默认为原始文件名.如果无法打开文件，它还会报告错误。读取时，它会报告读取的数据。对于调试，在每行之后打印树是有帮助的，直到你让它工作正常。 (代码是可以发布的。)我将地址添加到打印输出中；它有助于识别/验证树结构。
在按等级排序的给定输入文件中，您最终会得到一棵具有 6 级 (0..5) 的倾斜树:
File: input.original
Read: 121 40
Read: 456 50
Read: 445 60
Read: 123 70
Read: 677 80
Read: 546 90
Completed tree:
121 40 (0x7FCCD3C00340: 0x000000000000 - 0x7FCCD3C02780)
456 50 (0x7FCCD3C02780: 0x000000000000 - 0x7FCCD3C027A0)
445 60 (0x7FCCD3C027A0: 0x000000000000 - 0x7FCCD3C027C0)
123 70 (0x7FCCD3C027C0: 0x000000000000 - 0x7FCCD3C027E0)
677 80 (0x7FCCD3C027E0: 0x000000000000 - 0x7FCCD3C02800)
546 90 (0x7FCCD3C02800: 0x000000000000 - 0x000000000000)
121 40
Parent tree:
Level 0: 121 40
Level 1: 456 50 ( 40 R)
Level 2: 445 60 ( 50 R)
Level 3: 123 70 ( 60 R)
Level 4: 677 80 ( 70 R)
Level 5: 546 90 ( 80 R)
要获得请求的输出，您需要一个不同的输入文件:
123 70
456 50
546 90
121 40
445 60
677 80
这会产生:
File: input.req
Read: 123 70
Read: 456 50
Read: 546 90
Read: 121 40
Read: 445 60
Read: 677 80
Completed tree:
121 40 (0x7F99B94027C0: 0x000000000000 - 0x000000000000)
456 50 (0x7F99B9402780: 0x7F99B94027C0 - 0x7F99B94027E0)
445 60 (0x7F99B94027E0: 0x000000000000 - 0x000000000000)
123 70 (0x7F99B9400340: 0x7F99B9402780 - 0x7F99B94027A0)
677 80 (0x7F99B9402800: 0x000000000000 - 0x000000000000)
546 90 (0x7F99B94027A0: 0x7F99B9402800 - 0x000000000000)
123 70
Parent tree:
Level 0: 123 70
Level 1: 456 50 ( 70 L) 546 90 ( 70 R)
Level 2: 121 40 ( 50 L) 445 60 ( 50 R) 677 80 ( 90 L)
给定输入文件:
305 8
772 51
140 83
877 53
499 74
183 3
240 21
810 49
159 68
977 36
385 3
252 35
163 76
283 12
740 46
829 42
526 51
401 64
726 65
226 3
902 75
(ID 使用 100 到 999 之间的随机数生成，成绩使用 0 到 100 之间的随机数生成)，输出为:
File: input-21.txt
Read: 305 8
Read: 772 51
Read: 140 83
Read: 877 53
Read: 499 74
Read: 183 3
Read: 240 21
Read: 810 49
Read: 159 68
Read: 977 36
Read: 385 3
Read: 252 35
Read: 163 76
Read: 283 12
Read: 740 46
Read: 829 42
Read: 526 51
Read: 401 64
Read: 726 65
Read: 226 3
Read: 902 75
Completed tree:
183 3 (0x7FE3795000A0: 0x000000000000 - 0x7FE379500140)
385 3 (0x7FE379500140: 0x000000000000 - 0x7FE379500260)
226 3 (0x7FE379500260: 0x000000000000 - 0x000000000000)
305 8 (0x7FE379500000: 0x7FE3795000A0 - 0x7FE379500020)
283 12 (0x7FE3795001A0: 0x000000000000 - 0x000000000000)
240 21 (0x7FE3795000C0: 0x7FE3795001A0 - 0x7FE3795000E0)
252 35 (0x7FE379500160: 0x000000000000 - 0x000000000000)
977 36 (0x7FE379500120: 0x7FE379500160 - 0x7FE3795001C0)
829 42 (0x7FE3795001E0: 0x000000000000 - 0x000000000000)
740 46 (0x7FE3795001C0: 0x7FE3795001E0 - 0x000000000000)
810 49 (0x7FE3795000E0: 0x7FE379500120 - 0x000000000000)
772 51 (0x7FE379500020: 0x7FE3795000C0 - 0x7FE379500040)
526 51 (0x7FE379500200: 0x000000000000 - 0x000000000000)
877 53 (0x7FE379500060: 0x7FE379500200 - 0x7FE379500080)
401 64 (0x7FE379500220: 0x000000000000 - 0x7FE379500240)
726 65 (0x7FE379500240: 0x000000000000 - 0x000000000000)
159 68 (0x7FE379500100: 0x7FE379500220 - 0x000000000000)
499 74 (0x7FE379500080: 0x7FE379500100 - 0x7FE379500180)
902 75 (0x7FE379500280: 0x000000000000 - 0x000000000000)
163 76 (0x7FE379500180: 0x7FE379500280 - 0x000000000000)
140 83 (0x7FE379500040: 0x7FE379500060 - 0x000000000000)
305 8
Parent tree:
Level 0: 305 8
Level 1: 183 3 ( 8 L) 772 51 ( 8 R)
Level 2: 385 3 ( 3 R) 240 21 ( 51 L) 140 83 ( 51 R)
Level 3: 226 3 ( 3 R) 283 12 ( 21 L) 810 49 ( 21 R) 877 53 ( 83 L)
Level 4: 977 36 ( 49 L) 526 51 ( 53 L) 499 74 ( 53 R)
Level 5: 252 35 ( 36 L) 740 46 ( 36 R) 159 68 ( 74 L) 163 76 ( 74 R)
Level 6: 829 42 ( 46 L) 401 64 ( 68 L) 902 75 ( 76 L)
Level 7: 726 65 ( 64 R)
我试验了 200 条成绩记录，没有问题。该数据在树中有 19 个级别，记录最多的级别有 28 个记录。它并没有强调队列大小，但它应该至少绕过队列末端一次。
我可能会添加命令行选项来控制是否在添加数据时报告数据，以及是否在打印树时打印地址，等等。我还会添加代码来释放树，然后准备好在给定多个文件名时循环处理多个文件，或者在没有给定文件时处理标准输入。然而，这有点超出了眼前的问题。
关于c - 如何打印带父节点的层序二叉搜索树，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/47577238/