Javacript二叉樹常見算法實現及快速排序求第K大值

leeon 發布于2019-08-26 12:15 / 1599人閱讀

摘要：后面也寫了幾種常見的排序算法，并用快排求第大值，另外如果之前版的作者看到的話可以留言，我會標明文章引用。

之前實習筆試的時候刷題一直用的java，也參考某篇文章寫過java版的二叉樹常見算法，因為馬上要轉正面試了，這幾天都在準備面試，就把之前的翻出來用javascript重新寫了一遍，二叉樹基本都是遞歸處理的，也比較簡單，就當做熱身。后面也寫了幾種常見的排序算法，并用快排求第K大值，另外如果之前java版的作者看到的話可以留言，我會標明文章引用。

Javacript二叉樹常見算法實現 節點構造函數和二叉樹構造函數

function Node(key) {
    this.key = key;
    this.left = null;
    this.right = null;
}
function binaryTree() {
    this.root = null;
}

插入節點生成二叉樹

binaryTree.prototype.insert = function(root, key) {
    var node = new Node(key);
    if (root === null) { //樹根節點為空則將此節點作為根節點
        this.root = node;
    } else if (node.key < root.key) { //小于左孩子節點則要么作為左子節點要么遞歸插入左部門
        if (root.left === null) {
            root.left = node;
        } else {
            this.insert(root.left, key);
        }
    } else { //大于右孩子節點則要么作為右子節點要么遞歸插入到右部分
        if (root.right === null) {
            root.right = node;
        } else {
            this.insert(root.right, key);
        }
    }
}

先序遍歷

//先序遍歷遞歸方法
binaryTree.prototype.preOrder = function(node) {
    if (node !== null) {
        console.log(node.key); //先打印當前結點
        this.inOrder(node.left); //打印左結點
        this.inOrder(node.right); //打印右結點
    }
}

//先序遍歷非遞歸方法
//首先將根節點入棧，如果棧不為空，取出節點打印key值，然后依次取右節點和左節點入棧，依次重復
binaryTree.prototype.preOrder2 = function(node) {
    let stack = [];
    stack.push(node);
    while (stack.length > 0) {
        let n = stack.pop();
        console.log(n.key);
        if (n.right != null) {
            stack.push(n.right);
        }
        if (n.left != null) {
            stack.push(n.left);
        }
    }
}

中序遍歷

//中序遍歷遞歸方法
binaryTree.prototype.inOrder = function(node) {
    if (node !== null) {
        this.inOrder(node.left);
        console.log(node.key);
        this.inOrder(node.right);
    }
}

//中序遍歷非遞歸方法
//依次取左節點入棧直到左下角節點入棧完畢，彈出節點打印key,如果該節點有右子節點，將其入棧
binaryTree.prototype.inOrder2 = function(node) {
    let stack = [];
    while (node != null || stack.length) {
        if (node != null) {
            stack.push(node);
            node = node.left;
        } else {
            let n = stack.pop();
            console.log(n.key);
            node = n.right;
        }
    }
}

后序遍歷

binaryTree.prototype.postOrder = function(node) {
    if (node !== null) {
        this.inOrder(node.left);
        this.inOrder(node.right);
        console.log(node.key);
    }
}

求樹的深度

binaryTree.prototype.treeDepth = function(node) {
    if (node === null) {
        return 0;
    }
    let left = this.treeDepth(node.left);
    let right = this.treeDepth(node.right);
    return (left > right) ? (left + 1) : (right + 1);
}

判斷兩棵樹結構是否相同

binaryTree.prototype.structCmp = function(root1, root2) {
    if (root1 == null && root2 == null) { //根節點都為空返回true
        return true;
    }
    if (root1 == null || root2 == null) { //根節點一個為空一個不為空返回false
        return false;
    }
    let a = this.structCmp(root1.left, root2.left); //都有孩子節點則遞歸判斷左邊是不是相同并且右邊也相同
    let b = this.structCmp(root1.right, root2.right);
    return a && b; //左子樹相同并且右子樹相同
}

得到第k層節點個數

binaryTree.prototype.getLevelNum = function(root, k) {
    if (root == null || k < 1) {
        return 0;
    }
    if (k == 1) {
        return 1;
    }
    return this.getLevelNum(root.left, k - 1) + this.getLevelNum(root.right, k - 1); //從左子樹角度看，根節點第k層就是相對于左子樹k-1層，把左子樹右子樹k-1層相加即可
}

求二叉樹的鏡像

binaryTree.prototype.mirror = function(node) {
    if (node == null) return;
    [node.left, node.right] = [node.right, node.left]; //交換左右子樹并依次遞歸
    this.mirror(node.left);
    this.mirror(node.right);
}

最近公共祖先節點

binaryTree.prototype.findLCA = function(node, target1, target2) {
    if (node == null) {
        return null;
    }
    if (node.key == target1 || node.key == target2) { //如果當前結點和其中一個節點相等則當前結點為公共祖先
        return node;
    }
    let left = this.findLCA(node.left, target1, target2);
    let right = this.findLCA(node.right, target1, target2);
    if (left != null && right != null) { //如果左右子樹都沒找到則目標節點分別在左右子樹，根節點為其祖先
        return node;
    }
    return (left != null) ? left : right; // 找到的話返回
}

測試用

var tree = new binaryTree();
let arr = [45, 5, 13, 3, 23, 7, 111];
arr.forEach((node) => {

tree.insert(tree.root, node);

});

var tree2 = new binaryTree();
let arr2 = [46, 6, 14, 4, 24, 8, 112];
arr2.forEach((node) => {

tree2.insert(tree2.root, node);

});

tree.preOrder(tree.root);
tree.preOrder2(tree.root);
tree2.inOrder(tree2.root);
tree.inOrder2(tree.root);
let depth = tree.treeDepth(tree.root);
console.log(depth);
let isstructCmp = tree2.structCmp(tree.root, tree2.root);
console.log(isstructCmp);
let num = tree.getLevelNum(tree.root, 4);
console.log(num);
tree.mirror(tree.root);
tree.inOrder(tree.root);
let n = tree.findLCA(tree.root, 111, 3);
console.log(n);

快速排序求第K大值 快速排序

function quickSort(array) {
  if(array.length <= 1){
      return array;
  }
  let middle = Math.floor(array.length / 2)
  let pivot = array.splice(middle, 1);
  let left =[], right = [];
  for(let i = 0; i < array.length; i++) {
      if(array[i] < pivot) {
          left.push(array[i]);
      } else {
          right.push(array[i]);
      }
      
  }
  return quickSort(left).concat(pivot, quickSort(right));
}

快速排序改進求第K大值

思想是通過快排把數組切割成左中右三部分，將K與右邊數組（當然選左邊數組也可以）長度作比較，如果右邊數組長度為K-1,則中間元素即為第K大值，如果右邊數組長度大于等于K，則第K大元素肯定在右邊，則只需要對右邊數組遞歸求K大值，如果右邊數組長度小于K-1，則第K大值在左邊，在左數組求第k-1-right.length大值即可

function getK(array, k) {
  if(array.length <= 1){
      return array;
  }
  let middle = Math.floor(array.length / 2)
  let pivot = array.splice(middle, 1);
  let left =[], right = [];
  for(let i = 0; i < array.length; i++) {
      if(array[i] < pivot) {
          left.push(array[i]);
      } else {
          right.push(array[i]);
      }
      
  }
  if(right.length == k - 1){
      return pivot;
  } else if (right.length >= k) {
      return getK(right, k);
  } else {
      return getK(left, k-right.length-1);
  }
}

另外此方法也不是最佳解法，還有一種比較好的解法是利用建立K個元素的最小堆，新元素替換堆頂元素并調整堆，最后得到的K個元素即為最大的K個元素，時間復雜度NlogK

GPU云服務器云服務器二叉樹排序樹規則二叉樹算法實現二叉樹最優二叉樹算法圖

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

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

基礎數據結構和算法概念

摘要：數據結構程序數據結構算法數據結構基本概念數據的邏輯結構反映數據元素之間的關系的數據元素集合的表示。這兩部分信息組成數據元素的存儲映象，稱為結點。本文涉及更多的是概念，代碼部分請參考之前寫過的 2 篇博客基于 Javascript 的排序算法基于 javascript 的基本數據結構和查找算法本文主要是基礎的數據結構和算法概念，可能部分地方會涉及更高級的算法和算法，具體內容以...

fsmStudy 2019-08-23 11:52 評論0 收藏0
PHP面試：說下什么是堆和堆排序？

摘要：一個常見的例子就是優先隊列，還有排序算法之一的堆排序。另外我們還將學習堆排序，并將使用實現堆。堆排序在堆排序中，我們需要用給定的值構建一個一個堆。偽代碼如下從上面的偽代碼可以看到，堆排序的第一步就是構建一個堆。堆是什么？堆是基于樹抽象數據類型的一種特殊的數據結構，用于許多算法和數據結構中。一個常見的例子就是優先隊列，還有排序算法之一的堆排序。這篇文章我們將討論堆的屬性、不同類型的堆...

twohappy 2019-07-01 10:32 評論0 收藏0
面試算法實踐與國外大廠習題指南

摘要：面試算法實踐與國外大廠習題指南翻譯自維護的倉庫，包含了在線練習算法概述與大廠習題實戰等內容。面試算法實踐與國外大廠習題指南在線練習在線面試編程數據結構鏈表即是由節點組成的線性集合，每個節點可以利用指針指向其他節點。面試算法實踐與國外大廠習題指南翻譯自 Kevin Naughton Jr. 維護的倉庫 interviews，包含了在線練習、算法概述與大廠習題實戰等內容。筆者發現正好和...

genedna 2019-08-14 17:46 評論0 收藏0