- package ccnu.offer.tree;
- import java.util.ArrayList;
- import java.util.LinkedList;
- import java.util.Scanner;
- import java.util.Stack;
- public class Demo02 {
- public static void main(String[] args) {
- Demo02 d = new Demo02(); // Node root = d.createBiTree();// d.preOrder(root); Node root1 = d.createBiTreeByPreIn(new int[]{1, 2, 4, 6, 7, 3, 5, 8, 9}, new int[]{2, 6, 4, 7, 1, 5, 9, 8, 3}, 0, 0, 9); // postSerials = [6, 7, 4, 2, 9, 8, 5, 3, 1]// Node root1 = d.createBiTreeByPreIn(new int[]{1, 2, 4, 5, 3, 6, 7}, new int[]{4, 2, 5, 1, 3, 7, 6}, 0, 0, 7); // postSerials = [6, 7, 4, 2, 9, 8, 5, 3, 1]// Node root1 = d.createBiTreeByPreIn(new int[]{1, 2, 3, 4, 5}, new int[]{2, 1, 4, 3, 5}, 0, 0, 5); // postSerials = [6, 7, 4, 2, 9, 8, 5, 3, 1]// d.preOrder(root1); System.out.println(d.preOrder1(root1)); System.out.println(d.inOrder1(root1)); System.out.println(d.postOrder1(root1));// System.out.println(d.postOrder2(root1)); System.out.println(d.levelOrder(root1)); System.out.println(d.levelOrder1(root1)); /*ArrayList levelSerials = d.levelOrder(root1); for(Integer levelSerial : levelSerials){ if(levelSerial == -1){ System.out.println(); }else{ System.out.print(levelSerial); } }*/ } public Node createBiTree(){ Scanner sc = new Scanner(System.in); int val; Node root; val = sc.nextInt(); if(val == -1){ return null; }else{ root = new Node(val); root.lchild = createBiTree(); root.rchild = createBiTree(); } return root; } public Node createBiTreeByPreIn(int[] pre, int[] in, int preBegin, int inBegin, int len){ if(pre == null || in == null || pre.length != in.length || pre.length == 0 || in.length == 0){ return null; } if(len <= 0){ return null; } Node root = new Node(pre[preBegin]); int rootIndex; for(rootIndex = 0; in[rootIndex] != pre[preBegin]; rootIndex++); root.lchild = createBiTreeByPreIn(pre, in, preBegin + 1, inBegin, rootIndex - inBegin); root.rchild = createBiTreeByPreIn(pre, in, preBegin + (rootIndex - inBegin) + 1, rootIndex + 1, len - (rootIndex - inBegin) - 1); return root; } public void preOrder(Node root){ // 递归 if(root != null){ System.out.print(root.val); preOrder(root.lchild); preOrder(root.rchild); } } public ArrayList preOrder1(Node root){ // 非递归 ArrayList preSerials = new ArrayList(); Stack s = new Stack(); while(root != null || !s.isEmpty()){ if(root != null){ preSerials.add(root.val); s.push(root); root = root.lchild; }else{ root = s.pop(); root = root.rchild; } } return preSerials; } public void inOrder(Node root){ // 递归 if(root != null){ inOrder(root.lchild); System.out.print(root.val); inOrder(root.rchild); } } public ArrayList inOrder1(Node root){ // 非递归 ArrayList inSerials = new ArrayList(); Stack s = new Stack(); while(root != null || !s.isEmpty()){ // 当整棵树根节点被访问时,此时栈为空,接着访问根节点的右子树,而当某个树root的左子树为空时,栈一定不为空,应为root在栈顶----!s.isEmpty()就是访问当前根节点(栈顶元素) if(root != null){ // 当前树的root不为空,将其入栈,并将root重新指向其左子树 s.push(root); root = root.lchild; }else{ // 当root为空时,说明其父节点(栈顶元素)的左孩子为空,则应该访问,继而在将root指向栈顶元素的右子树 root = s.pop(); inSerials.add(root.val); root = root.rchild; } } return inSerials; } public void postOrder(Node root){ // 递归 if(root != null){ postOrder(root.lchild); postOrder(root.rchild); System.out.print(root.val); } } public ArrayList postOrder1(Node root){ // 非递归 ArrayList postSerials = new ArrayList(); Stack s = new Stack(); Node isAccess = null; // 记录最近的访问节点 while(root != null || !s.isEmpty()){ if(root != null){ s.push(root); root = root.lchild; }else{ // 某棵子树木有左子树 root = s.peek(); root = root.rchild; if(root == null || isAccess == root){ // 木有右子树或者右子树已经被访问,那么就可以访问访问栈顶元素(左右子树均已访问) root = s.pop(); postSerials.add(root.val); isAccess = root; // 记录刚访问的这个节点 root = null; // 刚访问的root的左右子树均已经访问(root也访问了),此时应该从获取栈顶元素(root的父节点),遍历父节点的右子树 }else{ s.push(root); root = root.lchild; } } } return postSerials; } public ArrayList postOrder2(Node root) { ArrayList postSerials = new ArrayList(); ArrayList leftPostSerials = new ArrayList(); ArrayList rightPostSerials = new ArrayList(); if (root == null) { return postSerials; } leftPostSerials = postOrder2(root.lchild); rightPostSerials = postOrder2(root.rchild); postSerials.addAll(leftPostSerials); postSerials.addAll(rightPostSerials); postSerials.add(root.val); return postSerials; } public ArrayList levelOrder(Node root){ // 自上而下,自左向右 int levels = 0; // 记录二叉树的层数 ArrayList levelSerials = new ArrayList(); LinkedList levelNodes = new LinkedList(); Node rightmost1 = null; // 始终指向正在访问的当前层的最右一个节点 Node rightmost2 = null; // 始终指向正在访问的当前层的当前节点的最右一个节点 while(root != null || !levelNodes.isEmpty()){ if(root != null){ // 初始化第一个节点 levelNodes.push(root); rightmost1 = root; rightmost2 = root; root = null; }else{ root = levelNodes.pop(); levelSerials.add(root.val); if(root.lchild != null){ levelNodes.addLast(root.lchild); rightmost2 = root.lchild; } if(root.rchild != null){ levelNodes.addLast(root.rchild); rightmost2 = root.rchild; } if(root == rightmost1){ levels++; levelSerials.add(-1); // 表示此处是此层的最后一个节点 rightmost1 = rightmost2; } root = null; } } System.out.println("levels: " + levels); return levelSerials; } public ArrayList levelOrder1(Node root){ // 自下而上,自右向左 ArrayList levelSerials = new ArrayList(); LinkedList levelNodes = new LinkedList(); Stack accessNodes = new Stack(); Node rightmost1 = null; Node rightmost2 = null; while(root != null || !levelNodes.isEmpty()){ if(root != null){ levelNodes.push(root); rightmost1 = root; rightmost2 = root; root = null; }else{ root = levelNodes.pop(); accessNodes.push(root); if(root.lchild != null){ levelNodes.addLast(root.lchild); rightmost2 = root.lchild; } if(root.rchild != null){ levelNodes.addLast(root.rchild); rightmost2 = root.rchild; } if(root == rightmost1){ accessNodes.push(new Node(-1)); // 标志下一层的额外节点 rightmost1 = rightmost2; } root = null; } } while(!accessNodes.isEmpty()){ levelSerials.add(accessNodes.pop().val); } return levelSerials; } private class Node{ private int val; private Node lchild = null; private Node rchild = null; public Node(int val) { this.val = val; } }}
来源: http://www.92to.com/bangong/2017/04-21/20664101.html