同样是大伙面试时碰上几率比较高的一套类型题,跟数据结构相关的东西永远是核心... 废话不多说 直接上代码
/**
* @author luochengcheng
* 定义二叉树
*/
class Node {
private char key;
private Node left, right;
public Node(char key) {
this(key, null, null);
}
public Node(char key, Node left, Node right) {
this.key = key;
this.left = left;
this.right = right;
}
public char getKey() {
return key;
}
public void setKey(char key) {
this.key = key;
}
public Node getLeft() {
return left;
}
public void setLeft(Node left) {
this.left = left;
}
public Node getRight() {
return right;
}
public void setRight(Node right) {
this.right = right;
}
}
public class BinaryTree {
protected Node root;
public BinaryTree(Node root) {
this.root = root;
}
public Node getRoot() {
return root;
}
/** 构造树 */
public static Node init() {
Node a = new Node('A');
Node b = new Node('B', null, a);
Node c = new Node('C');
Node d = new Node('D', b, c);
Node e = new Node('E');
Node f = new Node('F', e, null);
Node g = new Node('G', null, f);
Node h = new Node('H', d, g);
return h;// root
}
/** 访问节点 */
public static void visit(Node p) {
System.out.print(p.getKey() + " ");
}
/** 递归实现前序遍历 */
protected static void preorder(Node p) {
if (p != null) {
visit(p);
preorder(p.getLeft());
preorder(p.getRight());
}
}
/** 递归实现中序遍历 */
protected static void inorder(Node p) {
if (p != null) {
inorder(p.getLeft());
visit(p);
inorder(p.getRight());
}
}
/** 递归实现后序遍历 */
protected static void postorder(Node p) {
if (p != null) {
postorder(p.getLeft());
postorder(p.getRight());
visit(p);
}
}
/** 非递归实现前序遍历 */
protected static void iterativePreorder(Node p) {
Stack<Node> stack = new Stack<Node>();
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());
}
}
}
/** 非递归实现前序遍历2 */
protected static void iterativePreorder2(Node p) {
Stack<Node> stack = new Stack<Node>();
Node node = p;
while (node != null || stack.size() > 0) {
while (node != null) {//压入所有的左节点,压入前访问它
visit(node);
stack.push(node);
node = node.getLeft();
}
if (stack.size() > 0) {
node = stack.pop();
node = node.getRight();
}
}
}
/** 非递归实现后序遍历 */
protected static void iterativePostorder(Node p) {
Node q = p;
Stack<Node> stack = new Stack<Node>();
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 iterativePostorder2(Node p) {
Stack<Node> lstack = new Stack<Node>();
Stack<Node> rstack = new Stack<Node>();
Node node = p, right;
do {
while (node != null) {
right = node.getRight();
lstack.push(node);
rstack.push(right);
node = node.getLeft();
}
node = lstack.pop();
right = rstack.pop();
if (right == null) {
visit(node);
} else {
lstack.push(node);
rstack.push(null);
}
node = right;
} while (lstack.size() > 0 || rstack.size() > 0);
}
/** 非递归实现后序遍历 单栈法*/
protected static void iterativePostorder3(Node p) {
Stack<Node> stack = new Stack<Node>();
Node node = p, prev = p;
while (node != null || stack.size() > 0) {
while (node != null) {
stack.push(node);
node = node.getLeft();
}
if (stack.size() > 0) {
Node temp = stack.peek().getRight();
if (temp == null || temp == prev) {
node = stack.pop();
visit(node);
prev = node;
node = null;
} else {
node = temp;
}
}
}
}
/** 非递归实现后序遍历4 双栈法*/
protected static void iterativePostorder4(Node p) {
Stack<Node> stack = new Stack<Node>();
Stack<Node> temp = new Stack<Node>();
Node node = p;
while (node != null || stack.size() > 0) {
while (node != null) {
temp.push(node);
stack.push(node);
node = node.getRight();
}
if (stack.size() > 0) {
node = stack.pop();
node = node.getLeft();
}
}
while (temp.size() > 0) {
node = temp.pop();
visit(node);
}
}
/** 非递归实现中序遍历 */
protected static void iterativeInorder(Node p) {
Stack<Node> stack = new Stack<Node>();
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;
}
}
/** 非递归实现中序遍历2 */
protected static void iterativeInorder2(Node p) {
Stack<Node> stack = new Stack<Node>();
Node node = p;
while (node != null || stack.size() > 0) {
while (node != null) {
stack.push(node);
node = node.getLeft();
}
if (stack.size() > 0) {
node = stack.pop();
visit(node);
node = node.getRight();
}
}
}
/**
* @param args
*/
public static void main(String[] args) {
BinaryTree tree = new BinaryTree(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(" Pre-Order:");
iterativePreorder(tree.getRoot());
System.out.println();
System.out.print("Pre-Order2:");
iterativePreorder2(tree.getRoot());
System.out.println();
System.out.print(" In-Order:");
iterativeInorder(tree.getRoot());
System.out.println();
System.out.print(" In-Order2:");
iterativeInorder2(tree.getRoot());
System.out.println();
System.out.print(" Post-Order:");
iterativePostorder(tree.getRoot());
System.out.println();
System.out.print("Post-Order2:");
iterativePostorder2(tree.getRoot());
System.out.println();
System.out.print("Post-Order3:");
iterativePostorder3(tree.getRoot());
System.out.println();
System.out.print("Post-Order4:");
iterativePostorder4(tree.getRoot());
System.out.println();
}
}
分享到:
相关推荐
java实现创建二叉树,并且遍历二叉树(此处使用递归方式遍历); 创建二叉树的方式有很多,此处使用线性的链表转化成二叉树,链表节点的顺序就是前序遍历的顺序,链表中的null值,代表二叉树左节点或者右节点为null...
层次遍历二叉树
遍历二叉树 遍历二叉树的先序、中序和非递归遍历二叉树的六种算法
按层次遍历二叉树的算法 简单易懂 按层次遍历二叉树的算法 简单易懂
小小学习,C语言数据结构,中序遍历二叉树非递归算法
数据结构非递归先序、中序、后序遍历二叉树,数据结构非递归先序、中序、后序遍历二叉树
java实现二叉树非递归前序中序后序遍历
按层次遍历二叉树
递归遍历二叉树、c语言以及数据结构均要用到,我还会上传非递归的··
该算法采用欧拉路径遍历二叉树,使用java语言实现的
逐层遍历二叉树的结点~~~~~~~~~
遍历二叉树程序,亲自调试,注释详尽,有不懂的随时和大家交流,希望能帮到大家~
非递归中序遍历二叉树
编写按层次顺序(同一层自左至右)遍历二叉树的算法。 (1)二叉树采用二叉链表作为存储结构。 (2)按题集p44面题6.69所指定的格式输出建立的二叉树。 (3)输出层次遍历结果。 (4)测试用例自己设计。
按层次遍历二叉树,简单易懂,操作容易,结构清晰,运用c语言编程
后序遍历二叉树非递归算法的推导及形式化证明,难得的期刊论文资料,对研究二叉树的非递归性遍历有很大帮助
遍历二叉树java代码
二叉树遍历 二叉树遍历
用C语言实现二叉树的前序遍历、中序遍历以及后序遍历。
遍历二叉树的几种算法实现,主要如下: 1.前序遍历二叉树; 2.中序遍历二叉树; 3.后序遍历二叉树; 4.层次遍历二叉树。