http://blog.csdn.net/chj97/article/details/6845824
import java.util.*;
public class BinaryTree {
private BinaryTree lchild;
private BinaryTree rchild;
private Object data;
/**
* @param args
*/
public BinaryTree(BinaryTree l, BinaryTree r, Object data) {
lchild = l;
rchild = r;
this.data = data;
}
public static void main(String[] args) {
// TODO Auto-generated method stub
BinaryTree G= new BinaryTree(null, null, 'G');
BinaryTree H= new BinaryTree(null, null, 'H');
BinaryTree F= new BinaryTree(G, H, 'F');
BinaryTree D= new BinaryTree(null, F, 'D');
BinaryTree E= new BinaryTree(null, null, 'E');
BinaryTree B= new BinaryTree(D, E, 'B');
BinaryTree C= new BinaryTree(null, null, 'C');
BinaryTree A = new BinaryTree(B, C, 'A');
System.out.println("先序遍历。。。。。。。");
pre(A);
System.out.println();
System.out.println("中序遍历。。。。。。。");
in(A);
System.out.println();
System.out.println("后序遍历。。。。。。。");
post(A);
System.out.println();
System.out.println("非递归先序遍历。。。。。。。");
preTraverse(A);
System.out.println();
System.out.println("非递归中序遍历。。。。。。。");
inTraverse(A);
System.out.println();
System.out.println("非递归后序遍历。。。。。。。");
postTraverse(A);
System.out.println();
System.out.println("非递归后序遍历2。。。。。。。");
postTraverse2(A);
System.out.println();
}
public static void visit(BinaryTree bt) {
System.out.print(bt.data + " ");
}
//递归先序遍历
public static void pre(BinaryTree root) {
if(root == null)return;
visit(root);
if(root.lchild != null)pre(root.lchild);
if(root.rchild != null)pre(root.rchild);
}
//递归中序遍历
public static void in(BinaryTree root) {
if(root == null)return;
if(root.lchild != null)in(root.lchild);
visit(root);
if(root.rchild != null)in(root.rchild);
}
//递归后序遍历
public static void post(BinaryTree root) {
if(root == null)return;
if(root.lchild != null)post(root.lchild);
if(root.rchild != null)post(root.rchild);
visit(root);
}
//非递归先序遍历
public static void preTraverse(BinaryTree root) {
Stack s = new Stack();
s.push(root);
while(!s.isEmpty()) {
BinaryTree bt = (BinaryTree)s.pop();
visit(bt);
if(bt.rchild != null) s.push(bt.rchild);
if(bt.lchild != null) s.push(bt.lchild);
}
}
//非递归中序遍历
public static void inTraverse(BinaryTree root) {
Stack s = new Stack();
BinaryTree p = root;
while(p!=null || !s.isEmpty()) {
if(p!=null) {
s.push(p);
p = p.lchild;
}
else {
p = (BinaryTree)s.pop();
visit(p);
p = p.rchild;
}
}
}
//非递归后序遍历
public static void postTraverse(BinaryTree root) {
Stack s = new Stack();
BinaryTree p = root;
//pre标记最近出栈的节点,用于判断是否是p节点的右孩子,如果是的话,就可以访问p节点
BinaryTree pre = p;
//flag标记是出栈还是继续将左孩子进栈
boolean flag = true;
while(p!=null || !s.isEmpty()) {
if(p!=null && flag) {
s.push(p);
p = p.lchild;
}
else {
if(s.isEmpty()) return;
p = (BinaryTree)s.peek();
if(p.rchild != null && p.rchild!=pre) {
p = p.rchild;
flag = true;
}
else {
p = (BinaryTree)s.pop();
visit(p);
flag = false;
pre = p;
}
}
}
}
//非递归后序遍历2
public static void postTraverse2(BinaryTree root) {
Stack s = new Stack();
BinaryTree p = root;
//pre标记最近出栈的节点,用于判断是否是p节点的右孩子,如果是的话,就可以访问p节点
BinaryTree pre = p;
while(p!=null || !s.isEmpty()) {
if(p!=null) {
s.push(p);
p = p.lchild;
}
else {
if(s.isEmpty()) return;
p = (BinaryTree)s.peek();
if(p.rchild != null && p.rchild!=pre) {
p = p.rchild;
}
else {
p = (BinaryTree)s.pop();
visit(p);
pre = p;
p = null;
}
}
}
}
}
相关推荐
[问题描述] 建立二叉树,并输出二叉树的先序,中序和后序遍历序列,以及二叉树的叶子数。 [基本要求] 要求根据读取的元素建立二叉树,能输出各种遍历。 [实现提示] 可通过输入带空格的前序序列建立二叉链表。
本文主要通过python以非递归形式实现二叉树构造、前序遍历,中序遍历,后序遍历,层次遍历以及求二叉树的深度及叶子结点数。其他非递归形式的遍历,想必大多人应该都很清楚,就不再声明。如果你用C或者C++或者其他...
java实现二叉树非递归前序中序后序遍历
主要介绍了Java实现的二叉树常用操作,包括二叉树的前序建树,前中后递归非递归遍历及层序遍历等相关操作技巧,需要的朋友可以参考下
java实现二叉树的遍历,包括前序中序后序遍历,递归和非递归实现。
构造二叉树根据前序与中序遍历序列构造二叉树根据先序遍历构造二叉搜索树根据中序与后序遍历序列构造二叉树根据前序与后序遍历序列构造二叉树 二叉树的遍历顺序及方法可参考之前写过的二叉树的遍历(JAVA递归和非...
二叉树的前序遍历、中序遍历、后序遍历的递归和非递归方法的java实现。
因此,满二叉树的前序遍历、中序遍历和后序遍历均可以通过递归方式实现。 以前序遍历为例,满二叉树的前序遍历顺序为:根、左、右。 在具体实现过程中,我们可以通过构造一个满二叉树,然后进行前序遍历来获取遍历...
1:构造一个二叉树 2:二叉树前序遍历(递归) 3:二叉树中序遍历(递归) 4:二叉树后续遍历(递归) 5:二叉树前序遍历(非递归) 6:二叉树中序遍历(非递归) 7:二叉树后序遍历(非递归)
详细介绍了JAVA中二叉树的非递归遍历方式,三种方式都是采用栈来辅助完成,其中前序遍历采用的是先入右子节点再入左子节点的方法,这样弹出栈时左在前,右在后。中序遍历的话则是要先一直到达最左的子节点,然后才弹...
结构清晰地介绍了二叉树的遍历方法 前序 中序 后序 都有,附带详细的注释,希望像能对和我一样入门级的朋友们有所帮助
二叉树的非递归遍历运算 建立二叉树的三叉链式存储结构,在此基础上完成...4) 非递归的先序遍历、中序遍历、后序遍历算法 5)查找指定结点的双亲。 6)查找指定结点x,若存在返回true,否则返回false 7)求各结点的度。
利用java编写的二叉树的遍历,包括前序,中序以及后序,遍历方式包含递归和非递归,值得学习。
对于树的遍历,无论是前序、中序还是后序遍历,大家可能下意识的就会想到使用递归操作,为什么呢?因为递归操作实现起来“简单”啊! 下面为实现二叉树中序遍历的 Java 递归实现,代码来自于 Gitee 的「myleetcode」...
1. **二叉树的建立与遍历**:介绍了二叉树的基本概念,以及如何使用递归和非递归方法进行前序、中序和后序遍历。 2. **冒泡排序**:通过一个简单直观的算法示例,展示了如何通过重复遍历和交换相邻元素来实现排序。...
要求采用二叉链表作为存储结构,完成二叉树的建立,前序、中序和后序遍历的操作,求所有叶子及结点总数的操作等。 具体要求如下: ①给出基于二叉链表的二叉树类的定义; ②给出二叉树初始化(构造函数)的实现; ③...
另外前序、中序、后序遍历算法都给出了递归和非递归两种实现方式) :wrench:(其中删除节点操作在LeetCode刷题时使用了, 中序遍历给出了递归、使用栈的非递归以及不使用栈的非递归实现) :wrench: :wrench:图的两种遍历...
另外前序、中序、后序遍历算法都给出了递归和非递归两种实现方式) :wrench:(其中删除节点操作在LeetCode刷题时使用了, 中序遍历给出了递归、使用栈的非递归以及不使用栈的非递归实现) :wrench: :wrench:图的两种遍历...