資料結構☞二叉搜尋樹BST

二叉查找樹（Binary Search Tree），（又：二叉搜尋樹，二叉排序樹）它可以是一棵空樹，也可以是具有下列性質的二叉樹：若它的左子樹不空，則左子樹上所有結點的值均小于它的根結點的值；若它的右子樹不空，則右子樹上所有結點的值均大于它的根結點的值；它的左、右子樹也分别為二叉排序樹。二叉搜尋樹作為一種經典的資料結構，它既有連結清單的快速插入與删除操作的特點，又有數組快速查找的優勢；是以應用十分廣泛，例如在檔案系統和資料庫系統一般會采用這種資料結構進行高效率的排序與檢索操作

樹的定義

樹由一組以邊連接配接的節點組成。公司的組織結構圖就是一個樹的例子，參見下圖

組織結構圖是用來描述一個組織的架構。在圖 10-1 中，每個方框都是一個節點，連接配接方框

的線叫做邊。節點代表了該組織中的各個職位，邊描述了各職位間的關系。比如，CIO 直

接彙報給 CEO，那麼兩者就用一條邊連接配接起來。開發經理向 CIO 彙報，也用一條邊連接配接

起來。銷售副總監和開發經理沒有直接的聯系，是以兩個節點間沒有用一條邊相連。

下圖的樹展示了更多有關樹的術語，在後續讨論中将會提到。一棵樹最上面的節點稱為

根節點，如果一個節點下面連接配接多個節點，那麼該節點稱為父節點，它下面的節點稱為子

節點。一個節點可以有 0 個、1 個或多個子節點。沒有任何子節點的節點稱為葉子節點。

沿着一組特定的邊，可以從一個節點走到另外一個與它不直接相連的節點。從一個節點到另一個節點的這一組邊稱為路徑，在圖中用虛線表示。以某種特定順序通路樹中所有的節點稱為樹的周遊。

樹可以分為幾個層次，根節點是第 0 層，它的子節點是第 1 層，子節點的子節點是第2層，以此類推。樹中任何一層的節點可以都看做是子樹的根，該子樹包含根節點的子節點，子節點的子節點等。我們定義樹的層數就是樹的深度。

這種自上而下的樹與人們的直覺相反。現實世界裡，樹的根是在底下的。在計算機科學裡，自上而下的樹則是個由來已久的習慣。事實上，計算機科學家高德納曾經試圖改變這個習慣，但沒幾個月他就發現，大多數計算機科學家都不願用自然的、自下而上的方式描述樹，于是，這件事也就隻好不了了之。最後，每個節點都有一個與之相關的值，該值有時被稱為鍵。

二叉樹和二叉查找樹

叉排序樹的查找過程和次優二叉樹類似，通常采取二叉連結清單作為二叉排序樹的存儲結構。中序周遊二叉排序樹可得到一個關鍵字的有序序列，一個無序序列可以通過構造一棵二叉排序樹變成一個有序序列，構造樹的過程即為對無序序列進行排序的過程。每次插入的新的結點都是二叉排序樹上新的葉子結點，在進行插入操作時，不必移動其它結點，隻需改動某個結點的指針，由空變為非空即可。搜尋,插入,删除的複雜度等于樹高，O(log(n))

二叉樹每個節點的子節點不允許超過兩個。通過将子節點的個數限定為 2，可以寫出高效的程式在樹中插入、查找和删除資料。

下圖展示了一棵二叉樹

當考慮某種特殊的二叉樹，比如二叉查找樹時，确定子節點非常重要。二叉查找樹是一種特殊的二叉樹，相對較小的值儲存在左節點中，較大的值儲存在右節點中。這一特性使得查找的效率很高，對于數值型和非數值型的資料，比如單詞和字元串，都是如此。

實作二叉查找樹

實作Node

二叉查找樹由節點組成，是以我們要定義的第一個對象就是 Node，該對象和連結清單類似。Node 類的定義如下：

class Node {
  constructor(key) {
    this.key = key;
    this.left = null;
    this.right = null;
  }
}

Node 對象既儲存資料，也儲存和其他節點的連結（left 和 right）。

實作BST

設根節點為目前節點。
如果待插入節點儲存的資料小于目前節點，則設新的目前節點為原節點的左節點；反
之，執行第 4 步。
如果目前節點的左節點為 null，就将新的節點插入這個位置，退出循環；反之，繼續
執行下一次循環。
設新的目前節點為原節點的右節點。
如果目前節點的右節點為 null，就将新的節點插入這個位置，退出循環；反之，繼續
有了上面的算法，就可以開始實作 BST 類了。

class BinarySearchTree {
  constructor() {
    this.root = null;
  }
  insert(key) {
    // 插入
    const newNode = new Node(key);
    if (this.root === null) {
      this.root = newNode;
    } else {
      this.insertNode(this.root, newNode);
    }
  }
  insertNode(node, newNode) {
    if (newNode.key < node.key) {
      if (node.left === null) {
        node.left = newNode;
      } else {
        this.insertNode(node.left, newNode);
      }
    } else {
      if (node.right === null) {
        node.right = newNode;
      } else {
        this.insertNode(node.right, newNode);
      }
    }
  }
}

增加中序、先序和後序周遊

class BinarySearchTree {
  ...
  inOrderTraverse(callback) {
    // 中序查找
    this.inOrderTraverseNode(this.root, callback);
  }
  preOrderTraverse(callback) {
    // 先序查找
    this.preOrderTraverseNode(this.root, callback);
  }
  postOrderTraverse(callback) {
    // 後序查找
    this.postOrderTraverseNode(this.root, callback);
  }
  inOrderTraverseNode(node, callback) {
    if (node !== null) {
      this.inOrderTraverseNode(node.left, callback);
      callback(node.key);
      this.inOrderTraverseNode(node.right, callback);
    }
  }
  preOrderTraverseNode(node, callback) {
    if (node !== null) {
      callback(node.key);
      this.preOrderTraverseNode(node.left, callback);
      this.preOrderTraverseNode(node.right, callback);
    }
  }
  postOrderTraverseNode(node, callback) {
    if (node !== null) {
      this.postOrderTraverseNode(node.left, callback);
      this.postOrderTraverseNode(node.right, callback);
      callback(node.key);
    }
  }
}

在二叉查找樹上進行查找

查找給定值；
查找最小值；
查找最大值。

class BinarySearchTree {
  ...
  min() {
    // 最小值
    return this.minNode(this.root);
  }
  max() {
    // 最大值
    return this.maxNode(this.root);
  }
  search(key) {
    // 查找
    this.searchNode(this.root, key);
  }
  minNode(node) {
    if (node) {
      while (node && node.left !== null) {
        node = node.left;
      }
      return node.key;
    }
    return null;
  }
  maxNode(node) {
    if (node) {
      while (node && node.right !== null) {
        node = node.right;
      }
      return node.key;
    }
    return null;
  }
  searchNode(node, key) {
    if (node === null) return false;
    if (key < node.key) {
      return this.searchNode(node.left, key);
    } else if (key > node.key) {
      return this.searchNode(node.right, key);
    } else {
      return true;
    }
  }
  findMinNode(node) {
    if (node) {
      while (node && node.left !== null) {
        node = node.left;
      }
      return node.key;
    }
    return null;
  }
}

從二叉查找樹上删除節點

class BinarySearchTree {
  ...
  remove(key) {
    //移除樹節點
    this.removeNode(this.root, key);
  }
  removeNode(node, key) {
    if (node === null) return null;

    if (key < node.key) {
      node.left = this.removeNode(node.left, key);
      return node;
    } else if (key > node.key) {
      node.right = this.removeNode(node.right, key);
      return node;
    } else {
      if (node.left === null && node.right === null) {
        node = null;
        return node;
      } else if (node.left === null) {
        node = node.right;
        return node;
      } else if (node.right === null) {
        node = node.left;
        return node;
      }

      const aux = this.findMinNode(node.right);
      node.key = aux.key;
      node.right = this.removeNode(node.right, aux.key);
      return node;
    }
  }
}

完整代碼

class Node {
  constructor(key) {
    this.key = key;
    this.left = null;
    this.right = null;
  }
}

class BinarySearchTree {
  constructor() {
    this.root = null;
  }
  insert(key) {
    // 插入
    const newNode = new Node(key);
    if (this.root === null) {
      this.root = newNode;
    } else {
      this.insertNode(this.root, newNode);
    }
    console.log(this.root);
  }
  inOrderTraverse(callback) {
    // 中序查找
    this.inOrderTraverseNode(this.root, callback);
  }
  preOrderTraverse(callback) {
    // 先序查找
    this.preOrderTraverseNode(this.root, callback);
  }
  postOrderTraverse(callback) {
    // 後序查找
    this.postOrderTraverseNode(this.root, callback);
  }
  min() {
    // 最小值
    return this.minNode(this.root);
  }
  max() {
    // 最大值
    return this.maxNode(this.root);
  }
  search(key) {
    // 查找
    this.searchNode(this.root, key);
  }
  remove(key) {
    //移除樹節點
    this.removeNode(this.root, key);
  }
  insertNode(node, newNode) {
    if (newNode.key < node.key) {
      if (node.left === null) {
        node.left = newNode;
      } else {
        this.insertNode(node.left, newNode);
      }
    } else {
      if (node.right === null) {
        node.right = newNode;
      } else {
        this.insertNode(node.right, newNode);
      }
    }
  }
  inOrderTraverseNode(node, callback) {
    if (node !== null) {
      this.inOrderTraverseNode(node.left, callback);
      callback(node.key);
      this.inOrderTraverseNode(node.right, callback);
    }
  }
  preOrderTraverseNode(node, callback) {
    if (node !== null) {
      callback(node.key);
      this.preOrderTraverseNode(node.left, callback);
      this.preOrderTraverseNode(node.right, callback);
    }
  }
  postOrderTraverseNode(node, callback) {
    if (node !== null) {
      this.postOrderTraverseNode(node.left, callback);
      this.postOrderTraverseNode(node.right, callback);
      callback(node.key);
    }
  }
  minNode(node) {
    if (node) {
      while (node && node.left !== null) {
        node = node.left;
      }
      return node.key;
    }
    return null;
  }
  maxNode(node) {
    if (node) {
      while (node && node.right !== null) {
        node = node.right;
      }
      return node.key;
    }
    return null;
  }
  searchNode(node, key) {
    if (node === null) return false;
    if (key < node.key) {
      return this.searchNode(node.left, key);
    } else if (key > node.key) {
      return this.searchNode(node.right, key);
    } else {
      return true;
    }
  }
  removeNode(node, key) {
    if (node === null) return null;

    if (key < node.key) {
      node.left = this.removeNode(node.left, key);
      return node;
    } else if (key > node.key) {
      node.right = this.removeNode(node.right, key);
      return node;
    } else {
      if (node.left === null && node.right === null) {
        node = null;
        return node;
      } else if (node.left === null) {
        node = node.right;
        return node;
      } else if (node.right === null) {
        node = node.left;
        return node;
      }

      const aux = this.findMinNode(node.right);
      node.key = aux.key;
      node.right = this.removeNode(node.right, aux.key);
      return node;
    }
  }
  findMinNode(node) {
    if (node) {
      while (node && node.left !== null) {
        node = node.left;
      }
      return node.key;
    }
    return null;
  }
}

資料結構☞二叉搜尋樹BST

樹的定義

二叉樹和二叉查找樹

實作二叉查找樹

實作Node

實作BST

增加中序、先序和後序周遊

在二叉查找樹上進行查找

從二叉查找樹上删除節點

完整代碼

繼續閱讀

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

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裝置模型（中）之上層容器