c - 试图从存储在二进制文件中的前序遍历中构建树？

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 结尾。但我在构建它时遇到了麻烦。有小费吗？

标签： cstructtreebinarytree-traversal

Answer 1

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

你创建一个函数process_node，它接受一个参数，它是应该指向新节点的指针的地址。第一次调用该函数时，这将是指向根节点的指针的地址。

该函数process_node执行以下操作：

1. 它为一个分配内存struct Tnode。
2. 然后它读取int key和char childfrom 文件并将该信息写入新分配的struct Tnode.
3. 然后它将新创建的节点的地址写入它作为函数参数接收的地址（在第一次函数调用时，它是指向根节点的指针的地址）。这样，新节点现在正确链接到树。
4. 如果新节点有一个右子节点，那么函数process_node现在将递归调用自身，但这次函数调用的函数参数将是其right成员变量的地址。这样，新调用的函数将改为写入该地址。如果节点没有右孩子，则right成员变量设置为NULL。
5. 对左孩子重复第 4 步。
6. 函数返回。

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