算法-二叉树的三种遍历方式

3/8/2017来源:ASP.NET技巧人气:3907

偶然翻到了去年三月份自己写的一份关于二叉树的三种遍历方式(准确的说,是6中,包含递归和非递归),好久不复习关于算法相关的知识,这些基础还都是在前年备战考研的过程中准备的。希望自己以后多多复习之前的只是,温故而知新,不要捡起芝麻丢了西瓜。 废话不多说,还是直接上代码: 1.Node节点类

package BinTreeTraverse; /** * <p>创建人:刘星 创建日期:2017-3-7 下午4:53:51</p> * <p>功能描述:(node节点类)</p> * @version V1.0 */ public class Node { Node leftChild;//节点的左孩子节点 Node rightChild;//节点的右孩子节点 int data;//节点存储的数据 Node(int newData) {//构造函数,默认左右孩子都为空 leftChild = null; rightChild = null; data = newData; } }

2.遍历实现类

package BinTreeTraverse; import java.util.LinkedList; import java.util.List; import java.util.Stack; /** * <p>创建人:刘星 创建日期:2017-3-7 下午4:51:37</p> * <p>功能描述:(遍历二叉树实现类)</p> * @version V1.0 */ public class BinTreeTraverse { PRivate int[] array = { 1, 2, 3, 4, 5, 6, 7, 8,9};//由于节点存储数据类型为int,这里定义一个int的数组 private static List<Node> nodeList = null;//节点列表,通过左右指针关系构建二叉树的父子关系 /** * * <p>创建人:刘星 创建日期:2017-3-7下午4:57:56</p> * <p>功能描述:(将数组节点插入到二叉树中,构造一棵二叉树)</p> * @param 对方法中某参数的说明 * @return 对方法返回值的说明 * @exception 对方法可能抛出的异常进行说明 * @version 1.0 */ public void createBinTree() { nodeList = new LinkedList<Node>(); // 将一个数组的值依次转换为Node节点 for (int nodeIndex = 0; nodeIndex < array.length; nodeIndex++) { nodeList.add(new Node(array[nodeIndex])); } // 对前lastParentIndex-1个父节点按照父节点与孩子节点的数字关系建立二叉树 for (int parentIndex = 0; parentIndex < array.length / 2 - 1; parentIndex++) { // 左孩子 nodeList.get(parentIndex).leftChild = nodeList .get(parentIndex * 2 + 1); // 右孩子 nodeList.get(parentIndex).rightChild = nodeList .get(parentIndex * 2 + 2); } // 最后一个父节点:因为最后一个父节点可能没有右孩子,所以单独拿出来处理 int lastParentIndex = array.length / 2 - 1; // 左孩子 nodeList.get(lastParentIndex).leftChild = nodeList .get(lastParentIndex * 2 + 1); // 右孩子,如果数组的长度为奇数才建立右孩子 if (array.length % 2 == 1) { nodeList.get(lastParentIndex).rightChild = nodeList .get(lastParentIndex * 2 + 2); } } /** * 先序遍历 * * 这三种不同的遍历结构都是一样的,只是先后顺序不一样而已 * * @param node * 遍历的节点 */ public static void preOrderTraverse(Node node) { if (node == null) return; System.out.print(node.data + " ");//这里用控制台输出代表访问当前节点 preOrderTraverse(node.leftChild); preOrderTraverse(node.rightChild); } /** * 中序遍历 * * 这三种不同的遍历结构都是一样的,只是先后顺序不一样而已 * * @param node * 遍历的节点 */ public static void inOrderTraverse(Node node) { if (node == null) return; inOrderTraverse(node.leftChild); System.out.print(node.data + " "); inOrderTraverse(node.rightChild); } /** * 后序遍历 * * 这三种不同的遍历结构都是一样的,只是先后顺序不一样而已 * * @param node * 遍历的节点 */ public static void postOrderTraverse(Node node) { if (node == null) return; postOrderTraverse(node.leftChild); postOrderTraverse(node.rightChild); System.out.print(node.data + " "); } /** * 先序遍历 非递归算法 * 借助栈来实现 * @param args */ public static void preOrderTraverseWithoutRec(Node node){ if (node == null) return; Stack<Node> stack = new Stack<Node>(); while(!stack.isEmpty()|| node != null){ if(node != null){ System.out.print(node.data + " "); stack.push(node); node = node.leftChild; }else{ node = stack.pop(); node = node.rightChild; } } } /** * 中序遍历 非递归算法 * * @param args */ public static void inOrderTraverseWithoutRec(Node node){ if (node == null) return; Stack<Node> stack = new Stack<Node>(); while(!stack.isEmpty()|| node != null){ if(node != null){ stack.push(node); node = node.leftChild; }else{ node = stack.pop(); System.out.print(node.data + " "); node = node.rightChild; } } } /** * 后序遍历 非递归算法 * * @param args */ public static void postOrderTraverseWithoutRec(Node node){ if (node == null) return; Stack<Node> stack = new Stack<Node>(); while(!stack.isEmpty()|| node != null){ if(node != null){ stack.push(node); node = node.leftChild; }else{ node = stack.pop(); System.out.print(node.data+" "); node = node.rightChild; } } } public static void main(String[] args) { BinTreeTraverse binTree = new BinTreeTraverse(); binTree.createBinTree(); // nodeList中第0个索引处的值即为根节点 Node root = nodeList.get(0); System.out.println("先序遍历:"); preOrderTraverse(root); System.out.println(); System.out.println("中序遍历:"); inOrderTraverse(root); System.out.println(); System.out.println("后序遍历:"); postOrderTraverse(root); System.out.println(); System.out.println("先序遍历非递归算法:"); preOrderTraverseWithoutRec(root); System.out.println(); System.out.println("中序遍历非递归算法:"); inOrderTraverseWithoutRec(root); System.out.println(); System.out.println("后序遍历非递归算法:"); postOrderTraverseWithoutRec(root); System.out.println(); } }

3.总结 熟练并掌握算法的核心思想是关键。记得当时备战考研时看的书,里面多是用c来实现的。当时并不太明白好多细节。现在能熟练的用java复现也算是自己的一种成长吧。在之后的学习之路中我应该多多关注算法并和大家分享算法的实现。