Apakah algoritma traversal Java Morris dan aplikasinya dalam pokok binari?

1. Morris traversal

1. Apakah Morris traversal

Morris traversal ialah algoritma untuk binari tree traversal, yang boleh dilaksanakan tanpa menggunakan timbunan atau queue Order traversal. Kerumitan masa bagi algoritma ini ialah O(n) dan kerumitan ruang ialah O(1).

2. Idea asas

Idea asas Morris traversal adalah menggunakan penunjuk nod daun untuk menyimpan maklumat sementara untuk menjimatkan ruang. Khususnya, untuk nod yang sedang dilalui, jika ia mempunyai nod anak kiri, cari nod paling kanan dalam subpokok kiri, halakan nod anak kanannya ke nod semasa, dan kemudian kemas kini nod semasa ke nod anak kirinya. Jika ia tidak mempunyai anak kiri, keluarkan nilai nod semasa dan kemas kini nod semasa kepada anak kanannya. Ulangi langkah di atas sehingga pokok lengkap dilalui.

3. Kelebihan dan kekurangan Morris traversal

Kelebihan Morris traversal ialah kerumitan ruang adalah rendah O(1), tetapi kelemahannya ialah ia akan mengubah struktur pokok binari asal , jadi ia perlu dilalui Selepas selesai, pulihkan pokok binari. Selain itu, algoritma mungkin lebih perlahan sedikit daripada algoritma rekursif atau menggunakan tindanan.

4. Pengikatan pokok binari

Pengikatan pokok binari terutamanya menggunakan medan penunjuk nol dalam nod daun untuk menyimpan nod pendahulu atau seterusnya dalam susunan lintasan tertentu , dengan itu mencapai tujuan daripada pokok binari petunjuk

Sebagai contoh, hasil traversal tertib dalam rajah di bawah ditunjukkan di bawah Medan penunjuk nol ditunjuk mengikut traversal tertib

Pokok binari petunjuk berada di bawah Melukisnya di sebelah kiri menunjukkan bahawa nod kiri menghala kepadanya, dan melukisnya di sebelah kanan menunjukkan bahawa nod yang betul menunjuk kepada 7 , kemudian nod kiri 7 mata kepada 5, dan nod pengganti 7 ialah 1, kemudian nod 7 mata kanan kepada 1

Daripada ini, kita boleh membuat kesimpulan bahawa nod yang menunjuk ke nod semasa dalam traversal tertib pokok binari ialah subpokok kiri nod semasa Nod paling kanan, sebagai contoh, nod paling kanan nod kiri 2, yang menghala ke nod 1, ialah 7, dan nod paling kanan 4 nod kiri 4, yang menghala ke nod 2, ialah 2. Titik ini akan dilalui kemudian oleh Morris sangat penting

Pelaksanaan kod khusus adalah seperti berikut:

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;
    }
}

Tetapi apabila melaksanakan traversal Morris, tidak perlu memberi petunjuk pada nod kiri nod, hanya nod kanan nod Hanya melakukan petunjuk Sebab khusus dianalisis di bawah.

2

1. Analisis urutan pertengahan Morris traversal

Kami berkata di atas Semasa Morris traversal, kami hanya perlu mengetahui nod yang betul, yang diterangkan di sini Apabila kami melintasi pokok dalam-. perintah, seperti pokok seperti ini, kita langkah demi langkah nod.left datang ke nod 6 , kiri nod ini kosong, jadi kita mencetak nilai nod 6. Pada masa ini kita perlu kembali ke sebelumnya nod. Jika kita ingin melintasi rekursi tertib, kita perlu kembali ke timbunan sebelumnya, dan traversal Morris kita Ia adalah mustahil untuk kembali secara rekursif, jadi pada masa ini kita hanya perlu menunjukkan nod kanan 6. Pada masa ini , nod kanan 6 mata kepada 4, kita boleh kembali ke 4, mencetak nod 4, dan 4 juga merupakan petunjuk Mengembalikan 2, mencetak 2, dan kemudian pergi ke nod kanan 5 daripada 2. Nod kiri 5. kosong, jadi 5 dicetak, dan kemudian ia pergi ke nod kanan 7 daripada 5, dan nod kanan 7 dan 7 juga dicetak Selepas threading, masukkan nod kanan 7 sebagai 1, kemudian cetak 1, masukkan 3 nod dan cetak

Kerana sebaiknya jangan ubah struktur pokok, jadi apabila kita mencetak, kita akan mengulirkan Nod kanan nod ditetapkan kepada kosong

2. Idea ​​dalam urutan Morris traversal

Morris traversal menggunakan idea pokok binari petunjuk proses traversal, dengan itu mencapai kerumitan ruang O(1)

Pelaksanaan khusus adalah seperti berikut:

1 Mulakan nod semasa sebagai nod akar

2. Jika nod kiri nod semasa kosong, keluarkan nod semasa, dan kemudian melintasi subpokok kanan nod semasa, iaitu, 'curr=curr.right'

3 Jika nod semasa nod kiri nod tidak kosong, cari nod pendahulu nod semasa, iaitu nod paling kanan nod kiri nod semasa, direkodkan sebagai 'sebelumnya'

• jika' prev.right'' kosong, kemudian tuding pre.right ke nod curr, dan kemudian melintasi subpokok kiri nod semasa, iaitu, 'curr=curr.left'

• Jika' prev.right'' tidak kosong, menunjukkan bahawa subpokok kiri nod semasa telah dilalui, putuskan sambungan `prev.right`, iaitu, 'prev.left=null', keluarkan nod semasa , dan kemudian melintasi subpokok kanan Pokok nod semasa, iaitu `curr=curr.right`.

3 Pelaksanaan kod khusus

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;
    }
}

Ujian:

Ia masih merupakan pokok binari, outputnya adalah seperti berikut:

[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]

Atas ialah kandungan terperinci Apakah algoritma traversal Java Morris dan aplikasinya dalam pokok binari?. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!