二叉树
1 2 3 4 5
| class Node<V>{ V value; Node left; Node right; }
|
问题一
用递归和非递归两种方式实现二叉树的先序、中序、后序遍历
如何直观的打印一颗二叉树 ?
如何完成二叉树的宽度优先遍历 ?
左右节点(孩子)都为空的节点就叫做叶子节点
递归序
1 2 4 4 4(三次返回)2 5 5 5 2 (三次返回2)1 3 6 6 6 3 7 7 7 3 (三次返回7) 3 (三次返回3)1
在递归序的基础上,有三种遍历方式
- 先序:对于所有子树来说,都是先打印子树的头节点,在打印子树的左边节点,在打印子树的右边节点
1 2 4 5 3 6 7
第一次来到某个节点,就直接打印该节点,其他时候不打印
- 中序:对于每一颗子树,都是先打印左边节点,在打印头节点,在打印右边节点
4 2 5 1 6 3 7
第一次来到某个节点什么都不做,第二次来到某个节点打印该节点,第三次来到某个节点,什么都不做
- 后序:对于每一颗子树,都是先打印左边节点,在打印右边节点,在打印头节点
4 5 2 6 7 3 1
第一次来到某个节点什么都不做,第二次来到某个节点什么都不做,第三次来到某个节点,打印该节点
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25
| public static void preOrderRecur(Node head){ if(head == null){ return; } System.out.print(head.value + " "); preOrderRecur(head.left); preOrderRecur(head.right); } public static void inOrderRecur(Node head){ if(head == null){ return; } inOrderRecur(head.left); System.out.print(head.left + " "); inOrderRecur(head.right); } public static void postOrderRecur(Node head){ if(head == null){ return; } preOrderRecur(head.left); preOrderRecur(head.right); System.out.print(head.value + " "); }
|
非递归实现先序遍历
- 先把头节点入栈
- 从栈中弹出一个节点记为cur
- 打印或者处理cur
- 把cur的孩子先右再左入栈(如果有的话)
- 重复以上步骤
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
| public static void preOrderUnRecur(Node head){ System.out.print("pre-order: "); if(head != null){ Stack<Node> stack = new Stack<>(); stack.add(head); while (!stack.isEmpty()){ head = stack.pop(); System.out.print(head.value + " "); if(head.right != null){ stack.push(head.right); } if(head.left != null){ stack.push(head.left); } } } System.out.println(); }
|
中序遍历
每棵子树整棵树的左边界进栈,依次弹出的过程中,打印,对于弹出节点的右树重复左边界入栈的操作
- 从头节点开始,每个节点的左边界(左边的全部节点,包括头节点)全部入栈
- 弹出一个节点cur,打印该节点
- 对于cur,把cur的右节点作为新的头节点,重复节点的左边界进栈
- 弹出一个节点cur,打印该节点(直到栈空)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
| public static void inOrderUnRecur(Node head){ System.out.println("in-order: "); if(head != null){ Stack<Node> stack = new Stack<>(); while (!stack.isEmpty() head != null){ if(head != null){ stack.push(head); head = head.left; }else { head = stack.pop(); System.out.println(head.value + " "); head = head.right; } } } System.out.println(); }
|
后序遍历(准备两个栈 s1 s2)
- 先把头节点入栈s1
- 从栈s1中弹出一个节点cur
- 把cur的子节点按照先左再右的顺序入栈s1
- 把cur放入栈s2
- 从栈s1中弹出一个节点cur(这一步开始重复知道s1为空)
- 按照出栈顺序打印s2栈中元素
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21
| public static void postOrderUnRecur(Node head){ System.out.println("pos-order: "); if(head != null){ Stack<Node> s1 = new Stack<>(); Stack<Node> s2 = new Stack<>(); s1.push(head); while (!s1.isEmpty()){ head = s1.pop(); if(head.left != null){ s1.push(head.left); } if(head.right != null){ s1.push(head.right); } } while (!s2.isEmpty()){ System.out.println(s2.pop() + " "); } System.out.println(); } }
|
对于二叉树来说
先序遍历就是二叉树的深度优先遍历
二叉树的宽度优先遍历
- 设置一个队列
- 头节点入队列
- 出队列设置为cur,并打印cur
- 对于cur,先放cur的左节点,再放cur的右节点
- 出队列设置为cur,并打印cur,对于cur, 先放左再放右(重复知道队列为空)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
| public static void w(Node head){ if(head == null){ return; } Queue<Node> queue = new LinkedList<>(); queue.add(head); while(!queue.isEmpty()){ Node cur = queue.poll(); System.out.print(cur.value); if(cur.left != null){ queue.add(cur.left); } if(cur.right != null){ queue.add(cur.right); } } }
|
求一颗二叉树的最大宽度
- 定义一个HashMap用于记录每个节点在第几层
- 定义 curLevel 记录当前层数 curLevelNodes 记录当前层节点数 max 记录节点最多的层数
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31
| public static void w(Node head){ if(head == null){ return; } Queue<Node> queue = new LinkedList<>(); queue.add(head); HashMap<Node, Interger> levelMap = new HashMap<>(); levelMap.put(head, 1); int curLevel = 1; int curLevelNodes = 0; int max = Interger.M 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; } 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); } } }
|