数据结构-----创建递归非递归遍历二叉树

class BiTreeNode { public BiTreeNode left; public BiTreeNode right; public int value; public BiTreeNode(int value) { this.value = value; } } public class BiTree { public int count = 0; public static List<Integer> preOrderList = new ArrayList<>(); public static List<Integer> inOrderList = new ArrayList<>(); public static List<Integer> postOrderList = new ArrayList<>(); public static List<Integer> preOrderListNoRecursion = new ArrayList<>(); public static List<Integer> inOrderListNoRecursion = new ArrayList<>(); public static List<Integer> postOrderListNoRecursion = new ArrayList<>(); public static List<Integer> levelOrderList = new ArrayList<>(); /** * 根据一个数组创建一个二叉树(注意我们规定数组中元素为-1表示此元素不存在) * @param array * @return */ public BiTreeNode createBiTree(int[] array) { BiTreeNode[] nodeArray = new BiTreeNode[array.length]; //current和parent两个下标移动频率是不相同的,parent会在current%2==0的时候进行移动 int current = 0; int parent = 0; while(current < array.length) { BiTreeNode node = null; if(array[current] != -1) { node = new BiTreeNode(array[current]); nodeArray[current] = node; } //为了避免第一个节点也加入到判断中,增加了下面这个if判断,因为第一个节点下标值为0, //0%0==0会导致nodeArray[parent].right = node;执行,也就是出现第一个节点的右孩子是自己的情况出现 if(current > 0) { if(current % 2 == 1) nodeArray[parent].left = node; else { nodeArray[parent].right = node; parent++; } } current++; } return nodeArray[0]; } /** * 先序遍历实现(递归) * @param node * @return */ public void preOrderTraverse(BiTreeNode node) { if(node != null) { preOrderList.add(node.value); preOrderTraverse(node.left); preOrderTraverse(node.right); } } /** * 先序遍历实现(非递归) * 实现思路: 根据先序遍历的特点,先访问根节点,再访问左孩子和右孩子,对于每一个结点我们都可以看做是根节点,我们将该结点记为temp,对其进行直接访问,并同时入栈 * 访问结束之后,判断temp的左孩子是否为空，不为空的话,则访问他的左孩子,即将他的左孩子当成下一次的根节点;如果为空的话,则取出栈顶结点并进行出栈操作,同时将 * 栈顶元素的右结点作为下一次的根节点; * @param node */ public void preOrderTraverseNoRecursion(BiTreeNode node) { Stack<BiTreeNode> stack = new Stack<>(); BiTreeNode temp = node; while(temp != null ||!stack.isEmpty()) { while(temp != null) { preOrderListNoRecursion.add(temp.value); stack.push(temp); temp = temp.left; } if(!stack.isEmpty()) { temp = stack.pop(); temp = temp.right; } } } /** * 中序遍历实现(递归) * @param node */ public void inOrderTraverse(BiTreeNode node) { if(node != null) { inOrderTraverse(node.left); inOrderList.add(node.value); inOrderTraverse(node.right); } } /** * 中序遍历实现(非递归) * 实现思路: 其实和先序遍历执行过程是一样的，只不过是在Stack中栈元素退出的时候才会添加到List中去 * @param node */ public void inOrderTraverseNoRecursion(BiTreeNode node) { Stack<BiTreeNode> stack = new Stack<>(); BiTreeNode temp = node; while(temp != null || !stack.isEmpty()) { while(temp != null) { stack.push(temp); temp = temp.left; } if(!stack.isEmpty()) { temp = stack.pop(); inOrderListNoRecursion.add(temp.value); temp = temp.right; } } } /** * 后序遍历实现(递归) * @param node */ public void postOrderTraverse(BiTreeNode node) { if(node != null) { postOrderTraverse(node.left); postOrderTraverse(node.right); postOrderList.add(node.value); } } /** * 后序遍历实现(非递归) * 实现思路: 为了保证根节点在左孩子和右孩子之后访问,对于任意一个结点,首先将其入栈,如果这个结点不存在左孩子或者右孩子的话,则直接访问他,若其存在 * 左孩子或者右孩子,但是之前已经访问过了,具体来讲就是我们这个的pre存储的就是之前一次访问的结点,那么也会直接访问该结点;若不是上面两种情况,则判断 * 当前结点左孩子是否为空，不为空的话则将其入栈,判断右孩子是否为空,不为空的话也会入栈; * @param node */ public void postOrderTraverseNoRecursion(BiTreeNode node) { BiTreeNode pre = null;//前一次访问结点 BiTreeNode cur;//当前访问结点 Stack<BiTreeNode> stack = new Stack<>(); if(node == null) return; stack.push(node); while(!stack.isEmpty()) { cur = stack.peek();//获得栈顶元素 if((cur.left == null && cur.right == null) || (pre != null && (pre == cur.left || pre == cur.right))) { postOrderListNoRecursion.add(cur.value); stack.pop(); pre = cur; }else { if(cur.right != null) stack.push(cur.right); if(cur.left != null) stack.push(cur.left); } } } /** * 层次遍历实现 * 实现思路是:使用队列实现 * @param node */ public void levelOrderTraverse(BiTreeNode node) { Queue<BiTreeNode> queue = new LinkedList<>(); BiTreeNode temp; queue.offer(node); //队列不空 while(!queue.isEmpty()) { temp = queue.poll(); levelOrderList.add(temp.value); if(temp.left != null) queue.offer(temp.left); if(temp.right != null) queue.offer(temp.right); } } /** * 打印输出 * @param list */ public void print(List<Integer> list,String content) { System.out.print(content+": "); for(int i = 0;i < list.size();i++) System.out.print(list.get(i)+" "); System.out.println(); } public static void main(String[] args) { BiTree tree = new BiTree(); int[] array = {1,2,3,4,5,-1,-1,-1,-1,6,7}; BiTreeNode node = null; node = tree.createBiTree(array); //递归版本 tree.preOrderTraverse(node); tree.print(preOrderList, "前序遍历(递归)"); tree.inOrderTraverse(node); tree.print(inOrderList, "中序遍历(递归)"); tree.postOrderTraverse(node); tree.print(postOrderList, "后序遍历(递归)"); //非递归版本 tree.preOrderTraverseNoRecursion(node); tree.print(preOrderListNoRecursion, "前序遍历(非递归)"); tree.inOrderTraverseNoRecursion(node); tree.print(inOrderListNoRecursion, "中序遍历(非递归)"); tree.postOrderTraverseNoRecursion(node); tree.print(postOrderListNoRecursion, "后序遍历(非递归)"); //层次遍历 tree.levelOrderTraverse(node); tree.print(levelOrderList, "层次遍历"); } }