public class BTNode {
private char key;
private BTNode left,right;
public BTNode(char key) {
// TODO Auto-generated constructor stub
this(key,null,null);
}
public BTNode(char key, BTNode left, BTNode right) {
// TODO Auto-generated constructor stub
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;
}
}
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 root;
return h;
}
/**访问节点*/
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) {
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("递归先序遍历:");
preorder(tree.getRoot());
System.out.println();
//递归实现中序遍历
System.out.print("递归中序遍历:");
inorder(tree.getRoot());
System.out.println();
//递归实现后序遍历
System.out.print("递归后序遍历:");
postorder(tree.getRoot());
System.out.println();
}
}
分享到:
相关推荐
java实现创建二叉树,并且遍历二叉树(此处使用递归方式遍历); 创建二叉树的方式有很多,此处使用线性的链表转化成二叉树,链表节点的顺序就是前序遍历的顺序,链表中的null值,代表二叉树左节点或者右节点为null...
java实现二叉树非递归前序中序后序遍历
该算法采用欧拉路径遍历二叉树,使用java语言实现的
遍历二叉树java代码
一个简单的课程设计,使用Java来实现二叉树的中序遍历
用java实现二叉树遍历 包括先序,中序,后序 后续是自己写的算法 可以运行
在Java中,实现二叉树的先序遍历可以通过递归来完成。先序遍历的顺序是:首先访问根节点,然后递归地先序遍历左子树,最后递归地先序遍历右子树。 在这段代码中,Node类定义了二叉树的节点,包含数据域和指向左右子...
建立二叉树,前后中序遍历二叉树,求二叉树的深度
java编程,二叉树的中序遍历,递归实现
java实现创建二叉树,并且遍历二叉树(此处使用非递归方式遍历); 用出栈入栈的方式遍历二叉树。
使用java语言,对数据结构中的二叉树进行遍历,包含算法逻辑。
非递归中序遍历二叉树
编写先序遍历二叉树的非递归算法程序,要求: (1)以二叉链表建立二叉树。 (2)输出遍历的结点序列。 (3)有实例验算。
java实现 二叉树的遍历 前序遍历用到递归, 中序和后序遍历用到栈, 其实还是有一定难度的
分层遍历二叉树
java语言实现的二叉树的各种操作(包括递归与非递归遍历二叉树,求二叉树的高度,节点总数,叶子节点等)
在Java中,实现二叉树的中序遍历同样可以通过递归来完成。中序遍历的顺序是:首先递归地中序遍历左子树,然后访问根节点,最后递归地中序遍历右子树。 在这段代码中,Node类定义了二叉树的节点,BinaryTree类包含一...
在Java中,实现二叉树的后序遍历可以通过递归来完成。后序遍历的顺序是:首先递归地遍历左子树,然后递归地遍历右子树,最后访问根节点。 在这段代码中,Node类定义了二叉树的节点,BinaryTree类包含一个指向根节点...
Java版二叉树遍历非递归程序,里面写的一般,希望大家喜欢!
NULL 博文链接:https://sun810.iteye.com/blog/1261373