1.写出遍历序列2.根据遍历序列画出二叉树

(a) 已知前序和中序序列，{wy}确定二叉树。

例：前序：ABDEGCFH，中序：DBGEAFHC，画出二叉树。

分析：前序序列的{dy}个是根，这是解题的突破口。

步骤：①前序序列的{dy}个是根 ②在中序序列中标出根，分成左右子树 ③在前序序列中标出左右子树(根据结点个数即可) ④分别对左右子树的前序和中序序列重复以上步骤直至完成。

(b) 已知后序和中序序列，{wy}确定二叉树。

例：后序：DGEBHFCA，中序：DBGEAFHC，画出二叉树。

分析：后序序列的{zh1}一个是根，这是解题的突破口。

步骤：①后序序列的{zh1}一个是根 ②在中序序列中标出根，分成左右子树 ③在后序序列中标出左右子树(根据结点个数即可) ④分别对左右子树的后序和中序序列重复以上步骤直至完成。

(c) 已知前序和后序序列，不存在度为1的结点时能{wy}确定二叉树。

例：前序：ABDEC，后序：DEBCA，画出二叉树。又前序AB，后序BA则不能{wy}确定二叉树。

注：对于不存在度为1的结点的二叉树，首先确定根结点，然后总可以将其余结点序列划分成左右子树，以此类推即可确定二叉树。

说明：画出二叉树后可以进行遍历以便验证。

3. 编写算法

思路：按五种形态(①--⑤)分析，适度简化。

例：求二叉树结点的个数。

分析：① 0; ② 1; ③ L+1; ④ 1+R; ⑤ 1+L+R。

简化：② 1+L₌₀+R₌₀ ③ 1+L+R₌₀ ④ 1+L₌₀+R ⑤ 1+L+R 可合并成⑤一种情况。

int NodeCount ( BinTree bt )

{

if ( bt==0 ) return 0;

else return 1 + NodeCount(bt->lchild) + NodeCount(bt->rchild);

}

例：求二叉树叶子结点的个数。

分析：① 0; ② 1; ③ L; ④ R; ⑤ L+R。简化：③④⑤可合并成⑤。

int LeafCount ( BinTree bt )

{

if ( bt==0 ) return 0;

else if ( bt->lchild==0 and bt->rchild==0 ) return 1;

else return LeafCount(bt->lchild) + LeafCount(bt->rchild);

}

例：求二叉树的深度。

分析：① 0; ② 1; ③ 1+L; ④ 1+R; ⑤ 1+max(L,R)。简化：②③④⑤可合并成⑤。

int Depth ( BinTree bt )

{

if ( bt==0 ) return 0;

else return 1 + max(Depth(bt->lchild), Depth(bt->rchild));

}