Qu'est-ce que l'algorithme de traversée Java Morris et son application dans les arbres binaires ?
- PHPzavant
- 2023-05-10 15:13:121354parcourir
1. Morris traversal
1. Qu'est-ce que Morris traversal
Morris traversal est un algorithme de traversée d'arbre binaire, qui peut être utilisé sans utiliser de pile ou de file d'attente. Afin de réaliser un parcours dans l'ordre. La complexité temporelle de cet algorithme est O(n) et la complexité spatiale est O(1).
2. Idée de base
L'idée de base du parcours Morris est d'utiliser le pointeur nul du nœud feuille pour stocker des informations temporaires afin d'économiser de l'espace. Plus précisément, pour le nœud actuellement parcouru, s'il a un nœud enfant gauche, recherchez le nœud le plus à droite dans le sous-arbre gauche, pointez son nœud enfant droit vers le nœud actuel, puis mettez à jour le nœud actuel vers son nœud enfant gauche. S'il n'a pas d'enfant gauche, affichez la valeur du nœud actuel et mettez à jour le nœud actuel avec son enfant droit. Répétez les étapes ci-dessus jusqu'à ce que l'arborescence complète soit parcourue.
3. Avantages et inconvénients du parcours de Morris
L'avantage du parcours de Morris est que la complexité spatiale est faible en O(1), mais son inconvénient est qu'il modifiera le structure arborescente binaire d'origine. Par conséquent, il est nécessaire de restaurer l'arborescence binaire après l'avoir parcourue. De plus, l'algorithme peut être légèrement plus lent que les algorithmes récursifs ou utilisant la pile.
4. Threading d'arbres binaires
Le threading d'arbres binaires utilise principalement le champ de pointeur nul dans les nœuds feuilles pour stocker les prédécesseurs dans un certain ordre de parcours ou les nœuds suivants, atteignant ainsi l'objectif de l'arbre binaire d'indices
Par exemple, les résultats du parcours dans l'ordre dans la figure ci-dessous sont présentés ci-dessous, et le domaine du pointeur nul est indice selon le parcours dans l'ordre#🎜 🎜#
De cela, nous pouvons conclure que : parcours dans l'ordre d'un arbre binaire Le nœud pointant vers le nœud actuel est le nœud le plus à droite du sous-arbre gauche du nœud actuel. le nœud pointant vers 1 est le nœud gauche de 1, le nœud le plus à droite du nœud 2 est 7 et le nœud pointant vers le nœud 2 est le nœud gauche de 2. Le nœud le plus à droite 4 du nœud 4. Ceci est très important dans le Morris suivant traversal
L'implémentation spécifique du code est la suivante :
public class InorderThreadedBinaryTree {
private ThreadTreeNode pre = null;
public void threadedNodes(ThreadTreeNode node) {
//如果node==null，不能线索化
if (node == null) {
return;
}
//1、先线索化左子树
threadedNodes(node.left);
//2、线索化当前结点
//处理当前结点的前驱结点
//以8为例来理解
//8结点的.left = null，8结点的.leftType = 1
if (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;
}
}Mais lors de l'implémentation de la traversée de Morris, il n'est pas nécessaire de threader le nœud gauche du nœud, seulement le nœud droit de le nœud est fileté. Les raisons spécifiques sont analysées ci-dessous
2. Traversée de Morris dans l'ordre#🎜 🎜#
1. 🎜#Nous avons dit ci-dessus que seul le bon nœud doit être indiqué lors du parcours de Morris. Voici une explication pour vous lorsque nous effectuons un parcours dans l'ordre. Lors de la construction d'un arbre, par exemple, c'est un arbre comme celui-ci. par étape, node.left arrive au nœud 6. La gauche de ce nœud est vide, nous imprimons donc la valeur du nœud 6. A ce moment, nous devons revenir Si nous voulons parcourir le nœud précédent de manière récursive dans l'ordre, nous avons besoin pour revenir à la pile précédente, cependant, nous ne pouvons pas revenir récursivement pendant le parcours de Morris, donc pour le moment, nous n'avons besoin que de threader le nœud droit de 6. À ce moment, la droite de 6 pointe vers 4, nous pouvons revenir à 4, imprimer le nœud 4, 4 est également renvoyé à 2, imprimer 2, puis passer au nœud droit de 2, 5 et le nœud gauche de 5. est vide, donc imprimer 5, puis entrer le nœud droit 7 sur 5 , imprimez 7, le nœud droit de 7 est également indiqué, entrez le nœud droit de 7 comme 1, puis imprimez 1, entrez le nœud 3 et imprimez Parce qu'il est préférable de ne pas changer la structure de l'arbre, donc lors de l'impression, nous définissons le nœud droit du nœud fileté sur vide
2 L'idée dein-. order Morris traversal
Morris traversal utilise l'idée d'un arbre binaire d'indices La pile n'est pas utilisée pendant le processus de traversée, obtenant ainsi une complexité spatiale de O(1)
.
- Si 'prev.right'' n'est pas vide, indiquant que le sous-arbre gauche du nœud actuel a été traversé, déconnectez `prev.right`, c'est-à-dire 'prev.left=null', affichez le nœud actuel, puis parcourez le sous-arbre droit du sous-arbre du nœud actuel, à savoir `curr=curr.right`.
- 3 Implémentation de code spécifique
public class Morris { /** * 将当前根结点中序遍历的结果存储到list集合中 * @param root 根结点 * @return 中序遍历的结合 */ public List<Integer> inorderTraversal(TreeNode root) { List<Integer> 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; } }.Test :
# 🎜🎜#
est toujours un tel arbre binaire, le résultat est le suivant :
#🎜🎜 #[6, 4, 2, 5, 7, 1, 3]
三.前序Morris遍历
1.前序Morris遍历的思路
前序和中序的遍历很想,只不过在打印(收集结点信息的时候不同),中序遍历是在当前结点的左节点为空(curr.left==null),或者当前结点已经被线索化(prev.right==curr)的时候进行打印,仔细观察前序遍历的过程,我们通过修改打印的顺序即可.前序遍历是在当前结点的左节点为空(curr.left==null),或者当前结点没有被线索化(prev.right==null)的时候进行打印
具体的思路如下:
1.初始化当前的结点为根结点
2.若当前的结点的左节点为空,则输出当前结点,然后遍历当前结点的右子树,即'curr=curr.right'
3.若当前结点的左节点不为空,则找到当前结点的前驱节点,即当前结点左节点的最右侧结点,记为'prev'
如果'prev.right''为空,输出当前节点,然后将pre.right指向curr结点,然后遍历当前结点的左子树,即'curr=curr.left'
如果'prev.right''不为空,说明已经遍历完了当前节点的左子树,断开 `prev.right` 的连接,即'prev.left=null',然后遍历当前节点的右子树,即 `curr=curr.right`.
2.具体的代码实现
public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> 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.若当前的结点的左节点为空,则输出当前结点,然后遍历当前结点的右子树,即'curr=curr.right'
3.若当前结点的左节点不为空,则找到当前结点的前驱节点,即当前结点左节点的最右侧结点,记为'prev'
如果'prev.right''为空,然后将pre.right指向curr结点,然后遍历当前结点的左子树,即'curr=curr.left'
如果'prev.right''不为空,此时进行逆序存储,说明已经遍历完了当前节点的左子树,断开 `prev.right` 的连接,即'prev.left=null',然后遍历当前节点的右子树,即 `curr=curr.right`.
2.具体的代码实现
public List<Integer> postorderTraversal(TreeNode root) {
List<Integer> res = new ArrayList<>();
TreeNode dump = new TreeNode(0);//建立一个临时结点
dump.left = root; //设置dump的左节点为root
TreeNode curr = dump; //当前节点为dump
while (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, List<Integer> 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]
Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!