统计二叉树中叶子结点的个数
算法基本思想：先序
(
或中序或后序
)
遍历二叉树，在遍历过程中查找叶子结点，并计数。由此，需在遍
历算法中增添一个
“
计数
”
的参数，并将算法中
“
访问结点
”
的操作改为：若是叶子，则计数器增
1
。
求二叉树深度
算法基本思想：首先分析二叉树的深度和它的左、右子树深度之间的关系。从二叉树深度的定义可知，
二叉树的深度应为其左、右子树深度的最大值加
1
。由此，需先分别求得左、右子树的深度，算法中
“
访
问结点
”
的操作为：求得左、右子树深度的最大值，然后加
1
。
复制二叉树
算法思想：复制出左子树和右子树，之后创建左右子树的根节点。
输出二叉树上从根到所有叶子结点的路径
算法思想：对二叉树做前序遍历，遇到节点则对应节点数据入栈，如果节点是叶子节点，则将当前栈内
数据进行遍历输出，之后弹出栈顶元素；否则递归执行上面的操作，对左子树和右子树进行操作，弹出
栈顶元素
建立二叉树的存储结构
通过输入一个二叉树的字符串描述，获得二叉树的在链式存储结构体。
首先扩展二叉树，对二叉树的每个节点的空指针引出一个虚节点，其值设为
‘#’
，称这种树为扩展二叉 树。
根据前序遍历和中序遍历得到后续遍历
给定前序遍历和中序遍历结果，请问这个树的后序遍历结果是多少？例如已知前序遍历序列为
ABCDEF
中序遍历序列为
CBAEDF
，后序遍历结果为？
前序遍历中
A
是第一个是根节点，中序遍历中
A
的左边是左子树内容，右边的是右子树内容。在看前序遍
历中
BC
的关系，结合中序遍历得到中间图。
EDF
的关系也可以根据刚才规律可以得出。
算法实现思想：递归实现，首先从中序遍历中用
Search
函数找到前序遍历得到的第一个字符位置，如果
找到了创建该字符节点，以此位置划分对前序
[ps+1..ps+k-is]
位置中序
[is..k-1]
位置为单位构建左子树，
以前序
[ps+k-is+1..ps+n-1]
位置中序
[k+1..n+is-1]
位置为单位构建右子树。