二叉樹的實作和周遊

什麼是二叉樹

簡單了解為對于一個節點來說，最多擁有一個上級節點，同時最多具備左右兩個下級節點的資料結構。

由于很多排序算法都是基于二叉樹實作的，多叉樹也是二叉樹延伸過去的，是以二叉樹的建樹和周遊就顯得非常重要。

二叉樹建樹

一般情況是給你一個串，要求讓你以前序，中序，後序的方式建樹。那麼此時我們就需要首先了解三個概念：

前序周遊
中序周遊
後序周遊

我們來看看一棵二叉樹的結構：

/ <br /> 1 2

/ \ / <br /> 3 4 5 6

0就是整個二叉樹的根節點，1就是0這個節點的左子樹，2就是0這個節點的右子樹。有了這個知識，我們就可以了解前中後序周遊這個位置屬性就是指的根在哪個位置，前序周遊就是根在前，是以就是根左子樹右子樹的周遊方式；中序周遊就是根在中間，是以就是左子樹根右子樹的周遊方式；後序周遊就是根在最後，是以就是左子樹右子樹根的周遊方式。

周遊的方式有三種，對應的建樹方式有已知中序和前序建樹，已知中序和後序建樹，已知前序和後序建樹三種。

如果我們僅僅是想建構一棵二叉平衡樹，可以簡單使用某一種序列建樹。用僞代碼表示這三種周遊方式就是

前序周遊的方式建樹

new Tree(根節點);
buildTree(左子樹);
buildTree(右子樹);

中序周遊的方式建樹

buildTree(左子樹);
new Tree(根節點);
buildTree(右子樹);

後序周遊的方式建樹

buildTree(左子樹);
buildTree(右子樹);
new Tree(根節點);

前序建樹

我們現在以序列 1, 2, 3, 4, 5, 6, 7, 8, 9 為例，如果是前序建樹方式，那麼二叉樹的結構應該為：

實作也比較簡單

package com.chaojilaji.book.tree;

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

public class Handle {

    /**
     * 前序建樹
     *
     * @param input
     * @param index
     * @return
     */
    public static Tree buildTreePrologue(int[] input, int index) {
        // TODO: 2022/1/12 根節點就是目前index這個節點
        Tree tree = new Tree();
        tree.setValue(input[index]);
        // TODO: 2022/1/12 左右兩個節點分别為 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();
    }
}

執行結果如下：

{
    "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
        }
    }
}

中序建樹

以 1，2，3，4，5，6，7序列為例，如果是中序建樹的方式，那麼二叉樹的結構應該為

代碼如下：

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 {

    /**
     * 中序建樹
     * @param input
     * @param height
     * @param maxHeight
     * @return
     */
    public static Tree buildTree2(Queue<Integer> input, int height, int maxHeight) {
        // TODO: 2022/1/12 根節點就是目前index這個節點
        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();
    }
}

相對前序建樹以擴充的方式建立二叉樹，中序建樹由于無法很好的控制索引，是以這裡使用了一個隊列來存儲整個序列，同時需要算出以目前的節點數，算出建立一棵二叉平衡樹，最小的深度為多少。然後按照之前給出的僞代碼，按照左根右的方式指派和遞歸調用即可。

運作的結果如下：

{
    "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
        }
    }
}

後序建樹

有了中序周遊，其實後序周遊就非常簡單了，以序列1,2,3,4,5,6,7為例，建樹應該為

代碼如下：

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 {

    /**
     * 後序建樹
     *
     * @return
     */
    public static Tree buildTree3(Queue<Integer> input, int height, int maxHeight) {
        // TODO: 2022/1/12 根節點就是目前index這個節點
        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();
    }


}

通過分析三個建樹方法的代碼你可以發現，其實本質上，根指派代碼，與調用左右子樹建樹函數的擺放的位置不同，就早就了這三種不同的算法。

三種建樹方法對應的三種周遊方法本質差別也就是列印值語句與調用左右子樹列印值函數的擺放位置不同。如果舉一反三的話，我們可以很容易的得出二叉樹前中後序周遊的代碼。那麼，請你自己先嘗試一下。

二叉樹的周遊

根據建樹的經驗，知道，我們隻需要寫出一種周遊方法，那麼其他兩種周遊方式都有了。差別隻不過是換換列印語句的位置。

對于前序周遊，寫法如下：

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

那麼我們來做一個實驗，首先根據序列1,2,3,4,5,6,7利用前序周遊建構出一棵平衡二叉樹，然後列印出其前序中序後序周遊的順序。完整的代碼如下：

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 {


    /**
     * 前序建樹
     *
     * @param input
     * @param index
     * @return
     */
    public static Tree buildTreePrologue(int[] input, int index) {
        // TODO: 2022/1/12 根節點就是目前index這個節點
        Tree tree = new Tree();
        tree.setValue(input[index]);
        // TODO: 2022/1/12 左右兩個節點分别為 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;
    }

    /**
     * 中序建樹
     *
     * @param input
     * @param height
     * @param maxHeight
     * @return
     */
    public static Tree buildTree2(Queue<Integer> input, int height, int maxHeight) {
        // TODO: 2022/1/12 根節點就是目前index這個節點
        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;
    }

    /**
     * 後序建樹
     *
     * @return
     */
    public static Tree buildTree3(Queue<Integer> input, int height, int maxHeight) {
        // TODO: 2022/1/12 根節點就是目前index這個節點
        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();
    }
}

最終的結果如下：

二叉樹的實作和周遊

什麼是二叉樹

二叉樹建樹

前序建樹

中序建樹

後序建樹

二叉樹的周遊

繼續閱讀

[轉]ISUP信令的IAM消息詳細内容

CSMA/CD1． CSMA/CD的概述2． CSMA 的工作原理3． CSMA/CD控制規程及特點4． CSMA/CD協定5． CSMA/CD的優點6．結束語

極大似然法(ML)與最大期望法(EM)

[HTML5]自定義屬性 data-* 和 jQuery.data 詳解

七牛雲-C#SDK-上傳-前期準備

C++ 第十五周報告1--《冒泡法排序》

筆試面試題目：滑動視窗(二)

交通/城市相關的公開的資料集上學時整理的Xie et al., 2020收集的

資料結構與算法（27）——排序（二）

Dijkstra--簡易版（最短路徑）

GitHub連夜封殺！這份阿裡 10W 字内部 Java 字面試手冊到底有多強？

vue-cli簡介（中文翻譯）

Ajax發送和擷取json資料到Spring mvc 1.spring mvc後端2.web前段

Linux裝置模型（中）之上層容器

JSONObject包導入異常 java.lang.NoClassDefFoundErrorweb項目的導入包的問題

hdu7108哈希