import java.util.Stack;
/**
*
* @author ss
* 用栈完成二叉树的遍历
*/
public class Node {
//三个属性 值 左节点 右节点
private String value;
private Node nodeLeft;
private Node nodeRight;
public Node(String value){
this.value=value;
}
private static void showValue(String value){
System.out.println(value);
}
/**
* 构造二叉树
* @return
*/
private static Node init(){
Node node1=new Node("A");
Node node2=new Node("B");
Node node3=new Node("C");
Node node4=new Node("D");
Node node5=new Node("E");
Node node6=new Node("F");
Node node7=new Node("G");
node1.nodeLeft=node2;
node1.nodeRight=node3;
node2.nodeLeft=node4;
node2.nodeRight=node5;
node3.nodeLeft=node6;
node3.nodeRight=node7;
//返回根节点
return node1;
}
/**
* 前序遍历二叉树
* @param node
*/
public static void iteratorPreNodeTree(Node node){
Stack<Node> stack=new Stack<Node>();
if(node!=null){
stack.push(node);
while(!stack.empty()){
node=stack.pop();
showValue(node.value);
if(node.nodeRight!=null){
stack.push(node.nodeRight);
}
if(node.nodeLeft!=null){
stack.push(node.nodeLeft);
}
}
}
}
/**
* 中序遍历二叉树
* @param args
*/
public static void iterarorMidNodeTree(Node node){
Stack<Node> stack=new Stack<Node>();
while(node!=null){
while(node!=null){
if(node.nodeRight!=null){
stack.push(node.nodeRight);//将右节点压入栈
}
stack.push(node);//将当前节点压入栈
node=node.nodeLeft;
}
node=stack.pop();
while(!stack.empty()&&node.nodeRight==null){
showValue(node.value);
node=stack.pop();//取出左节点之后取出根节点
}
showValue(node.value);
if(!stack.empty()){
node=stack.pop();
}else{
node=null;
}
}
}
/**
* 后序遍历二叉树
* @param node
*/
public static void iteratorPostNodeTree(Node node){
//定义标记node 记录上一个节点
Node tempNode=node;
Stack<Node> stack=new Stack<Node>();
while(node!=null){
//左节点入栈
for(;node.nodeLeft!=null;node=node.nodeLeft){
stack.push(node);
}
//当前节点无右子 或者右子已经输出
while(node!=null&&(node.nodeRight==null||node.nodeRight==tempNode)){
showValue(node.value);
tempNode=node;
if(stack.empty()){
return;
}
node=stack.pop();
}
//处理右子
stack.push(node);
node=node.nodeRight;
}
}
//单元测试
public static void main(String[] args) {
Node root=init();
System.out.println("前序遍历二叉树");
iteratorPreNodeTree(root);
System.out.println("中序遍历二叉树");
iterarorMidNodeTree(root);
System.out.println("后序遍历二叉树");
iteratorPostNodeTree(root);
}
}
分享到:
相关推荐
详细演示二叉树的创建和后序遍历,使用C++完成。
用C++写的二叉树先序遍历、中序遍历和后序遍历非递归算法
用C++写的,包括二叉树的构建,二叉树的先序遍历、中序遍历和后序遍历非递归算法。
二叉树先序、中序、后序遍历非递归算法,简述了二叉树的基本算法。
链式二叉树的后序创建、递归后序遍历、非递归堆栈后序遍历、后序销毁
这是数据结构中二叉树的后序遍历的非递归算法的源代码。
不用栈 非递归后序遍历二叉树 有mark标志
非递归后序遍历二叉树: 非递归中序遍历二叉树(算法2): 层次遍历二叉树: 递归计算单分支结点: 递归计算双分支结点: 递归计算叶子数: 二叉数的深度: 交换二叉树的左右子树: 二叉树已左右交换。 ...
数据结构中关于二叉树的遍历,非递归算法数上未给出
非递归实现二叉树的先、中、后序遍历 typedef struct binarytree /*定义一棵二叉树*/ { char data; struct binarytree *LChild,*RChild; }BiTNode,*BiTree;
用非递归后序遍历二叉树的方式实现的表达式计算,进行了精细的表达式逻辑判断和处理,可进行加减乘除、括号、小数的计算。项目结构清晰,基本都有代码注释,可用于数据结构实验。同为学习人,能力有限,不足之处还请...
二叉树 非递归前中后序遍历汇总 C语言 希望大家给予建议
1.建立完全二叉树 2.先序非递归遍历二叉树函数 & 先序递归遍历二叉树验证 3.中序非递归遍历二叉树函数 & 中序递归遍历二叉树验证 4.后序非递归遍历二叉树函数 & 后序递归遍历二叉树验证
本程序采用非递归方法实现对二叉树的先序、中序、后序遍历.自定义栈和树的结构。
自己编写的实验二叉树的后序遍历非递归算法 包括以递归中序遍历建立二叉树 前序,中序,后序递归以及非递归实现二叉树的遍历 经vc6.0编译通过 自己实验,不足之处应该很多,望指出
数据结构试验报告用先序中序建立二叉树后序遍历非递归.pdf
二叉树后序遍历的非递归算法,后序遍历运算
二叉树先序、中序、后序三种遍历的非递归算法
二叉树遍历算法 (递归的、非递归的中序、前序、后序遍历 和 层次遍历 以及 求二叉树的宽度和深度)
数据结构二叉树链式结构的前序遍历,中序遍历,后序遍历用递归的方法,层级遍历采用队列结构