使用javascript實(shí)現(xiàn)排序二叉樹（1）

Caicloud 發(fā)布于2019-08-23 11:29 / 2726人閱讀

摘要：使用實(shí)現(xiàn)排序二叉樹排序二叉樹的定義二叉樹的基礎(chǔ)上，左節(jié)點(diǎn)比父節(jié)點(diǎn)要小，右節(jié)點(diǎn)比父節(jié)點(diǎn)要大的二叉樹，叫排序二叉樹。下期內(nèi)容實(shí)現(xiàn)排序二叉樹的中序前序后續(xù)遍歷實(shí)現(xiàn)二叉樹的節(jié)點(diǎn)查找功能實(shí)現(xiàn)排序二叉樹的刪除節(jié)點(diǎn)功能應(yīng)用排序二叉樹實(shí)現(xiàn)一個(gè)小游戲

使用javascript實(shí)現(xiàn)排序二叉樹（1）

排序二叉樹的定義：二叉樹的基礎(chǔ)上，左節(jié)點(diǎn)比父節(jié)點(diǎn)要小，右節(jié)點(diǎn)比父節(jié)點(diǎn)要大的二叉樹，叫排序二叉樹。

下面直接進(jìn)入到我們的javascript代碼定義排序二叉樹的過程

/*
    分析二叉樹的結(jié)構(gòu)得出，二叉樹由節(jié)點(diǎn)構(gòu)成，每個(gè)節(jié)點(diǎn)又有自己的左右子樹。
    并且有一個(gè)根節(jié)點(diǎn)
*/
function BinaryTree(){
  var root = null; //根節(jié)點(diǎn)默認(rèn)為null
  /*
    1.節(jié)點(diǎn)類型的構(gòu)造函數(shù),默認(rèn)左右子樹都為空
  */
  function Node(key){
    this.key = key;
    this.left = null;
    this.right = null;
  }
  /*
      2.根據(jù)排序二叉樹的規(guī)律，我們定義一個(gè)插入節(jié)點(diǎn)的方法，去填充排序二叉樹。該方法是BinaryTree的一個(gè)方法，需要綁定在this上讓其他調(diào)用者能調(diào)用。而不是作為內(nèi)部方法。
  */
  this.insert = function(key){     
    var newNode = new Node(key);
    if(root === null){
       root = newNode;
    }else{
       insertNode(root,newNode)
    }
  }
  var insertNode = function(node,newNode){
    if(newNode.key < node.key){
      if(node.left === null){
         node.left = newNode;
      }else{
         insertNode(node.left,newNode)
      }
    }else{
      if(newNode.key > node.key){
        if(node.right === null){
          node.right = newNode;
        }else{
          insertNode(node.right,newNode)
        }
      }
    }
  }
}

/*
    測試：查看是否報(bào)錯(cuò)，具體的流程邏輯可以通過打斷點(diǎn)來判斷是否與自己設(shè)想的一樣。
                      8
                   7     9
                 3         12
               2   4
                     6
                   5
*/
var nodes = [8,7,3,4,6,5,2,9,12]
var binaryTree = new BinaryTree();
nodes.forEach((item)=>{
    binaryTree.insert(item)
})

通過斷點(diǎn)調(diào)試，最后得到的一個(gè)二叉樹應(yīng)該是這樣的。也是符合二叉排序樹的定義的。

重點(diǎn)

分析數(shù)據(jù)結(jié)構(gòu)的一個(gè)規(guī)律，從而能夠定義出節(jié)點(diǎn)類型中有哪些屬性

方法不要都綁定在 this 上面，因?yàn)橛行┖瘮?shù)是不需要暴露出去的，而是內(nèi)部使用的。

我覺得讓我收獲比較大的是這里的 insert 這個(gè)函數(shù)中又調(diào)用一個(gè) insertNode 的函數(shù)，因?yàn)槭聦?shí)上真正的插入節(jié)點(diǎn)是需要兩個(gè)參數(shù)的，一個(gè)父節(jié)點(diǎn)，一個(gè)要插入的節(jié)點(diǎn)。所以會(huì)需要遞歸調(diào)用，如果不依靠 insertNode 直接用 insert方法去遞歸是沒法遞歸的。因?yàn)橥獠繅焊@取不到 root 。之前還想著只用一個(gè)方法就實(shí)現(xiàn)插入遞歸，但是確實(shí)不行。

下期內(nèi)容

實(shí)現(xiàn)排序二叉樹的中序前序后續(xù) 遍歷

實(shí)現(xiàn)二叉樹的節(jié)點(diǎn)查找功能

實(shí)現(xiàn)排序二叉樹的刪除節(jié)點(diǎn)功能

應(yīng)用排序二叉樹實(shí)現(xiàn)一個(gè)小游戲