Java 中用于先序遍历的 Morris 遍历

2024 年 9 月 10 日 | 阅读 3 分钟

在本节中，我们将学习Java 中的莫里斯前序遍历。在莫里斯遍历中，我们无需递归或堆栈即可完成树的遍历。莫里斯遍历基于线索二叉树。

莫里斯前序遍历算法

以下是莫里斯前序遍历的算法，它几乎与莫里斯中序遍历相似。

如果左子节点为空，则显示当前节点的数据，然后移动到右子节点。
否则，请确保中序前驱节点的右子节点指向当前节点。
出现两种情况
1. 如果当前节点被中序前驱节点的右子节点指向，则将右子节点设置为 NULL，然后移动到当前节点的右子节点。
2. 如果右子节点为空，则将其设置为当前节点。显示当前节点的数据，然后移动到当前节点的左子节点。
重复此过程，直到当前节点不等于 NULL。

实施

让我们看看使用上述算法实现的莫里斯前序遍历。

文件名： BTree1.java

// a class for representing the 
// nodes of a binary tree
class BTreeNode 
{
int val; // for storing value of the node
// for referring to the left and right nodes
// lt for left and rt for right
BTreeNode lt, rt; 
// constructor of the class BTreeNode
BTreeNode(int item)
{
// initializing the nodes
val = item;
lt = rt = null;
}
}
public class BTree1 
{
// rt is the root node
BTreeNode rt;
// The method morrisTrvrslPreorder() is used for traversing the
// binary tree without the help of recursion
// and without the help of stack 
void morrisTrvrslPreorder(BTreeNode r) 
{
// loop used for traversing
while (r != null) 
{
// If the left child is equal to null, then display
// the data of the current node and move to
// the right child.
if (r.lt == null) 
{
System.out.print(r.val + " ");
r = r.rt;
} 
else 
{
// Finding the inorder predecessor
// curr is the current node
BTreeNode curr = r.lt;
while (curr.rt != null && curr.rt != r) 
{
curr = curr.rt;
}
// When this node is already being pointed out 
// by the right child of the inorder predecessor
if (curr.rt == r) 
{
curr.rt = null;
r = r.rt;
}
// If the right child does not point to the node, then display
// the value of the node and make the right child point towards the node
else 
{
System.out.print(r.val + " ");
curr.rt = r;
r = r.lt;
}
}
}
}
// main method
public static void main(String argvs[])
{
// The binary tree constructed in this code
//                        6
//                      /   \
//	        8	 9
//                  /   \       \
//                1      4      7
//                       /
//                    5
// creating an object of the class BTree1
BTree1 tree = new BTree1();
// creating the root node
tree.rt = new BTreeNode(6);
// creating the remaining nodes of the binary tree
tree.rt.lt = new BTreeNode(8);
tree.rt.rt = new BTreeNode(9);
tree.rt.lt.lt = new BTreeNode(1);
tree.rt.lt.rt = new BTreeNode(4);
tree.rt.rt.rt = new BTreeNode(7);
tree.rt.lt.rt.lt = new BTreeNode(5);
// The print statement
System.out.print("The inorder traversal of the binary tree is: \n" );
tree.morrisTrvrslPreorder(tree.rt);
}
}

输出

The preorder traversal of the binary tree is: 
6 8 1 4 5 9 7

时间复杂度： 由于该算法与莫里斯中序遍历相似。因此，上述程序的总时间复杂度为 O(n)。

注意：在许多地方，人们说递归方法进行前序遍历不消耗任何空间。但这并不完全正确。在递归中，即使我们没有显式提供堆栈，也会使用堆栈。

莫里斯遍历可以在二叉树内部修改的帮助下工作。如果没有内部修改，莫里斯遍历将无法工作。因此，如果不允许内部修改，则应考虑莫里斯遍历。

下一主题Java 中的包命名约定

Java 中用于先序遍历的 Morris 遍历

莫里斯前序遍历算法

实施

注意：在许多地方，人们说递归方法进行前序遍历不消耗任何空间。但这并不完全正确。在递归中，即使我们没有显式提供堆栈，也会使用堆栈。

联系信息

关注我们

教程

面试题

在线编译器

Python

Java

.Net Framework

AI, ML and Data Science

Cloud Technology

B.Tech and MCA

Web Technology

PHP

Software Testing

Technical Interview

Java Interview

Python

Web Interview

Database Interview

B.Tech / MCA

Important Interview

Software Testing Interview

Company Interviews

Online Compilers

Multiple Choice Questions

Java Conversion

Java Misc

Java 中用于先序遍历的 Morris 遍历

莫里斯前序遍历算法

实施

注意：在许多地方，人们说递归方法进行前序遍历不消耗任何空间。但这并不完全正确。在递归中，即使我们没有显式提供堆栈，也会使用堆栈。

相关帖子

Java Program to Count All Possible Paths Between Two Vertices

ArgoUML Java 反向工程

检查给定字符串是否包含所有数字（Java）

用 Java 构建科学计算器

Java 中构造函数和方法的区别

Java 中的四面体数

How to Create Package in Java

Java 中的离零最远程序

LCM of Two Numbers in Java

Java 中反转带特殊字符的字符串

订阅 Tpoint Tech

联系信息

关注我们

教程

面试题

在线编译器