Jadual Kandungan
参考链接
Rumah Java javaTutorial 详解java中二叉树的深度优先遍历

详解java中二叉树的深度优先遍历

Jun 28, 2020 am 09:42 AM
java Pokok binari

详解java中二叉树的深度优先遍历

这两天在做二叉树相关的算法题,做一点学习笔记。(连二叉树都不会?确实不熟练,平时工作也没有要去写二叉树相关的算法或者数据结构的场景。因为自己菜,所以更加要努力学!)

定义

先看下维基百科的解释:在计算机科学中,二叉树(英语:Binary tree)是每个节点最多只有两个分支(即不存在分支度大于2的节点)的树结构。通常分支被称作“左子树”或“右子树”。二叉树的分支具有左右次序,不能随意颠倒。

由于二叉树本身定义的特点,具有高度的局部重复性,所以在深度优先遍历二叉树时,通常采用递归的方式去实现,这样实现出来的代码非常简洁漂亮,也比较容易看懂。

深度优先遍历

一般我们深度优先遍历二叉树有三种最常见的顺序遍历:前序、中序、后序。

前序的遍历顺序为:访问根结点 -> 遍历左子树 -> 遍历右子树

中序的遍历顺序为:遍历左子树 -> 访问根结点 -> 遍历右子树

后序的遍历顺序为:遍历左子树 -> 遍历右子树 -> 访问根结点

注意这里的左右是整个子树,而不是一个结点,因为我们需要遍历整棵树,所以每次遍历都是按照这个顺序去执行,直到叶子结点。

举个例子,假如有如下二叉树:

0.jpg

前序遍历得到的序列就是 A - B - C - D - E

中序遍历得到的序列就是 B - A - D - C - E

后序遍历得到的序列就是 B - D - E - C - A

思路我们就用前序遍历来讲(非常不建议去人肉递归,至少我的脑子吃不消三层。。。):

第一层递归:

先访问根结点,所以输出根结点 A,然后遍历左子树(L1),再遍历右子树(R1);

第二层递归:

对于 L1,先访问根结点,所以输出此时的根结点 B,然后发现 B 的左右子树为空,结束递归;

对于 R1,先访问根结点,所以输出此时的根结点 C,然后遍历左子树(L2),再遍历右子树(R2);

第三层递归:

对于 L2,先访问根结点,所以输出此时的根结点 D,然后发现 D 的左右子树为空,结束递归;

对于 R2,先访问根结点,所以输出此时的根结点 E,然后发现 E 的左右子树为空,结束递归;

前中后序特征

根据前中后序的定义,其实我们不难发现有如下特征:

• 前序的第一个一定是 root 节点,后序的最后一个一定是 root 节点

• 每种排序的左子树和右子树分布都是有规律的

• 对于每一个子树都遵循上面两个规律的树

2.jpg

这些特征也就是定义中对顺序的表现。

各种推导

这边列举一下对于二叉树的遍历最基本的几个算法题:

• 给定二叉树得出其前/中/后序遍历的序列;

• 根据前序和中序推导后序(或者推导整颗二叉树);

• 根据后序和中序推导前序(或者推导整颗二叉树);

对于二叉树的遍历,前面也讲过,通常采用递归来做,对于递归,有模版可以直接套用:

public void recur(int level, int param) {
    
    // terminator
    if (level > MAX_LEVEL) {
        // process result
         return;   
    }
    
    // process current logic
    process(level, param);
    
    // drill down
    recur(level+1, newParam);
    
    // restore current status
}
Salin selepas log masuk

这个是我这两天看极客时间的算法训练营中超哥(覃超)讲到的比较实用的小技巧(这个模版对于新手特别好),遵循上面的三步骤(如果有局部变量需要释放或者额外处理则第四步去做)能比较有条理的写出递归代码。

这里拿根据前序和中序推导后序来举例:

先初始化两个序列:

int[] preSequence = {1, 2, 3, 4, 5, 6, 7, 8, 9};
int[] inSequence = {2, 3, 1, 6, 7, 8, 5, 9, 4};
Salin selepas log masuk

通过上面说到的几个特征,我们已经可以找到最小重复子问题了,每次递归

根据前序的第一个结点值去匹配中序中该结点值所在的索引 i,这样我们就能得到索引 i 的前后两部份分别对应左右子树,接着分别去遍历这两个左右子树,然后输出当前前序的第一个结点值,也就是根结点。

根据自顶向下的程序设计方法,我们可以先写出如下初始递归调用:

List<Integer> result = new ArrayList<>();
preAndInToPost(0, 0, preSequence.length, preSequence, inSequence, result);
Salin selepas log masuk

第一个参数表示前序序列的第一个元素索引;

第二个参数表示中序序列的第一个元素索引;

第三个参数表示序列长度;

第四个参数表示前序序列;

第五个参数表示后序序列;

第六个参数用于保存结果;

先来考虑终止条件是什么,也就是什么时候结束递归,当我们的根结点为空的时候终止,对应这里就是序列长度为零的时候。

if (length == 0) {
    return;
}
Salin selepas log masuk

接着考虑处理逻辑,也就是找到索引 i:

int i = 0;
while (inSequence[inIndex + i] != preSequence[preIndex]) {
    i++;
}
Salin selepas log masuk

然后开始向下递归:

preAndInToPost(preIndex + 1, inIndex, i, preSequence, inSequence, result);
preAndInToPost(preIndex + i + 1, inIndex + i + 1, length - i - 1, preSequence, inSequence, result);
result.add(preSequence[preIndex]);
Salin selepas log masuk

因为推导的是后序序列,所以顺序如上,添加根结点的操作是在最后的。前三个参数如何得出来的呢,我们走一下第一次遍历就可以得出来。

前序序列的第一个结点 1 在中序序列中的索引为 2,此时

左子树的中序系列起始索引为总序列的第 1 个索引,长度为 2;

左子树的前序序列起始索引为总序列的第 2 个索引,长度为 2;

右子树的中序系列起始索引为总序列的第 3 个索引,长度为 length - 3;

右子树的前序序列起始索引为总序列的第 3 个索引,长度为 length - 3;

完整代码如下:

/**
 * 根据前序和中序推导后序
 *
 * @param preIndex    前序索引
 * @param inIndex     中序索引
 * @param length      序列长度
 * @param preSequence 前序序列
 * @param inSequence  中序序列
 * @param result      结果序列
 */
private void preAndInToPost(int preIndex, int inIndex, int length, int[] preSequence, int[] inSequence, List<Integer> result) {
    if (length == 0) {
        return;
    }

    int i = 0;
    while (inSequence[inIndex + i] != preSequence[preIndex]) {
        i++;
    }

    preAndInToPost(preIndex + 1, inIndex, i, preSequence, inSequence, result);
    preAndInToPost(preIndex + i + 1, inIndex + i + 1, length - i - 1, preSequence, inSequence, result);
    result.add(preSequence[preIndex]);
}
Salin selepas log masuk

参考链接

• 维基百科 - 二叉树(https://zh.wikipedia.org/wiki/%E4%BA%8C%E5%8F%89%E6%A0%91)

推荐教程:《java教程

Atas ialah kandungan terperinci 详解java中二叉树的深度优先遍历. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!

Kenyataan Laman Web ini
Kandungan artikel ini disumbangkan secara sukarela oleh netizen, dan hak cipta adalah milik pengarang asal. Laman web ini tidak memikul tanggungjawab undang-undang yang sepadan. Jika anda menemui sebarang kandungan yang disyaki plagiarisme atau pelanggaran, sila hubungi admin@php.cn

Alat AI Hot

Undresser.AI Undress

Undresser.AI Undress

Apl berkuasa AI untuk mencipta foto bogel yang realistik

AI Clothes Remover

AI Clothes Remover

Alat AI dalam talian untuk mengeluarkan pakaian daripada foto.

Undress AI Tool

Undress AI Tool

Gambar buka pakaian secara percuma

Clothoff.io

Clothoff.io

Penyingkiran pakaian AI

AI Hentai Generator

AI Hentai Generator

Menjana ai hentai secara percuma.

Artikel Panas

R.E.P.O. Kristal tenaga dijelaskan dan apa yang mereka lakukan (kristal kuning)
2 minggu yang lalu By 尊渡假赌尊渡假赌尊渡假赌
Repo: Cara menghidupkan semula rakan sepasukan
1 bulan yang lalu By 尊渡假赌尊渡假赌尊渡假赌
Hello Kitty Island Adventure: Cara mendapatkan biji gergasi
4 minggu yang lalu By 尊渡假赌尊渡假赌尊渡假赌

Alat panas

Notepad++7.3.1

Notepad++7.3.1

Editor kod yang mudah digunakan dan percuma

SublimeText3 versi Cina

SublimeText3 versi Cina

Versi Cina, sangat mudah digunakan

Hantar Studio 13.0.1

Hantar Studio 13.0.1

Persekitaran pembangunan bersepadu PHP yang berkuasa

Dreamweaver CS6

Dreamweaver CS6

Alat pembangunan web visual

SublimeText3 versi Mac

SublimeText3 versi Mac

Perisian penyuntingan kod peringkat Tuhan (SublimeText3)

Akar Kuasa Dua di Jawa Akar Kuasa Dua di Jawa Aug 30, 2024 pm 04:26 PM

Panduan untuk Square Root di Java. Di sini kita membincangkan cara Square Root berfungsi di Java dengan contoh dan pelaksanaan kodnya masing-masing.

Nombor Sempurna di Jawa Nombor Sempurna di Jawa Aug 30, 2024 pm 04:28 PM

Panduan Nombor Sempurna di Jawa. Di sini kita membincangkan Definisi, Bagaimana untuk menyemak nombor Perfect dalam Java?, contoh dengan pelaksanaan kod.

Penjana Nombor Rawak di Jawa Penjana Nombor Rawak di Jawa Aug 30, 2024 pm 04:27 PM

Panduan untuk Penjana Nombor Rawak di Jawa. Di sini kita membincangkan Fungsi dalam Java dengan contoh dan dua Penjana berbeza dengan contoh lain.

Weka di Jawa Weka di Jawa Aug 30, 2024 pm 04:28 PM

Panduan untuk Weka di Jawa. Di sini kita membincangkan Pengenalan, cara menggunakan weka java, jenis platform, dan kelebihan dengan contoh.

Nombor Armstrong di Jawa Nombor Armstrong di Jawa Aug 30, 2024 pm 04:26 PM

Panduan untuk Nombor Armstrong di Jawa. Di sini kita membincangkan pengenalan kepada nombor Armstrong di java bersama-sama dengan beberapa kod.

Nombor Smith di Jawa Nombor Smith di Jawa Aug 30, 2024 pm 04:28 PM

Panduan untuk Nombor Smith di Jawa. Di sini kita membincangkan Definisi, Bagaimana untuk menyemak nombor smith di Jawa? contoh dengan pelaksanaan kod.

Soalan Temuduga Java Spring Soalan Temuduga Java Spring Aug 30, 2024 pm 04:29 PM

Dalam artikel ini, kami telah menyimpan Soalan Temuduga Spring Java yang paling banyak ditanya dengan jawapan terperinci mereka. Supaya anda boleh memecahkan temuduga.

Cuti atau kembali dari Java 8 Stream Foreach? Cuti atau kembali dari Java 8 Stream Foreach? Feb 07, 2025 pm 12:09 PM

Java 8 memperkenalkan API Stream, menyediakan cara yang kuat dan ekspresif untuk memproses koleksi data. Walau bagaimanapun, soalan biasa apabila menggunakan aliran adalah: bagaimana untuk memecahkan atau kembali dari operasi foreach? Gelung tradisional membolehkan gangguan awal atau pulangan, tetapi kaedah Foreach Stream tidak menyokong secara langsung kaedah ini. Artikel ini akan menerangkan sebab -sebab dan meneroka kaedah alternatif untuk melaksanakan penamatan pramatang dalam sistem pemprosesan aliran. Bacaan Lanjut: Penambahbaikan API Java Stream Memahami aliran aliran Kaedah Foreach adalah operasi terminal yang melakukan satu operasi pada setiap elemen dalam aliran. Niat reka bentuknya adalah

See all articles