詳解Java?二叉樹(shù)的實(shí)現(xiàn)和遍歷

更新時(shí)間：2022年03月24日 09:21:31 作者：炒雞辣雞123

二叉樹(shù)可以簡(jiǎn)單理解為對(duì)于一個(gè)節(jié)點(diǎn)來(lái)說(shuō)，最多擁有一個(gè)上級(jí)節(jié)點(diǎn)，同時(shí)最多具備左右兩個(gè)下級(jí)節(jié)點(diǎn)的數(shù)據(jù)結(jié)構(gòu)。本文將詳細(xì)介紹一下Java中二叉樹(shù)的實(shí)現(xiàn)和遍歷，需要的可以參考一下

什么是二叉樹(shù)

簡(jiǎn)單理解為對(duì)于一個(gè)節(jié)點(diǎn)來(lái)說(shuō)，最多擁有一個(gè)上級(jí)節(jié)點(diǎn)，同時(shí)最多具備左右兩個(gè)下級(jí)節(jié)點(diǎn)的數(shù)據(jù)結(jié)構(gòu)。

由于很多排序算法都是基于二叉樹(shù)實(shí)現(xiàn)的，多叉樹(shù)也是二叉樹(shù)延伸過(guò)去的，所以二叉樹(shù)的建樹(shù)和遍歷就顯得非常重要。

二叉樹(shù)建樹(shù)

一般情況是給你一個(gè)串，要求讓你以前序，中序，后序的方式建樹(shù)。那么此時(shí)我們就需要首先了解三個(gè)概念：

前序遍歷
中序遍歷
后序遍歷

我們來(lái)看看一棵二叉樹(shù)的結(jié)構(gòu)：

1 2

3 4 5 6

0就是整個(gè)二叉樹(shù)的根節(jié)點(diǎn)，1就是0這個(gè)節(jié)點(diǎn)的左子樹(shù)，2就是0這個(gè)節(jié)點(diǎn)的右子樹(shù)。有了這個(gè)知識(shí)，我們就可以理解前中后序遍歷這個(gè)位置屬性就是指的根在哪個(gè)位置，前序遍歷就是根在前，所以就是根左子樹(shù)右子樹(shù)的遍歷方式；中序遍歷就是根在中間，所以就是左子樹(shù)根右子樹(shù)的遍歷方式；后序遍歷就是根在最后，所以就是左子樹(shù)右子樹(shù)根的遍歷方式。

遍歷的方式有三種，對(duì)應(yīng)的建樹(shù)方式有已知中序和前序建樹(shù)，已知中序和后序建樹(shù)，已知前序和后序建樹(shù)三種。

如果我們僅僅是想構(gòu)建一棵二叉平衡樹(shù)，可以簡(jiǎn)單使用某一種序列建樹(shù)。用偽代碼表示這三種遍歷方式就是

1.前序遍歷的方式建樹(shù)

new Tree(根節(jié)點(diǎn));
buildTree(左子樹(shù));
buildTree(右子樹(shù));

2.中序遍歷的方式建樹(shù)

buildTree(左子樹(shù));
new Tree(根節(jié)點(diǎn));
buildTree(右子樹(shù));

3.后序遍歷的方式建樹(shù)

buildTree(左子樹(shù));
buildTree(右子樹(shù));
new Tree(根節(jié)點(diǎn));

前序建樹(shù)

我們現(xiàn)在以序列 1, 2, 3, 4, 5, 6, 7, 8, 9 為例，如果是前序建樹(shù)方式，那么二叉樹(shù)的結(jié)構(gòu)應(yīng)該為：

實(shí)現(xiàn)也比較簡(jiǎn)單

package com.chaojilaji.book.tree;

import com.chaojilaji.auto.autocode.utils.Json;

public class Handle {

    /**
     * 前序建樹(shù)
     *
     * @param input
     * @param index
     * @return
     */
    public static Tree buildTreePrologue(int[] input, int index) {
        // TODO: 2022/1/12 根節(jié)點(diǎn)就是當(dāng)前index這個(gè)節(jié)點(diǎn)
        Tree tree = new Tree();
        tree.setValue(input[index]);
        // TODO: 2022/1/12 左右兩個(gè)節(jié)點(diǎn)分別為 2*index-1和2*index+1
        int[] children = new int[]{2 * index + 1, 2 * index + 2};
        if (children[0] < input.length) {
            tree.setLeftChild(buildTreePrologue(input, children[0]));
        }
        if (children[1] < input.length) {
            tree.setRightChild(buildTreePrologue(input, children[1]));
        }
        return tree;
    }


    public static void demo() {
        int[] a = new int[]{1, 2, 3, 4, 5, 6, 7, 8, 9};
        Tree tree = buildTreePrologue(a, 0);
        System.out.println(Json.toJson(tree));

    }

    public static void main(String[] args) {
        demo();
    }
}

執(zhí)行結(jié)果如下：

{
    "value": 1,
    "left_child": {
        "value": 2,
        "left_child": {
            "value": 4,
            "left_child": {
                "value": 8,
                "left_child": null,
                "right_child": null
            },
            "right_child": {
                "value": 9,
                "left_child": null,
                "right_child": null
            }
        },
        "right_child": {
            "value": 5,
            "left_child": null,
            "right_child": null
        }
    },
    "right_child": {
        "value": 3,
        "left_child": {
            "value": 6,
            "left_child": null,
            "right_child": null
        },
        "right_child": {
            "value": 7,
            "left_child": null,
            "right_child": null
        }
    }
}

中序建樹(shù)

以 1，2，3，4，5，6，7序列為例，如果是中序建樹(shù)的方式，那么二叉樹(shù)的結(jié)構(gòu)應(yīng)該為

代碼如下：

package com.chaojilaji.book.tree;

import com.chaojilaji.auto.autocode.utils.Json;
import com.chaojilaji.auto.autocode.utils.MathUtils;

import java.util.LinkedList;
import java.util.Objects;
import java.util.Queue;

public class Handle {

    /**
     * 中序建樹(shù)
     * @param input
     * @param height
     * @param maxHeight
     * @return
     */
    public static Tree buildTree2(Queue<Integer> input, int height, int maxHeight) {
        // TODO: 2022/1/12 根節(jié)點(diǎn)就是當(dāng)前index這個(gè)節(jié)點(diǎn)
        Tree tree = new Tree();

        if (height < maxHeight) {
            tree.setLeftChild(buildTree2(input, height + 1, maxHeight));
        }
        if (!input.isEmpty()) {
            tree.setValue(input.poll());
        }
        if (height < maxHeight) {
            tree.setRightChild(buildTree2(input, height + 1, maxHeight));
        }
        return tree;
    }

    public static void demo() {
        int[] a = new int[]{1, 2, 3, 4, 5, 6, 7};
        Queue<Integer> queue = new LinkedList<>();
        for (int i = 0; i < a.length; i++) {
            queue.add(a[i]);
        }
        Integer maxCeng = new Double(Math.ceil(MathUtils.getLogAN(2, a.length + 1))).intValue();
        System.out.println(Json.toJson(buildTree2(queue, 1, maxCeng)));
    }

    public static void main(String[] args) {
        demo();
    }
}

相對(duì)前序建樹(shù)以擴(kuò)展的方式建立二叉樹(shù)，中序建樹(shù)由于無(wú)法很好的控制索引，所以這里使用了一個(gè)隊(duì)列來(lái)存儲(chǔ)整個(gè)序列，同時(shí)需要算出以當(dāng)前的節(jié)點(diǎn)數(shù)，算出建立一棵二叉平衡樹(shù)，最小的深度為多少。然后按照之前給出的偽代碼，按照左根右的方式賦值和遞歸調(diào)用即可。
運(yùn)行的結(jié)果如下：

{
    "value": 4,
    "left_child": {
        "value": 2,
        "left_child": {
            "value": 1,
            "left_child": null,
            "right_child": null
        },
        "right_child": {
            "value": 3,
            "left_child": null,
            "right_child": null
        }
    },
    "right_child": {
        "value": 6,
        "left_child": {
            "value": 5,
            "left_child": null,
            "right_child": null
        },
        "right_child": {
            "value": 7,
            "left_child": null,
            "right_child": null
        }
    }
}

后序建樹(shù)

有了中序遍歷，其實(shí)后序遍歷就非常簡(jiǎn)單了，以序列1,2,3,4,5,6,7為例，建樹(shù)應(yīng)該為

代碼如下：

package com.chaojilaji.book.tree;

import com.chaojilaji.auto.autocode.utils.Json;
import com.chaojilaji.auto.autocode.utils.MathUtils;

import java.util.LinkedList;
import java.util.Objects;
import java.util.Queue;

public class Handle {

    /**
     * 后序建樹(shù)
     *
     * @return
     */
    public static Tree buildTree3(Queue<Integer> input, int height, int maxHeight) {
        // TODO: 2022/1/12 根節(jié)點(diǎn)就是當(dāng)前index這個(gè)節(jié)點(diǎn)
        Tree tree = new Tree();

        if (height < maxHeight) {
            tree.setLeftChild(buildTree3(input, height + 1, maxHeight));
        }

        if (height < maxHeight) {
            tree.setRightChild(buildTree3(input, height + 1, maxHeight));
        }
        if (!input.isEmpty()) {
            tree.setValue(input.poll());
        }
        return tree;
    }

    public static void demo() {
        int[] a = new int[]{1, 2, 3, 4, 5, 6, 7};
        Queue<Integer> queue = new LinkedList<>();
        for (int i = 0; i < a.length; i++) {
            queue.add(a[i]);
        }
        Integer maxCeng = new Double(Math.ceil(MathUtils.getLogAN(2, a.length + 1))).intValue();                                                     
        System.out.println(Json.toJson(buildTree3(queue, 1, maxCeng)));

    }

    public static void main(String[] args) {
        demo();
    }


}

通過(guò)分析三個(gè)建樹(shù)方法的代碼你可以發(fā)現(xiàn)，其實(shí)本質(zhì)上，根賦值代碼，與調(diào)用左右子樹(shù)建樹(shù)函數(shù)的擺放的位置不同，就早就了這三種不同的算法。

三種建樹(shù)方法對(duì)應(yīng)的三種遍歷方法本質(zhì)區(qū)別也就是打印值語(yǔ)句與調(diào)用左右子樹(shù)打印值函數(shù)的擺放位置不同。如果舉一反三的話，我們可以很容易的得出二叉樹(shù)前中后序遍歷的代碼。那么，請(qǐng)你自己先嘗試一下。

二叉樹(shù)的遍歷

根據(jù)建樹(shù)的經(jīng)驗(yàn)，知道，我們只需要寫(xiě)出一種遍歷方法，那么其他兩種遍歷方式都有了。區(qū)別只不過(guò)是換換打印語(yǔ)句的位置。
對(duì)于前序遍歷，寫(xiě)法如下：

public static void print1(Tree tree) {
    if (Objects.isNull(tree)) return;
    if (Objects.nonNull(tree.getValue())) {
        System.out.print(tree.getValue());
    }
    if (Objects.nonNull(tree.getLeftChild())) {
        print1(tree.getLeftChild());
    }
    if (Objects.nonNull(tree.getRightChild())) {
        print1(tree.getRightChild());
    }
}

那么我們來(lái)做一個(gè)實(shí)驗(yàn)，首先根據(jù)序列1,2,3,4,5,6,7利用前序遍歷構(gòu)建出一棵平衡二叉樹(shù)，然后打印出其前序中序后序遍歷的順序。完整的代碼如下：

package com.chaojilaji.book.tree;

import com.chaojilaji.auto.autocode.utils.Json;
import com.chaojilaji.auto.autocode.utils.MathUtils;

import java.util.LinkedList;
import java.util.Objects;
import java.util.Queue;

public class Handle {


    /**
     * 前序建樹(shù)
     *
     * @param input
     * @param index
     * @return
     */
    public static Tree buildTreePrologue(int[] input, int index) {
        // TODO: 2022/1/12 根節(jié)點(diǎn)就是當(dāng)前index這個(gè)節(jié)點(diǎn)
        Tree tree = new Tree();
        tree.setValue(input[index]);
        // TODO: 2022/1/12 左右兩個(gè)節(jié)點(diǎn)分別為 2*index-1和2*index+1
        int[] children = new int[]{2 * index + 1, 2 * index + 2};
        if (children[0] < input.length) {
            tree.setLeftChild(buildTreePrologue(input, children[0]));
        }
        if (children[1] < input.length) {
            tree.setRightChild(buildTreePrologue(input, children[1]));
        }
        return tree;
    }

    /**
     * 中序建樹(shù)
     *
     * @param input
     * @param height
     * @param maxHeight
     * @return
     */
    public static Tree buildTree2(Queue<Integer> input, int height, int maxHeight) {
        // TODO: 2022/1/12 根節(jié)點(diǎn)就是當(dāng)前index這個(gè)節(jié)點(diǎn)
        Tree tree = new Tree();

        if (height < maxHeight) {
            tree.setLeftChild(buildTree2(input, height + 1, maxHeight));
        }
        if (!input.isEmpty()) {
            tree.setValue(input.poll());
        }
        if (height < maxHeight) {
            tree.setRightChild(buildTree2(input, height + 1, maxHeight));
        }
        return tree;
    }

    /**
     * 后序建樹(shù)
     *
     * @return
     */
    public static Tree buildTree3(Queue<Integer> input, int height, int maxHeight) {
        // TODO: 2022/1/12 根節(jié)點(diǎn)就是當(dāng)前index這個(gè)節(jié)點(diǎn)
        Tree tree = new Tree();

        if (height < maxHeight) {
            tree.setLeftChild(buildTree3(input, height + 1, maxHeight));
        }

        if (height < maxHeight) {
            tree.setRightChild(buildTree3(input, height + 1, maxHeight));
        }
        if (!input.isEmpty()) {
            tree.setValue(input.poll());
        }
        return tree;
    }

    public static void print1(Tree tree) {
        if (Objects.isNull(tree)) return;
        if (Objects.nonNull(tree.getValue())) {
            System.out.print(tree.getValue());
        }
        if (Objects.nonNull(tree.getLeftChild())) {
            print1(tree.getLeftChild());
        }
        if (Objects.nonNull(tree.getRightChild())) {
            print1(tree.getRightChild());
        }
    }

    public static void print2(Tree tree) {
        if (Objects.isNull(tree)) return;
        if (Objects.nonNull(tree.getLeftChild())) {
            print2(tree.getLeftChild());
        }
        if (Objects.nonNull(tree.getValue())) {
            System.out.print(tree.getValue());
        }
        if (Objects.nonNull(tree.getRightChild())) {
            print2(tree.getRightChild());
        }
    }

    public static void print3(Tree tree) {
        if (Objects.isNull(tree)) return;
        if (Objects.nonNull(tree.getLeftChild())) {
            print3(tree.getLeftChild());
        }
        if (Objects.nonNull(tree.getRightChild())) {
            print3(tree.getRightChild());
        }
        if (Objects.nonNull(tree.getValue())) {
            System.out.print(tree.getValue());
        }
    }

    public static void demoPrint() {
        int[] a = new int[]{1, 2, 3, 4, 5, 6, 7};
        Tree tree = buildTreePrologue(a, 0);
        print1(tree);
        System.out.println();
        print2(tree);
        System.out.println();
        print3(tree);
    }

    public static void main(String[] args) {
        demoPrint();
    }
}

最終的結(jié)果如下：