二叉樹的周遊和重建

二叉樹是樹的一種，由一個根節點和兩棵互不相交左右子樹的二叉樹組成。

二叉樹有很多性質，就不一一舉例了~

先來說一下最簡單的關于二叉樹常用的3種周遊方式。層序周遊就略過了~

前序周遊：根節點，左節點，右節點。

結果就是：ABDGHCEIF

二叉樹的周遊和重建

中序周遊：左節點，根節點，右節點。

結果就是：GDHBAEICF

二叉樹的周遊和重建

後序周遊：左節點，右節點，根節點。

結果就是：GHDBIEFCA

二叉樹的周遊和重建

概念就說到這裡，開始敲代碼~

首先，建立數節點。

public class TreeNode {

    private int index;      

    private String data;           //資料域 

    private TreeNode leftChild;    //左子樹

    private TreeNode rightChild;   //右子樹

    public int getIndex() {
        return index;
    }


    public void setIndex(int index) {
        this.index = index;
    }


    public String getData() {
        return data;
    }


    public void setData(String data) {
        this.data = data;
    }

     public TreeNodeString(String data) {
        this.data = data;
    }

    public TreeNode(int index, String data) {
        this.index = index;
        this.data = data;
        this.leftChild = null;
        this.rightChild = null;
    }
}

然後我們來建構一個二叉樹：

/**
 * 建構二叉樹
 *                  A
 *              B       C
 *          D       E      F
 *      G       H     I
 */
public void createBinaryTree() {
    //我們需要一個根節點
    root = new TreeNode(1, "A");   
    TreeNode treeNodeB = new TreeNode(2, "B");
    TreeNode treeNodeC = new TreeNode(3, "C");
    TreeNode treeNodeD = new TreeNode(4, "D");
    TreeNode treeNodeE = new TreeNode(5, "E");
    TreeNode treeNodeF = new TreeNode(6, "F");
    TreeNode treeNodeG = new TreeNode(7, "G");
    TreeNode treeNodeH = new TreeNode(8, "H");
    TreeNode treeNodeI = new TreeNode(9, "I");
    //分别對應節點的左右子樹。
    root.leftChild = treeNodeB;
    root.rightChild = treeNodeC;
    treeNodeB.leftChild = treeNodeD;
    treeNodeD.leftChild = treeNodeG;
    treeNodeD.rightChild = treeNodeH;
    treeNodeC.leftChild = treeNodeE;
    treeNodeC.rightChild = treeNodeF;
    treeNodeE.rightChild = treeNodeI;

}

二叉樹建立完成之後，

開始周遊，首先使用循環的方式進行前序周遊，循環需要借助棧來實作周遊。

/**
 *  前序周遊  非遞歸
 * @param treeNode
 */
public void nonRecOrder(TreeNode treeNode){
    if(treeNode == null){
        return;
    }
    Stack<TreeNode> stack = new Stack<>();
    //首先把根節點放入棧中
    stack.push(treeNode);
    while (!stack.isEmpty()){
        //彈出根結點
        TreeNode node = stack.pop();
        System.out.println("data:" + node.data);
        //如果有右子結點，則壓入節點
        if(node.rightChild!=null){
            //如果左節點有值，則右節點在棧底，最後才會輸出
            stack.push(node.rightChild);
        }
        //如果有右左結點，則壓入節點
        if(node.leftChild!=null){
            //下次循環把左子節點當根節點繼續彈出
            stack.push(node.leftChild);
        }
    }
}

接着來介紹使用遞歸的方式進行周遊

/**
 *  前序周遊  遞歸
 * @param treeNode
 */
public void preOrder(TreeNode treeNode){
    if(treeNode == null){
        return;
    }else{
        //首先把每個節點當成根節點輸出
        System.out.println("data:" + treeNode.data);
        //如果左節點有值，則輸出左節點
        preOrder(treeNode.leftChild);
        ///如果右節點有值，輸出右節點。
        preOrder(treeNode.rightChild);
    }
}
/**
 *  中序周遊  遞歸
 * @param treeNode
 */
public void midOrder(TreeNode treeNode){
    if(treeNode == null){
        return;
    }else{
        //遞歸左子樹，直到左節點為null，return。
        midOrder(treeNode.leftChild);
        //輸出節點。
        System.out.println("data:" + treeNode.data);
        //遞歸右子樹
        midOrder(treeNode.rightChild);
    }
}
/**
 *  後序周遊  遞歸
 * @param treeNode
 */
public void postOrder(TreeNode treeNode){
    if(treeNode == null){
        return;
    }else{
         //遞歸左子樹，直到左節點為null，return。
        postOrder(treeNode.leftChild);
         //遞歸右子樹，直到左節點為null，return。
        postOrder(treeNode.rightChild);
        //輸出節點
        System.out.println("data:" + treeNode.data);
    }
}

二叉樹的周遊了解了還是比較簡單的，下面來看一下二叉樹的重建。

已知前序周遊結果：ABDGHCEIF 中序周遊結果：GDHBAEICF，求二叉樹。

根據前序周遊的特性，可以知道A是根節點，這種在中序中可以得出 A節點左邊的就是左節點，右邊的就是右節點。這個規律可以使用遞歸

二叉樹的周遊和重建

下面就來看看重建二叉樹的遞歸代碼，具體的在代碼中都有注釋

/**
 * 已知前序和中序
 * @param pre       前序集合
 * @param startPre  前序集合起始點
 * @param endPre    前序集合總長度
 * @param in        中序集合
 * @param startIn   中序集合起始點
 * @param endIn     中序集合總長度
 * @return
 */
public TreeNodeString resetBinaryTreeString(String[] pre ,int startPre,int  endPre,String[] in,int startIn,int endIn){
    //如果開始大于結束，就說明這個樹已經結束了
    if(startPre > endPre || startIn > endIn) {
        return null;
    }
    //把前序的頭節點放入樹中當根節點
    TreeNodeString node = new TreeNodeString(pre[startPre]);
    //周遊中序的所有節點
    for (int i = startIn; i <= endIn; i++) {
        //找到根節點在中序中的位置
        if(pre[startPre] == in[i]){
           node.leftChild = resetBinaryTreeString(
                    pre,            //前序集合
                    startPre + 1,   //前序左子樹起始點： startPre + 1
                    startPre + (i - startIn),//左子樹長度：i是root節點在中序周遊的位置,
                                             // (i - startIn)是中序周遊中左子樹的長度，
                                             // 是以左子樹的總長度：前序的 startPre + 中序周遊中左子樹的長度
                    in,             //中序集合
                    startIn,        //中序左子樹的起始點：startIn
                    i - 1);         //中序左子樹的總長度：i -1
            node.rightChild = resetBinaryTreeString(
                    pre,             //前序集合
                    startPre + (i - startIn) + 1,//前序右子樹起始點： 前序左子樹的長度+1 , {startPre + (i - startIn)} + 1
                    endPre,          //前序右子樹總長度： 前序的總長度
                    in,              //中序集合
                    i + 1,           //中序右子樹的起始點：i+1
                    endIn);          //中序右子樹總長度： 中序的總長度
            break;
        }
    }
    return node;
}

這些是最近看二叉樹的一些收獲~簡單的分享一下。

下面貼上全部代碼：

public class BinaryTree {

private TreeNode root;

public BinaryTree() {
    root = new TreeNode(1, "A");
}

/**
 * 建構二叉樹
 *                  A
 *              B       C
 *          D       E      F
 *      G       H     I
 */
public void createBinaryTree() {
    root = new TreeNode(1, "A");
    TreeNode treeNodeB = new TreeNode(2, "B");
    TreeNode treeNodeC = new TreeNode(3, "C");
    TreeNode treeNodeD = new TreeNode(4, "D");
    TreeNode treeNodeE = new TreeNode(5, "E");
    TreeNode treeNodeF = new TreeNode(6, "F");
    TreeNode treeNodeG = new TreeNode(7, "G");
    TreeNode treeNodeH = new TreeNode(8, "H");
    TreeNode treeNodeI = new TreeNode(9, "I");

    root.leftChild = treeNodeB;
    root.rightChild = treeNodeC;
    treeNodeB.leftChild = treeNodeD;
    treeNodeD.leftChild = treeNodeG;
    treeNodeD.rightChild = treeNodeH;
    treeNodeC.leftChild = treeNodeE;
    treeNodeC.rightChild = treeNodeF;
    treeNodeE.rightChild = treeNodeI;

}

/**
 *  前序周遊  遞歸
 * @param treeNode
 */
public void preOrder(TreeNode treeNode){
    if(treeNode == null){
        return;
    }else{
        //首先輸出根節點。
        System.out.println("data:" + treeNode.data);
        //不斷的調用自身函數，把左節點輸出。
        preOrder(treeNode.leftChild);
        //根節點和左節點輸出完成，輸出右節點。
        preOrder(treeNode.rightChild);
    }
}
/**
 *  中序周遊  遞歸
 * @param treeNode
 */
public void midOrder(TreeNode treeNode){
    if(treeNode == null){
        return;
    }else{
        midOrder(treeNode.leftChild);
        System.out.println("data:" + treeNode.data);
        midOrder(treeNode.rightChild);
    }
}
/**
 *  後序周遊  遞歸
 * @param treeNode
 */
public void postOrder(TreeNode treeNode){
    if(treeNode == null){
        return;
    }else{
        postOrder(treeNode.leftChild);
        postOrder(treeNode.rightChild);
        System.out.println("data:" + treeNode.data);
    }
}
/**
 *  前序周遊  非遞歸
 * @param treeNode
 */
public void nonRecOrder(TreeNode treeNode){
    if(treeNode == null){
        return;
    }
    Stack<TreeNode> stack = new Stack<>();
    stack.push(treeNode);
    while (!stack.isEmpty()){
        //彈出根結點
        TreeNode node = stack.pop();
        System.out.println("data:" + node.data);
        //如果有右子結點，則壓入節點
        if(node.rightChild!=null){
            //如果左節點有值，則右節點在棧底，最後才會輸出
            stack.push(node.rightChild);
        }
        //如果有右左結點，則壓入節點
        if(node.leftChild!=null){
            //下次循環把左子節點當根節點繼續彈出
            stack.push(node.leftChild);
        }
    }
}

/**
 * 已知前序和中序
 * @param pre       前序集合
 * @param startPre  前序集合起始點
 * @param endPre    前序集合總長度
 * @param in        中序集合
 * @param startIn   中序集合起始點
 * @param endIn     中序集合總長度
 * @return
 */
public TreeNode resetBinaryTreeString(String[] pre ,int startPre,int  endPre,String[] in,int startIn,int endIn){
    //如果開始大于結束，就說明這個樹已經結束了
    if(startPre > endPre || startIn > endIn) {
        return null;
    }
    //把前序的頭節點放入樹中當根節點
    TreeNode node = new TreeNode(pre[startPre]);
    //周遊中序的所有節點
    for (int i = startIn; i <= endIn; i++) {
        //找到根節點在中序中的位置
        if(pre[startIn] == in[i]){
            node.leftChild = resetBinaryTreeString(
                    pre,            //前序集合
                    startPre + 1,   //前序左子樹起始點： startPre + 1
                    startPre + (i - startIn),//左子樹長度：i是root節點在中序周遊的位置,
                    // (i - startIn)是中序周遊中左子樹的長度，
                    // 是以左子樹的總長度：前序的 startPre + 中序周遊中左子樹的長度
                    in,             //中序集合
                    startIn,        //中序左子樹的起始點：startIn
                    i - 1);         //中序左子樹的總長度：i -1
            node.rightChild = resetBinaryTreeString(
                    pre,             //前序集合
                    startPre + (i - startIn) + 1,//前序右子樹起始點： 前序左子樹的長度+1 , {startPre + (i - startIn)} + 1
                    endPre,          //前序右子樹總長度： 前序的總長度
                    in,              //中序集合
                    i + 1,           //中序右子樹的起始點：i+1
                    endIn);          //中序右子樹總長度： 中序的總長度
            break;
        }
    }
    return node;
}

public static void main(String[] args){
    BinaryTree binaryTree= new BinaryTree();
    binaryTree.createBinaryTree();

    System.out.println("非遞歸前序");
    binaryTree.nonRecOrder(binaryTree.root);

    System.out.println("遞歸前序");
    binaryTree.preOrder(binaryTree.root);

    System.out.println("遞歸中序");
    binaryTree.midOrder(binaryTree.root);

    System.out.println("遞歸後序");
    binaryTree.postOrder(binaryTree.root);

    String[] pre = {"A","B","D","G","H","C","E","I","F"};

    String[] mid = {"G","D","H","B","A","E","I","C","F"};

    TreeNode root = binaryTree.resetBinaryTreeString(pre, 0, pre.length - 1, mid, 0, mid.length - 1);

    System.out.println("重建二叉樹前序");
    binaryTree.preOrder(root);
}

public class TreeNode {
    /**
     *
     */
    private int index;
    /**
     * 資料域
     */
    private String data;
    /**
     * 左子樹
     */
    private TreeNode leftChild;
    /**
     * 右子樹
     */
    private TreeNode rightChild;


    public int getIndex() {
        return index;
    }


    public void setIndex(int index) {
        this.index = index;
    }


    public String getData() {
        return data;
    }


    public void setData(String data) {
        this.data = data;
    }


    public TreeNode(int index, String data) {
        this.index = index;
        this.data = data;
        this.leftChild = null;
        this.rightChild = null;
    }

    public TreeNode(String data) {
        this.data = data;
    }
}

}

二叉樹的周遊和重建

前序周遊：根節點，左節點，右節點。

中序周遊：左節點，根節點，右節點。

後序周遊：左節點，右節點，根節點。

繼續閱讀

樹的基本概念(定義、基本術語、性質)

GSL--GNU Scientific Library

D5|哈希表，善用資料結構

如何成為一名.net 工程師?

BMP檔案結構及圖像每行位元組計算方法

D. Ehab the Xorcist(構造+思維)

查找算法之二分查找查找算法之二分查找

JAVA高效程式設計指南

CQ V1.0分詞bates(基于雙數組tire樹)—應該是目前最快的中文分詞算法

【資料結構】醫院選址

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

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

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

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

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

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