目录

通过递归方式对三种顺序进行遍历

非递归方法做到先序遍历

非递归中序排列

非递归的后序遍历

按照宽度遍历

主函数测试

---

自定义java拟二叉树结构

  public static class Node {public int value;public Node left;public Node right;public Node(int value) {this.value = value;}}public static void f(Node head) {//        2   2,null,2,null,2//到底部会回到自己本身3次//       / \//    null nullif (head == null) {return;}//1f(head.left);//2f(head.right);//3}

在遍历的过程中每个节点都会遍历（回到本身）3次，全部打印称为递归序

 通过不同的打印时机，得到以下三种遍历方法 1先序遍历，第1次遇到本身打印 2中序遍历，第2次遇到本身打印 3后序遍历，第3次遇到本身打印

通过递归方式对三种顺序进行遍历

public static void preOrderRecur(Node head) {//先序遍历，只在第一次打印valueif (head == null) {return;}System.out.println(head.value + " ");preOrderRecur(head.left);preOrderRecur(head.right);}public static void inOrderRecur(Node head) {//中序遍历，只在第2次打印valueif (head == null) {return;}preOrderRecur(head.left);System.out.println(head.value + " ");preOrderRecur(head.right);}public static void posOrderRecur(Node head) {//后序遍历，只在第3次打印valueif (head == null) {return;}preOrderRecur(head.left);preOrderRecur(head.right);System.out.println(head.value + " ");}

非递归方法做到先序遍历

  public static void pre(Node head) {//使用非递归的方式做到先序遍历System.out.print("pre-order: ");if (head != null) {Stack<Node> stack = new Stack<Node>();//准备一个栈stack.add(head);//加入头结点while (!stack.isEmpty()) {//zia栈不等于空的取快递循环head = stack.pop();//1先弹出头结点System.out.print(head.value + " ");//2执行打印if (head.right != null) {//3如果右不为空，先压右stack.push(head.right);}if (head.left != null) {//3左不为空则压左stack.push(head.left);}}}System.out.println();}

       

非递归中序排列

整个树左边进栈，父节点弹出后，才进入可能有的右边界

//整棵树均可以被左边界或右边界分解public static void midOder(Node head) {//使用非递归的方式做到中序遍历System.out.print("mid-order: ");if (head != null) {Stack<Node> stack = new Stack<Node>();//准备一个栈while (!stack.isEmpty() || head != null) {//zia栈不等于空的取快递循环if (head != null) {//进栈，如果有左边界就一直进栈stack.push(head);head = head.left;} else {//当进入最底层时弹出依次节点，打印并进入右节点head = stack.pop();System.out.print(head.value + " ");//2执行打印head = head.right;}}}System.out.println();}

 

 

 

非递归的后序遍历

申请一个辅助栈，1弹出一个数放进收集辅助栈，2先放左后放右，3重复然后将收集栈打印，得到即是后序遍历

 public static void pos(Node head) {//使用非递归的方式做到后序递归if (head != null) {Stack<Node> stack = new Stack<Node>();//准备一个栈Stack<Node> help = new Stack<Node>();//准备一个辅助栈stack.push(head);//加入头结点while (!stack.isEmpty()) {//zia栈不等于空的取快递循环head = stack.pop();//1先弹出头结点help.push(head);if (head.left != null) {//3左不为空则压左stack.push(head.left);}if (head.right != null) {//3如果右不为空压右stack.push(head.right);}}while (!help.isEmpty()) {System.out.println(help.pop().value + " ");}}System.out.println();}

 

按照宽度遍历

使用队列，从左到右，先进先出

以及如何找到一层中宽度最大的数值

  public static void w(Node head) {//按照宽度遍历if (head == null) {return;}LinkedList<Node> queue = new LinkedList<>();//队列queue.add(head);while (!queue.isEmpty()) {Node cur = queue.poll();//弹出一个节点，首次是头结点System.out.println(cur.value);//并打印值if (cur.left != null) {//父节点存在的左右均进队，循环queue.add(cur.left);}if (cur.right != null) {queue.add(cur.right);}}}public static int maxw(Node head) {//使用哈希表找到二叉树最大的宽度if (head == null) {return 0;}LinkedList<Node> queue = new LinkedList<>();//队列queue.add(head);HashMap<Node, Integer> levelmap = new HashMap<>();//建立一个表记录每个节点所在的层数levelmap.put(head, 1);int curlevel = 1;//当前在第几层int curlevelnodes = 0;//在当前层发现的节点数int max = Integer.MIN_VALUE;//所有层最大的宽度while (!queue.isEmpty()) {Node cur = queue.poll();//弹出一个节点，首次是头结点int curNodeLevel = levelmap.get(cur);if (curNodeLevel == curlevel) {//如果当前节点所在层，未进入下一层时，该层数宽度++curlevelnodes++;} else {//进入下一层了max = Math.max(max, curlevelnodes);curlevel++;curlevelnodes = 1;//已经到达了计数为1}System.out.println(cur.value);//并打印值if (cur.left != null) {//父节点存在的左右均进队，循环levelmap.put(cur.left, curNodeLevel + 1);queue.add(cur.left);}if (cur.right != null) {levelmap.put(cur.right, curNodeLevel + 1);queue.add(cur.right);}}max = Math.max(max, curlevelnodes);//比较最后一层宽度return max;}

主函数测试

   //            5//           / \//          3   8//         /\   / \//        2 4   7  10//       /\     /  / \//      1 66   6  9  11public static void main(String[] args) {Node head = new Node(5);head.left = new Node(3);head.right = new Node(8);head.left.left = new Node(2);head.left.right = new Node(4);head.left.left.left = new Node(1);head.left.left.right = new Node(66);head.right.left = new Node(7);head.right.left.left = new Node(6);head.right.right = new Node(10);head.right.right.left = new Node(9);head.right.right.right = new Node(11);System.out.println("===============================");preOrderRecur(head);System.out.println("后序");midOder(head);System.out.println("最大宽度");System.out.println(maxw(head));//5