算法基礎(chǔ)之二叉樹(shù)

趙連江發(fā)布于2019-08-23 11:52 / 2134人閱讀

摘要：本文主要包括樹(shù)相關(guān)的算法，二叉樹(shù)結(jié)點(diǎn)基本結(jié)構(gòu)如下本文還會(huì)繼續(xù)更新。判斷是否平衡二叉樹(shù)判斷是否對(duì)稱二叉樹(shù)判斷是否完全二叉樹(shù)判斷是否滿二叉樹(shù)堆操作默認(rèn)大根堆獲取堆大小查看堆頂元素添加一個(gè)元素打印堆取出對(duì)頂元素

本文主要包括樹(shù)相關(guān)的算法，二叉樹(shù)結(jié)點(diǎn)基本結(jié)構(gòu)如下

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

本文還會(huì)繼續(xù)更新。

二叉樹(shù)的深度

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--;
    }
}

二叉樹(shù)的前序遍歷

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);
  }
}

二叉樹(shù)的中序遍歷

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);
  }
}

二叉樹(shù)的后序遍歷

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);
  }
}

二叉樹(shù)的層序遍歷

/* 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;
}

根據(jù)層序遍歷建立二叉樹(shù)

//層序的空節(jié)點(diǎn)使用 null
function Tree(arr, node, num){   //也可以通過(guò) new 調(diào)用
  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;
}

根據(jù)中序遍歷和前序遍歷重建二叉樹(shù)

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;
}

根據(jù)中序遍歷和后序遍歷重建二叉樹(shù)

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;
}

求二叉樹(shù)的最遠(yuǎn)節(jié)點(diǎn)距離

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

  function _maxDistance(curr){   //curr: 當(dāng)前節(jié)點(diǎn)；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;
  }
}

二叉樹(shù)的鏡像

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);
    }
}

二叉搜索樹(shù)轉(zhuǎn)雙向鏈表

將左子樹(shù)構(gòu)成雙向鏈表，返回的是左子樹(shù)的尾結(jié)點(diǎn)，將其連接到root的左邊；
將右子樹(shù)構(gòu)成雙向鏈表，將其追加到root結(jié)點(diǎn)之后，并返回尾結(jié)點(diǎn)；
向左遍歷返回的鏈表至頭結(jié)點(diǎn)處，即為所求雙向鏈表的首結(jié)點(diǎn)。

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;
    }
}

判斷是否平衡二叉樹(shù)

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--;
        }
    }
}

判斷是否對(duì)稱二叉樹(shù)

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);
    }
}

判斷是否完全二叉樹(shù)

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;
}

判斷是否滿二叉樹(shù)

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; // 默認(rèn)大根堆
    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];
    },
    // 添加一個(gè)元素
    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();
    },

    // 取出對(duì)頂元素
    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云服務(wù)器云服務(wù)器二叉樹(shù)算法最優(yōu)二叉樹(shù)算法圖二叉樹(shù) python二叉樹(shù)

文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請(qǐng)注明本文地址：http://systransis.cn/yun/97592.html

發(fā)表評(píng)論

登陸后可評(píng)論

0條評(píng)論

趙連江

男|高級(jí)講師

我要關(guān)注我要私信

TA的文章

TMWhost：$31.5/季/1核/2GB內(nèi)存/150GB空間/1TB流量/200Mbps-300

閱讀 1385·2021-09-13 10:25
css-doodle初認(rèn)識(shí)

閱讀 570·2019-08-30 15:53
CSS中幾種常用的選擇器

閱讀 2279·2019-08-30 15:44
《css世界》- 詳細(xì)重點(diǎn)筆記與技巧

閱讀 2041·2019-08-29 17:20
webpack4 系列教程(九): CSS Tree Shaking

閱讀 1606·2019-08-29 16:36
css3水滴效果，地圖標(biāo)記效果

閱讀 1807·2019-08-29 14:10
js放大鏡效果

閱讀 1794·2019-08-29 12:44
數(shù)據(jù)類型之字符串篇

閱讀 1176·2019-08-23 14:13

成人国产在线小视频_日韩寡妇人妻调教在线播放_色成人www永久在线观看_2018国产精品久久_亚洲欧美高清在线30p_亚洲少妇综合一区_黄色在线播放国产_亚洲另类技巧小说校园_国产主播xx日韩_a级毛片在线免费

資訊專欄INFORMATION COLUMN

上云采購(gòu)季！| 2核2G4M爆款云服務(wù)器低至59元/年，更有多臺(tái)、長(zhǎng)期優(yōu)惠，快來(lái)選購(gòu)！

算法基礎(chǔ)之二叉樹(shù)

相關(guān)文章

**JavaScript算法之二叉搜索樹(shù)**

**利用PHP實(shí)現(xiàn)常用的數(shù)據(jù)結(jié)構(gòu)之二叉樹(shù)（小白系列文章五）**

**利用PHP實(shí)現(xiàn)常用的數(shù)據(jù)結(jié)構(gòu)之二叉樹(shù)（小白系列文章六）**

**學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)與算法之二叉搜索樹(shù)**

PHPer面試必看：分門(mén)別類帶你擼《劍指Offer》之二叉樹(shù)

發(fā)表評(píng)論

0條評(píng)論

趙連江

男|高級(jí)講師

TA的文章

TMWhost：$31.5/季/1核/2GB內(nèi)存/150GB空間/1TB流量/200Mbps-300

css-doodle初認(rèn)識(shí)

CSS中幾種常用的選擇器

《css世界》- 詳細(xì)重點(diǎn)筆記與技巧

webpack4 系列教程(九): CSS Tree Shaking

css3水滴效果，地圖標(biāo)記效果

js放大鏡效果

數(shù)據(jù)類型之字符串篇

最新活動(dòng)

資訊專欄INFORMATION COLUMN

上云采購(gòu)季！| 2核2G4M爆款云服務(wù)器低至59元/年，更有多臺(tái)、長(zhǎng)期優(yōu)惠，快來(lái)選購(gòu)！

算法基礎(chǔ)之二叉樹(shù)

相關(guān)文章

發(fā)表評(píng)論

0條評(píng)論

男|高級(jí)講師

TA的文章

最新活動(dòng)

上云采購(gòu)季！| 2核2G4M爆款云服務(wù)器低至59元/年，更有多臺(tái)、長(zhǎng)期優(yōu)惠，快來(lái)選購(gòu)！