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

以下是Python3代码实现：

class Node:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None

def build_tree(arr):
    if not arr:
        return None
    mid = len(arr) // 2
    root = Node(arr[mid])
    root.left = build_tree(arr[:mid])
    root.right = build_tree(arr[mid+1:])
    return root

def preorder_traversal(root):
    if not root:
        return
    print(root.value, end=' ')
    preorder_traversal(root.left)
    preorder_traversal(root.right)

def inorder_traversal(root):
    if not root:
        return
    inorder_traversal(root.left)
    print(root.value, end=' ')
    inorder_traversal(root.right)

def postorder_traversal(root):
    if not root:
        return
    postorder_traversal(root.left)
    postorder_traversal(root.right)
    print(root.value, end=' ')

def level_order_traversal(root):
    if not root:
        return
    queue = [root]
    while queue:
        node = queue.pop(0)
        print(node.value, end=' ')
        if node.left:
            queue.append(node.left)
        if node.right:
            queue.append(node.right)

def tree_height(root):
    if not root:
        return 0
    left_height = tree_height(root.left)
    right_height = tree_height(root.right)
    return max(left_height, right_height) + 1

def node_count(root):
    if not root:
        return 0
    left_count = node_count(root.left)
    right_count = node_count(root.right)
    return left_count + right_count + 1

arr = ['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i']
root = build_tree(arr)

print("先序遍历：", end='')
preorder_traversal(root)
print()

print("中序遍历：", end='')
inorder_traversal(root)
print()

print("后序遍历：", end='')
postorder_traversal(root)
print()

print("层次遍历：", end='')
level_order_traversal(root)
print()

print("二叉树的高度为：", tree_height(root))

print("二叉树的节点个数为：", node_count(root))

输出结果：

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