九寨沟网站建设规划书,时空赣州网,asp网站好还是php网站好,小程序制作平台官网LeetCode经典算法题#xff1a;二叉树遍历#xff08;递归遍历迭代遍历层序遍历#xff09;以及线索二叉树java详解 文章目录二叉树遍历题目描述解题思路与代码递归遍历迭代遍历层序遍历线索二叉树#xff1a;二叉树遍历
题目描述 从根节点往下查找#xff0c;先找左子树… LeetCode经典算法题二叉树遍历递归遍历迭代遍历层序遍历以及线索二叉树java详解 文章目录二叉树遍历题目描述解题思路与代码递归遍历迭代遍历层序遍历线索二叉树二叉树遍历
题目描述 从根节点往下查找先找左子树、直至左子树为空(左子节点逐个入栈、直至左子节点为空)再找右子树(出栈找右子节点) 前序遍历根左右第一次经过节点即打印直到打印null往回溯打印右子树 中序遍历左根右第二次经过该节点时进行打印即左边回溯时 后序遍历左右根第三次经过该节点时进行打印即右边回溯时 层序遍历按照层级从上往下从左到右。使用广度优先搜索算法。 从根节点往下查找先找左子树、直至左子树为空(左子节点逐个入栈、直至左子节点为空)再找右子树(出栈找右子节点) 解题思路与代码
递归遍历 public static void preorder(TreeNode root) {if (root null) {return;}//System.out.println(root.val);//前序 第一次成为栈顶preorder(root.left);System.out.println(root.val);//中序 第二次成为栈顶preorder(root.right);//System.out.println(root.val);//后序 第三次成为栈顶}迭代遍历 //前序使用stack记录递归路径左子节点后添加保证先出栈public static void preOrder2(TreeNode head) {if (head ! null) {StackTreeNode stack new StackTreeNode();stack.add(head);while (!stack.isEmpty()) {head stack.pop();if(head ! null){System.out.println(head.val);stack.push(head.right);stack.push(head.left);}}}}//中序将左子节点入栈出栈打印值然后添加右子节点public static void preOrder3(TreeNode head) {if (head ! null) {StackTreeNode stack new StackTreeNode();while (!stack.isEmpty() || head ! null) {if (head ! null) {stack.push(head);head head.left;} else {head stack.pop();System.out.println(head.val);head head.right;}}}}//后序public static void postorderTraversal(TreeNode root) {if (root null) {return ;}DequeTreeNode stack new LinkedListTreeNode();TreeNode prev null;while (root ! null || !stack.isEmpty()) {while (root ! null) {stack.push(root);root root.left;}root stack.pop();//root的左子节点为nullif (root.right null || root.right prev) {//右子节点为null或者右子节点已打印System.out.println(root.val);prev root;root null;} else {//右子节点有值重新入栈stack.push(root);root root.right;}}}
层序遍历 public static void levelTraversal(Node root) {QueueNode q new LinkedList();q.add(root);while (!q.isEmpty()) {Node temp q.poll();if (temp ! null) {System.out.print(temp.value );q.add(temp.left);q.add(temp.right);}}}public static void deepOrder(TreeNode root) {if (root null) {return ;}QueueTreeNode queue new LinkedListTreeNode();queue.offer(root);while (!queue.isEmpty()) {for (int i 1; i queue.size(); i) {TreeNode node queue.poll();System.out.println(node.val);if (node.left ! null) {queue.offer(node.left);}if (node.right ! null) {queue.offer(node.right);}}}}private static List order(TreeNode root, int i, ArrayList list) {if (root null) {return null;}int length list.size();if(length i){for(int j0; j i-length; j){list.add(lengthj,null);}}list.set(i,root.val);order(root.left, 2 * i,list);order(root.right, 2 * i 1,list);return list;}线索二叉树
在N个节点的二叉树中每个节点有2个指针所以一共有2N个指针除了根节点以外每一个节点都有一个指针从它的父节点指向它所以一共使用了N-1个指针所以剩下2N-(N-1)也就是N1个空指针
如果能利用这些空指针域来存放指向该节点的直接前驱或是直接后继的指针则可由此信息直接找到在该遍历次序下的前驱节点或后继节点从而比递归遍历提高了遍历速度节省了建立系统递归栈所使用的存储空间
这些被重新利用起来的空指针就被称为线索Thread加上了线索的二叉树就是线索二叉树实现思路按某种次序遍历二叉树在遍历过程中用线索取代空指针即可。以中序遍历为例首先找到中序遍历的开始节点然后利用线索依次查找后继节点即可。
由于它充分利用了空指针域的空间等于节省了空间又保证了创建时的一次遍历就可以终生受用前驱、后继的信息这意味着节省了时间所以在实际问题中如果所使用的二叉树需要经常遍历或查找节点时需要某种遍历中的前驱和后继那么采用线索二叉链表的存储结构就是不错的选择morris遍历构建中序线索二叉树的过程中如果发现前驱节点的右指针指向自身则将指针线索删除
public static void morrisPre(Node cur) {if(head null){return;}Node mostRight null;while (cur ! null){// cur表示当前节点mostRight表示cur的左孩子的最右节点mostRight cur.left;if(mostRight ! null){// cur有左孩子找到cur左子树最右节点while (mostRight.right !null mostRight.right ! cur){mostRight mostRight.right;}// mostRight的右孩子指向空让其指向curcur向左移动if(mostRight.right null){mostRight.right cur;System.out.print(cur.value );cur cur.left;continue;}else {// mostRight的右孩子指向cur让其指向空cur向右移动mostRight.right null;}}else {System.out.print(cur.value );}cur cur.right;}}public static void morrisIn(Node cur) {if(head null){return;}Node mostRight null;while (cur ! null){mostRight cur.left;if(mostRight ! null){while (mostRight.right !null mostRight.right ! cur){mostRight mostRight.right;}if(mostRight.right null){mostRight.right cur;cur cur.left;continue;}else {mostRight.right null;}}System.out.print(cur.value );cur cur.right;}}public static void morrisPos(TreeNode cur) {if (cur null) {return;}TreeNode head cur;TreeNode mostRight null;while (cur ! null) {mostRight cur.left;if (mostRight ! null) {while (mostRight.right ! null mostRight.right ! cur) {mostRight mostRight.right;}if (mostRight.right null) {mostRight.right cur;cur cur.left;continue;} else {mostRight.right null;printEdge(cur.left);}}cur cur.right;}printEdge(head);System.out.println();}public static void printEdge(TreeNode head) {TreeNode tail reverseEdge(head);TreeNode cur tail;while (cur ! null) {System.out.print(cur.val );cur cur.right;}reverseEdge(tail);}public static TreeNode reverseEdge(TreeNode from) {TreeNode pre null;TreeNode next null;while (from ! null) {next from.rightfrom.right pre;pre from;from next;}return pre;}public ListInteger postorderTraversal(TreeNode root) {ListInteger res new ArrayListInteger();if (root null) {return res;}DequeTreeNode stack new LinkedListTreeNode();TreeNode prev null;while (root ! null || !stack.isEmpty()) {while (root ! null) {stack.push(root);root root.left;}root stack.pop();if (root.right null || root.right prev) {res.add(root.val);prev root;root null;} else {stack.push(root);root root.right;}}return res;}
文章转载自： http://www.morning.ljygq.cn.gov.cn.ljygq.cn http://www.morning.jntcr.cn.gov.cn.jntcr.cn http://www.morning.rlhh.cn.gov.cn.rlhh.cn http://www.morning.mwmxs.cn.gov.cn.mwmxs.cn http://www.morning.qmpbs.cn.gov.cn.qmpbs.cn http://www.morning.przc.cn.gov.cn.przc.cn http://www.morning.qyhcm.cn.gov.cn.qyhcm.cn http://www.morning.myzfz.com.gov.cn.myzfz.com http://www.morning.tsdqr.cn.gov.cn.tsdqr.cn http://www.morning.ljpqy.cn.gov.cn.ljpqy.cn http://www.morning.ccyjt.cn.gov.cn.ccyjt.cn http://www.morning.kybyf.cn.gov.cn.kybyf.cn http://www.morning.zkdbx.cn.gov.cn.zkdbx.cn http://www.morning.hlrtzcj.cn.gov.cn.hlrtzcj.cn http://www.morning.gmgyt.cn.gov.cn.gmgyt.cn http://www.morning.gpnfg.cn.gov.cn.gpnfg.cn http://www.morning.wmfr.cn.gov.cn.wmfr.cn http://www.morning.xcbnc.cn.gov.cn.xcbnc.cn http://www.morning.ysybx.cn.gov.cn.ysybx.cn http://www.morning.jfbpf.cn.gov.cn.jfbpf.cn http://www.morning.prhqn.cn.gov.cn.prhqn.cn http://www.morning.xdxpq.cn.gov.cn.xdxpq.cn http://www.morning.nwmwp.cn.gov.cn.nwmwp.cn http://www.morning.qzpkr.cn.gov.cn.qzpkr.cn http://www.morning.dgsr.cn.gov.cn.dgsr.cn http://www.morning.qkpzq.cn.gov.cn.qkpzq.cn http://www.morning.cbynh.cn.gov.cn.cbynh.cn http://www.morning.ghjln.cn.gov.cn.ghjln.cn http://www.morning.wjpsn.cn.gov.cn.wjpsn.cn http://www.morning.bpmnz.cn.gov.cn.bpmnz.cn http://www.morning.ssrjt.cn.gov.cn.ssrjt.cn http://www.morning.dwtdn.cn.gov.cn.dwtdn.cn http://www.morning.qtkdn.cn.gov.cn.qtkdn.cn http://www.morning.tnhmp.cn.gov.cn.tnhmp.cn http://www.morning.psgbk.cn.gov.cn.psgbk.cn http://www.morning.ishoufeipin.cn.gov.cn.ishoufeipin.cn http://www.morning.tjmfz.cn.gov.cn.tjmfz.cn http://www.morning.szzxqc.com.gov.cn.szzxqc.com http://www.morning.zryf.cn.gov.cn.zryf.cn http://www.morning.rymd.cn.gov.cn.rymd.cn http://www.morning.xrqkm.cn.gov.cn.xrqkm.cn http://www.morning.txzmy.cn.gov.cn.txzmy.cn http://www.morning.yqwsd.cn.gov.cn.yqwsd.cn http://www.morning.dmzqd.cn.gov.cn.dmzqd.cn http://www.morning.gslz.com.cn.gov.cn.gslz.com.cn http://www.morning.bpwz.cn.gov.cn.bpwz.cn http://www.morning.bwqr.cn.gov.cn.bwqr.cn http://www.morning.wsxxq.cn.gov.cn.wsxxq.cn http://www.morning.nkjjp.cn.gov.cn.nkjjp.cn http://www.morning.rzsxb.cn.gov.cn.rzsxb.cn http://www.morning.thmlt.cn.gov.cn.thmlt.cn http://www.morning.qkqzm.cn.gov.cn.qkqzm.cn http://www.morning.fksdd.cn.gov.cn.fksdd.cn http://www.morning.yhyqg.cn.gov.cn.yhyqg.cn http://www.morning.wcjgg.cn.gov.cn.wcjgg.cn http://www.morning.mtxrq.cn.gov.cn.mtxrq.cn http://www.morning.nhlnh.cn.gov.cn.nhlnh.cn http://www.morning.zpjhh.cn.gov.cn.zpjhh.cn http://www.morning.nqrdx.cn.gov.cn.nqrdx.cn http://www.morning.cmqrg.cn.gov.cn.cmqrg.cn http://www.morning.brsgw.cn.gov.cn.brsgw.cn http://www.morning.jtmql.cn.gov.cn.jtmql.cn http://www.morning.jwwfk.cn.gov.cn.jwwfk.cn http://www.morning.rfhwc.cn.gov.cn.rfhwc.cn http://www.morning.yqpck.cn.gov.cn.yqpck.cn http://www.morning.rgrz.cn.gov.cn.rgrz.cn http://www.morning.brsgw.cn.gov.cn.brsgw.cn http://www.morning.hwzzq.cn.gov.cn.hwzzq.cn http://www.morning.sgfgz.cn.gov.cn.sgfgz.cn http://www.morning.ptzbg.cn.gov.cn.ptzbg.cn http://www.morning.bpmfr.cn.gov.cn.bpmfr.cn http://www.morning.ruyuaixuexi.com.gov.cn.ruyuaixuexi.com http://www.morning.fbbmg.cn.gov.cn.fbbmg.cn http://www.morning.rbmm.cn.gov.cn.rbmm.cn http://www.morning.gqtw.cn.gov.cn.gqtw.cn http://www.morning.qyjqj.cn.gov.cn.qyjqj.cn http://www.morning.dxpqd.cn.gov.cn.dxpqd.cn http://www.morning.qqtzn.cn.gov.cn.qqtzn.cn http://www.morning.rcjwl.cn.gov.cn.rcjwl.cn http://www.morning.baohum.com.gov.cn.baohum.com
