本文共 4993 字，大约阅读时间需要 16 分钟。
首先定义二叉树结构，接着创建二叉树，实现二叉树的递归先、中、后序遍历
package treeLearn;
import java.util.LinkedList;
import java.util.List;import javax.xml.soap.Node;
public class CreateTree {
public static void main(String[] args) { // TODO 自动生成的方法存根 CreateTree t = new CreateTree(); int[] arr = {0,1,2,3,4,5,6,7}; List<Tree> tree = new LinkedList<Tree>(); t.createTree(arr,tree); System.out.print("先序遍历："); t.preOrderTraversal(tree.get(0)); System.out.println(); System.out.print("中序遍历："); t.inOrderTraversal(tree.get(0)); System.out.println(); System.out.print("后序遍历："); t.postOrderTraversal(tree.get(0)); } public void createTree(int[] arr,List<Tree> tree) { //将数组元素变为树节点元素 for(int i=0;i<arr.length;i++) { Tree t = new Tree(arr[i]); tree.add(t); } //给所有父节点设定子节点 for(int i=0;i<arr.length/2-1;i++) { //相当于为编号i的节点确定子节点 //左子节点编号为2*n，右子节点为2*n+1，但是因为编号从0开始，故都在加一 tree.get(i).setLchild(tree.get(i*2+1)); tree.get(i).setRchild(tree.get(2*i+2)); //这里父节点有1（2,3）,2（4,5）,3（6,7）,4（8,9） //但是最后一个父节点有可能没有右子节点 需要单独处理 } //单独处理最后一个父节点，因为他可能没有右节点 int index = tree.size()/2-1; tree.get(index).setLchild(tree.get(index*2+1));//先设置左子节点 if(tree.size()%2==1) {//如果有奇数个节点，最后一个父节点才有右节点 tree.get(index).setRchild(tree.get(index*2+2)); } } /* * 遍历当前节点的值 */ public void checkCurrentNode(Tree tree) { System.out.print(tree.getData()+" "); } /** * 先序遍历二叉树 * @param tree */ public void preOrderTraversal(Tree tree) { if(tree==null) {//很重要，必须有这个条件，当遇到叶子节点用来停止向下遍历 return; } checkCurrentNode(tree); preOrderTraversal(tree.getLchild()); preOrderTraversal(tree.getRchild()); } public void inOrderTraversal(Tree tree) { if(tree==null) { return; } inOrderTraversal(tree.getLchild()); checkCurrentNode(tree); inOrderTraversal(tree.getRchild()); } /** * 后序遍历二叉树 * @param root 根节点 */ public void postOrderTraversal(Tree tree){ if (tree == null) //很重要，必须加上 return; postOrderTraversal(tree.getLchild()); postOrderTraversal(tree.getRchild()); checkCurrentNode(tree); } } class Tree{ private Tree lchild;//左孩子 private Tree rchild;//右孩子 private int data;//数据域 public Tree(int data) { this.data = data; this.lchild = null; this.rchild = null; } public Tree getLchild() { return lchild; }public void setLchild(Tree lchild) {
this.lchild = lchild; }public Tree getRchild() {
return rchild; }public void setRchild(Tree rchild) {
this.rchild = rchild; }public int getData() {
return data; }public void setData(int data) {
this.data = data; } }
接下来是二叉树的非递归先、中、后序遍历以及DFS和BFS的实现
package treeLearn;
import java.util.ArrayDeque;
import java.util.ArrayList; import java.util.LinkedList; import java.util.List; import java.util.Stack;public class TreeTraversal {
public static void main(String[] args) { // TODO 自动生成的方法存根 TreeTraversal t = new TreeTraversal(); CreateTree tt = new CreateTree(); int[] arr = {0,1,2,3,4,5,6,7}; List<Tree> tree = new LinkedList<Tree>(); tt.createTree(arr,tree); System.out.print("DFS："); t.dfs(tree.get(0)); System.out.println(); System.out.print("BFS："); t.bfs(tree.get(0)); } /* * 遍历当前节点的值 */ public void checkCurrentNode(Tree tree) { System.out.print(tree.getData()+" "); } /** * 非递归先序遍历二叉树 * @param tree */ public void preOrderTraversal(Tree tree) { Stack<Tree> stack = new Stack<Tree>(); Tree t = tree; while(t!=null||!stack.isEmpty()) { while(t!=null) { checkCurrentNode(t);//读取根节点以及左子树节点 stack.push(t);//并将读取到的左子树节点入栈 t = t.getLchild();//指针下移，一直指向左子树节点，直至节点不存在 } if(!stack.isEmpty()) { t = stack.pop();//将栈内元素弹出 t = t.getRchild();//指针指向栈内节点的右子树节点， //当不为空时，会再次进入while循环输出并入栈，再次读取该子树的左子树节点 } } } public void inOrderTraversal(Tree tree) { Stack<Tree> stack = new Stack<Tree>(); Tree t = tree; while(t!=null&&!stack.isEmpty()) { while(t!=null) { stack.push(t); t = t.getLchild(); } if(!stack.isEmpty()) { t = stack.pop(); checkCurrentNode(t); t = t.getRchild(); } } } public void postOrderTraversal(Tree tree) { Stack<Tree> stack = new Stack<Tree>(); Tree t = tree,prev = tree; while(t!=null&&!stack.isEmpty()) { while(t!=null) { stack.push(t); t = t.getLchild(); } if(!stack.isEmpty()) { Tree temp = stack.peek().getRchild();//指向当前栈顶一节点的右子树节点 if(temp==null||temp==prev) {//若当前栈顶节点的右子树节点为null //保证当前栈顶元素无兄弟节点 t = stack.pop(); checkCurrentNode(t);//弹出栈顶元素并输出 prev = t;//记录已经输出的元素 t = null;//t为空时才能进入栈操作 }else { //如果当前节点存在兄弟节点则需进入while循环再次入栈操作 t = temp; } } } } //通过队列实现 public void bfs(Tree tree) { if(tree==null) { return; } LinkedList<Tree> queue = new LinkedList<Tree>(); queue.offer(tree);//首先将根节点存入队列 //当队列中有值时，每次取队首的节点打印，打印之后判断是否有子节点 //若有，将子节点加入队列 while(queue.size()>0) { Tree t = queue.peek(); queue.poll();//取出队首元素并打印 System.out.print(t.getData()+" "); if(t.getLchild()!=null) {//如果有左子节点，则将其加入队列 queue.offer(t.getLchild()); } if(t.getRchild()!=null) {//如果有右子节点，则将其存入队列 queue.offer(t.getRchild()); } } } //通过栈来实现 public void dfs(Tree tree) { if(tree==null) { return; } ArrayDeque<Tree> stack = new ArrayDeque<Tree>(); stack.push(tree); while(!stack.isEmpty()) { Tree t = stack.pop(); if(t.getRchild()!=null) { stack.push(t.getRchild()); } System.out.print(t.getData()+" "); if(t.getLchild()!=null) { stack.push(t.getLchild()); } } } }
转载地址：http://vreii.baihongyu.com/