java实现二叉树遍历的三种方式
这篇文章主要为大家详细介绍了java实现二叉树遍历的三种方式，具有一定的参考价值，感兴趣的小伙伴们可以参考一下本文实例为大家分享了java实现二叉树遍历的具体代码，供大家参考，具体内容如下
二叉树如下：
遍历结果如下：
以下是实现代码：
package bintree;
import java.util.stack;
/**
* @author bin.zhang
* @version 2017年8月29日 上午10:22:01
*/
public class bintreetraversal {
public static void main(string[] args) {
system.out.print("前序：");
traversal.preorder();
traversal.preorderrecursion(traversal.createbintree());
system.out.print("中序：");
traversal.inorder();
traversal.inorderrecursion(traversal.createbintree());
system.out.print("后序：");
traversal.postorder();
traversal.postorderrecursion(traversal.createbintree());
}
}
/**
* 节点数据结构
*
* @author bin.zhang
* @version 2017年8月30日 上午11:49:38
*/
class bintreenode {
bintreenode() {
}
bintreenode(char data, int flag, bintreenode lchild, bintreenode rchild) {
this.data = data;
this.flag = flag;
this.lchild = lchild;
this.rchild = rchild;
}
char data;
int flag;
bintreenode lchild, rchild;
}
class traversal {
/**
* 创建一棵二叉树
*
* @author bin.zhang
* @return 根节点
*/
public static bintreenode createbintree() {
bintreenode r3 = new bintreenode('f', 0, null, null);
bintreenode l2 = new bintreenode('d', 0, null, null);
bintreenode r2 = new bintreenode('e', 0, null, r3);
bintreenode l1 = new bintreenode('b', 0, l2, r2);
bintreenode r1 = new bintreenode('c', 0, null, null);
bintreenode t = new bintreenode('a', 0, l1, r1);
return t;
}
// 前序
public static void preorder() {
bintreenode p = createbintree();
stack<bintreenode> stack = new stack<bintreenode>();
while (p != null || !stack.empty()) {
if (p != null) {
system.out.print(p.data);
stack.push(p);
p = p.lchild;
}
else {
p = stack.pop();
p = p.rchild;
}
}
system.out.println();
}
// 前序递归
public static void preorderrecursion(bintreenode top) {
if (top != null) {
system.out.println(top.data);
preorderrecursion(top.lchild);
preorderrecursion(top.rchild);
}
}
// 中序
public static void inorder() {
bintreenode p = createbintree();
stack<bintreenode> stack = new stack<bintreenode>();
while (p != null || !stack.empty()) {
if (p != null) {
stack.push(p);
p = p.lchild;
}
else {
p = stack.pop();
system.out.print(p.data);
p = p.rchild;
}
}
system.out.println();
}
// 中序递归
public static void inorderrecursion(bintreenode top) {
if (top != null) {
inorderrecursion(top.lchild);
system.out.println(top.data);
inorderrecursion(top.rchild);
}
}
// 后序
public static void postorder() {
bintreenode p = createbintree();
stack<bintreenode> stack = new stack<bintreenode>(); // 初始化栈
int mark = 1; // 转向标志
while (p != null || !stack.empty()) { // 遍历
if (p != null && mark != 0) {
stack.push(p);
p = p.lchild;
}// 转向左子树
else {
p = stack.pop();
p.flag++; // 退栈
if (p.flag == 1) {
stack.push(p);
p = p.rchild;
mark = 1;
} // 转向右子树
else if (p.flag == 2 && !stack.empty()) { // 输出结点
system.out.print(p.data);
mark = 0;
}
else if (p.flag == 2 && stack.empty()) { // 输出根结点并退出
system.out.print(p.data);
break;
}
} // if-else
} // while
system.out.println();
}
// 后序递归
public static void postorderrecursion(bintreenode top) {
if (top != null) {
postorderrecursion(top.lchild);
postorderrecursion(top.rchild);
system.out.println(top.data);
}
}
}
以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持CodeAE代码之家。
原文链接：https://blog.csdn.net/zhangbinu/article/details/77679901
http://www.zzvips.com/article/173892.html
页:
[1]