前言:
而今小伙伴们对“二叉树的后根遍历算法”大体比较关切,我们都需要学习一些“二叉树的后根遍历算法”的相关文章。那么小编同时在网络上搜集了一些有关“二叉树的后根遍历算法””的相关文章,希望兄弟们能喜欢,你们快快来学习一下吧!先序遍历与后序遍历
先序遍历根节点,再遍历左子树,再遍历右子树。
后序遍历先遍历左子树,再遍历右子树,再遍历根节点。
先序遍历递归实现:
public static void preOrderByRecursion(TreeNode root) { // 打印节点值 System.out.println(root.value); preOrder(root.left); preOrder(root.right);}
先序遍历的非递归实现:
非递归实现需要借助栈这样一个数据结构,实际上递归实现也是依靠栈,只不过是隐式的。
先将根节点压入栈中。弹出栈中的节点,将弹出节点的右子节点压入栈中,再将弹出节点的左子树压入栈中。重复步骤2,直到栈为空。
public static void preOrder(TreeNode root) { if (root == null) { return; } Stack<TreeNode> stack = new Stack<>(); stack.push(root); while (!stack.empty()) { TreeNode node = stack.pop(); // 打印节点值 System.out.print(node.value + " "); if (node.right != null) { stack.push(node.right); } if (node.left != null) { stack.push(node.left); } }}
后序遍历递归实现:先序遍历反过来,就不赘述了。
public static void postOrderByRecursion(TreeNode root) { postOrderByRecursion(root.left); postOrderByRecursion(root.right); System.out.println(root.value);}
后序遍历非递归实现:后序遍历就是先序遍历反过来,所以需要两个栈,多出来的栈用来反向输出。
public static void postOrder(TreeNode root) { if (root == null) { return; } Stack<TreeNode> s1 = new Stack<>(); Stack<TreeNode> s2 = new Stack<>(); s1.push(root); while (!s1.empty()) { TreeNode node = s1.pop(); s2.push(node); if (node.left != null) { s1.push(node.left); } if (node.right != null) { s1.push(node.right); } } while (!s2.empty()) { System.out.println(s2.pop().value); }}中序遍历
中序遍历先遍历左子树,再遍历根节点,再遍历右子树。
递归遍历:
public static void inOrderByRecursion(TreeNode root) { if (root == null) { return; } inOrderByRecursion(root.left); // 打印节点值 System.out.println(root.value); inOrderByRecursion(root.right);}
非递归遍历:
将二叉树的左侧“边”从上到下依次压入栈中。从栈中弹出节点对以弹出节点的右子节点为根节点的子树,重复步骤1。重复2、3步骤,直到栈为空。
public static void inOrder(TreeNode root) { if (root == null) { return; } Stack<TreeNode> stack = new Stack<>(); TreeNode cur = root; while (cur != null) { stack.push(cur); cur = cur.left; } while (!stack.empty()) { TreeNode node = stack.pop(); System.out.println(node.value); cur = node.right; while (cur != null) { stack.push(cur); cur = cur.left; } }}层序遍历
层序遍历顾名思义就是一层一层,从左到右的遍历二叉树。需要用到队列这一数据结构。
将根节点推入队列。从队列中取出一个节点。先将取出节点的左子节点推入队列,再将取出节点的右子节点推入队列。重复2、3步骤直到队列中无节点可取。
public static void floorOrder(TreeNode root) { if (root == null) { return; } Queue<TreeNode> queue = new LinkedList<>(); queue.add(root); while (!queue.isEmpty()) { TreeNode node = queue.poll(); System.out.println(node.value); if (node.left != null) { queue.add(node.left); } if (node.right != null) { queue.add(node.right); } }}
标签: #二叉树的后根遍历算法