3

我最近在面试时遇到了这个问题，面试官要求我创建两个函数。Function1 应该采用 n 叉树并转换为字节数组，而 function2 应该采用 byte[] 并构建 n 叉树。如果它是一棵二叉树，我会使用 null 的特殊字符进行预排序遍历并存储在数组中并转换为 byte[] 但这里是 n-ary 树（有很多孩子）。我不知道如何存储它并用数组重建 n 叉树。将这个 n 元树存储到数组中的任何想法或公式？我感谢您的帮助。

4

4 回答 4

2

需要区分两种情况：1.完全 n-ary Trees和 2. sparse n-ary or non-Complete Trees。在第一种情况下，假设N=5，因此 Tree 中的每个级别i将恰好具有（即不少于，不多）5^i个节点；另一方面，在第二种情况下，此规则无效，因为可以通过构造随机填充树。

完整的n叉树可以序列化成数组；简单地从完整的二叉搜索树扩展：节点（中间节点和叶子节点）通过级别i相互关联，实际N通过论坛N i+1+c* 相互关联，其中c是第 c 个子节点。采用级别顺序遍历，树可以在字节数组中优化序列化（不需要更多字符，请阅读下文）。这里有一个全面的解释。

不幸的是，对于非完全 n 元树，正如预期的那样，上述公式不适用。因此需要采用不同的方法。一种方法包括序列化指示不存在子代的特殊字符，或者更好地序列化子代指针的 N​​ULL 值。这种方法不是最优的，因为需要更多的字符（总共需要N个额外的字节），但它是一种非常简单且可行的方法。让我们看一个例子：

       A
     / | \ 
    B  C  D
   / \     \
  E   F     G

采用前序遍历，将上述非完全n叉树序列化如下

 A B E / F / / C / D G / / /

'/' 映射 NULL 并提供将树反序列化为原始树的能力。采用先序遍历的方式访问Tree，输出上述字符数组。总共 *2*N* 个字节被序列化，因为在这种情况下，每个 Tree 值正好是 1 个字符。作为反序列化算法，仍然可以采用前序遍历：只需少量修改即可识别 NULL 映射模式，如上所示。一个 C++ 代码示例在这里。

总结、序列化和反序列化非完整或稀疏的 n 元树有点棘手，需要更多的字节来强制映射 NULL。

于 2015-02-22T21:28:13.380 回答
2

在我看来，递归是一个很好的用途。编写一个方法（子例程、函数），写出一个节点和它下面的所有树。它会写出节点，然后写出子节点的数量（叶节点为零），然后调用自己来写入每个子节点（如果有的话）。现在调用树中顶部节点上的方法，您已经对其进行了序列化。

要反序列化，请编写一个读取节点的方法。它将读取节点本身，读取子节点的数量，然后读取每个子节点（如果有）。在流上调用它一次，它将把所有后代节点都放在适当位置的顶部节点交给你——整个树。

这个故事的寓意是递归（实际上只是一种获取和使用堆栈的便捷方式）对于处理图形非常有用。图表比你想象的要多得多。

于 2013-11-22T21:05:15.007 回答
0

Actually wikipedia helped me to find solution. I am able to store the n-ary tree into array and convert into byte[] and then convert the byte[] back to array using the below formula c-th child is found at index k*i + 1 + c parent is found at index i -1/2

于 2013-11-27T02:28:39.347 回答
0

这是代码，BFS + Queue，应该可以直接阅读。

class Node:
    def __init__(self, val):
        self.val = val 
        self.children = []

class Codec:
    def serialize(self, root):
        if root is None:
            return ""
        res = [root.val, "#"]
        q = collections.deque([root])
        while q:
            node = q.popleft()
            for child in node.children:
                res.append(child.val)
                q.append(child)
            res.append("#")
        return ",".join(res)

    def deserialize(self, s):
        if len(s) == 0:
            return
        vals = s.split(",")
        q = collections.deque()
        root = Node(vals[0])
        q.append(root)
        i = 1
        while q:
            node = q.popleft()
            i += 1
            while vals[i] != "#":
                child = Node(vals[i])
                node.children.append(child)
                q.append(child)
                i += 1
        return root
于 2019-03-13T20:41:31.307 回答