數(shù)據(jù)結(jié)構(gòu)與算法對的javaScript描述-二叉搜索樹

forrest23 發(fā)布于2019-08-21 18:24 / 1412人閱讀

摘要：定義樹以及相關(guān)概念二叉搜索樹的定義首先是二叉樹最多有兩個節(jié)點，分別是左右節(jié)點子節(jié)點的位置是確定的，變現(xiàn)為左子節(jié)點的值小于其父節(jié)點右子節(jié)點的值大于其父節(jié)點在中的描述描述的完整代碼傳送門可視化傳送門節(jié)點類樹是由節(jié)點組成的，要實現(xiàn)樹那么先要實現(xiàn)節(jié)

定義 樹以及相關(guān)概念

二叉搜索樹的定義

首先是二叉樹

最多有兩個節(jié)點，分別是左右節(jié)點

子節(jié)點的位置是確定的，變現(xiàn)為

左子節(jié)點的值小于其父節(jié)點

右子節(jié)點的值大于其父節(jié)點

BST在JS中的描述

JS描述的完整代碼傳送門
可視化BST傳送門

節(jié)點類 Node

樹是由節(jié)點組成的，要實現(xiàn)樹那么先要實現(xiàn)節(jié)點

節(jié)點的要素

data:每個節(jié)點都需要有一個數(shù)值

left:左子節(jié)點，在沒有左子節(jié)點的時候指向空對象null

right: 右子節(jié)點，在沒有右子節(jié)點的時候指向空對象null

count: 計數(shù)值，累計插入的次數(shù)，這個是非必須的，作為一個要素是為了后續(xù)處理插入重復(fù)值的問題

show: 顯示方法，展示該節(jié)點的值（和插入次數(shù)），在這里返回一個包含值（和插入次數(shù)）的對象

js的描述

class Node {
  constructor (data,
               count = 1,
               left = null,
               right = null)
  {
    // 數(shù)值
    this.data = data
    // 出現(xiàn)次數(shù)
    this.count = count
    // 左右節(jié)點指向
    this.left = left
    this.right = right
  }
  show () {
    return {
      data: this.data,
      count: this.count
    }
  }
}

BST 二叉搜索樹類 屬性

目前我們只需要一個根節(jié)點的屬性，因此一個基本的BST可以描述為:

class BST {
  constructor () {
    // 初始化跟節(jié)點為null
    this.root = null
  }
}

插入方法

我們有了一個基本的BST,這時候我們可以new一個 bst，那么我們怎么插入數(shù)據(jù)呢？這時候我們需要一個insert方法，這個方法有以下的條件：

插入的是節(jié)點，也就是上述的類Node的一個實例

如果沒有根節(jié)點，bst的根節(jié)點指向該節(jié)點

如果有根節(jié)點則向下遍歷，找到合適的位置插入該節(jié)點，遍歷規(guī)則如下圖：

帶有插入方法的BSTjs的描述如下

class BST {
  constructor () {
    // 初始化跟節(jié)點為null
    this.root = null
  }
  /**
   * 插入數(shù)據(jù)
   * @param data
   */
  insert (data) {
    let n = new Node(data, 1)
    if (this.root === null) {
      // 沒有根節(jié)點，新的樹把待插入的值作為根節(jié)點
      this.root = n
    } else {
      // 有根節(jié)點，遍歷樹直到找到合適的位置
      let current = this.root
      while (true) {
        if (data < current.data) {
          if (current.left === null) {
            current.left = n
            break
          }
          current = current.left
        } else if (data === current.data) {
          current.count += 1
          break
        } else {
          if (current.right === null) {
            current.right = n
            break
          }
          current = current.right
        }
      }
    }
  }
}

插入一組測試數(shù)據(jù)測試

let testData = [
  43,
  34,
  67,
  23,
  34,
  45,
  2,
  78,
  34
]

let bst = new BST()
console.log(JSON.stringify(bst))

for (let data of testData) {
  bst.insert(data)
}
console.log(JSON.stringify(bst))

插入數(shù)據(jù)前：

{"root":null}

插入數(shù)據(jù)后

{
    "root": {
        "data": 43,
        "count": 1,
        "left": {
            "data": 34,
            "count": 3,
            "left": {
                "data": 23,
                "count": 1,
                "left": {
                    "data": 2,
                    "count": 1,
                    "left": null,
                    "right": null
                },
                "right": {
                    "data": 28,
                    "count": 1,
                    "left": null,
                    "right": null
                }
            },
            "right": null
        },
        "right": {
            "data": 67,
            "count": 1,
            "left": {
                "data": 45,
                "count": 1,
                "left": null,
                "right": null
            },
            "right": {
                "data": 78,
                "count": 1,
                "left": null,
                "right": null
            }
        }
    }
}

插入數(shù)據(jù)之后我們是通過nodejs的logger來查看bst，事實上，我們還需要其他的遍歷方法來查看bst

BST的遍歷

遍歷二叉樹通常有三種遍歷方法，分別是中序、先序和后序，他們的遍歷路徑不一樣

中序遍歷

中序遍歷應(yīng)該是最常用的一種遍歷方法

js中的描述

/**
   * 中序遍歷
   * @param node
   */
  inOrder (node) {
    if (node !== null) {
      this.inOrder(node.left)
      console.log(`data:${node.data},count:${node.count}`)
      this.inOrder(node.right)
    }
  }

上述例子中的輸出結(jié)果

中序
data:2,count:1
data:23,count:1
data:28,count:1
data:34,count:3
data:43,count:1
data:45,count:1
data:67,count:1
data:78,count:1

路徑圖

先序遍歷

js中的描述

  /**
   * 先序遍歷
   * @param node
   */
  preOrder (node) {
    if (node !== null) {
      console.log(`data:${node.data},count:${node.count}`)
      this.preOrder(node.left)
      this.preOrder(node.right)
    }
  }

上述例子中的輸出結(jié)果

先序
data:43,count:1
data:34,count:3
data:23,count:1
data:2,count:1
data:28,count:1
data:67,count:1
data:45,count:1
data:78,count:1

路徑圖

后序遍歷

js中的描述

  /**
   * 后序遍歷
   * @param node
   */
  postOrder (node) {
    if (node !== null) {
      this.postOrder(node.left)
      this.postOrder(node.right)
      console.log(`data:${node.data},count:${node.count}`)
    }
  }

上述例子中的輸出結(jié)果

后序
data:2,count:1
data:28,count:1
data:23,count:1
data:34,count:3
data:45,count:1
data:78,count:1
data:67,count:1
data:43,count:1

路徑圖

查找

在二叉搜索樹中查找數(shù)據(jù)非常簡單

最大值與最小值

最小值為樹中的最左邊的葉子節(jié)點得到值，最大值為最右邊子節(jié)點的值

  /**
   * 查找最小值
   * @returns {CanvasPixelArray|string|Object[]|*}
   */
  getMin (node) {
    let current = node || this.root
    while (current.left !== null) {
      current = current.left
    }
    return current
  }
  
  /**
   * 查找最大值
   * @returns {CanvasPixelArray|string|Object[]|*}
   */
  getMax (node) {
    let current = node || this.root
    while (current.right !== null) {
      current = current.right
    }
    return current
  }

查找指定數(shù)據(jù)

根據(jù)數(shù)據(jù)的大小判斷向左向右查找使得查找非常有效率

  /**
   * 查找數(shù)據(jù)
   * @param data
   * @returns {*}
   */
  find (data) {
    let current = this.root,
      result = null
    while (current !== null) {
      if (data === current.data) {
        result = current
        break
      } else if (data < current.data) {
        current = current.left
      } else {
        current = current.right
      }
    }
    return result
  }

bst.getMax().data // 78
bst.getMax().count // 1
bst.getMin().data // 2
bst.getMin().count // 1

刪除數(shù)據(jù)

刪除數(shù)據(jù)其實是操作二叉搜索樹中最麻煩的一部分

我的思路如下：

待刪除節(jié)點沒有子節(jié)點：

父節(jié)點鏈向該節(jié)點的鏈接指向null

待刪除節(jié)點只有左節(jié)點或者右節(jié)點

父節(jié)點鏈向他的鏈接指向他的子節(jié)點

待刪除節(jié)點既有左節(jié)點又有右節(jié)點

用他的右子樹的最小節(jié)點取代（值和計數(shù)替代）待刪除節(jié)點

在他的右子樹中刪除右子樹中的最小節(jié)點

基于此，JS中的描述為

  /**
   * 刪除數(shù)據(jù)
   * @param data
   */
  remove ( data ) {
    this.root = this.removeDataFromNode(this.root, data)
  }
  
  /**
   * 從指定節(jié)點中刪除數(shù)據(jù)
   * @param node
   * @param data
   * @returns {*}
   */
  removeDataFromNode (node, data) {
    if (node !== null) {
      if (data === node.data) {
        if (node.left === null && node.right === null) {
        //  沒有子節(jié)點
          return null
        }
        if (node.right === null) {
        //  只有左節(jié)點
          return node.left
        }
        if (node.left === null) {
        //  只有右節(jié)點
          return node.right
        }
        // 有做節(jié)點和右節(jié)點
        // 取右節(jié)點的最小值
        let tempNode = this.getMin(node.right)
        node.data = tempNode.data
        node.count = tempNode.count
        node.right = this.removeDataFromNode(node.right, tempNode.data)
        return node
      } else if (data < node.data) {
        node.left = this.removeDataFromNode(node.left, data)
        return node
      } else {
        node.right = this.removeDataFromNode(node.right, data)
        return node
      }
    } else {
      return null
    }
  }