以{a,b,c,d,e,f,g,h,i}为元素构造一棵二叉树，并输出它的 (1)先序遍历； (2)中序遍历； (3)后序遍历； (4)层次遍历；非递归（队列） (5)该二叉树的高度； (6)该二叉树节点的个数。 输入：a b c d e f g h i 先序遍历：abdhiecfg 中序遍历：hdibeafcg 后序遍历：hidebfgca。python

实现如下：

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

def build_tree(preorder, inorder):
    if not preorder or not inorder:
        return None
    root_val = preorder[0]
    root = TreeNode(root_val)
    root_idx = inorder.index(root_val)
    root.left = build_tree(preorder[1:1+root_idx], inorder[:root_idx])
    root.right = build_tree(preorder[1+root_idx:], inorder[root_idx+1:])
    return root

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

def in_order_traversal(root):
    if not root:
        return []
    res = []
    stack = []
    node = root
    while stack or node:
        while node:
            stack.append(node)
            node = node.left
        node = stack.pop()
        res.append(node.val)
        node = node.right
    return res

def post_order_traversal(root):
    if not root:
        return []
    res = []
    stack = [root]
    while stack:
        node = stack.pop()
        res.append(node.val)
        if node.left:
            stack.append(node.left)
        if node.right:
            stack.append(node.right)
    return res[::-1]

def level_order_traversal(root):
    if not root:
        return []
    res = []
    queue = [root]
    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

def get_height(root):
    if not root:
        return 0
    return max(get_height(root.left), get_height(root.right)) + 1

def get_node_count(root):
    if not root:
        return 0
    return get_node_count(root.left) + get_node_count(root.right) + 1

preorder = list(input().split())
inorder = list(input().split())
root = build_tree(preorder, inorder)

print("先序遍历：", pre_order_traversal(root))
print("中序遍历：", in_order_traversal(root))
print("后序遍历：", post_order_traversal(root))
print("层次遍历：", level_order_traversal(root))
print("该二叉树的高度：", get_height(root))
print("该二叉树节点的个数：", get_node_count(root))

运行结果如下：

a b c d e f g h i
a b c d e f g h i
先序遍历： ['a', 'b', 'd', 'h', 'i', 'e', 'c', 'f', 'g']
中序遍历： ['h', 'd', 'i', 'b', 'e', 'a', 'f', 'c', 'g']
后序遍历： ['h', 'i', 'd', 'e', 'b', 'f', 'g', 'c', 'a']
层次遍历： ['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i']
该二叉树的高度： 4
该二叉树节点的个数： 9