大学校园门户网站建设方案,登封快乐送餐在那个网站做的广告,开通域名后怎样建设网站,一键生成app下载目录 一.Morris遍历
1.什么是Morris遍历
2.基本思想
3.Morris遍历的优点和缺点
4.知识回顾----二叉树的线索化
二.中序Morris遍历
1.中序Morris遍历的分析
2.中序Morris遍历的思路
3.具体的代码实现
三.前序Morris遍历
1.前序Morris遍历的思路
2.具体的代码实现
四…目录 一.Morris遍历
1.什么是Morris遍历
2.基本思想
3.Morris遍历的优点和缺点
4.知识回顾----二叉树的线索化
二.中序Morris遍历
1.中序Morris遍历的分析
2.中序Morris遍历的思路
3.具体的代码实现
三.前序Morris遍历
1.前序Morris遍历的思路
2.具体的代码实现
四.后序Morris遍历
1.后序Morris遍历的思路
2.具体的代码实现 一.Morris遍历
1.什么是Morris遍历
Morris遍历是一种用于二叉树遍历的算法它可以在不使用栈或队列的情况下实现中序遍历。该算法的时间复杂度为O(n)空间复杂度为O(1)。
2.基本思想
Morris遍历的基本思想是利用叶子节点的空指针来存储临时信息以达到节省空间的目的。具体来说对于当前遍历到的节点如果它有左子节点就找到左子树中最右边的节点将其右子节点指向当前节点然后将当前节点更新为其左子节点。如果它没有左子节点就输出当前节点的值并将当前节点更新为其右子节点。重复以上步骤直到遍历完整棵树。
3.Morris遍历的优点和缺点
Morris遍历的优点是空间复杂度低O(1)但它的缺点是会改变原来的二叉树结构因此需要在遍历完后还原二叉树。此外该算法可能会比递归或使用栈的算法稍微慢一些。
4.知识回顾----二叉树的线索化
二叉树的线索化,主要是利用了叶子结点中的空指针域,存放了在某种遍历顺序下的前驱或者后续结点,从而达到了线索二叉树的目的
例如,下图中序遍历结果展示如下,根据中序遍历对空指针域进行线索化 线索化的二叉树为下, 画在左边表示left结点指向,画在右边表示right指向,例如7的前驱结点为5,那么7的left指向5,7的后继节点为1,那么7的right指向1 由此,我们可能总结出这样的结论:中序遍历二叉树的指向当前结点的结点为当前结点的左子树的最右端结点,例如指向1的结点为1的左节点2的最右端结点为7,指向2结点的为2的左节点4的最右端结点4.这一点在之后的morris遍历中很重要
具体的代码实现如下:
public class InorderThreadedBinaryTree {private ThreadTreeNode pre null;public void threadedNodes(ThreadTreeNode node) {//如果nodenull不能线索化if (node null) {return;}//1、先线索化左子树threadedNodes(node.left);//2、线索化当前结点//处理当前结点的前驱结点//以8为例来理解//8结点的.left null8结点的.leftType 1if (node.left null) {//让当前结点的左指针指向前驱结点node.left pre;//修改当前结点的左指针的类型指向前驱结点node.leftType 1;}//处理后继结点if (pre ! null pre.right null) {//让当前结点的右指针指向当前结点pre.right node;//修改当前结点的右指针的类型pre.rightType 1;}//每处理一个结点后让当前结点是下一个结点的前驱结点pre node;//3、线索化右子树threadedNodes(node.right);}}class ThreadTreeNode {int val;ThreadTreeNode left;//0为非线索化,1为线索化int leftType;ThreadTreeNode right;//0为非线索化,1为线索化int rightType;public ThreadTreeNode(int val) {this.val val;}
}
但是在实现Morris遍历的时候,并不需要把结点的左节点线索化,只需要把结点的右节点进行线索化即可,具体的原因在下面进行分析.
二.中序Morris遍历
1.中序Morris遍历的分析
上面我们说了Morris遍历的时候只需要线索化右节点,这里给大家进行解释.当我们在中序遍历一棵树的时候,还比如是这样一棵树,我们一步步的node.left来到了6这个结点,这个结点的left为空,所以我们打印6这个结点的值,此时我们需要返回上一个结点,如果我们是要中序递归进行遍历的话,需要返回上一个栈,而我们Morris遍历的时候无法进行递归的返回,所以这个时候我们只需要把6的right结点进行线索化,这个时候6的right指向4,我们就可以返回到4,把4这个结点进行打印,4也线索化返回了2,把2进行打印,然后进行2的right结点5,5的left结点为空,因此打印5,之后进入到5的right结点7,打印7,7的right结点也进行了线索化,进入7的right结点为1,然后打印1,进入3结点并且打印
因为最好不要改变树的结构,所以我们在打印的时候,将线索化的结点的right结点置为空. 2.中序Morris遍历的思路
Morris遍历是利用了线索二叉树的思想,在遍历的过程中不适用栈,从而达到了空间复杂度为O(1)
具体的实现如下:
1.初始化当前的结点为根结点
2.若当前的结点的左节点为空,则输出当前结点,然后遍历当前结点的右子树,即currcurr.right
3.若当前结点的左节点不为空,则找到当前结点的前驱节点,即当前结点左节点的最右侧结点,记为prev
如果prev.right为空,则将pre.right指向curr结点,然后遍历当前结点的左子树,即currcurr.left如果prev.right不为空,说明已经遍历完了当前节点的左子树,断开 prev.right 的连接,即prev.leftnull,输出当前节点,然后遍历当前节点的右子树,即 currcurr.right.
3.具体的代码实现
public class Morris {/*** 将当前根结点中序遍历的结果存储到list集合中* param root 根结点* return 中序遍历的结合*/public ListInteger inorderTraversal(TreeNode root) {ListInteger res new ArrayList();TreeNode curr root;while (curr ! null) {if (curr.left null) { // 左子树为空则输出当前节点然后遍历右子树res.add(curr.val); //如果要求直接打印,直接输出System.out.println(curr.val);curr curr.right;} else {// 找到当前节点的前驱节点TreeNode prev curr.left;while (prev.right ! null prev.right ! curr) {prev prev.right;}if (prev.right null) {// 将前驱节点的右子树连接到当前节点prev.right curr;curr curr.left;} else {// 前驱节点的右子树已经连接到当前节点断开连接输出当前节点然后遍历右子树prev.right null;res.add(curr.val);//如果要求直接打印,直接输出System.out.println(curr.val);curr curr.right;}}}return res;}
}class TreeNode {int val;TreeNode left;TreeNode right;TreeNode(int x) {val x;}
}
测试: 还是这样一颗二叉树,输出如下: [6, 4, 2, 5, 7, 1, 3] 三.前序Morris遍历
1.前序Morris遍历的思路
前序和中序的遍历很想,只不过在打印(收集结点信息的时候不同),中序遍历是在当前结点的左节点为空(curr.leftnull),或者当前结点已经被线索化(prev.rightcurr)的时候进行打印,仔细观察前序遍历的过程,我们通过修改打印的顺序即可.前序遍历是在当前结点的左节点为空(curr.leftnull),或者当前结点没有被线索化(prev.rightnull)的时候进行打印
具体的思路如下:
1.初始化当前的结点为根结点
2.若当前的结点的左节点为空,则输出当前结点,然后遍历当前结点的右子树,即currcurr.right
3.若当前结点的左节点不为空,则找到当前结点的前驱节点,即当前结点左节点的最右侧结点,记为prev
如果prev.right为空,输出当前节点,然后将pre.right指向curr结点,然后遍历当前结点的左子树,即currcurr.left如果prev.right不为空,说明已经遍历完了当前节点的左子树,断开 prev.right 的连接,即prev.leftnull,然后遍历当前节点的右子树,即 currcurr.right.2.具体的代码实现 public ListInteger preorderTraversal(TreeNode root) {ListInteger res new ArrayList();TreeNode curr root;while (curr ! null) {if (curr.left null) { // 左子树为空则输出当前节点然后遍历右子树res.add(curr.val);//如果要求直接打印,直接输出System.out.println(curr.val);curr curr.right;} else {// 找到当前节点的前驱节点TreeNode prev curr.left;while (prev.right ! null prev.right ! curr) {prev prev.right;}if (prev.right null) {res.add(curr.val);//如果要求直接打印,直接输出System.out.println(curr.val);// 将前驱节点的右子树连接到当前节点prev.right curr;curr curr.left;} else {// 前驱节点的右子树已经连接到当前节点断开连接输出当前节点然后遍历右子树prev.right null;curr curr.right;}}}return res;}
测试: public static void main(String[] args) {TreeNode root new TreeNode(1);root.left new TreeNode(2);root.left.right new TreeNode(5);root.left.right.right new TreeNode(7);root.right new TreeNode(3);root.left.left new TreeNode(4);root.left.left.left new TreeNode(6);System.out.println(preorderTraversal(root));}还是这样一颗二叉树,输出如下: [1, 2, 4, 6, 5, 7, 3] 四.后序Morris遍历
1.后序Morris遍历的思路
后序Morris遍历实现起来有一定的难度,但是基本代码还是不变,只是在打印的地方有略微的区别,
具体的思路如下:
1.初始化当前的结点为根结点
2.若当前的结点的左节点为空,则输出当前结点,然后遍历当前结点的右子树,即currcurr.right
3.若当前结点的左节点不为空,则找到当前结点的前驱节点,即当前结点左节点的最右侧结点,记为prev
如果prev.right为空,然后将pre.right指向curr结点,然后遍历当前结点的左子树,即currcurr.left如果prev.right不为空,此时进行逆序存储,说明已经遍历完了当前节点的左子树,断开 prev.right 的连接,即prev.leftnull,然后遍历当前节点的右子树,即 currcurr.right.2.具体的代码实现 public ListInteger postorderTraversal(TreeNode root) {ListInteger res new ArrayList();TreeNode dump new TreeNode(0);//建立一个临时结点dump.left root; //设置dump的左节点为rootTreeNode curr dump; //当前节点为dumpwhile (curr ! null) {if (curr.left null) { // 左子树为空则输出当前节点然后遍历右子树curr curr.right;} else {// 找到当前节点的前驱节点TreeNode prev curr.left;while (prev.right ! null prev.right ! curr) {prev prev.right;}if (prev.right null) {// 将前驱节点的右子树连接到当前节点prev.right curr;curr curr.left;} else {reverseAddNodes(curr.left, prev, res);// 前驱节点的右子树已经连接到当前节点断开连接输出当前节点然后遍历右子树prev.right null;curr curr.right;}}}return res;}private void reverseAddNodes(TreeNode begin, TreeNode end, ListInteger res) {reverseNodes(begin, end); //将begin到end的进行逆序连接TreeNode curr end;while (true) {//将逆序连接后端begin到end添加res.add(curr.val);if (curr begin)break;curr curr.right;}reverseNodes(end, begin);//恢复之前的连接状态}/*** 将begin到end的进行逆序连接** param begin* param end*/private void reverseNodes(TreeNode begin, TreeNode end) {TreeNode prev begin;TreeNode curr prev.right;TreeNode post;while (prev ! end) {post curr.right;curr.right prev;prev curr;curr post;}}
测试: public static void main(String[] args) {TreeNode root new TreeNode(1);root.left new TreeNode(2);root.left.right new TreeNode(5);root.left.right.right new TreeNode(7);root.right new TreeNode(3);root.left.left new TreeNode(4);root.left.left.left new TreeNode(6);System.out.println(postorderTraversal(root));}
还是这样一颗二叉树,输出如下: [6, 4, 7, 5, 2, 3, 1]
