二叉排序樹

Soarkey 發布于2019-08-23 14:14 / 628人閱讀

摘要：節點的構造函數默認為其初始化都是。二叉排序樹插入插入節點只要遵循一個原則就好大與就向中插入，小于就向插入。初始化數據樹現在來試試實例化一個來看看效果。

JavaScript 數據結構篇之 BST 前言

有段時間沒有寫文章了，整個人感覺變得有點懶散了，大家可不要向我一樣哦~
今天開始 seaconch 打算開始記錄 JavaScript 數據結構的學習經歷。
至此，開始。

課本：《學習JavaScript數據結構與算法 (第2版)》

術語：

BST (binary sort tree)

LST (left subtree)

RST (right subtree)

OUTLINE

特性

定義

插入

查找

最大

最小

移除

遍歷

AVL

源碼

特性

BST 有如下特性：

若 LST 不為空，則 LST 所有節點值都小于它的根節點值

若 RST 不為空，則 RST 所有節點值都大于它的根節點值

左右子樹也都是 BST

沒有重復鍵

定義

為了存儲 BST，我們先定義一個 Node 類型，存儲各個節點。

Node 節點的構造函數默認為其初始化 Subtree 都是 null。

/**
 * 節點
 */
class Node {

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

}

然后是 BST

BST 的類型我們只初始化了一個根節點 root。

/**
 * 二叉排序樹
 */
class BinarySearchTree {

  constructor() {
    this.root = null;
  }

}

插入

插入節點只要遵循一個原則就好：大與 node.key 就向 node.right 中插入，小于 node.key 就向 node.left 插入。

首先定義私有函數。

const insertNode = Symbol("insertNode");

  /**
   * 插入節點
   */
  insert(key) {

    let newNode = new Node(key);
    if (this.root === null) this.root = newNode;
    else this[insertNode](this.root, newNode);

  }

  /**
   * 插入節點
   * @param {當前節點} node 
   * @param {新節點} 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);

    }
  }

這里稍微的說明一下，之所以寫成私有函數，無非就是為了不希望外部看到這些沒必要的。

其實東西多了感覺也會亂糟糟的...

接下來為了查看一下效果，我們來寫一個初始化 BST 的函數。

我們的目標是初始化一個這樣的 BST。

/**
 * 初始化數據
 * @param {樹} tree 
 */
function initialization(tree) {

  let treeKeys = [50, 25, 13, 5, 19, 35, 28, 49, 75, 64, 56, 74, 85, 79, 99];

  treeKeys.forEach( key => tree.insert(key) )

}

現在來試試實例化一個 BST 來看看效果。

let tree = new BinarySearchTree();

initialization(tree);

console.log(tree.root);

打印效果如圖

查找

由:

若 LST 不為空，則 LST 所有節點值都小于它的根節點值

若 RST 不為空，則 RST 所有節點值都大于它的根節點值

左右子樹也都是 BST

因此我們可以相對快速的查找元素。

定義私有函數

const searchNode = Symbol("searchNode");

  /**
   * 是否存在目標 key
   */
  existKey(key) {
    return this[searchNode](this.root, key);
  }

  /**
   * 
   * @param {當前節點} node 
   * @param {key} key 
   */
  [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;
    
  }

我們的思路是這樣的：

如果要查找的 key值小于當前節點的 key值，則向 LST 繼續查找;
如果要查找的 key值大于當前節點的 key值，則向 RST 繼續查找;
如果要查找的 key值等于當前節點的 key值，則返回 true

運行效果如下：

最大值

由：

若 RST 不為空，則 RST 所有節點值都大于它的根節點值

左右子樹也都是 BST

我們可以求得最大值

很明顯是這樣的

代碼如下

定義私有函數

const maxNode = Symbol("maxNode");

  /**
   * 獲取最大節點 key
   */
  max() {
    return this[maxNode](this.root);
  }

  /**
   * 獲取最大節點 key
   * @param {節點} node 
   */
  [maxNode] (node) {

    if (node) {
    
      while (node && node.right !== null) {
      
        node = node.right;
      }
      return node.key;
    }
    return null;
  }

輸出結果為：99

最小值

獲取最小值的方法與最大值類似，只是方向變了一下

定義私有函數

const minNode = Symbol("minNode");

  /**
   * 獲取最小節點 key
   */
  min() {
    return this[minNode](this.root);
  }

  /**
   * 獲取最小節點 key
   * @param {節點} node 
   */
  [minNode] (node) {

    if (node) {
    
      while (node && node.left !== null) {
      
        node = node.left;
      }
      return node.key;
    }
    return null;
  }

運行結果自然是：5

移除

移除相對來說復雜一點，因為假如我們要移除的是一個父節點，那他們的子節點怎么辦？

當然也是有相應的應對措施的。

對于沒有 subtree 的 node 來說，只需要把他們修改為 null 即可

對于存在 subtree 的 node 來說，就要考慮所有情況分別處理

當 LST === null 時 => RST 上前來頂替待刪除節點的位置

當 RST === null 時 => LST 上前來頂替待刪除節點的位置

當 LST && RST 都不是 null 時，由 RST 中最小節點上前來頂起待刪除節點的位置

圖例說明：

1. LST 等于 null

2. RST 等于 null

3. LST 和 RST 都不等于 null

定義私有函數

const removeNode = Symbol("removeNode");
const findMinNode = Symbol("findMinNode");

  /**
   * 刪除節點
   */
  remove(key) {
    this[removeNode](this.root, key);
  }

  /**
   * 刪除節點，返回刪除后的 tree
   * @param {當前節點} node 
   * @param {key} key 
   */
  [removeNode] (node, key) {

    if (node === null) /** the tree is empty or does not have this key who you want to remove. */ return null;

    if (key < node.key) /** the key of currrent node is bigger than target key. */ {

      node.left = this[removeNode](node.left, key);
      return node;

    } else if (key > node.key) /** smaller */ {

      node.right = this[removeNode](node.right, key);
      return node;

    } else /** 相等 */ {

      if (node.left === null && node.right === null) {
        /**
         * 當前節點沒有左右節點，可以放心刪除
         */
        node = null;
        return node;
      }

      /**
       * 當前節點有一個節點，讓子節點`頂`上來
       */
      if (node.left === null) {
        
        node = node.right;
        return node

      } else if (node.right === null) {

        node = node.left;
        return node;

      }

      /**
       * 來到這里代表當前節點有兩個子節點
       */
      let aux = this[findMinNode](node.right); // 找到右節點的最小節點
      node.key = aux.key; // 把要刪除的節點的 key 覆蓋為右側最小節點 key
      node.right = this[removeNode](node.right, aux.key); // 重構 right side tree (刪除上面找到的 aux 節點)
      return node;
    }
  }

  /**
   * 返回目標節點分支下最小節點
   * @param {目標節點} node 
   */
  [findMinNode] (node) {

    while (node && node.left !== null) {
    
      node = node.left;
    }
    return node;
  }

好了，現在來一起運行一下，看一下效果吧

遍歷

遍歷 BST 一般有三種方式：

- 先序
- 中序
- 后序

seaconch 畫了 3 張圖幫助理解:

先序遍歷：

中序遍歷：

后序遍歷：

這里我們只演示中序遍歷的代碼

中序遍歷

所謂前序，中序，后序一般都是指具體操作的位置，在這里表示回調函數的位置

定義私有函數

const inOrderTraverseNode = Symbol("inOrderTraverseNode");

  /**
   * 中序遍歷，標準名稱為: `inOrderTraverse`
   */
  middleOrderTraverse(cb) {
    this[inOrderTraverseNode](this.root, cb);
  }

  /**
   * 
   * @param {當前節點} node 
   * @param {回調} cb 
   */
  [inOrderTraverseNode] (node, cb) {
    if (node !== null) {
      this[inOrderTraverseNode](node.left, cb);
      cb(node.key); // 回調在中間就是中序
      this[inOrderTraverseNode](node.right, cb);
    }
  }

結果是按照順序輸出了各個節點的 key:

AVL

Adelson-Velskii-Landi(AVL) 自平衡樹

BST 有一定的問題，比如當你添加了很多大于 root 的元素，而只添加了很少的小于 root 的元素，那么 BST 將嚴重失衡，最直觀的一個說明就是，獲取最大值的速度明顯沒有獲取最小值的速度快。

AVL 樹就是為了解決 BST 失衡的問題

AVL 在每次添加或刪除元素的時候，嘗試自平衡，使左右子樹高度差 >= 1

(hr(右子樹高度) - hl(左子樹高度) in (-1, 0, 1))

源碼

源碼如下：

/**
 * 節點
 */
class Node {

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

const insertNode = Symbol("insertNode");
const removeNode = Symbol("removeNode");
const findMinNode = Symbol("findMinNode");
const minNode = Symbol("minNode");
const maxNode = Symbol("maxNode");
const searchNode = Symbol("searchNode");
const inOrderTraverseNode = Symbol("inOrderTraverseNode");
const preOrderTraverseNode = Symbol("preOrderTraverseNode");
const postOrderTraverseNode = Symbol("postOrderTraverseNode");
/**
 * 二叉排序樹
 */
class BinarySearchTree {

  constructor() {
    this.root = null;
  }

  /**
   * 插入節點
   */
  insert(key) {

    let newNode = new Node(key);
    if (this.root === null) this.root = newNode;
    else this[insertNode](this.root, newNode);

  }

  /**
   * 插入節點
   * @param {當前節點} node 
   * @param {新節點} 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);

    }
  }

  /**
   * 刪除節點
   */
  remove(key) {
    this[removeNode](this.root, key);
  }

  /**
   * 刪除節點，返回刪除后的 tree
   * @param {當前節點} node 
   * @param {key} key 
   */
  [removeNode] (node, key) {

    if (node === null) /** the tree is empty or does not have this key who you want to remove. */ return null;

    if (key < node.key) /** the key of currrent node is bigger than target key. */ {

      node.left = this[removeNode](node.left, key);
      return node;

    } else if (key > node.key) /** smaller */ {

      node.right = this[removeNode](node.right, key);
      return node;

    } else /** 相等 */ {

      if (node.left === null && node.right === null) {
        /**
         * 當前節點沒有左右節點，可以放心刪除
         */
        node = null;
        return node;
      }

      /**
       * 當前節點有一個節點，讓子節點`頂`上來
       */
      if (node.left === null) {
        
        node = node.right;
        return node

      } else if (node.right === null) {

        node = node.left;
        return node;

      }

      /**
       * 來到這里代表當前節點有兩個子節點
       */
      let aux = this[findMinNode](node.right); // 找到右節點的最小節點
      node.key = aux.key; // 把要刪除的節點的 key 覆蓋為右側最小節點 key
      node.right = this[removeNode](node.right, aux.key); // 重構 right side tree (刪除上面找到的 aux 節點)
      return node;
    }
  }

  /**
   * 返回目標節點分支下最小節點
   * @param {目標節點} node 
   */
  [findMinNode] (node) {

    while (node && node.left !== null) {

      node = node.left;
    }
    return node;
  }

  /**
   * 獲取最小節點 key
   */
  min() {
    return this[minNode](this.root);
  }

  /**
   * 獲取最小節點 key
   * @param {節點} node 
   */
  [minNode] (node) {

    if (node) {

      while (node && node.left !== null) {

        node = node.left;
      }
      return node.key;
    }
    return null;
  }

  /**
   * 獲取最大節點 key
   */
  max() {
    return this[maxNode](this.root);
  }

  /**
   * 獲取最大節點 key
   * @param {節點} node 
   */
  [maxNode] (node) {

    if (node) {

      while (node && node.right !== null) {

        node = node.right;
      }
      return node.key;
    }
    return null;
  }

  /**
   * 是否存在目標 key
   */
  existKey(key) {
    return this[searchNode](this.root, key);
  }

  /**
   * 
   * @param {當前節點} node 
   * @param {key} key 
   */
  [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;

  }

  /**
   * 中序遍歷，標準名稱為: `inOrderTraverse`
   */
  middleOrderTraverse(cb) {
    this[inOrderTraverseNode](this.root, cb);
  }

  /**
   * 
   * @param {當前節點} node 
   * @param {回調} cb 
   */
  [inOrderTraverseNode] (node, cb) {
    if (node !== null) {
      this[inOrderTraverseNode](node.left, cb);
      cb(node.key); // 回調在中間就是中序
      this[inOrderTraverseNode](node.right, cb);
    }
  }

  preOrderTraverse(cb) {
    this[preOrderTraverseNode](this.root, cb);
  }

  /**
   * 
   * @param {*} node 
   * @param {*} cb 
   */
  [preOrderTraverseNode] (node, cb) {
    if (node !== null) {
      cb(node.key); // 回調在前
      this[preOrderTraverseNode](node.left, cb);
      this[preOrderTraverseNode](node.right, cb);
    }
  }

  postOrderTraverse(cb) {
    this[postOrderTraverseNode](this.root, cb);
  }

  /**
   * 
   * @param {*} node 
   * @param {*} cb 
   */
  [postOrderTraverseNode] (node, cb) {
    if (node !== null) {
      this[postOrderTraverseNode](node.left, cb);
      this[postOrderTraverseNode](node.right, cb);
      cb(node.key); // 回調在后
    }
  }
}


/**
 * 初始化數據
 * @param {樹} tree 
 */
function initialization(tree) {

  let treeKeys = [50, 25, 13, 5, 19, 35, 28, 49, 75, 64, 56, 74, 85, 79, 99];

  treeKeys.forEach( key => tree.insert(key) )

}

let tree = new BinarySearchTree();

initialization(tree);

// tree.preOrderTraverse(v => console.log(v));
tree.middleOrderTraverse(v => console.log(v));
// tree.postOrderTraverse(v => console.log(v));

// console.log("the min node.key is: ", tree.min());
// console.log("the max node.key is: ", tree.max());

// let tempKey = 49;
// console.log("the key of [", tempKey, "]", tree.existKey(tempKey) ? "real" : "not", "exist.");

// tree.remove(49)
// console.log("remove key [", tempKey, "]");

// console.log("the key of [", tempKey, "]", tree.existKey(tempKey) ? "real" : "not", "exist.");

continue...

GPU云服務器云服務器二叉樹排序樹規則二叉排序樹刪除二叉排序樹c語言二叉查找樹

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/100324.html

二叉樹遍歷

摘要：前言本篇文章是在二叉排序樹的基礎上進行遍歷查找與刪除結點。接下來我們根據構造的這顆二叉樹進行相應遍歷查找與刪除操作。遍歷二叉樹二叉樹的遍歷分為深度優先遍歷和廣度優先遍歷。中序遍歷二叉排序樹，得到的數組是有序的且是升序的。前言本篇文章是在二叉排序樹的基礎上進行遍歷、查找、與刪除結點。那么首先來看一下什么是二叉排序樹？二叉排序樹定義二叉排序樹，又稱二叉查找樹、二叉搜索樹。若...

aboutU 2019-08-26 13:54 評論0 收藏0
JS實現二叉排序樹

摘要：實現二叉排序樹實現二叉排序樹初始化二叉樹只接受一個數組作為參數根節點接受傳入的參數數組初始化每個樹節點當前節點的值左子樹右子樹構建二叉樹請選擇一個數組參數插入節點當前需要插入的節點根節點不存在值時插入節點到根節點當前節點的小于父節點時當 JS實現二叉排序樹 JS實現二叉排序樹 1. 初始化二叉樹 function BinaryTree (arr) { ...

sherlock221 2019-08-21 17:35 評論0 收藏0
JavaScript 數據結構與算法之美 - 非線性表中的樹、堆是干嘛用的？其數據結構是怎樣的？

摘要：筆者寫的數據結構與算法之美系列用的語言是，旨在入門數據結構與算法和方便以后復習。非線性表中的樹堆是干嘛用的其數據結構是怎樣的希望大家帶著這兩個問題閱讀下文。其中，前中后序，表示的是節點與它的左右子樹節點遍歷訪問的先后順序。 showImg(https://segmentfault.com/img/bVbuvnj?w=900&h=250); 1. 前言想學好前端，先練好內功，內功不行，...

singerye 2019-08-26 10:09 評論0 收藏0
堆排序就這么簡單

摘要：一堆排序介紹來源百度百科堆排序是指利用堆積樹堆這種數據結構所設計的一種排序算法，它是選擇排序的一種。一、堆排序介紹來源百度百科：堆排序(Heapsort)是指利用堆積樹（堆）這種數據結構所設計的一種排序算法，它是選擇排序的一種。可以利用數組的特點快速定位指定索引的元素。堆分為大根堆和小根堆，是完全二叉樹。前面我已經有二叉樹入門的文章了，當時講解的是二叉查找樹，那上面所說的完全二...

NickZhou 2019-08-19 10:43 評論0 收藏0
用JS實現數據結構----排序二叉樹

摘要：代碼實現創建一個排序二叉樹節點類根節點插入節點以上便是創建排序二叉樹的實現方式重點在于插入節點的具體實現，即注釋的代碼片段。排序二叉樹 showImg(https://segmentfault.com/img/bVbfdbp?w=1047&h=472); 如上圖為典型的排序二叉樹，左孩子的值比節點的值小，右孩子的值比節點的值大，關于具體的樹的定義及二叉樹的定義可以百度或查閱相關資料。...

ispring 2019-08-23 11:00 評論0 收藏0