对于二叉树的遍历,很久没看了;目前只记得采用递归的方法来编码实现;前一阵子被人问到用非递归的方法实现先序遍历,当时没想出来,现在复习了之后写了下两种方式遍历实现的代码;
package com.fishtour.research.rand;
import java.util.Stack;
/** 二叉树遍历 */
public class BinTree {
protected BTNode root;
public BinTree(BTNode root) {
this.root = root;
}
public BTNode getRoot() {
return root;
}
/** 构造树 */
public static BTNode init() {
BTNode a = new BTNode('A');
BTNode b = new BTNode('B', null, a);
BTNode c = new BTNode('C');
BTNode d = new BTNode('D', b, c);
BTNode e = new BTNode('E');
BTNode f = new BTNode('F', e, null);
BTNode g = new BTNode('G', null, f);
BTNode h = new BTNode('H', d, g);
return h;// root
}
/** 访问节点 */
public static void visit(BTNode p) {
System.out.print(p.getKey() + " ");
}
/** 递归实现前序遍历 */
protected static void preorder(BTNode p) {
if (p != null) {
visit(p);
preorder(p.getLeft());
preorder(p.getRight());
}
}
/** 递归实现中序遍历 */
protected static void inorder(BTNode p) {
if (p != null) {
inorder(p.getLeft());
visit(p);
inorder(p.getRight());
}
}
/** 递归实现后序遍历 */
protected static void postorder(BTNode p) {
if (p != null) {
postorder(p.getLeft());
postorder(p.getRight());
visit(p);
}
}
/** 非递归实现前序遍历 */
protected static void iterativePreorder(BTNode p) {
Stack<BTNode> stack = new Stack<BTNode>();
if (p != null) {
stack.push(p);
while (!stack.empty()) {
p = stack.pop();
visit(p);
if (p.getRight() != null)
stack.push(p.getRight());
if (p.getLeft() != null)
stack.push(p.getLeft());
}
}
}
/** 非递归实现后序遍历 */
protected static void iterativePostorder(BTNode p) {
BTNode q = p;
Stack<BTNode> stack = new Stack<BTNode>();
while (p != null) {
// 左子树入栈
for (; p.getLeft() != null; p = p.getLeft())
stack.push(p);
// 当前节点无右子或右子已经输出
while (p != null && (p.getRight() == null || p.getRight() == q)) {
visit(p);
q = p;// 记录上一个已输出节点
if (stack.empty())
return;
p = stack.pop();
}
// 处理右子
stack.push(p);
p = p.getRight();
}
}
/** 非递归实现中序遍历 */
protected static void iterativeInorder(BTNode p) {
Stack<BTNode> stack = new Stack<BTNode>();
while (p != null) {
while (p != null) {
if (p.getRight() != null)
stack.push(p.getRight());// 当前节点右子入栈
stack.push(p);// 当前节点入栈
p = p.getLeft();
}
p = stack.pop();
while (!stack.empty() && p.getRight() == null) {
visit(p);
p = stack.pop();
}
visit(p);
if (!stack.empty())
p = stack.pop();
else
p = null;
}
}
public static void main(String[] args) {
BinTree tree = new BinTree(init());
System.out.print(" Pre-Order:");
preorder(tree.getRoot());
System.out.println();
System.out.print(" In-Order:");
inorder(tree.getRoot());
System.out.println();
System.out.print("Post-Order:");
postorder(tree.getRoot());
System.out.println();
System.out.print("iter Pre-Order:");
iterativePreorder(tree.getRoot());
System.out.println();
System.out.print("iter In-Order:");
iterativeInorder(tree.getRoot());
System.out.println();
System.out.print("iter Post-Order:");
iterativePostorder(tree.getRoot());
System.out.println();
}
}
/** 二叉树节点 */
class BTNode {
private char key;
private BTNode left, right;
public BTNode(char key) {
this(key, null, null);
}
public BTNode(char key, BTNode left, BTNode right) {
this.key = key;
this.left = left;
this.right = right;
}
public char getKey() {
return key;
}
public void setKey(char key) {
this.key = key;
}
public BTNode getLeft() {
return left;
}
public void setLeft(BTNode left) {
this.left = left;
}
public BTNode getRight() {
return right;
}
public void setRight(BTNode right) {
this.right = right;
}
}
分享到:
相关推荐
二叉树递归与非递归遍历
二种非递归实现 二叉树中序遍历: 递归实现 非递归实现 二叉树后序遍历: 递归实现 非递归实现 二叉树层次遍历 二叉树层次创建,创建方法遵循卡特兰数 http://write.blog.csdn.net/postedit/17380455
自己写的相当全的二叉树函数操作集合,包括二叉树的递归遍历和非递归遍历,以及计算二叉树的深度和叶子节点等
用C++写的,包括二叉树的构建,二叉树的先序遍历、中序遍历和后序遍历非递归算法。
二叉树的非递归遍历 二叉树的非递归遍历二叉树的非递归遍历二叉树的非递归遍历二叉树的非递归遍历二叉树的非递归遍历二叉树的非递归遍历二叉树的非递归遍历二叉树的非递归遍历
二叉树的递归遍历、非递归遍历和层次遍历
中根顺序递归建立二叉树,递归及非递归遍历二叉树。C++面向过程实现
用C++写的二叉树先序遍历、中序遍历和后序遍历非递归算法
二叉树的非递归遍历,使用C++实现二叉树的非递归遍历,对正在学习算法的同学应该挺有帮助的
包含了二叉树的递归与非递归的先序、中序、后序遍历以及层次遍历和求叶子节点数所有基本的操作。
二叉树的创建与三种遍历的递归与非递归实现 包括二叉树的动态创建,前序遍历,中序遍历,后续遍历的递归与非递归方法的实现。
非递归先序遍历二叉树: 非递归中序遍历二叉树: 非递归后序遍历二叉树: 非递归中序遍历二叉树(算法2): 层次遍历二叉树: 递归计算单分支结点: 递归计算双分支结点: 递归计算叶子数: 二叉数的深度:...
该程序代码实现了二叉树的递归生成创建,递归前序遍历,递归中序遍历,递归后序遍历,非递归前序遍历,非递归中序遍历,非递归后序遍历,以及递归层次遍历,递归求度为0,1,2的节点数,非递归求度为0,1,2的节点数。...
递归和非递归都有,还有计算单节点双节点数 ,功能强大!
已经经过不断的调试可以跑起来了 有详细的注释
包含一下方法: 1.通过一个数组来构造一颗...6.使用非递归 先序遍历一棵二叉树 7.使用非递归 中序遍历一棵二叉树 8.使用非递归 后序遍历一棵二叉树 PS:代码为C++代码 可以直接下载使用!!! PS2:每句代码都有详细注释
二叉树先序、中序、后序遍历非递归算法,简述了二叉树的基本算法。
经典的数据结构问题:二叉树非递归遍历算法实现 二叉树递归遍历算法实现