二叉树遍历算法 （递归的、非递归的中序、前序、后序遍历 和 层次遍历 以及 求二叉树的宽度和深度）
需积分: 31 15 浏览量
2015-09-22
16:44:41
上传
评论 4
收藏 158KB PDF 举报
二叉树的遍历
前序遍历递归算法：
代码如下：
public void preOrderTraver(Node root){
if(root != null){
visit(root);
preOrderTraver(root.getLeft());
preOrderTraver(root.getRight());
}
}
二叉树的前序遍历的规则是依次访问根-》左子树-》右子树。并且左子树、右子树均是一棵
二叉树。
对于一棵最小的子树来说，它的结构有如下四种情况：
1） 根 2） 根 3） 根 4）根
/\ / \
叶子 叶子 叶子 叶子
注意：不存在无根的子树
根据二叉树的前序遍历的规则， 我们能够发现 前序遍历的过程是可以抽象成依次访问根
-》左子树-》右子树 的， 并且对于每一棵子树我们采用相同的遍历规则，只是当前的根
有所不同而已。
现在，我们考虑一下遍历终止的条件：
当我们将二叉树中所有结点都遍历过了之后，这时我们遍历结束。当然，这也可以等价于我
们访问过了二叉树的根节点和所有子树的根节点。这个条件在我们编程时，更容易实现。
当根为 null 时，说明该棵子树已经遍历完成
1、当二叉树为空树时，显然无需遍历。
2、当二叉树不为空树时，等价于该二叉树有根节点。对于前序遍历来说，我们先要访问根
节点，然后访问左子树，然后右子树。
因为二叉树的子树也是二叉树，当我们遍历左右子树时，只需要把子树当成二叉树一样遍历
就好（重复上面的 1、2 过程），不同的是，此时的根为子树的根。
我们能够发现 当没有根可以遍历时，我们就遍历完了整棵二叉树。
中序遍历和后序遍历是相同的道理。
中序遍历递归算法：
代码如下：
public void inOrderTraver(Node root){
if(root != null){
preOrderTraver(root.getLeft());
visit(root);
剩余25页未读，继续阅读
资源评论
