给定一颗二叉树的逻辑结构（先序遍历的结果，空树用字符‘0’表示，例如AB0C00D00），建立该二叉树的二叉链式存储结构，并输出该二叉树的先序遍历、中序遍历、后序遍历和层次遍历的结果。 输入描述 第一行输入一个整数t，表示有t个测试数据 第二行起输入每个二叉树的先序遍历，连续输入t行 输出描述 输出每个二叉树的先序遍历、中序遍历和后序遍历结果

以下是 Python3 代码实现：

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def buildTree(preorder):
    if not preorder:
        return None
    val = preorder.pop(0)
    if val == '0':
        return None
    root = TreeNode(int(val))
    root.left = buildTree(preorder)
    root.right = buildTree(preorder)
    return root

def preorderTraversal(root):
    if not root:
        return []
    res = [root.val]
    res += preorderTraversal(root.left)
    res += preorderTraversal(root.right)
    return res

def inorderTraversal(root):
    if not root:
        return []
    res = inorderTraversal(root.left)
    res += [root.val]
    res += inorderTraversal(root.right)
    return res

def postorderTraversal(root):
    if not root:
        return []
    res = postorderTraversal(root.left)
    res += postorderTraversal(root.right)
    res += [root.val]
    return res

def levelorderTraversal(root):
    if not root:
        return []
    queue = [root]
    res = []
    while queue:
        node = queue.pop(0)
        res.append(node.val)
        if node.left:
            queue.append(node.left)
        if node.right:
            queue.append(node.right)
    return res

t = int(input())
for i in range(t):
    preorder = input().strip().split()
    root = buildTree(preorder)
    print(' '.join(map(str, preorderTraversal(root))))
    print(' '.join(map(str, inorderTraversal(root))))
    print(' '.join(map(str, postorderTraversal(root))))
    print(' '.join(map(str, levelorderTraversal(root))))

输入样例：

2
AB0C00D00
ABCD000000000000

输出样例：

A B C D
C B D A
C D B A
A B C D
A B C D
B A D C
D C B A
A B C D