算法基礎之二叉樹

趙連江發布于2019-08-23 11:52 / 2128人閱讀

摘要：本文主要包括樹相關的算法，二叉樹結點基本結構如下本文還會繼續更新。判斷是否平衡二叉樹判斷是否對稱二叉樹判斷是否完全二叉樹判斷是否滿二叉樹堆操作默認大根堆獲取堆大小查看堆頂元素添加一個元素打印堆取出對頂元素

本文主要包括樹相關的算法，二叉樹結點基本結構如下

function TreeNode(x) {
  this.val = x;
  this.left = null;
  this.right = null;
}

本文還會繼續更新。

二叉樹的深度

function depth(pRoot){
    if(!pRoot){
        return 0;
    }

    var depth = 0;
    var currDepth = 0;
    dfs(pRoot);
    return depth;

    function dfs(node){
        if(!node){
            depth = depth > currDepth ? depth : currDepth;
            return;
        }
        currDepth++;
        dfs(node.left);
        dfs(node.right);
        currDepth--;
    }
}

二叉樹的前序遍歷

function preOrder(root){
  if(!root)
    return [];
  var result = [];
  _preOrder(root);
  return result;

  function _preOrder(node){
    result.push(node.val);
    node.left && _preOrder(node.left);
    node.right && _preOrder(node.right);
  }
}

二叉樹的中序遍歷

function inOrder(root){
  if(!root)
    return [];
  var result = [];
  _inOrder(root);
  return result;

  function _inOrder(node){
    node.left && _inOrder(node.left);
    result.push(node.val);
    node.right && _inOrder(node.right);
  }
}

二叉樹的后序遍歷

function postOrder(root){
  if(!root)
    return [];
  var result = [];
  _postOrder(root);
  return result;

  function _postOrder(node){
    node.left && _postOrder(node.left);
    node.right && _postOrder(node.right);
    result.push(node.val);
  }
}

二叉樹的層序遍歷

/* function TreeNode(x) {
    this.val = x;
    this.left = null;
    this.right = null;
} */
function printFromTopToBottom(root){
    if (!root) {
        return [];
    }
    var queue = [];
    queue.push(root);
    var result = [];

    while (queue.length) {
        var temp = queue.shift();
        result.push(temp.val);
        if (temp.left) {
            queue.push(temp.left);
        }
        if (temp.right) {
            queue.push(temp.right);
        }
    }
    return result;
}

根據層序遍歷建立二叉樹

//層序的空節點使用 null
function Tree(arr, node, num){   //也可以通過 new 調用
  if(!arr || arr.length === 0){
      return new TreeNode(null);
  }
  num = num || 1;
  node = node || new TreeNode(arr[num - 1]);

  var curr = node;
  if(num * 2 - 1 < arr.length && arr[num * 2 - 1] != null){
    curr.left = new TreeNode(arr[num * 2 - 1]);
    Tree(arr, curr.left, num * 2);
  }
  if(num * 2 < arr.length && arr[num * 2] != null){
    curr.right = new TreeNode(arr[num * 2]);
    Tree(arr, curr.right, num * 2 + 1);
  }
  return node;
}

根據中序遍歷和前序遍歷重建二叉樹

function reBuildTree_pi(pre, vin){
    if(pre.length == 0 || vin.length == 0 || pre.length !== vin.length){
        return null;
    };
    var index = vin.indexOf(pre[0]);
    var left = vin.slice(0,index);
    var right = vin.slice(index+1);
    var node = new TreeNode(vin[index]);
    node.left = reBuildTree_pi(pre.slice(1,index+1),left);
    node.right = reBuildTree_pi(pre.slice(index+1),right);
    return node;
}

根據中序遍歷和后序遍歷重建二叉樹

function reBuildTree_ip(vin, post){
    if(post.length == 0 || vin.length == 0 || vin.length !== post.length){
        return null;
    };
    var index = vin.indexOf(post.pop());
    var left = vin.slice(0,index);
    var right = vin.slice(index+1);
    var node = new TreeNode(vin[index]);
    node.left = reBuildTree_ip(left, post.slice(0,index));
    node.right = reBuildTree_ip(right, post.slice(index));
    return node;
}

求二叉樹的最遠節點距離

function maxDistance(root){     //root 二叉樹根節點；
  if(root === null) return 0;
  var max = 0;
  _maxDistance(root, max);
  return max;    //函數返回最大值

  function _maxDistance(curr){   //curr: 當前節點；max: 最大值；
    if(curr === null) return 0;
    var leftDepth = curr.left ? _maxDistance(curr.left) : 0;
    var rightDepth = curr.right ? _maxDistance(curr.right) : 0;
    if(leftDepth + rightDepth > max) max = leftDepth + rightDepth;
    return leftDepth > rightDepth ? leftDepth + 1 : rightDepth + 1;
  }
}

二叉樹的鏡像

function mirror(root){
    if(!root){
        return null;
    }
    var temp = root.left;
    root.left = root.right;
    root.right = temp;
    if(root.left){
        Mirror(root.left);
    }
    if(root.right){
        Mirror(root.right);
    }
}

二叉搜索樹轉雙向鏈表

將左子樹構成雙向鏈表，返回的是左子樹的尾結點，將其連接到root的左邊；
將右子樹構成雙向鏈表，將其追加到root結點之后，并返回尾結點；
向左遍歷返回的鏈表至頭結點處，即為所求雙向鏈表的首結點。

function convert(pRootOfTree){
    if(!pRootOfTree) {
        return null;
    }
    var lastNode = null;
    lastNode = ConvertNode(pRootOfTree);
    var head = lastNode;
    while(head && head.left) {
        head = head.left;
    }
    return head;

    function ConvertNode(node){
        if(!node){
            return;
        }
        if(node.left) {
            lastNode = ConvertNode(node.left);
        }
        node.left = lastNode;
        if(lastNode){
            lastNode.right = node;
        }
        lastNode = node;
        if(node.right){
            lastNode = ConvertNode(node.right);
        }
        return lastNode;
    }
}

判斷是否平衡二叉樹

function isBalancedTree(pRoot){
    if(!pRoot){
        return true;
    }

    var left = TreeDepth(pRoot.left);
    var right = TreeDepth(pRoot.right);
    var diff = left - right;

    if(diff > 1 || diff < -1)
        return false;

    return IsBalanced_Solution(pRoot.left) && IsBalanced_Solution(pRoot.right);

    function TreeDepth(pRoot){
        if(!pRoot){
            return 0;
        }

        var depth = 0;
        var currDepth = 0;
        dfs(pRoot);
        return depth;

        function dfs(node){
            if(!node){
                depth = depth > currDepth ? depth : currDepth;
                return;
            }
            currDepth++;
            dfs(node.left);
            dfs(node.right);
            currDepth--;
        }
    }
}

判斷是否對稱二叉樹

function isSymmetrical(pRoot){
    if(!pRoot){
      return true;
    }
    return symmetrical(pRoot, pRoot);

    function symmetrical(node1,node2){
        if(!node1 && !node2)
            return true;
        if(!node1 || !node2)
            return false;
        if(node1.val != node2.val)
            return false;
        return symmetrical(node1.left, node2.right) && symmetrical(node1.right, node2.left);
    }
}

判斷是否完全二叉樹

function isPrefectTree(root){
  if(!root)
    return true;
  var que = [];
  que.push(root);
  var curr;
  while(curr = que.shift()){
    que.push(curr.left);
    que.push(curr.right);
  }
  while (que.length > 0){
    if (que.pop())
      return false;
  }
  return true;
}

判斷是否滿二叉樹

function isFullTree(root){
  if(!root)
    return true;
  var que = [];
  que.push(root);
  var curr;
  var nodeNum = 0;

  while(curr = que.shift()){
    que.push(curr.left);
    que.push(curr.right);
    nodeNum++;
  }
  while (que.length > 0){
    if (que.pop())
      return false;
  }

  return (nodeNum & (nodeNum + 1)) === 0;
}

堆操作

function Heap(isMaxHeap) {
    isMaxHeap = isMaxHeap || true; // 默認大根堆
    this.list = [];
    this.flag = isMaxHeap;
  }
  Heap.prototype = {
    constuctor: Heap,

    // 獲取堆大小
    get length() {
      return this.list.length;
    },

    // 查看堆頂元素
    peek: function () {
      if (this.list.length === 0) return;
      return this.list[0];
    },
    // 添加一個元素
    add: function (val) {
      this.list.push(val);
      var i = this.list.length - 1,
        index, parent, cur;
      while (i > 0) {
        index = (i - 1) / 2;
        parent = this.list[index];
        cur = this.list[i];
        if (this.flag === true && parent < cur) {
          this._swap(index, i);
        } else if (this.flag === false && parent > cur) {
          this._swap(index, i);
        }
        i = index;
      }
    },

    _swap: function (i, j) {
      var temp = this.list[i];
      this.list[i] = this.list[j];
      this.list[j] = temp;
    },

    // 打印堆
    show: function () {
      return this.list.join();
    },

    // 取出對頂元素
    pop: function () {
      if (this.list.length === 0) return;
      var res = this.list[0];
      this.list[0] = this.list[this.list.length - 1];
      this.list.pop();
      var len = this.list.length - 1,
        i = 0;
      var left, right;
      while (i < len) {
        left = (i << 1) + 1;
        right = (i << 1) + 2;
        var maxIndex = i;
        if (this.flag == true) {
          if (left < len && this.list[left] > this.list[maxIndex]) maxIndex = left;
          if (right < len && this.list[right] > this.list[maxIndex]) maxIndex = right;
        } else {
          if (left < len && this.list[left] < this.list[maxIndex]) maxIndex = left;
          if (right < len && this.list[right] < this.list[maxIndex]) maxIndex = right;
        }
        if (maxIndex !== i) {
          this._swap(maxIndex, i);
          i = maxIndex;
        } else break;
      }
      return res;
    }
  };

GPU云服務器云服務器二叉樹算法最優二叉樹算法圖二叉樹 python二叉樹

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

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

JavaScript算法之二叉搜索樹

摘要：二叉搜索樹的特性二叉搜索樹由于其獨特的數據結構，使得其無論在增刪，還是查找，時間復雜度都是，為二叉樹的高度。二叉搜索樹的查找查找很簡單，根據左子節點比該節點小，右子節點比該節點大的原則進行循環判斷即可。什么是二叉樹二叉樹就是樹的每個節點最多只能有兩個子節點什么是二叉搜索樹二叉搜索樹在二叉樹的基礎上，多了一個條件，就是二叉樹在插入值時，若插入值比當前節點小，就插入到左節點，否則插...

khlbat 2019-08-21 16:26 評論0 收藏0
利用PHP實現常用的數據結構之二叉樹（小白系列文章五）

摘要：回來更新一波，最近刷劍指，才又發現樹真是一個大頭，二叉樹的題目和變化運用好多啊二叉樹算法引子很多人說二叉樹沒什么卵用，我覺得是他的工資和公司讓他跨不過這個坎還有很多人學了一些樹的知識，發現也用不上，我想說的是，讀一本書體現不了這本書回來更新一波，最近刷《劍指offer》，才又發現樹真是一個大頭，二叉樹的題目和變化運用好多啊～ /** * PHP二叉樹算法 * Create...

developerworks 2019-06-27 16:27 評論0 收藏0
利用PHP實現常用的數據結構之二叉樹（小白系列文章六）

摘要：回來更新一波，最近刷劍指，才又發現樹真是一個大頭，二叉樹的題目和變化運用好多啊二叉樹算法引子很多人說二叉樹沒什么卵用，我覺得是他的工資和公司讓他跨不過這個坎還有很多人學了一些樹的知識，發現也用不上，我想說的是，讀一本書體現不了這本書回來更新一波，最近刷《劍指offer》，才又發現樹真是一個大頭，二叉樹的題目和變化運用好多啊～ /** * PHP二叉樹算法 * Create...

Cympros 2019-06-28 13:56 評論0 收藏0
學習數據結構與算法之二叉搜索樹

摘要：二叉搜索樹是二叉樹的一種，其特征是左側子節點存儲比父節點小的值，右側子節點存儲比父節點大或等于父節點的值。實現和這個兩個方法其實挺簡單的，最小的節點就在二叉搜索樹的最左反之，最大的就在最右。本系列所有文章：第一篇文章：學習數據結構與算法之棧與隊列第二篇文章：學習數據結構與算法之鏈表第三篇文章：學習數據結構與算法之集合第四篇文章：學習數據結構與算法之字典和散列表第五篇文章：學習數據結構...

denson 2019-08-21 11:54 評論0 收藏0
PHPer面試必看：分門別類帶你擼《劍指Offer》之二叉樹

摘要：例如輸入前序遍歷序列和中序遍歷序列，則重建二叉樹并返回。操作給定的二叉樹，將其變換為源二叉樹的鏡像。劍指中還有一道類似的變種題目，就是下面的這道，之字形遍歷二叉樹。最后下面的兩道題目分別運用了二叉樹先序中序遍歷算法。開篇以下內容可能偏應試但很好理解，所以大家一定要堅持看下去，因為我們變強的過程注定孤獨的，堅持下來就會看到明天的太陽。回顧 showImg(https://user-...

li21 2019-07-01 10:26 評論0 收藏0