月份: 2020 年 4 月

目錄

前面我們講的都是線性表結構，棧、隊列等等。今天我們講一種非線性表結構，樹。樹這種數據結構比線性表的數據結構要複雜得多，內容也比較多，首先我們先從樹（Tree）開始講起。
@

樹(Tree)

樹型結構是一種非線性結構，它的數據元素之間呈現分支、分層的特點。

1.樹的定義

樹(Tree)是由n(n≥0)個結點構成的有限集合T，當n=0時T稱為空樹；否則，在任一非空樹T中：
(1)有且僅有一個特定的結點，它沒有前驅結點，稱其為根(Root)結點；
(2)剩下的結點可分為m(m≥0)個互不相交的子集T1，T2，…，Tm，其中每個子集本身又是一棵樹，並稱其為根的子樹(Subtree)。

注意：樹的定義具有遞歸性，即“樹中還有樹”。樹的遞歸定義揭示出了樹的固有特性

2.什麼是樹結構

什麼是“樹”？再好的定義，都沒有圖解來的直觀。所以我在圖中畫了幾棵“樹”。你來看看，這些“樹”都有什麼特徵？

你有沒有發現，“樹”這種數據結構真的很像我們現實生活中的“樹”

3.為什麼使用樹結構

在有序數組中，可以快速找到特定的值，但是想在有序數組中插入一個新的數據項，就必須首先找出新數據項插入的位置，然後將比新數據項大的數據項向後移動一位，來給新的數據項騰出空間，刪除同理，這樣移動很費時。顯而易見，如果要做很多的插入和刪除操作和刪除操作，就不該選用有序數組。另一方面，鏈表中可以快速添加和刪除某個數據項，但是在鏈表中查找數據項可不容易，必須從頭開始訪問鏈表的每一個數據項，直到找到該數據項為止，這個過程很慢。 樹這種數據結構，既能像鏈表那樣快速的插入和刪除，又能想有序數組那樣快速查找

4.樹的常用術語

結點——包含一個數據元素和若干指向其子樹的分支
度——結點擁有的子樹個數
樹的度——該樹中結點的最大度數
恭弘=叶 恭弘子——度為零的結點
分支結點（非終端結點）——度不為零的結點
孩子和雙親——結點的子樹的根稱為該結點的孩子，相應地，該結點稱為孩子的雙親
兄弟——同一個雙親的孩子
祖先和子孫——從根到該結點所經分支上的所有結點。相應地，以某一結點為根的子樹中的任一結點稱為該結點的子孫。
結點的層次——結點的層次從根開始定義，根結點的層次為1，其孩子結點的層次為2，……
堂兄弟——雙親在同一層的結點
樹的深度——樹中結點的最大層次
有序樹和無序樹——如果將樹中每個結點的各子樹看成是從左到右有次序的(即位置不能互換)，則稱該樹為有序樹；否則稱為無序樹。
森林——m(m≥0)棵互不相交的樹的有限集合

到這裏，樹就講的差不多了，接下來講講二叉樹（Binary Tree）

二叉樹(Binary Tree）

樹結構多種多樣，不過我們最常用還是二叉樹，我們平時最常用的樹就是二叉樹。二叉樹的每個節點最多有兩個子節點，分別是左子節點和右子節點。二叉樹中，有兩種比較特殊的樹，分別是滿二叉樹和完全二叉樹。滿二叉樹又是完全二叉樹的一種特殊情況。

1．二叉樹的定義和特點

二叉樹的定義：
二叉樹(Binary Tree)是n(n≥0)個結點的有限集合BT，它或者是空集，或者由一個根結點和兩棵分別稱為左子樹和右子樹的互不相交的二叉樹組成 。
————————————
二叉樹的特點：
每個結點至多有二棵子樹(即不存在度大於2的結點)；二叉樹的子樹有左、右之分，且其次序不能任意顛倒。

2．幾種特殊形式的二叉樹

1、滿二叉樹：
定義：深度為k且有2k-1個結點的二叉樹，稱為滿二叉樹。
特點：每一層上的結點數都是最大結點數
2、完全二叉樹：
定義：
深度為k，有n個結點的二叉樹當且僅當其每一個結點都與深度為k的滿二叉樹中編號從1至n的結點一一對應時，稱為完全二叉樹
特點:
特點一 : 恭弘=叶 恭弘子結點只可能在層次最大的兩層上出現;
特點二 : 對任一結點，若其右分支下子孫的最大層次為l，則其左分支下子孫的最大層次必為l 或l+1

建議看圖對應文字綜合理解

代碼創建二叉樹：

首先，創建一個節點Node類

package demo5;
/*
 * 節（結）點類 
 */
public class Node {
    //節點的權
    int value;
    //左兒子（左節點）
    Node leftNode;
    //右兒子（右節點）
    Node rightNode;
    //構造函數，初始化的時候就給二叉樹賦上權值
    public Node(int value) {
        this.value=value;
    }
    
    //設置左兒子（左節點）
    public void setLeftNode(Node leftNode) {
        this.leftNode = leftNode;
    }
    //設置右兒子（右節點）
    public void setRightNode(Node rightNode) {
        this.rightNode = rightNode;
    }

接着創建一個二叉樹BinaryTree 類

package demo5;
/*
 * 二叉樹Class
 */
public class BinaryTree {
    //根節點root
    Node root;
    
    //設置根節點
    public void setRoot(Node root) {
        this.root = root;
    }
    
    //獲取根節點
    public Node getRoot() {
        return root;
    }
}

最後創建TestBinaryTree 類（該類主要是main方法用來測試）來創建一個二叉樹

package demo5;
public class TestBinaryTree {

    public static void main(String[] args) {
        //創建一顆樹
        BinaryTree binTree = new BinaryTree();
        //創建一個根節點
        Node root = new Node(1);
        //把根節點賦給樹
        binTree.setRoot(root);
        //創建一個左節點
        Node rootL = new Node(2);
        //把新創建的節點設置為根節點的子節點
        root.setLeftNode(rootL);
        //創建一個右節點
        Node rootR = new Node(3);
        //把新創建的節點設置為根節點的子節點
        root.setRightNode(rootR);
        //為第二層的左節點創建兩個子節點
        rootL.setLeftNode(new Node(4));
        rootL.setRightNode(new Node(5));
        //為第二層的右節點創建兩個子節點
        rootR.setLeftNode(new Node(6));
        rootR.setRightNode(new Node(7));
    }

}

下面將會講的遍歷、查找節點、刪除節點都將圍繞這三個類開展

不難看出創建好的二叉樹如下（畫的不好，還望各位見諒）：

3．二叉樹的兩種存儲方式

二叉樹既可以用鏈式存儲，也可以用數組順序存儲。數組順序存儲的方式比較適合完全二叉樹，其他類型的二叉樹用數組存儲會比較浪費存儲空間，所以鏈式存儲更合適。

我們先來看比較簡單、直觀的鏈式存儲法。

接着是基於數組的順序存儲法（該例子是一棵完全二叉樹）

上面例子是一棵完全二叉樹，所以僅僅“浪費”了一個下標為0的存儲位置。如果是非完全二叉樹，則會浪費比較多的數組存儲空間，如下。

還記得堆和堆排序嗎，堆其實就是一種完全二叉樹，最常用的存儲方式就是數組。

4．二叉樹的遍歷

前面我講了二叉樹的基本定義和存儲方法，現在我們來看二叉樹中非常重要的操作，二叉樹的遍歷。這也是非常常見的面試題。

經典遍歷的方法有三種，前序遍歷、中序遍歷和後序遍歷

前序遍歷是指，對於樹中的任意節點來說，先打印這個節點，然後再打印它的左子樹，最後打印它的右子樹。

中序遍歷是指，對於樹中的任意節點來說，先打印它的左子樹，然後再打印它本身，最後打印它的右子樹。

後序遍歷是指，對於樹中的任意節點來說，先打印它的左子樹，然後再打印它的右子樹，最後打印這個節點本身。

我想，睿智的你已經想到了二叉樹的前、中、後序遍歷就是一個遞歸的過程。比如，前序遍歷，其實就是先打印根節點，然後再遞歸地打印左子樹，最後遞歸地打印右子樹。

在之前創建好的二叉樹代碼之上，我們來使用這三種方法遍歷一下~

依舊是在Node節點類上添加方法：可以看出遍歷方法都是用的遞歸思想

package demo5;
/*
 * 節（結）點類 
 */
public class Node {
//===================================開始 遍歷========================================
    //前序遍歷
    public void frontShow() {
        //先遍歷當前節點的內容
        System.out.println(value);
        //左節點
        if(leftNode!=null) {
            leftNode.frontShow();
        }
        //右節點
        if(rightNode!=null) {
            rightNode.frontShow();
        }
    }

    //中序遍歷
    public void midShow() {
        //左子節點
        if(leftNode!=null) {
            leftNode.midShow();
        }
        //當前節點
        System.out.println(value);
        //右子節點
        if(rightNode!=null) {
            rightNode.midShow();
        }
    }

    //後序遍歷
    public void afterShow() {
        //左子節點
        if(leftNode!=null) {
            leftNode.afterShow();
        }
        //右子節點
        if(rightNode!=null) {
            rightNode.afterShow();
        }
        //當前節點
        System.out.println(value);
    }

}

然後依舊是在二叉樹BinaryTree 類上添加方法，並且添加的方法調用Node類中的遍歷方法

package demo5;
/*
 * 二叉樹Class
 */
public class BinaryTree {

    public void frontShow() {
        if(root!=null) {
            //調用節點類Node中的前序遍歷frontShow（）方法
            root.frontShow();
        }
    }

    public void midShow() {
        if(root!=null) {
            //調用節點類Node中的中序遍歷midShow()方法
            root.midShow();
        }
    }

    public void afterShow() {
        if(root!=null) {
            //調用節點類Node中的後序遍歷afterShow()方法
            root.afterShow();
        }
    }

}

依舊是在TestBinaryTree類中測試

package demo5;

public class TestBinaryTree {

    public static void main(String[] args) {
        //前序遍歷樹
        binTree.frontShow();
        System.out.println("===============");
        //中序遍歷
        binTree.midShow();
        System.out.println("===============");
        //後序遍歷
        binTree.afterShow();
        System.out.println("===============");
        //前序查找
        Node result = binTree.frontSearch(5);
        System.out.println(result);
        
}

如果遞歸理解的不是很透，我可以分享一個學習的小方法：我建議各位可以這樣斷點調試，一步一步調，思維跟上，仔細推敲每一步的運行相信我，你會重新認識到遞歸！（像下面這樣貼個圖再一步一步斷點思維更加清晰）

貼一下我斷點對遞歸的分析，希望對你有一定的幫助~

二叉樹遍歷的遞歸實現思路自然、簡單，易於理解，但執行效率較低。為了提高程序的執行效率，可以顯式的設置棧，寫出相應的非遞歸遍歷算法。非遞歸的遍歷算法可以根據遞歸算法的執行過程寫出。至於代碼可以嘗試去寫一寫，這也是一種提升！具體的非遞歸算法主要流程圖貼在下面了：

二叉樹遍歷算法分析：

二叉樹遍歷算法中的基本操作是訪問根結點，不論按哪種次序遍歷，都要訪問所有的結點，對含n個結點的二叉樹，其時間複雜度均為O（n）。所需輔助空間為遍歷過程中所需的棧空間，最多等於二叉樹的深度k乘以每個結點所需空間數，最壞情況下樹的深度為結點的個數n，因此，其空間複雜度也為O(n)。

5．二叉樹中節點的查找與刪除

剛才講到二叉樹的三種金典遍歷放法，那麼節點的查找同樣是可以效仿的，分別叫做前序查找、中序查找以及後序查找，下面代碼只以前序查找為例，三者查找方法思路類似~

至於刪除節點，有三種情況：

1、如果刪除的是根節點，那麼二叉樹就完全被刪了
2、如果刪除的是雙親節點，那麼該雙親節點以及他下面的所有子節點所構成的子樹將被刪除
3、如果刪除的是恭弘=叶 恭弘子節點，那麼就直接刪除該恭弘=叶 恭弘子節點

那麼，我把完整的三個類給貼出來（包含創建、遍歷、查找、刪除）

依舊是Node節點類

package demo5;
/*
 * 節（結）點類 
 */
public class Node {
    //節點的權
    int value;
    //左兒子
    Node leftNode;
    //右兒子
    Node rightNode;
    //構造函數，初始化的時候就給二叉樹賦上權值
    public Node(int value) {
        this.value=value;
    }
    
    //設置左兒子
    public void setLeftNode(Node leftNode) {
        this.leftNode = leftNode;
    }
    //設置右兒子
    public void setRightNode(Node rightNode) {
        this.rightNode = rightNode;
    }
    
    //前序遍歷
    public void frontShow() {
        //先遍歷當前節點的內容
        System.out.println(value);
        //左節點
        if(leftNode!=null) {
            leftNode.frontShow();
        }
        //右節點
        if(rightNode!=null) {
            rightNode.frontShow();
        }
    }

    //中序遍歷
    public void midShow() {
        //左子節點
        if(leftNode!=null) {
            leftNode.midShow();
        }
        //當前節點
        System.out.println(value);
        //右子節點
        if(rightNode!=null) {
            rightNode.midShow();
        }
    }

    //後序遍歷
    public void afterShow() {
        //左子節點
        if(leftNode!=null) {
            leftNode.afterShow();
        }
        //右子節點
        if(rightNode!=null) {
            rightNode.afterShow();
        }
        //當前節點
        System.out.println(value);
    }

    //前序查找
    public Node frontSearch(int i) {
        Node target=null;
        //對比當前節點的值
        if(this.value==i) {
            return this;
        //當前節點的值不是要查找的節點
        }else {
            //查找左兒子
            if(leftNode!=null) {
                //有可能可以查到，也可以查不到，查不到的話，target還是一個null
                target = leftNode.frontSearch(i);
            }
            //如果不為空，說明在左兒子中已經找到
            if(target!=null) {
                return target;
            }
            //查找右兒子
            if(rightNode!=null) {
                target=rightNode.frontSearch(i);
            }
        }
        return target;
    }
    
    //刪除一個子樹
    public void delete(int i) {
        Node parent = this;
        //判斷左兒子
        if(parent.leftNode!=null&&parent.leftNode.value==i) {
            parent.leftNode=null;
            return;
        }
        //判斷右兒子
        if(parent.rightNode!=null&&parent.rightNode.value==i) {
            parent.rightNode=null;
            return;
        }
        
        //遞歸檢查並刪除左兒子
        parent=leftNode;
        if(parent!=null) {
            parent.delete(i);
        }
        
        //遞歸檢查並刪除右兒子
        parent=rightNode;
        if(parent!=null) {
            parent.delete(i);
        }
    }

}

依舊是BinaryTree 二叉樹類

package demo5;
/*
 * 二叉樹Class
 */
public class BinaryTree {
    //根節點root
    Node root;
    
    //設置根節點
    public void setRoot(Node root) {
        this.root = root;
    }
    
    //獲取根節點
    public Node getRoot() {
        return root;
    }

    public void frontShow() {
        if(root!=null) {
            //調用節點類Node中的前序遍歷frontShow（）方法
            root.frontShow();
        }
    }

    public void midShow() {
        if(root!=null) {
            //調用節點類Node中的中序遍歷midShow()方法
            root.midShow();
        }
    }

    public void afterShow() {
        if(root!=null) {
            //調用節點類Node中的後序遍歷afterShow()方法
            root.afterShow();
        }
    }
    //查找節點i
    public Node frontSearch(int i) {
        return root.frontSearch(i);
    }
    //刪除節點i
    public void delete(int i) {
        if(root.value==i) {
            root=null;
        }else {
            root.delete(i);
        }
    }
    
}

依舊是TestBinaryTree測試類

package demo5;

public class TestBinaryTree {

    public static void main(String[] args) {
        //創建一顆樹
        BinaryTree binTree = new BinaryTree();
        //創建一個根節點
        Node root = new Node(1);
        //把根節點賦給樹
        binTree.setRoot(root);
        //創建一個左節點
        Node rootL = new Node(2);
        //把新創建的節點設置為根節點的子節點
        root.setLeftNode(rootL);
        //創建一個右節點
        Node rootR = new Node(3);
        //把新創建的節點設置為根節點的子節點
        root.setRightNode(rootR);
        //為第二層的左節點創建兩個子節點
        rootL.setLeftNode(new Node(4));
        rootL.setRightNode(new Node(5));
        //為第二層的右節點創建兩個子節點
        rootR.setLeftNode(new Node(6));
        rootR.setRightNode(new Node(7));
        //前序遍歷樹
        binTree.frontShow();
        System.out.println("===============");
        //中序遍歷
        binTree.midShow();
        System.out.println("===============");
        //後序遍歷
        binTree.afterShow();
        System.out.println("===============");
        //前序查找
        Node result = binTree.frontSearch(5);
        System.out.println(result);
        
        System.out.println("===============");
        //刪除一個子樹
        binTree.delete(4);
        binTree.frontShow();
        
    }

}

到這裏，總結一下，我們學了一種非線性表數據結構，樹。關於樹，有幾個比較常用的概念你需要掌握，那就是：根節點、恭弘=叶 恭弘子節點、父節點、子節點、兄弟節點，還有節點的高度、深度、層數，以及樹的高度等。我們平時最常用的樹就是二叉樹。二叉樹的每個節點最多有兩個子節點，分別是左子節點和右子節點。二叉樹中，有兩種比較特殊的樹，分別是滿二叉樹和完全二叉樹。滿二叉樹又是完全二叉樹的一種特殊情況。二叉樹既可以用鏈式存儲，也可以用數組順序存儲。數組順序存儲的方式比較適合完全二叉樹，其他類型的二叉樹用數組存儲會比較浪費存儲空間。除此之外，二叉樹里非常重要的操作就是前、中、後序遍歷操作，遍歷的時間複雜度是O(n)，你需要理解並能用遞歸代碼來實現。

如果本文章對你有幫助，哪怕是一點點，請點個讚唄，謝謝~

歡迎各位關注我的公眾號，一起探討技術，嚮往技術，追求技術…說好了來了就是盆友喔…

本站聲明:網站內容來源於博客園,如有侵權,請聯繫我們,我們將及時處理

【其他文章推薦】

※帶您來了解什麼是 USB CONNECTOR  ?

※自行創業 缺乏曝光? 下一步”網站設計“幫您第一時間規劃公司的門面形象

※如何讓商品強力曝光呢? 網頁設計公司幫您建置最吸引人的網站，提高曝光率!!

※綠能、環保無空污,成為電動車最新代名詞，目前市場使用率逐漸普及化

※廣告預算用在刀口上，網站設計公司幫您達到更多曝光效益

※試算大陸海運運費!