Java Morris トラバーサルアルゴリズムとそのバイナリツリーへの応用とは何ですか?-Java チュートリアル-php.cn

1. モリストラバーサル

1. モリストラバーサルとは

モリストラバーサルは、スタックやキューを使用せずに実装できるバイナリツリートラバーサルのアルゴリズムです。このアルゴリズムの時間計算量は O(n)、空間計算量は O(1) です。

2. 基本的な考え方

モリストラバーサルの基本的な考え方は、リーフノードの null ポインタを使用して一時的な情報を保存し、スペースを節約することです。具体的には、現在通過しているノードについて、左側の子ノードがある場合は、左側のサブツリーで右端のノードを見つけ、その右側の子ノードが現在のノードを指すようにしてから、現在のノードをその左側の子ノードに更新します。左の子がない場合は、現在のノードの値を出力し、現在のノードを右の子に更新します。ツリー全体を走査するまで、上記の手順を繰り返します。

3. モリストラバーサルの長所と短所

モリストラバーサルの利点は、空間計算量が O(1) であることですが、欠点は、元の二分木構造を変更してしまうことです。 , そのため、それをたどる必要があります。完了したら、バイナリツリーを復元します。さらに、このアルゴリズムは、再帰的アルゴリズムまたはスタックを使用するアルゴリズムよりもわずかに遅い場合があります。

4. バイナリツリーのスレッド化

バイナリツリーのスレッド化では、主にリーフノードの null ポインタフィールドを使用して、先行ノードまたは後続ノードを特定の走査順序で格納し、目的を達成します。手がかりバイナリツリーの

# たとえば、次の図の順序トラバーサル結果は以下に示されており、ヌルポインタフィールドは順序トラバーサルに従って手がかりになります。

Java Morris トラバーサルアルゴリズムとそのバイナリツリーへの応用とは何ですか?

# #手がかり付き二分木は下向きです。左に描くと左のノードが指すことを示し、右に描くと右のノードが指すことを示します。たとえば、7 の先行ノードは次のようになります。 5 の場合、7 の左側のノードは 5 を指し、7 の後継ノードは 1 で、7 の右側のノードは 1

Java Morris トラバーサルアルゴリズムとそのバイナリツリーへの応用とは何ですか?

これから、次のようになります。バイナリツリーの順序トラバーサルで現在のノードを指すノードは、現在のノードの左のサブツリーであると結論付けます。右端のノード (たとえば、ノード 1 を指す左ノード 2 の右端のノード) は次のようになります。 7、そしてノード 2 を指す左側のノード 4 の右端のノード 4 は 2 です。この点は後で 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;
    }
}

ログイン後にコピー

しかし、モリストラバーサルを実装する場合、ノードの左側のノードをスレッドする必要はなく、ノードの右側のノードのみが手掛かりを実行するだけです。具体的な理由は以下で分析されます。

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. インオーダーモリストラバーサルの考え方 Java Morris トラバーサルアルゴリズムとそのバイナリツリーへの応用とは何ですか?

モリストラバーサルは、手がかりバイナリツリーのアイデアを使用します。走査プロセスにより、O(1) の空間複雑度が達成されます。

具体的な実装は次のとおりです:

1. 現在のノードをルートノードとして初期化します

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 inorderTraversal(TreeNode root) {
        List 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;
    }
}

ログイン後にコピー

テスト:

これは依然としてバイナリツリーであり、出力は次のとおりです:

Java Morris トラバーサルアルゴリズムとそのバイナリツリーへの応用とは何ですか? [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`.

Java Morris トラバーサルアルゴリズムとそのバイナリツリーへの応用とは何ですか?

2.具体的代码实现

    public List preorderTraversal(TreeNode root) {
        List 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`.

Java Morris トラバーサルアルゴリズムとそのバイナリツリーへの応用とは何ですか?

2.具体的代码实现

    public List postorderTraversal(TreeNode root) {
        List 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 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));
    }

ログイン後にコピー

还是这样一颗二叉树,输出如下: