Java Morris 순회 알고리즘과 이진 트리에서의 적용은 무엇입니까?
- PHPz앞으로
- 2023-05-10 15:13:121315검색
1. 모리스 순회
1. 모리스 순회란
모리스 순회는 스택이나 큐를 사용하지 않고 순차 순회를 구현할 수 있는 이진 트리 순회 알고리즘입니다. 이 알고리즘의 시간 복잡도는 O(n)이고 공간 복잡도는 O(1)입니다.
2. 기본 아이디어
모리스 탐색의 기본 아이디어는 리프 노드의 널 포인터를 사용하여 공간을 절약하기 위해 임시 정보를 저장하는 것입니다. 특히, 현재 순회하는 노드의 경우 왼쪽 자식 노드가 있는 경우 왼쪽 하위 트리에서 가장 오른쪽 노드를 찾고 오른쪽 자식 노드가 현재 노드를 가리킨 다음 현재 노드를 왼쪽 자식 노드로 업데이트합니다. 왼쪽 자식이 없으면 현재 노드의 값을 출력하고 현재 노드를 오른쪽 자식으로 업데이트합니다. 전체 트리를 탐색할 때까지 위 단계를 반복합니다.
3. 모리스 탐색의 장점과 단점
모리스 탐색의 장점은 공간복잡도가 낮다는 점 O(1)이나, 단점은 원래 이진 트리 구조를 변경하므로 이진 트리를 다음과 같이 만들어야 합니다. 순회 후 복원되었습니다. 또한 이 알고리즘은 재귀 또는 스택 사용 알고리즘보다 약간 느릴 수 있습니다.
4. 이진 트리의 단서
이진 트리의 스레딩은 주로 리프 노드의 널 포인터 필드를 사용하여 특정 순회 순서로 선행 노드 또는 후속 노드를 저장함으로써 단서 이진 트리의 목적을 달성합니다. 예를 들어, 아래 그림의 순회 결과는 순차 순회에 따라 널 포인터 필드가 단서가 됩니다.
단서가 있는 이진 트리를 왼쪽에 그린다는 것은 왼쪽이 아래에 있다는 의미입니다. 노드는 이를 가리키고 오른쪽에 그리는 것은 오른쪽을 의미합니다. 예를 들어 7의 선행 노드는 5, 왼쪽 노드 7은 5, 후속 노드 7은 1, 오른쪽 노드 7을 가리킵니다. 1
이로부터 우리는 다음과 같은 결론을 내릴 수 있습니다: 순차 순회 이진 트리의 현재 노드를 가리키는 노드는 현재 노드의 왼쪽 하위 트리의 가장 오른쪽 노드입니다. to 1은 1, 노드 2의 가장 오른쪽 노드는 7, 노드 2를 가리키는 노드는 2입니다. 왼쪽 노드 4의 가장 오른쪽 노드 4입니다. 이는 후속 Morris 탐색에서 매우 중요합니다
특정 코드가 구현됩니다.
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;
}
}그러나 Morris 순회를 구현할 때 노드의 왼쪽 노드 단서를 넣을 필요는 없으며 해당 노드의 오른쪽 노드만 단서하면 됩니다.
2. 에서. -order Morris traversal
1. 중간 순서 Morris traversal 분석
위에서 Morris traversal에 대해 이야기했습니다. 올바른 노드만 알아내면 여기서는 트리를 순서대로 순회하는 경우에 대해 설명하겠습니다. 이런 트리로 차근차근 node.left가 노드 6으로 오고, 이 노드의 왼쪽이 비어 있으므로 노드 6의 값을 출력합니다. 이때 이전 노드로 돌아가야 합니다. 순서대로 순회하려면 이전 스택으로 돌아가야 하고, 순회할 때는 Morris Recursive 반환이 불가능하므로 이때는 오른쪽 노드 6만 스레드하면 됩니다. 이때, 6의 오른쪽 노드가 4를 가리키면 4로 돌아가 노드 4를 인쇄하고 4도 스레드되어 2를 반환한 다음 2의 오른쪽 노드 5로 진행합니다. 5의 왼쪽 노드는 비어 있습니다. 이므로 5가 인쇄된 다음 5의 오른쪽 노드 7에 들어가서 7이 인쇄되고 오른쪽 노드 7도 인쇄됩니다. 스레딩의 경우 오른쪽 노드 7을 1로 입력한 다음 1을 인쇄하고 3을 입력합니다. node and print
트리의 구조는 바꾸지 않는 것이 가장 좋기 때문에 인쇄할 때 threaded node의 오른쪽 node를 공백으로 설정합니다.
2. -order Morris traversal
Morris traversal은 순회 과정에서 스택을 사용하지 않으므로 O(1)
의 공간 복잡도를 달성합니다.구체적인 구현은 다음과 같습니다.
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`입니다.
- 3. 특정 코드 구현
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;
}
}테스트:
이것은 여전히 이진 트리이며 출력은 다음과 같습니다.
三.前序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]
위 내용은 Java Morris 순회 알고리즘과 이진 트리에서의 적용은 무엇입니까?의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!