算法基础之二叉树

赵连江发布于2019-08-23 11:52 / 2115人阅读

摘要：本文主要包括树相关的算法，二叉树结点基本结构如下本文还会继续更新。判断是否平衡二叉树判断是否对称二叉树判断是否完全二叉树判断是否满二叉树堆操作默认大根堆获取堆大小查看堆顶元素添加一个元素打印堆取出对顶元素

本文主要包括树相关的算法，二叉树结点基本结构如下

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二叉树

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/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