[數據結構與算法-小白系列]第3️⃣天樹

語言: CN / TW / HK

樹的定義

數據結構中的樹結構和我們現實中的樹非常類似,學習的時候完全可以進行類比學習

數據結構中的,把現實中樹的根抽象為根結點,樹枝抽象為,樹枝的兩個端點抽象為結點,樹葉抽象為葉子結點,然後整體在整體翻轉180度,就得到了數據結構中的

除此之外,樹還有以下幾個概念高度,深度,

一圖勝過千言萬語

對着圖看文字解釋,加深理解

  • 高度 節點到葉子節點最長路徑
  • 深度 根節點到這個節點所經歷邊的個數
  • 層 深度+1

什麼是二叉樹

很好理解,每個節點 最多 有兩個"叉"的樹就是二叉樹。其中,二叉樹又分為 滿二叉樹完全二叉樹

  • 滿二叉樹

葉子節點全都在最底層,除了葉子節點之外,每個節點都有左右兩個子節點

  • 完全二叉樹

葉子節點都在最底下兩層,最後一層的葉子節點都靠左排列,並且除了最後一層,其他層的節點個數都要達到最大

一圖勝過千言萬語

其中我們把 左子樹上所有結點的數據域都小於等於根結點的數據域,右子樹上所有結點的數據域都大於等於根結點的數據域 的二叉樹稱之為二叉搜索樹

一圖勝過千言萬語

使用javascript實現二叉搜索樹

在寫代碼之前我們先分析下二叉搜索樹這種數據結構的特點如何使用編程思想表達出來

  • 首先我們需要一個創建節點的,並且每個節點都有leftright屬性及自身存放的數據key
function Node(data){
    this.key = data;
    this.left=null; // 左節點
    this.right=null; // 右節點
}

複製代碼
  • 遞歸遍歷整棵樹,找到需要插入數據對應的地方
情況1: 如果為空樹直接插入
情況2: 逐層遞歸遍歷節點,把小數插入到最左邊,大數插入到最右邊
複製代碼

開始擼代碼(註釋已給出)


function searchTree() {
  // 樹的節點
  function Node(data) {
    this.key = data;
    this.left = null;
    this.right = null;
  }
  //定義樹的根節點
  this.root = null;
  //插入方法
  searchTree.prototype.inster = function (key) {
    const newNode = new Node(key);
    // 如果是空樹,直接把當前值賦值給root
    if (this.root === null) {
      this.root = newNode;
    } else {
      this.insterNode(this.root, newNode);
    }
  };
  searchTree.prototype.insterNode = function (node, newNode) {
    // todo 遞歸查找當前數據應該在的位置
    if (newNode.key > node.key) {
      // 把新節點放到最右邊
      if (node.right === null) {
        node.right = newNode;
      } else {
        this.insterNode(node.right, newNode);
      }
    } else {
      // 把新節點放到左端
      if (node.left === null) {
        node.left = newNode;
      } else {
        this.insterNode(node.left, newNode);
      }
    }
  };
}
複製代碼

二叉搜索樹的遍歷

為什麼要遍歷?

遍歷就是為了按照某種順序獲得到全部數據,其中二叉搜索樹本身就是按照順序存儲數據的,所以遍歷二叉搜索樹更有實際意義

按照根結點的輸出位置,遍歷又大致可以分為以下幾種

  • 先序遍歷

根節點->左節點->右節點

  • 中序遍歷

左節點->根節點->右節點

  • 後序遍歷

左節點->右節點->根節點

一圖勝過千言萬語

使用javascript實現二叉搜索樹遍歷

先序遍歷

// handler用於接收處理遍歷數據的函數
  searchTree.prototype.Preorder = function (handler) {
    this.preOrderNode(this.root, handler);
  };
  searchTree.prototype.preOrderNode = function (node, handler) {
    if (node != null) {
      handler(node.key);  // 先序
      this.preOrderNode(node.left, handler);
      this.preOrderNode(node.right, handler);
    }
  };
複製代碼

中序遍歷

// handler用於接收處理遍歷數據的函數
  searchTree.prototype.Middle = function (handler) {
    this.preOrderNode(this.root, handler);
  };
  searchTree.prototype.MiddleNode = function (node, handler) {
    if (node != null) {
      this.preOrderNode(node.left, handler);
      handler(node.key); // 中序
      this.preOrderNode(node.right, handler);
    }
  };
複製代碼

後序遍歷

// handler用於接收處理遍歷數據的函數
  searchTree.prototype.After = function (handler) {
    this.preOrderNode(this.root, handler);
  };
  searchTree.prototype.AfterNode = function (node, handler) {
    if (node != null) {
      this.preOrderNode(node.left, handler);
      this.preOrderNode(node.right, handler);
      handler(node.key);  // 後序
    }
  };
複製代碼

測試

let s = new searchTree();
s.inster(10);
s.inster(8);
s.inster(7);
s.inster(6);
s.inster(12);
s.inster(14);
//中序遍歷
s.Middle(function (val) {
  console.log(val);
});
console.log(s);
複製代碼

結果

可以看出,中序遍歷正好是數據從大到小排序好的結果

理解二叉平衡樹(紅黑樹)

為什麼會有平衡二叉樹?

如果我們使用樹結構存儲這樣一組數據1,2,3,4,5,6

如果這樣的數據量非常大呢? 這時樹的深度就會變的非常深,對應的遞歸遍歷整個樹的效率就會變的比較低,所有我們需要引入平衡因子

什麼是平衡二叉樹

二叉樹中任意一個節點的左右子樹的高度相差不能大於 1 其中1可以理解為最優結果,也就是説,樹的左右節點存放的數據基本相等,這個時候可以保證樹的深度最小,效率最高

紅黑樹是怎樣做到自平衡的

首先説説紅黑樹的性質

  • 性質1:每個節點要麼是黑色,要麼是紅色。
  • 性質2:根節點是黑色。
  • 性質3:每個葉子節點是黑色。
  • 性質4:每個紅色結點的兩個子結點一定都是黑色。
  • 性質5:任意一結點到每個葉子結點的路徑都包含數量相同的黑

紅黑樹只要時刻滿足這些約束,就可以達到自平衡,其中自平衡常見的操作有變色,左旋轉,右旋轉,實現原理也比較複雜,在這裏就不進行源碼實現了

其他方法實現

上面我們實現了二叉搜索樹的插入和遍歷,還有在樹中查找一個鍵,查找最大值,最小值從樹中移除某個鍵等方法在文章中沒有實現,完整的源碼已經放到github,感興趣的可以自取研究哦

最後

吃不了學習的苦,就要吃生活的苦

如果此文對你有幫助,記得點贊關注哦💖