试图通过存储在二进制文件中的预遍历来构建树？

Question

我有一个二进制文件的示例：

0000000: 11111011 11111111 11111111 11111111 00000001 11111100  ......
0000006: 11111111 11111111 11111111 00000001 11111101 11111111  ......
000000c: 11111111 11111111 00000001 11111110 11111111 11111111  ......
0000012: 11111111 00000001 11111111 11111111 11111111 11111111  ......
0000018: 00000001 00000000 00000000 00000000 00000000 00000001  ......
000001e: 00000001 00000000 00000000 00000000 00000001 00000010  ......
0000024: 00000000 00000000 00000000 00000001 00000101 00000000  ......
000002a: 00000000 00000000 00000001 00000100 00000000 00000000  ......
0000030: 00000000 00000000                                      ..

这是同一文件的txt表示，其中每一行代表一个节点：

-5 1
-4 1
-3 1
-2 1
-1 1
 0 1
 1 1
 2 1
 5 1
 4 0

第一个数字是节点的值。下一个数字表示该节点有多少个子代。 0表示没有孩子。 1表示一个合适的孩子。 2表示剩下一个孩子。 3表示两个孩子。

这是节点的结构：

struct Tnode {
int key;
char child;
struct Tnode * left;
struct Tnode * right;
} Tnode;

当前，对于每个节点，我尝试使用fread两次，一次是获取int密钥，然后是char子级。但是，考虑到二叉树包含预遍历，我如何才能真正构建树？我们遇到的第一个节点必须是根节点。由于它旁边有一个1，因此它将只有一个正确的子代（将存储在char子代中）。因此，下一个节点必须是该节点的正确子节点，依此类推。基本上，在这个示例中，权利一直继续下去，直到以4结尾。但是我在构建它时遇到了麻烦。有提示吗？

Answer 1

您可以使用递归来解决此问题：

您创建一个函数read_node，该函数带有一个参数，该参数是应指向新节点的指针的地址。首次调用该函数时，这将是指向根节点的指针的地址。

功能read_node首先为一个struct Tnode分配内存。然后，它从文件中读取int key和char child，并将该信息写入新分配的struct Tnode。然后，它将新创建的节点的地址写到它作为函数参数接收到的地址（在第一个函数调用上是指向根节点的指针的地址）。这样，新节点现在已正确链接到树。如果新节点有一个正确的子节点，则函数read_node现在将递归调用其自身，但是此函数调用的函数参数这次将为其right成员变量的地址。如果没有正确的孩子，则将right成员变量设置为NULL。然后对左孩子执行相同的操作，然后函数返回。

在所有递归函数调用返回后，您应该具有一个完整的二叉树。