天天看點
傳回

資料結構與算法(九)

樹結構基礎部分

二叉樹

為什麼需要該資料結構

數組存儲方式的分析
  • 優點：
    • 通過 下标 方式通路元素，速度快
    • 對于 有序數組，還可以使用二分查找提高檢索速度
  • 缺點：如果要檢索具體某個值或插入值（按一定順序）會整體移動，效率較低，如下的示意圖
    資料結構與算法(九)
連結清單存儲方式的分析

優點：在一定程度上對數組存儲方式有優化

例如：插入一個數值節點，隻需要将插入節點，連結到連結清單中即可，同理，删除效率也很好

資料結構與算法(九)

  • 缺點：檢索效率較低

    需要從頭結點開始周遊查找。

簡單說：

  • 數組通路快，增删慢
  • 連結清單增删快，通路慢

那麼就出現了 樹 這種資料結構

樹存儲資料方式分析

提供資料 存儲 、讀取 效率。

例如：利用 二叉排序樹（Binary Sort Tree），既可以保證資料的檢索速度，同時也可以保證資料的插入、删除、修改 的速度

資料結構與算法(九)

如圖所示：

  • 插入時，小的數在 左節點、大的數在 右節點
  • 查找時：根據插入事的特性，基本上就類似折半查找了，每次都過濾一半的節點
  • 删除時：隻需要移動相鄰的節點的引用

樹的常用術語

資料結構與算法(九)
  • 節點：每一個圓圈表示一個節點，也稱節點對象
  • 根節點：最上面，最頂部的那個節點，也就是一棵樹的入口
  • 父節點：有子節點的節點
  • 子節點
  • 葉子節點：沒有子節點的節點

  • 節點的權：可以簡單的了解為節點值

    有時候也用 路徑 來表示

  • 路徑：從 root 節點找到該節點的路線
  • 層
  • 子樹：有子節點的父子兩層就可以稱為是一個子樹
  • 樹的高度：最大層數
  • 森林：多顆子樹構成森林

二叉樹的概念

  • 樹有很多種，每個節點 最多隻能有兩個子節點 的一種形式稱為 二叉樹
  • 二叉樹的子節點分為 左節點 和 右節點
    資料結構與算法(九)
  • 如果該二叉樹的所有 葉子節點 都在 最後一層，并且 節點總數 = 2^n-1 （n 為層數），則我們稱為 滿二叉樹
    資料結構與算法(九)
  • 如果該二叉樹的所有葉子節點都在最 後一層或倒數第二層，而且 最後一層的葉子節點在左邊連續，倒數第二層的葉子節點在右邊連續，我們稱為 完全二叉樹
    資料結構與算法(九)

二叉樹的周遊說明

有三種：

  • 前序周遊：先輸出父節點，再周遊左子樹（遞歸）和右子樹（遞歸）
  • 中序周遊：先周遊左子樹（遞歸），再輸出父節點，再周遊右子樹（遞歸）
  • 後序周遊：先周遊左子樹（遞歸），再周遊右子樹（遞歸），最後輸出父節點

前、中、後序主要差別是輸出父節點的時間來區分

二叉樹周遊思路分析

資料結構與算法(九)
  • 前序周遊：
    1. 先輸出目前節點（初始節點是 root 節點）
    2. 如果左子節點不為空，則遞歸繼續前序周遊
    3. 如果右子節點不為空，則遞歸繼續前序周遊
    上圖的輸出順序為：1、2、3、4
  • 中序周遊：
    1. 如果目前節點的左子節點不為空，則遞歸中序周遊
    2. 輸出目前節點
    3. 如果目前節點的右子節點不為空，則遞歸中序
    上圖的輸出順序為：2、1、4、3
  • 後序周遊：
    上圖的輸出順序為：2、4、3、1

周遊代碼實作 

//定義節點
class HeroNode{
    private int no;//目前節點編号
    private String name;//目前節點名字
    private HeroNode left;//目前節點左子樹
    private HeroNode right;//目前節點右子樹

    public HeroNode(int no, String name) {
        this.no = no;
        this.name = name;
    }

    public int getNo() {
        return no;
    }

    public void setNo(int no) {
        this.no = no;
    }

    public String getName() {
        return name;
    }

    public void setName(String name) {
        this.name = name;
    }

    public HeroNode getLeft() {
        return left;
    }

    public void setLeft(HeroNode left) {
        this.left = left;
    }

    public HeroNode getRight() {
        return right;
    }

    public void setRight(HeroNode right) {
        this.right = right;
    }

    @Override
    public String toString() {
        return "HeroNode{" +
                "no=" + no +
                ", name='" + name + '\'' +
                '}';
    }
    //前序周遊
    public void preOrder(){
        //先輸出目前節點
        System.out.println(this);
        //遞歸周遊左子節點
        if(this.left != null){
            this.left.preOrder();
        }
        //遞歸周遊右子節點
        if(this.right != null){
            this.right.preOrder();
        }
    }

    //中序周遊
    public void infixOrder(){
        //先輸出左子樹
        if(this.left != null){
            this.left.infixOrder();
        }
        //輸出目前節點
        System.out.println(this);
        //輸出右子樹
        if(this.right != null){
            this.right.infixOrder();
        }
    }

    //後序周遊
    public void postOrder(){
        //先輸出左子樹
        if(this.left != null){
            this.left.postOrder();
        }
        //輸出右子樹
        if(this.right != null){
            this.right.postOrder();
        }
        //輸出目前節點
        System.out.println(this);
    }
}
//建立二叉樹
class BinaryTree{
    private HeroNode root;

    public void setRoot(HeroNode root) {
        this.root = root;
    }
    //前序周遊
    public void preOrder(){
        if(this.root != null){
            this.root.preOrder();
        }else{
            System.out.println("目前二叉樹為空");
        }
    }
    //中序周遊
    public void infixOrder(){
        if(this.root != null){
            this.root.infixOrder();
        }else{
            System.out.println("目前二叉樹為空");
        }
    }
    //後序周遊
    public void postOrder(){
        if(this.root != null){
            this.root.postOrder();
        }else{
            System.out.println("目前二叉樹為空");
        }
    }
}

//建立二叉樹
BinaryTree binaryTree = new BinaryTree();

//手動建立二叉樹
HeroNode root = new HeroNode(1,"宋江");
HeroNode hero1 = new HeroNode(2,"吳用");
HeroNode hero2 = new HeroNode(3,"盧俊義");
HeroNode hero3 = new HeroNode(4,"林沖");
root.setLeft(hero1);
root.setRight(hero2);
hero2.setRight(hero3);
binaryTree.setRoot(root);

//周遊二叉樹
System.out.println("前序周遊");
binaryTree.preOrder();
//中序周遊
System.out.println("中序周遊");
binaryTree.infixOrder();
//後序周遊
System.out.println("後序周遊");
binaryTree.postOrder();
資料結構與算法(九)

二叉樹查找

要求：

  1. 編寫前、中、後序查找方法
  2. 并分别使用三種查找方式，查找

    id=5

     的節點
  3. 并分析各種查找方式，分别比較了多少次

由于二叉樹的查找是周遊查找，是以就簡單了，前面周遊規則已經寫過了，改寫成查找即可

//在節點中增加查找方法
//前序查找
public HeroNode preOrderSearch(int no){
    if(this.no == no){
        return this;
    }
    HeroNode resNode = null;
    if(this.left != null){
        resNode = this.left.preOrderSearch(no);
    }
    if(resNode != null){
        return resNode;
    }

    if(this.right != null){
        resNode = this.right.preOrderSearch(no);
    }

    return resNode;
}

//中序查找
public HeroNode infixOrderSearch(int no){
    HeroNode resNode = null;
    if(this.left != null){
        resNode = this.left.infixOrderSearch(no);
    }
    if(resNode != null){
        return resNode;
    }
    if(this.no == no){
        return this;
    }
    if(this.right != null){
        resNode = this.right.infixOrderSearch(no);
    }
    return resNode;
}

//後序查找
public HeroNode postOrderSearch(int no){
    HeroNode resNode = null;
    if(this.left != null){
        resNode = this.left.postOrderSearch(no);
    }
    if(resNode != null){
        return resNode;
    }

    if(this.right != null){
        resNode = this.right.postOrderSearch(no);
    }
    if(resNode != null){
        return resNode;
    }
    if(this.no == no){
        return this;
    }
    return null;
}
//在二叉樹中增加查找方法
//前序查找
public HeroNode preOrderSearch(int no){
    HeroNode resNode = null;
    if(this.root != null){
        resNode = this.root.preOrderSearch(no);
    }else{
        System.out.println("目前二叉樹為空");
    }
    return resNode;
}

//中序
public HeroNode infixOrderSearch(int no){
    HeroNode resNode = null;
    if(this.root != null){
        resNode = this.root.infixOrderSearch(no);
    }else{
        System.out.println("目前二叉樹為空");
    }
    return resNode;
}
//後序
public HeroNode postOrderSearch(int no){
    HeroNode resNode = null;
    if(this.root != null){
        resNode = this.root.postOrderSearch(no);
    }else{
        System.out.println("目前二叉樹為空");
    }
    return resNode;
}

可以看出：

  • 找到的次數和 查找的順序 有關，而查找順序就是哪一序有關
  • 找不到的次數則是相當于都周遊完成，是以是相等的次數

二叉樹删除

資料結構與算法(九)
  1. 如果删除的節點是 葉子節點，則删除該節點
  2. 如果删除的節點是非葉子節點，則删除該子樹

測試：删除 5 号葉子節點和 3 号子樹。

說明：目前的二叉樹不是規則的，如果不删除子樹，則需要考慮哪一個節點會被上提作為父節點。這個後續講解排序二叉樹時再來實作。先實作簡單的

思路分析：

  • 由于我們的二叉樹是單向的
  • 是以我們判定一個節點是否可以删除，是判斷它的 子節點，是否可删除，否則則沒法回到父節點删除了，因為要判斷被删除的節點滿足前面的兩點要求
    1. 目前節點的 左子節點 不為空，并且左子節點就是要删除的節點，則 left = null，并且傳回（結束遞歸删除）
    2. 目前節點的 右子節點 不為空，并且右子節點就是要删除的節點，則 right = null，并且傳回（結束遞歸删除）

    如果前面都沒有删除，則繼續遞歸删除。上面的要求是 2 點，實際上是，找到符合條件的節點則直接删除（因為不考慮是否有子樹）

    如果樹隻有一個 root 節點，則将 root 節點置空

//節點中增加删除方法
public void delete(int no){
    if(this.left != null){
        if(this.left.no == no){
            this.left = null;
            return;
        }
    }

    if(this.right != null){
        if(this.right.no == no){
            this.right = null;
            return;
        }
    }

    //向左遞歸
    if(this.left != null){
        this.left.delete(no);
    }

    //向右遞歸
    if(this.right != null){
        this.right.delete(no);
    }
}
//二叉樹中增加删除方法
public void delete(int no){
    if(this.root != null){
        if(this.root.getNo() == no){
            this.root = null;
            return;
        }else{
            this.root.delete(no);
        }
    }else{
        System.out.println("目前二叉樹為空");
    }
}

順序存儲二叉樹

基本概念

從資料存儲來看，數組存儲 方式和 樹 的存儲方式可以 互相轉換。即使數組可以轉換成樹，樹也可以轉換成數組。如下示意圖

資料結構與算法(九)

上圖閱讀說明：

  • 圓圈頂部的數字對應了數組中的索引
  • 圓圈内部的值對應的數數組元素的值

現在有兩個要求：

  1. 上圖的二叉樹的節點，要求以數組的方式來存儲

    arr=[1,2,3,4,5,6,7]
  2. 要求在周遊數組 arr 時，仍然可以以 前序、中序、後序的方式周遊

特點

想要 實作上面的兩個要求，需要知道順序存儲二叉樹的特點：

  1. 順序二叉樹 通常隻考慮 完全二叉樹
  2. 第 n 個元素的 左子節點 為

    2*n+1
  3. 第 n 個元素的 右子節點 為

    2*n+2
  4. 第 n 個元素的 父節點 為

    (n-1)/2

注：n 表示二叉樹中的第幾個元素（按 0 開始編号）

比如：

  • 元素 2 的左子節點為：

    2 * 1 + 1 = 3

     ，對比上圖去檢視，的确是 3
  • 元素 2 的右子節點為：

    2 * 1 + 2 = 4

     ，也 就是元素 5
  • 元素 3 的左子節點為：

    2 * 2 + 1 = 5

     ，也就是元素 6
  • 元素 3 的父節點為:

    (2-1)/2= 1/2 = 0

     ，也就是根節點 1

三種周遊方式 

//順序存儲二叉樹
class ArrayBinaryTree{
    private int[] array;

    public ArrayBinaryTree(int[] array) {
        this.array = array;
    }
    //前序周遊輸出順序存儲二叉樹
    public void preOrder(int index){
        if(array == null || array.length == 0){
            System.out.println("數組為空，不能周遊完全二叉樹");
        }
        //先輸出目前元素
        System.out.println(array[index]);
        //再遞歸輸出左子元素
        if((index*2+1) < array.length){
            preOrder((index*2 + 1));
        }
        //再遞歸輸出右子元素
        if((index*2+2) < array.length){
            preOrder((index*2 +2));
        }
    }
    public void preOrder(){
        preOrder(0);
    }
    //中序周遊輸出順序存儲二叉樹
    public void infixOrder(int index){
        if(array == null || array.length == 0){
            System.out.println("數組為空，不能周遊完全二叉樹");
        }
        if((index*2 +1) < array.length){
            infixOrder((index*2 + 1));
        }
        System.out.println(array[index]);
        if((index*2 + 2) < array.length){
            infixOrder((index*2+2));
        }
    }
    public void infixOrder(){
        infixOrder(0);
    }

    //後序周遊順序存儲二叉樹
    public void postOrder(int index){
        if(array == null || array.length == 0){
            System.out.println("數組為空，不能周遊完全二叉樹");
        }
        if((index*2 + 1) < array.length){
            postOrder((index*2+1));
        }
        if((index*2 + 2) < array.length){
            postOrder((index*2+2));
        }
        System.out.println(array[index]);
    }
    public void postOrder(){
        postOrder(0);
    }
}
資料結構與算法(九)
資料結構與算法(九)
資料結構與算法(九)

線索化二叉樹

引出線索化二叉樹

看如下問題：将數列

{1,3,6,8,10,14}

構成一顆二叉樹

資料結構與算法(九)

可以看到上圖的二叉樹為一顆 完全二叉樹。對他進行分析，可以發現如下的一些問題：

  1. 當對上面的二叉樹進行中序周遊時，數列為

    8,3,10,1,14,6
  2. 但是

    6,8,10,14

     這幾個節點的左右指針，并沒有完全用上

如果希望充分利用各個節點的左右指針，讓各個節點可以 指向自己的前後節點，這個時候就可以使用 線索化二叉樹 了

介紹

n 個節點的二叉樹連結清單中含有

n + 1

個空指針域，他的推導公式為

2n-(n-1) = n + 1

。

利用二叉連結清單中的空指針域，存放指向該節點在 某種周遊次序 *下的 **前驅** 和 **後繼** 節點的指針，這種附加的指針稱為*「線索」

  • 前驅：一個節點的前一個節點
  • 後繼：一個節點的後一個節點

如下圖，在中序周遊中，下圖的中序周遊為

8,3,10,1,14,6

，那麼 8 的後繼節點就為 3，3 的後繼節點是 10

資料結構與算法(九)

這種加上了線索的二叉樹連結清單稱為 線索連結清單（節點存儲了下一個節點，組成了連結清單，并且一般的二叉樹本來就是用連結清單實作的），相應的二叉樹稱為 線索二叉樹（Threaded BinaryTree）。根據線索性質的不同，線索二叉樹可分為：前、中、後序線索二叉樹。

思路分析

資料結構與算法(九)

将上圖的二叉樹，進行 中序線索二叉樹，中序周遊的數列為

8,3,10,1,14,6

那麼以上圖為例，線索化二叉樹後的樣子如下圖

資料結構與算法(九)
  • 的後繼節點為 3
  • 3 由于 左右節點都有元素，不能線索化
  • 10 的前驅節點為 3，後繼節點為 1
  • 1 不能線索化
  • 14 的前驅節點為 1，後繼節點為 6
  • 6 有左節點，不能線索化

注意：當線索化二叉樹後，那麼一個 Node 節點的 left 和 right 屬性，就有如下情況：

  1. left 指向的是 左子樹，也可能是指向 前驅節點

代碼實作 

//建立節點
class HeroNode{
    private int no;
    private String name;
    private HeroNode left;
    private HeroNode right;
    //左右子樹的類型，如果是左右子樹就是0，如果是前驅或者後繼節點就是1
    private int leftType;
    private int rightType;

    public HeroNode(int no, String name) {
        this.no = no;
        this.name = name;
    }

    public int getNo() {
        return no;
    }

    public void setNo(int no) {
        this.no = no;
    }

    public String getName() {
        return name;
    }

    public void setName(String name) {
        this.name = name;
    }

    public HeroNode getLeft() {
        return left;
    }

    public void setLeft(HeroNode left) {
        this.left = left;
    }

    public HeroNode getRight() {
        return right;
    }

    public void setRight(HeroNode right) {
        this.right = right;
    }

    public int getLeftType() {
        return leftType;
    }

    public void setLeftType(int leftType) {
        this.leftType = leftType;
    }

    public int getRightType() {
        return rightType;
    }

    public void setRightType(int rightType) {
        this.rightType = rightType;
    }

    @Override
    public String toString() {
        return "HeroNode{" +
                "no=" + no +
                ", name='" + name + '\'' +
                '}';
    }
}
//建立線索化二叉樹
class ThreadBinaryTree{
    private HeroNode root;//表示跟節點
    private HeroNode pre;//表示前驅節點

    public void setRoot(HeroNode root) {
        this.root = root;
    }
    public void threadedNodes(){
        threadedNodes(root);
    }
    //中序線索化周遊
    public void threadedList(){
        if(root == null){
            System.out.println("線索化二叉樹為空");
            return;
        }
        HeroNode node = root;
        while(node != null){
            //找到第一個有前驅節點的元素
            while(node.getLeftType() != 1){
                node = node.getLeft();
            }
            //輸出第一個元素
            System.out.println(node);
            //當有後繼節點的情況會進入
            while(node.getRightType() == 1){
                node = node.getRight();
                System.out.println(node);
            }
            //當一個節點沒有後繼節點的時候直接擷取右子樹
            node = node.getRight();
        }
    }

    //中序線索化
    public void threadedNodes(HeroNode node){
        if(node == null){
            return;
        }
        //先線索化左子樹
        threadedNodes(node.getLeft());
        //再線索化目前節點
        /*
        * 1.設定前驅節點，
        * 2.設定後繼節點
        * */
        if(node.getLeft() == null){
            node.setLeft(pre);
            node.setLeftType(1);
        }
        //線索化後繼節點，需要周遊到下一個節點的時候，通過下一個節點設定
        if(pre != null && pre.getRight() == null){
            pre.setRight(node);
            pre.setRightType(1);
        }
        //将前驅節點後移
        pre = node;
        //線索化右子樹
        threadedNodes(node.getRight());

    }
}

前序線索化和周遊 

//前序線索化
public void preThreadedNodes(HeroNode node){
    if(node == null){
        return;
    }
    //先序列化自己
    if(pre != null && node.getLeft() == null){
        node.setLeft(pre);
        node.setLeftType(1);
    }

    if(pre != null && pre.getRight() == null){
        pre.setRight(node);
        pre.setRightType(1);
    }

    pre = node;
    //再序列化遞歸左子樹
    if(node.getLeftType() == 0){
        preThreadedNodes(node.getLeft());
    }
    //再遞歸序列化右子樹
    if(node.getRightType() == 0){
        preThreadedNodes(node.getRight());
    }
}
//前序序列化周遊
public void preThreadedList(){
    if(root == null){
        System.out.println("線索化二叉樹為空");
        return;
    }
    HeroNode node = root;
    while(node != null){
        System.out.println(node);
        while(node.getLeftType() == 0){
            node = node.getLeft();
            System.out.println(node);
        }
        while (node.getRightType() == 1) {
            node = node.getRight();
            System.out.println(node);
        }
        node = node.getRight();
    }
}
二叉樹 子節點 子樹 遞歸 線索化
上一篇: 資料結構與算法（一）
下一篇: 機器學習緒論

繼續閱讀