如何从preorder树遍历生成的数组重构二进制树(How to reconstrunct a binary tree from an array produced by preorder tree

如何从preorder树遍历生成的数组重构二进制树(How to reconstrunct a binary tree from an array produced by preorder tree traversal)

我被要求实现一个预订树遍历函数，该函数应该返回一个表示树的数组，然后我被要求实现一个函数来重建我之前函数返回的数组中的树。 类似于从一台PC发送二叉树然后在接收端接收和重建它。 重要的是数据应该只传输一次，所以我不能使用标准的预订和顺序组合。

在我的解决方案中，打印每个节点，然后添加到包含所有打印节点的数组中，如果节点没有左子树，它将打印并添加字母“L”，如果树没有t有一个正确的子树，它将打印并将字母“R”添加到数组中。

那部分很容易，但是，我不知道如何重建接收方的树。 任何帮助或想法将非常感激。

以下是我为发送部分所做的事情：

class TreeNode(object): """This class represents a tree.""" def __init__(self, data, left=None, right=None): self.data = data self.left = left self.right = right def send(arr_tree, data): print(data) arr_tree.append(data) def send_sub_tree(arr_tree, node): send(arr_tree, node.data) if node.left is None: send(arr_tree, "L") else: send_sub_tree(arr_tree, node.left) if node.right is None: send(arr_tree, "R") else: send_sub_tree(arr_tree, node.right) if __name__ == '__main__': tree = TreeNode(1, TreeNode(2, TreeNode(4), TreeNode(5)), TreeNode(3, TreeNode(6), TreeNode(7))) received_tree = [] send_sub_tree(received_tree, tree) reconstructed_tree = reconstruct_tree(received_tree)

编辑：

我已经设法实现了某种类似的工作，但是它很乱并且没有完美地重建发送的部分：

def reconstruct_tree(arr_tree): node = TreeNode(arr_tree[0]) print(node.data) if arr_tree[1] == "L" and arr_tree[2] == "R": if len(arr_tree) > 3 and arr_tree[3] != "L" and arr_tree[3] != "R": node.right = reconstruct_tree(arr_tree[3:]) else: return node if arr_tree[1] != "L": node.left = reconstruct_tree(arr_tree[1:]) return node return node

I was asked to implement a preorder tree traversal function, that function should have returned an array representing the tree, and then I was asked to implement a function to reconstruct the tree from the array my previous function returned. Something like sending a binary tree from one pc and then receiving and reconstructing it on the receiving end. The important part is that the data should only be transferred once, so I couldn't use the standard preorder and inorder combination.

In my solution, each node is printed, and then added to an array that contains all of the printed nodes, if a node doesn't have a left subtree it will print and add the letter "L", and if the tree doesn't have a right subtree it will print and add the letter "R" to the array.

That part was easy, however, I didn't know how to reconstruct the tree on the receiving side. Any help or idea will be really appreciated.

Here is what I have done for the sending part:

class TreeNode(object): """This class represents a tree.""" def __init__(self, data, left=None, right=None): self.data = data self.left = left self.right = right def send(arr_tree, data): print(data) arr_tree.append(data) def send_sub_tree(arr_tree, node): send(arr_tree, node.data) if node.left is None: send(arr_tree, "L") else: send_sub_tree(arr_tree, node.left) if node.right is None: send(arr_tree, "R") else: send_sub_tree(arr_tree, node.right) if __name__ == '__main__': tree = TreeNode(1, TreeNode(2, TreeNode(4), TreeNode(5)), TreeNode(3, TreeNode(6), TreeNode(7))) received_tree = [] send_sub_tree(received_tree, tree) reconstructed_tree = reconstruct_tree(received_tree)

EDIT:

I have managed to implement something that kind-of works, but its messy and doesn't reconstruct the sent part perfectly:

def reconstruct_tree(arr_tree): node = TreeNode(arr_tree[0]) print(node.data) if arr_tree[1] == "L" and arr_tree[2] == "R": if len(arr_tree) > 3 and arr_tree[3] != "L" and arr_tree[3] != "R": node.right = reconstruct_tree(arr_tree[3:]) else: return node if arr_tree[1] != "L": node.left = reconstruct_tree(arr_tree[1:]) return node return node

最满意答案

这是你如何做到的。 我还在类中移动了函数，重命名了它们，并进行了一些修改：

class TreeNode(object): """This class represents a tree.""" def __init__(self, data, left=None, right=None): self.data = data self.left = left self.right = right def to_list(self): return [self.data] + ( self.left.to_list() if self.left else ["L"] ) + ( self.right.to_list() if self.right else ["R"] ) @staticmethod def from_list(lst): def recurse(it): try: data = next(it) except StopIteration: # Only happens if list is incomplete return if data == 'L' or data == 'R': return return TreeNode(data, recurse(it), recurse(it)) return recurse(iter(lst)) tree = TreeNode(1, TreeNode(2, TreeNode(4), TreeNode(5) ), TreeNode(3, TreeNode(6), TreeNode(7) ) ) lst = tree.to_list() print(lst) # Reverse operation recovered_tree = TreeNode.from_list(lst) # Make that a list again to see if it is the same tree lst2 = recovered_tree.to_list() print(lst2) # Same as lst

看它在repl.it上运行

请注意，您也可以使用“L”表示右侧子项，或者使用“R”表示左侧子项，因为数组中的位置已经确定了哪个孩子的意图。 一个特殊符号就足够了。

Here is how you could do it. I have also moved your functions inside the class, renamed them, and made some modifications:

class TreeNode(object): """This class represents a tree.""" def __init__(self, data, left=None, right=None): self.data = data self.left = left self.right = right def to_list(self): return [self.data] + ( self.left.to_list() if self.left else ["L"] ) + ( self.right.to_list() if self.right else ["R"] ) @staticmethod def from_list(lst): def recurse(it): try: data = next(it) except StopIteration: # Only happens if list is incomplete return if data == 'L' or data == 'R': return return TreeNode(data, recurse(it), recurse(it)) return recurse(iter(lst)) tree = TreeNode(1, TreeNode(2, TreeNode(4), TreeNode(5) ), TreeNode(3, TreeNode(6), TreeNode(7) ) ) lst = tree.to_list() print(lst) # Reverse operation recovered_tree = TreeNode.from_list(lst) # Make that a list again to see if it is the same tree lst2 = recovered_tree.to_list() print(lst2) # Same as lst

See it run on repl.it

Note that you could use "L" for the right-side child as well, or "R" for the left one, as the position in the array already leaves no doubt about which child is intended. One special symbol is enough.