Java Morris トラバーサル アルゴリズムとそのバイナリ ツリーへの応用とは何ですか?
- PHPz転載
- 2023-05-10 15:13:121354ブラウズ
1. モリス トラバーサル
1. モリス トラバーサルとは
モリス トラバーサルは、スタックやキューを使用せずに実装できるバイナリ ツリー トラバーサルのアルゴリズムです。このアルゴリズムの時間計算量は O(n)、空間計算量は O(1) です。
2. 基本的な考え方
モリス トラバーサルの基本的な考え方は、リーフ ノードの null ポインタを使用して一時的な情報を保存し、スペースを節約することです。具体的には、現在通過しているノードについて、左側の子ノードがある場合は、左側のサブツリーで右端のノードを見つけ、その右側の子ノードが現在のノードを指すようにしてから、現在のノードをその左側の子ノードに更新します。左の子がない場合は、現在のノードの値を出力し、現在のノードを右の子に更新します。ツリー全体を走査するまで、上記の手順を繰り返します。
3. モリス トラバーサルの長所と短所
モリス トラバーサルの利点は、空間計算量が O(1) であることですが、欠点は、元の二分木構造を変更してしまうことです。 , そのため、それをたどる必要があります。完了したら、バイナリ ツリーを復元します。さらに、このアルゴリズムは、再帰的アルゴリズムまたはスタックを使用するアルゴリズムよりもわずかに遅い場合があります。
4. バイナリ ツリーのスレッド化
バイナリ ツリーのスレッド化では、主にリーフ ノードの null ポインタ フィールドを使用して、先行ノードまたは後続ノードを特定の走査順序で格納し、目的を達成します。手がかりバイナリ ツリーの
# たとえば、次の図の順序トラバーサル結果は以下に示されており、ヌル ポインタ フィールドは順序トラバーサルに従って手がかりになります。
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;
}
} しかし、モリス トラバーサルを実装する場合、ノードの左側のノードをスレッドする必要はなく、ノードの右側のノードのみが手掛かりを実行するだけです。具体的な理由は以下で分析されます。2. -次モリス トラバーサル1. 中次モリス トラバーサルの分析モリス トラバーサルでは、正しいノードを見つけるだけでよいと述べましたが、これについてはここで説明します。たとえば、このツリーを順番に実行すると、ノード 6 に段階的に到達します。このノードの左側は空であるため、ノード 6 の値を出力します。この時点で、次の値を返す必要があります。順序どおりに再帰的にトラバースしたい場合は、前のスタックに戻る必要があり、モリス トラバーサルでは再帰的に戻ることは不可能なので、現時点では 6 の正しいノードを知る必要があるだけです。このとき、6 の右ノードは 4 を指します。4 に戻り、ノード 4 を出力します。4 も手がかりです。2 を返し、2 を出力し、2 の右ノード 5 に進みます。左ノード5 の 5 は空なので 5 が出力され、次に 5 の右ノード 7 に進み、7 と 7 の右ノードも出力されます。スレッド化後、7 の右ノードに 1 を入力し、1 を出力します。 3 番目のノードを入力して出力します。 # ツリーの構造を変更しないことが最善であるため、出力するときは、ノードの右側のノードを空に設定します。
##2. インオーダーモリストラバーサルの考え方
2現在のノードの左側のノードが空の場合は、現在のノードを出力し、現在のノードの右側のサブツリー、つまり 'curr=curr.right'3 をトラバースします。ノードの左ノードが空でない場合は、現在のノードの先行ノード、つまり、「prev」
# として記録されている現在のノードの左ノードの右端のノードを見つけます。 ##if' 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; } }テスト:
これは依然としてバイナリ ツリーであり、出力は次のとおりです:
[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]
以上がJava Morris トラバーサル アルゴリズムとそのバイナリ ツリーへの応用とは何ですか?の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。