当前位置： 移动技术网 > IT编程>开发语言>Java > java实现二叉树遍历的三种方式

java实现二叉树遍历的三种方式

2019年07月19日  | 移动技术网IT编程  | 我要评论

本文实例为大家分享了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);
  }
 }
}

以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持移动技术网。

您可能感兴趣的文章:

如对本文有疑问， 点击进行留言回复！！

相关文章:

验证码：
最近更新的文章
大家感兴趣的文章
移动技术网