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