建立网站tk,wordpress简洁博客模板下载,商城app源码,镇江市丹徒区建设局网站二叉树 1. 递归遍历1. 先序遍历2. 中序遍历3. 后序遍历 2. 非递归遍历2.1 先序遍历2.2 中序遍历2.3 后序遍历2.3.1 两栈实现2.3.2 一栈实现 1. 递归遍历
二叉树的结构定位为#xff1a; public static class TreeNode {public int val;public TreeNode left;public TreeNode … 二叉树 1. 递归遍历1. 先序遍历2. 中序遍历3. 后序遍历 2. 非递归遍历2.1 先序遍历2.2 中序遍历2.3 后序遍历2.3.1 两栈实现2.3.2 一栈实现 1. 递归遍历
二叉树的结构定位为 public static class TreeNode {public int val;public TreeNode left;public TreeNode right;public TreeNode(int v) {val v;}}1. 先序遍历 // 递归先序遍历public static void preOrder(TreeNode head){if (head null){return;}System.out.print(head.val ); // 打印preOrder(head.left); // 递归左子树preOrder(head.right); // 递归右子树}2. 中序遍历 // 递归中序遍历public static void inOrder(TreeNode head){if (head null){return;}inOrder(head.left); // 递归左子树System.out.print(head.val ); // 打印inOrder(head.right); // 递归右子树}3. 后序遍历 public static void posOrder(TreeNode head){if (headnull){return;}posOrder(head.left);posOrder(head.right);System.out.print(head.val );}2. 非递归遍历
2.1 先序遍历 // 栈实现非递归先序遍历public static void preOrder(TreeNode head){if (head! null){StackTreeNode stack new Stack();stack.push(head);while (!stack.isEmpty()){head stack.pop();System.out.print(head.val );// 栈先进后出 先序中左右 先压右再压左if (head.right ! null){stack.push(head.right);}if (head.left ! null){stack.push(head.left);}}System.out.println();}}2.2 中序遍历 // 栈实现非递归中序遍历 左中右// 原理还是先处理节点的左树 再到自己 再处理右树// 1. 子树的左边界全部进栈 进步骤 2// 2. 栈弹出节点并打印 此节点右树重复步骤 1// 3. 没有子树, 且栈空结束public static void inOrder(TreeNode head){if (head ! null){StackTreeNode stack new Stack();while (!stack.isEmpty() || head ! null){ // head ! null 有树// 步骤1if (head ! null){stack.push(head);head head.left;// 步骤2} else {head stack.pop();System.out.print(head.val );head head.right;}}System.out.println();}}2.3 后序遍历
2.3.1 两栈实现 // 栈实现非递归后序遍历 两个栈// 思路: 先序(中左右)--- 中右左 --- 后序(左右中)public static void posOrderTwoStack(TreeNode head){if (head! null){StackTreeNode stack new Stack();StackTreeNode collect new Stack();stack.push(head);while (!stack.isEmpty()){head stack.pop();collect.push(head); // 不打印 按照中右左进栈if (head.left ! null){stack.push(head.left);}if (head.right ! null){stack.push(head.right);}}// 出栈 左右中while (!collect.isEmpty()){System.out.print(collect.pop().val );}System.out.println();}}2.3.2 一栈实现 // 栈实现非递归后序遍历 一个栈public static void posOrderOneStack(TreeNode h){if (h ! null){StackTreeNode stack new Stack();stack.push(h);// 如果始终没有打印过节点, h就一直是头结点// 一旦打印过节点, h就变成打印节点// 之后h的含义: 上一次打印的节点while (!stack.isEmpty()){TreeNode cur stack.peek();// 取栈顶元素if (cur.left ! null h ! cur.left h! cur.right){// 有左树且左树没有被处理过stack.push(cur.left);}else if (cur.right ! null h! cur.right){// 有右树且右树没有被处理过stack.push(cur.right);}else {// 左树 右树 没有 或者 都被处理过了System.out.print(cur.val );h stack.pop(); // 指向上次打印节点}}}}
