二叉树
二叉树的概念
- 数中每个节点最多只能有两个子节点
二叉树节点结构
class Node<V>{ V value; Node left; Node right; } 复制代码
二叉树的先中后序遍历（递归版）
利用递归行为，会有三次机会到达自己，但是选择打印的时机不同
二叉树的先序遍历（递归版）
- 先访问
根节点 - 对根节点的
左子树进行先序遍历 - 对根节点的
右子树进行先序遍历
如果是先序遍历，那么上述的二叉树访问的顺序就是1,2,4,5,3,6,7
Java版
public static void preOrderRecur(Node head){ if(head == null){ return; } System.out.print(head.value); // 第一次到达这个节点的时候就打印了 preOrderRecur(head.left); preOrderRecur(head.right); } 复制代码
Javascript版
const preorder = (root) => { if (!root) { return; } console.log(root.val); preorder(root.left); preorder(root.right); }; 复制代码
二叉树的中序遍历（递归版）
- 对根节点的
左子树进行中序遍历 - 访问
根节点 - 对根节点的
右子树进行中序遍历
如果是中序遍历，那么上述的二叉树访问的顺序就是4,2,5,1,6,3,7
Java版
public static void inOrderRecur(Node head){ if(head == null){ return; } inOrderRecur(head.left); System.out.print(head.value); // 第二次到达这个节点的时候才打印 inOrderRecur(head.right); } 复制代码
Javascript版
const inorder = (root) => { if (!root) { return; } inorder(root.left); console.log(root.val); inorder(root.right); }; 复制代码
二叉树的后序遍历（递归版）
- 对根节点的
左子树进行后序遍历 - 对根节点的
右子树进行后序遍历 - 访问
根节点
如果是后序遍历，那么上述的二叉树访问的顺序就是4,5,2,6,7,3,1
Java版
public static void posOrderRecur(Node head){ if(head == null){ return; } posOrderRecur(head.left); posOrderRecur(head.right); System.out.print(head.value); // 最后到达这个节点的时候才打印 } 复制代码
Javascript版
const postorder = (root) => { if (!root) { return; } postorder(root.left); postorder(root.right); console.log(root.val); }; 复制代码
二叉树的先中后序遍历（非递归版）
任何递归函数都可以改成非递归函数
二叉树的先序遍历（非递归版）
思路
- 1.准备一个栈stack，
头入栈 - 2.从栈中弹出一个节点，记为cur
- 3.打印（处理）cur
- 4.将
右孩子入栈，然后左孩子入栈（如果有） - 5.重复2-4
比如上述二叉树，要进行非递归版的遍历：
- 1.stack=[],头入栈，stack=[1]
- 2.弹出并打印1，然后右孩子入栈，再左孩子入栈，stack=[3,2]
- 3.弹出并打印2，然后右孩子入栈，再左孩子入栈，stack=[3,5,4]
- 4.弹出并打印4，无左右孩子，继续弹出并打印5，无左右孩子，stack=[3]
- 5.继续弹出并打印3，然后右孩子入栈，再左孩子入栈，stack=[7,6]
- 6.继续弹出并打印6和7。所以最终打印出的顺序是1,2,4,5,3,6,7
Java版
public static void preOrderUnRecur(Node head){ if(head != null){ Stack<Node> stack = new Stack<Node>(); 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.printIn(); } 复制代码
Javascript版
const preorder = (root) => { if (!root) { return; } const stack = [root]; while (stack.length) { const n = stack.pop(); console.log(n.val); if (n.left) stack.push(n.left); if (n.right) stack.push(n.right); } }; preorder(bt); 复制代码
二叉树的中序遍历（非递归版）
思路：
- 整棵树的左边界上的所有数全部入栈
- 弹出时，打印
- 对弹出节点的右树上的左边界上的所有数入栈，重复
比如上述二叉树，要进行非递归版的遍历：
- 1.整棵树的左边界上的数人入栈，stack1=[1,2,4]
- 2.弹出打印4，无右树
- 3.弹出打印2，入右树，stack1=[1,5]
- 4.弹出打印5，无右孩子
- 5.弹出打印1，入右树中的左边界上的树，stack1=[3,6]
- 6.弹出打印6，无右树
- 7.弹出打印3，入右孩子，stack1=[7]
- 8.弹出打印7
另外还有个例子（左边是二叉树，右边是打印出来的顺序）：
网络异常，图片无法展示
|
Java版
public static void inOrderUnRecur(Node head){ if(head != null){ Stack<Node> stack = new Stack<Node>(); while(!stack.isEmpty() || head != null){ if(head != null){ // 左边界进栈 stack.push(head); head = head.left; }else{ // 左边界已经全部进栈，开始弹出，弹出时打印，开始进入右树的左边界入栈 head = stack.pop(); System.out.print(head.value); head = head.right; } } } System.out.printIn(); } 复制代码
Javascript版
const inorder = (root) => { if (!root) { return; } const stack = []; let p = root; while (stack.length || p) { while (p) { stack.push(p); p = p.left; } const n = stack.pop(); console.log(n.val); p = n.right; } }; 复制代码
二叉树的后序遍历（非递归版）
思路
- 1.准备两个栈，头入stack1
- 2.stack1弹出一个节点，记为cur，放入stack2中
- 3.左孩子入stack1后，再入右孩子
- 4.重复2-3，直到stack1遍历完
- 5.依次打印stack2
Java版
public static void posOrderUnRecur(Node head){ if(head != null){ Stack<Node> s1 = new Stack<Node>(); Stack<Node> s2 = new Stack<Node>(); s1.push(head); while(!s1.isEmpty()){ head = s1.pop(); s2.push(head); if(head.left != null){ s1.push(head.left); } if(head.right != null){ s1.push(head.right); } } while(!s2.isEmpty()){ System.out.printIn(s2.pop().value); } } System.out.printIn(); } 复制代码
Javascript版
const postorder = (root) => { if (!root) { return; } const outputStack = []; const stack = [root]; while (stack.length) { const n = stack.pop(); outputStack.push(n); if (n.left) stack.push(n.left); if (n.right) stack.push(n.right); } while(outputStack.length){ const n = outputStack.pop(); console.log(n.val); } };
