快捷導(dǎo)航

JS實現(xiàn)二叉查找樹的建立以及一些遍歷方法實現(xiàn)

更新時間：2017年04月17日 09:06:49 作者：DreamFJ

本篇文章主要介紹了JS實現(xiàn)二叉查找樹的建立以及一些遍歷方法實現(xiàn)，具有一定的參考價值，感興趣的小伙伴們可以參考一下。

二叉查找樹是由節(jié)點和邊組成的。

我們可以定義一個節(jié)點類Node，里面存放節(jié)點的數(shù)據(jù)，及左右子節(jié)點，再定義一個用來顯示數(shù)據(jù)的方法：

//以下定義一個節(jié)點類
function Node(data,left,right){
  // 節(jié)點的鍵值
  this.data = data;
  // 左節(jié)點
  this.left = left;
  // 右節(jié)點
  this.right = left;
  // 顯示該節(jié)點的鍵值
  this.show = show;
}
// 實現(xiàn)show方法
function show(){
  return this.data;
}

再定義一個二叉查找樹類BST，該類中有定義樹的根節(jié)點，初始化為null，然后定義插入節(jié)點的方法，還有一邊遍歷的方法：

// 二叉查找樹BST
// 有一個節(jié)點屬性，還有一些其他的方法，以下定義一個二叉查找樹BST類
function BST(){
  // 根節(jié)點初始化為空
  this.root = null;
  // 方法
  // 插入
  this.insert = insert;
  // 中序遍歷
  this.inorder = inorder;
  // 先序遍歷
  this.preorder = preorder;
  // 后序遍歷
  this.postorder = postorder;
}

//實現(xiàn)insert插入方法
function insert(data){
  // 創(chuàng)建一個節(jié)點保存數(shù)據(jù)
  var node = new Node(data,null,null);
  // 下面將節(jié)點node插入到樹中
  // 如果樹是空的，就將節(jié)點設(shè)為根節(jié)點
  if(!this.root){
    this.root = node;
  }else{ //樹不為空
    // 判斷插在父節(jié)點的左邊還是右邊
    // 所以先要保存一下父節(jié)點
    // var parent = this.root;
    var current = this.root;
    var parent;
    // 如果要插入的節(jié)點鍵值小于父節(jié)點鍵值，則插在父節(jié)點左邊，
    // 前提是父節(jié)點的左邊為空，否則要將父節(jié)點往下移一層，
    // 然后再做判斷
    while(true){
      // data小于父節(jié)點的鍵值
      parent = current;
      if(data < parent.data){
        // 將父節(jié)點往左下移(插入左邊)
        // parent = parent.left;
        current = current.left;
        // 如果節(jié)點為空，則直接插入
        if(!current){
          // ?。?！此處特別注意，如果就這樣把parent賦值為node，也僅僅只是parent指向node，
          // 而并沒有加到父元素的左邊?。。「緵]有加到樹中去。所以要先記住父元素，再把當(dāng)前元素加入進去
          parent.left = node;
          break;
        }      
      }else{ // 將父節(jié)點往右下移(插入右邊)
        current = current.right;
        if(!current){
          parent.right = node;
          break;
        }
      }
    }

  }
} 

//實現(xiàn)inorder遍歷方法(左中右)
function inorder(node){
  if(node){
    inorder(node.left);
    console.log(node.show());
    inorder(node.right);
  }
}

// 先序遍歷(中左右)
function preorder(node){
  if(node){
    console.log(node.show());
    preorder(node.left);
    preorder(node.right);
  }
}

// 后序遍歷(左右中)
function postorder(node){
  if(node){
    preorder(node.left);
    preorder(node.right);
    console.log(node.show());
  }
}

測試：

// 后序遍歷(左右中)
function postorder(node){
  if(node){
    postorder(node.left);
    postorder(node.right);
    console.log(node.show());
  }
}

// 實例化一個BST樹
var tree = new BST();
// 添加節(jié)點
tree.insert(30);
tree.insert(14);
tree.insert(35);
tree.insert(12);
tree.insert(17);
// 中序遍歷
tree.inorder(tree.root);
// 先序遍歷
tree.preorder(tree.root);
// 后序遍歷
tree.postorder(tree.root);

結(jié)果：

中序遍歷：

中序遍歷