二叉树-js(1.基础知识与基本操作)：

树的作用：

数组的查找性能为O(1),插入删除为O(n)

链表的查找性能为O(n),插入删除为O(1)

树是数组与链表之间一个折中的办法：查找性能为O(logn)，插入删除性能为O(logn)

二叉树的作用：

二叉树的前序遍历可以用来显示目录结构等；中序遍历可以实现表达式树，在编译器底层很有用；后序遍历可以用来实现计算目录内的文件及其信息等。

熟练使用二叉树在很多时候可以提升程序的运行效率，减少代码量，使程序更易读。

二叉树不仅是一种数据结构，也是一种编程思想。学好二叉树是程序员进阶的一个必然进程。

二叉树基本概念：

完全二叉树：所有叶子节点都在最后一层或者倒数第二层，且最后一层的叶子节点再左边连续，倒数第二层的叶子节点在右边连续。

（从上到下，从左到右数是没有中断的。一种数据比较有规律的树）

满二叉树：每一层都是满的，节点数为2^n-1 （n为层数）

满二叉树中的数字规律：

1.每一层的个数是2^(n-1)个，总节点数为 2^n-1 n为层数 (2^0 + 2^1 +2^2 =2^3-1)

2.一个节点的位置为i，左节点位置为i*2+1,右节点位置为i*2+1

image.png

二叉树的基本操作：

二叉树的构建:(数组转二叉树)

问题来源：101. 对称二叉树

[1,2,2,3,4,4,3]

转为二叉树的结构为：

[1,2,2,null,3,null,3]

转为二叉树的结构为

利用完全二叉树叶子节点与根节点之间的数据关系：

父节点的序号为i时(从0开始)，左节点为i*2+1,右节点为i*2+2（完全二叉树可能最后一个父节点上没有右节点）

class TreeNode {
  constructor (val) {
    this.val = val
    this.left = this.right = undefined
  }
  setLeft (left) {
    this.left= left
    return this // 为了链式调用
  }
  setRight (right) {
    this.right = right
    return this // 为了链式调用
  }
}

class BinaryTree {
  constructor () {
    this.root = null
  }

  setRoot (node) {
    this.root = node
  }

  getRoot () {
    return this.root
  }

  arrayToBtree (arr) { // 从左到右广度遍历的数组，转二叉树(针对完全二叉树)
    let nodeList = arr.map(item => new TreeNode(item))
    this.setRoot(nodeList[0])
    let i = 0
    // 给存在右节点的节点添加两个节点
    for (; i * 2 + 2 < arr.length; i++) {
      let node = nodeList[i]
      // left:i*2+1  right:i*2+2
      node.setLeft(nodeList[i * 2 + 1]).setRight(nodeList[i * 2 + 2])
    }
    // 最后一个节点可能为左节点
    if (i * 2 + 1 < arr.length) {
      nodeList[i].setLeft(nodeList[i * 2 + 1])
    }
  }
}
let tree = new BinaryTree()
tree.arrayToBtree([0, 1, 2, 3, 4, 5, 6])
console.log(tree.getRoot())

遍历:

遍历的序是以根节点的位置为基准的

前序遍历：根左右

中序遍历：左根右

后序遍历：左右根

遍历是以一个子树为单位进行递归的遍历

所以上面这个二叉树的中序遍历流程为：

子树1（由于是子树所以继续递归）

节点1.1、节点1.2、节点1.3 3，1，4

子树1遍历完毕，遍历与1平级的2

节点2 0

2遍历完毕，遍历与之平级的子树3

节点3.1、3.2、3.3 5，2，6

前序：0, 1, 3, 4, 2, 5, 6

中序：3, 1, 4, 0, 5, 2, 6

后续： 3, 4, 1, 5, 6, 2, 0

 // 前序遍历 （根左右）
  preorderShow (result = []) {
    result.push(this.val)
    this.left&& this.left.preorder(result) // 如果有左节点，那么进行递归
    this.right && this.right.preorder(result)
    return result
  }

  // 中序遍历 （左根右）
  inorderShow (result = []) {
    this.left&& this.left.inorder(result)
    result.push(this.val)
    this.right && this.right.inorder(result)
    return result
  }
  // 后续遍历 （左右根）
  postorderShow (result = []) {
    this.left&& this.left.postorder(result)
    this.right && this.right.postorder(result)
    result.push(this.val)
    return result
  }

查找：

  // 前序查找
  preorderSearch (val) {
    if (this.val === val) { // 根节点找到
      return this
    }
    let target = null
    target = this.left&& this.left.preorderSearch(val) // 左子树可能找到，可能没找到
    if (target !== undefined) {
      return target
    } else { // 左子树没找到找右子树
      return this.right && this.right.preorderSearch(val)
    }
  }
  // 中序查找
  inorderSearch (val) {
    let target = null
    target = this.left&& this.left.inorderSearch(val) // 左子树可能找到，可能没找到
    if (target !== undefined) {
      return target
    } else {
      if (this.val === val) { // 左子树没找到找根节点
        return this
      } else { // 根节点没找到找右子树
        return this.right && this.right.inorderSearch(val)
      }
    }
  }
  // 后续查找
  postOrderSearch (val) {
    let target = null
    target = this.left&& this.left.postOrderSearch(val) // 左子树可能找到，可能没找到
    if (target !== undefined) {
      return target
    } else {
      target = this.right && this.right.postOrderSearch(val) // 左子树没找到找右子树
      if (target !== undefined) {
        return target
      } else if (this.val === val) { // 右子树没找到找根节点
        return this
      }
    }
  }

删除：

删除一个节点就是将父节点对它的指向设置为undefined

所以在寻找节点并删除的遍历过程中，遍历父节点，判断父节点中是否有子节点需要删除

边界值：根节点没有父节点

只有在树中可以判断一个节点是否为根节点，所以对根节点的删除在树中处理。

BinaryTree：

delete (val) {
    if (this.root === val) {
      this.root = null
    } else {
      this.root.delete(val)
    }
  }

TreeNode:

 delete (val) {
    if (this.left&& this.left.val === val) {
      this.left= undefined
      return
    }
    if (this.right && this.right.val === val) {
      this.right = undefined
      return
    }
    this.left&& this.left.delete(val)
    this.right && this.right.delete(val)
  }

leetcode二叉树的对称：

根节点：判断左右两个子树是否对称

非根节点：对比两个子树是否对称，一层一层的递归判，判断根节点是否相等，再判断A1.left,与A2.right的子树是否对称。

当两棵树的根节点值不相等即可判断为不对称，终止递归

初步思路伪代码：

function isMirror(A1,A2) {
    if(A1.val!== A2.val) { return false }
    ......
    return isMirror(A1.left,A2.right) && isMirror(A1.right,A2.left)
}

改写前序遍历:

之前的前序遍历是写在TreeNode中,递归的终止条件是.left或者.right为空

class TreeNode {
    .
    .
    .
  preorderShow (result = []) {
    result.push(this.val)
    this.left && this.left.preorderShow(result)
    this.right && this.right.preorderShow(result)
    return result
  }
}

改写之后，TreeNode自身没有遍历方法，而是将TreeNode作为参数,此时的递归终止条件为传入的treeNode为空

function preorderShow (treeNode, result = []) {
  if (!treeNode) { return result }
  result.push(treeNode.val)
  preorderShow(treeNode.left, result)
  preorderShow(treeNode.right, result)
  return result
}

所以根据之前的思路以及第2种遍历方法的思想：判断两棵树相等的递归终止条件为两棵树都为空

判断两棵树不等的递归终止条件有有一颗为空，或都不为空但是值不相等

所以题解：

function isMirror (A1, A2) {
  if (A1 == null && A2 == null) { return true }
  if ((!A1 && A2) || (A1 && !A2) || A1.val !== A2.val) { return false }
  return isMirror(A1.left, A2.right) && isMirror(A1.right, A2.left)
}

var isSymmetric = function (root) {
    if(root == null) return true
  return isMirror(root.left, root.right)
}

官方java题解：

以上涉及到的所有代码：

class TreeNode {
  constructor (val) {
    this.val = val
    this.left = this.right = undefined
  }
  setLeft (left) {
    this.left = left
    return this // 为了链式调用
  }
  setRight (right) {
    this.right = right
    return this // 为了链式调用
  }
  // 前序遍历 （根左右）
  preorderShow (result = []) {
    result.push(this.val)
    this.left && this.left.preorderShow(result)
    this.right && this.right.preorderShow(result)
    return result
  }
  // 中序遍历 （左根右）
  inorderShow (result = []) {
    this.left && this.left.inorderShow(result)
    result.push(this.val)
    this.right && this.right.inorderShow(result)
    return result
  }
  // 后续遍历 （左右根）
  postorderShow (result = []) {
    this.left && this.left.postorderShow(result)
    this.right && this.right.postorderShow(result)
    result.push(this.val)
    return result
  }
  // 前序查找
  preorderSearch (val) {
    if (this.val === val) { // 根节点找到
      return this
    }
    let target = null
    target = this.left && this.left.preorderSearch(val) // 左子树可能找到，可能没找到
    if (target !== undefined) {
      return target
    } else { // 左子树没找到找右子树
      return this.right && this.right.preorderSearch(val)
    }
  }
  // 中序查找
  inorderSearch (val) {
    let target = null
    target = this.left && this.left.inorderSearch(val) // 左子树可能找到，可能没找到
    if (target !== undefined) {
      return target
    } else {
      if (this.val === val) { // 左子树没找到找根节点
        return this
      } else { // 根节点没找到找右子树
        return this.right && this.right.inorderSearch(val)
      }
    }
  }
  // 后续查找
  postOrderSearch (val) {
    let target = null
    target = this.left && this.left.postOrderSearch(val) // 左子树可能找到，可能没找到
    if (target !== undefined) {
      return target
    } else {
      target = this.right && this.right.postOrderSearch(val) // 左子树没找到找右子树
      if (target !== undefined) {
        return target
      } else if (this.val === val) { // 右子树没找到找根节点
        return this
      }
    }
  }
  delete (val) {
    if (this.left && this.left.val === val) {
      this.left = undefined
      return
    }
    if (this.right && this.right.val === val) {
      this.right = undefined
      return
    }
    this.left && this.left.delete(val)
    this.right && this.right.delete(val)
  }
}

class BinaryTree {
  constructor () {
    this.root = null
  }

  setRoot (node) {
    this.root = node
  }

  getRoot () {
    return this.root
  }

  arrayToBtree (arr) { // 从左到右广度遍历的数组，转二叉树(针对完全二叉树)
    let nodeList = arr.map(item => new TreeNode(item))
    this.setRoot(nodeList[0])
    let i = 0
    // 给存在右节点的节点添加两个节点
    for (; i * 2 + 2 < arr.length; i++) {
      let node = nodeList[i]
      // left:i*2+1  right:i*2+2
      node.setLeft(nodeList[i * 2 + 1]).setRight(nodeList[i * 2 + 2])
    }
    // 最后一个节点可能为左节点
    if (i * 2 + 1 < arr.length) {
      nodeList[i].setLeft(nodeList[i * 2 + 1])
    }
  }

  delete (val) {
    if (this.root === val) {
      this.root = null
    } else {
      this.root.delete(val)
    }
  }
}

let tree = new BinaryTree()
tree.arrayToBtree([0, 1, 2, 3, 4, 5, 6])
console.log(tree.getRoot())
let root = tree.getRoot()
let preorder = root.preorderShow()
console.log(preorder) // [ 0, 1, 3, 4, 2, 5, 6 ]

let inorder = root.inorderShow()
console.log(inorder) // [ 3, 1, 4, 0, 5, 2, 6 ]

let postorder = root.postorderShow()
console.log(postorder) // [ 3, 4, 1, 5, 6, 2, 0 ]

console.log(root.preorderSearch(3))
console.log(root.preorderSearch(2))

console.log(root.inorderSearch(6))
console.log(root.inorderSearch(1))

console.log(root.postOrderSearch(5))
console.log(root.postOrderSearch(1))

console.log(root.postOrderSearch(8)) // undefined

tree.delete(2)
console.log(root.preorderShow()) // [ 0, 1, 3, 4 ]

// 前序遍历
function preorderShow (treeNode, result = []) {
  if (!treeNode) { return result }
  result.push(treeNode.val)
  preorderShow(treeNode.left, result)
  preorderShow(treeNode.right, result)
  return result
}
console.log(preorderShow(root, [])) // [ 0, 1, 3, 4 ]


// 二叉树的对称
function isMirror (A1, A2) {
  if (A1 == null && A2 == null) { return true }
  if ((!A1 && A2) || (A1 && !A2) || A1.val !== A2.val) { return false }
  return isMirror(A1.left, A2.right) && isMirror(A1.right, A2.left)
}
function isSymmetric (root) {
  if (root == null) return true
  return isMirror(root.left, root.right)
}
console.log(isSymmetric(root)) // false

二叉树进阶

红黑树、线段树、搜索树、B+树、语法树、哈夫曼树

最后编辑于：2020.04.13 20:02:25

人面猴
序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
沈念sama阅读 218,284评论 6赞 506
死咒
序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
沈念sama阅读 93,115评论 3赞 395
救了他两次的神仙让他今天三更去死
文/潘晓璐我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
开封第一讲书人阅读 164,614评论 0赞 354
道士缉凶录：失踪的卖姜人
文/不坏的土叔我叫张陵，是天一观的道长。经常有香客问我，道长，这世上最难降的妖魔是什么？我笑而不...
开封第一讲书人阅读 58,671评论 1赞 293
港岛之恋（遗憾婚礼）
正文为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
茶点故事阅读 67,699评论 6赞 392
恶毒庶女顶嫁案：这布局不是一般人想出来的
文/花漫我一把揭开白布。她就那样静静地躺着，像睡着了一般。火红的嫁衣衬着肌肤如雪。梳的纹丝不乱的头发上，一...
开封第一讲书人阅读 51,562评论 1赞 305
城市分裂传说
那天，我揣着相机与录音，去河边找鬼。笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。我是一名探鬼主播，决...
沈念sama阅读 40,309评论 3赞 418
双鸳鸯连环套：你想象不到人心有多黑
文/苍兰香墨我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
开封第一讲书人阅读 39,223评论 0赞 276
万荣杀人案实录
序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
沈念sama阅读 45,668评论 1赞 314
护林员之死
正文独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋以下内容为张勋视角年9月15日...
茶点故事阅读 37,859评论 3赞 336
白月光启示录
正文我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
茶点故事阅读 39,981评论 1赞 348
活死人
序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
沈念sama阅读 35,705评论 5赞 347
日本核电站爆炸内幕
正文年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
茶点故事阅读 41,310评论 3赞 330
男人毒药：我在死后第九天来索命
文/蒙蒙一、第九天我趴在偏房一处隐蔽的房顶上张望。院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
开封第一讲书人阅读 31,904评论 0赞 22
一桩弑父案，背后竟有这般阴谋
文/苍兰香墨我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。一阵脚步声响...
开封第一讲书人阅读 33,023评论 1赞 270
情欲美人皮
我被黑心中介骗来泰国打工，没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。一个月前我还...
沈念sama阅读 48,146评论 3赞 370
代替公主和亲
正文我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
茶点故事阅读 44,933评论 2赞 355