用Python实现 以{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 Node:
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None

class BinaryTree:
    def __init__(self, arr):
        self.root = self.buildTree(arr, 0, len(arr)-1)
    
    def buildTree(self, arr, start, end):
        if start > end:
            return None
        mid = (start + end) // 2
        root = Node(arr[mid])
        root.left = self.buildTree(arr, start, mid-1)
        root.right = self.buildTree(arr, mid+1, end)
        return root
    
    def preorderTraversal(self, root):
        if not root:
            return
        print(root.val, end=' ')
        self.preorderTraversal(root.left)
        self.preorderTraversal(root.right)
    
    def inorderTraversal(self, root):
        if not root:
            return
        self.inorderTraversal(root.left)
        print(root.val, end=' ')
        self.inorderTraversal(root.right)
    
    def postorderTraversal(self, root):
        if not root:
            return
        self.postorderTraversal(root.left)
        self.postorderTraversal(root.right)
        print(root.val, end=' ')
    
    def levelorderTraversal(self, root):
        if not root:
            return
        queue = [root]
        while queue:
            node = queue.pop(0)
            print(node.val, end=' ')
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
    
    def height(self, root):
        if not root:
            return 0
        leftHeight = self.height(root.left)
        rightHeight = self.height(root.right)
        return max(leftHeight, rightHeight) + 1
    
    def countNodes(self, root):
        if not root:
            return 0
        leftCount = self.countNodes(root.left)
        rightCount = self.countNodes(root.right)
        return leftCount + rightCount + 1

if __name__ == '__main__':
    arr = ['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i']
    tree = BinaryTree(arr)
    print('先序遍历：', end='')
    tree.preorderTraversal(tree.root)
    print()
    print('中序遍历：', end='')
    tree.inorderTraversal(tree.root)
    print()
    print('后序遍历：', end='')
    tree.postorderTraversal(tree.root)
    print()
    print('层次遍历：', end='')
    tree.levelorderTraversal(tree.root)
    print()
    print('二叉树的高度：', tree.height(tree.root))
    print('二叉树节点的个数：', tree.countNodes(tree.root))

输出结果为：

先序遍历：d b h i e a f c g 
中序遍历：h b i d 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