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

非常抱歉，我之前的回答中有误，下面是正确的答案：

以下是以{a,b,c,d,e,f,g,h,i}为元素构造的二叉树：

        a
      /   \
     b     c
    / \   / \
   d   e f   g
          \
           h
            \
             i

(1) 先序遍历：a,b,d,e,c,f,h,i,g

(2) 中序遍历：d,b,e,a,f,h,c,g,i

(3) 后序遍历：d,e,b,h,i,f,g,c,a

(4) 层次遍历：a,b,c,d,e,f,g,h,i

(5) 该二叉树的高度为3。

(6) 该二叉树的节点个数为9。