人人都能看懂的数据结构 | 二叉树

掘金开发者社区 2021-01-14 18:22
  • 本文已获得原作者的独家授权,有想转载的朋友们可以在后台联系我申请开白哦!
  • PS:欢迎掘友们向我投稿哦,被采用的文章还可以送你掘金精美周边!

概述

二叉树中的节点最多只能有两个子节点:一个是左侧子节点,另一个是右侧子节点。二叉树分两种节点:一种有子节点的节点叫作“内部节点”;一种没有子节点的叫作“叶节点”

一棵标准的二叉树就长上图那样。

创建一棵BST(二叉查找树)

二叉查找树是一颗比较特殊的二叉树,树左侧的节点必须必右侧节点小。

需求分析

节点类:每个节点都要有一个元素(key),和左右指针(left、right);二叉树类:需要一个跟节点(root),需要一个插入节点方法(insert)。

代码实现


// 节点类
class Node {
  constructor(key) {
   //需要创建的元素
    this.key = key
    //左指针
    this.left = null
    //右指针
    this.right = null
  }
}

//二叉树类
class BinarySearchTree {
  constructor() {
   // 跟节点
    this.root = null
  }
  //插入节点方法
  insert(key) {}
}

插入节点需求分析

认真看的同学,会发现上面的insert方法是还没有实现的,实现其实本不难,但是我的本意是想让大家知道为什么是这样做,而不是直接贴代码。

不清楚手机是否能看清,图片的文字,这里还是把里面的文字帖了一下。

  • ①第一次进来,还是一棵空树,也就是还没有根节点;假设,现在要插入一个节点11,但是现在还没有根节点,那么这个11就应该成为根节点

  • ②假设下一次要插入一个节点7,那么这棵树应该存在根节点了,这次插入的节点就不应该成为根节点而是成为子节点,那么它应该成为谁的子节点呢?又应该成为左节点还是右节点呢?

  • 2.1:首页,应该从根节点开始对比,现在根节点是11,而要插入的节点是7,7比11小,那么7就应该在父节点的左边,反而就在右边。

  • 2.2:(这是图上红色部分)第一种情况,假设刚好当前的树根节点没有左节点,而要插入的节点7就顺理成章成为11的左节点了。

  • 2.3:(图上绿色部分)第二种情况,假设现在根节点已经存在左节点8,那么现在要插入的节点7就不能再成为节点11的左节点了,它只能继续往下走,继续跟8对比,现在又回到了2.1步骤,只是根节点换成了8,因此,添加节点是一个递归的过程。

代码实现插入节点需求


class BinarySearchTree {
  constructor() {
    this.root = null
    this.tree = []
  }

  insert(key) {
   // 如果还没有根节点就添加根节点
    if (this.root === null) {
      this.root = new Node(key)
    } else {
      // 如果有根节点就添加左节点或者右节点
      this.insertNode(this.root, key)
    }
  }

  insertNode(node, key) {
   // 要添加的节点,比父节点小,就走添加左节点流程,反而走添加右节点流程
    if (node.key > key) {
      // 如果刚好当前节点还没有左节点,那就直接添加,否则,就让继续执行insertNode函数递归下去,直到找到合适的位置创建
      node.left === null ? node.left = new Node(key) : this.insertNode(node.left, key)
    } else {
     // 如果刚好当前节点还没有右节点,那就直接添加,否则,就让继续执行insertNode函数递归下去,直到找到合适的位置创建
      node.right === null ? node.right = new Node(key) : this.insertNode(node.right, key)
    }
  }
}

测试插入节点实例


let tree = new BinarySearchTree()

tree.insert(11)

tree.insert(7)

tree.insert(15)

tree.insert(5)

tree.insert(9)

tree.insert(13)

console.log(tree.root)

代码结构如上图

二叉树的遍历

二叉树遍历方式

中:中节点(也可以说是父节点);右:右节点;左:左节点。

  • 中序遍历:以上行顺序访问所有节点的遍历方式,也就是以从最小到最大的顺序访问所有节点;访问规则是左中右

  • 先序遍历:先访问根节点,然后以同样方式访问左子树和右子树;访问规则是中左右

  • 后序遍历:先访问叶子节点,从左子树到右子树,再到根节点;访问规则是左右中

中序遍历

按照中序遍历的规则(左中右),上面那棵树应该如何遍历?

  • ①: 第一次按照规则可以按规左中右则拆成三部分[22,10,30],[56],[81,77,92],如上图。

  • ②: 第二次拆分,第一部分还有是内部节点,还可以按照规则拆分[10,22,30],第二部分,已经是叶节点了,就不用再拆了,直接拖下来[56],第三部分,还是内部节点,还可以按照规则拆分[77,81,92],如上图。

  • ③:第二次拆分完,全部节点都成立叶节点,就不需要再继续拆下去了,所以最终的中序遍历结果为:[10, 22, 30, 56, 77, 81, 92],如上图。

  • ④:很明显这个过程是一个递归的过程。

遍历规则都理顺了,那么用代码实现就非常简单了。

代码实现


class BinarySearchTree {
 constructor() {
      ...
      // 存放遍历后的结果
      this.tree = []
    }
 ...
    // 中序遍历
    inOrderTraverseNode(node) {
      if (node !== null) {
        this.inOrderTraverseNode(node.left)
        this.tree.push(node.key)
        this.inOrderTraverseNode(node.right)
      }
    }
}

let tree = new BinarySearchTree()
tree.insert(56)
tree.insert(22)
tree.insert(81)
tree.insert(10)
tree.insert(30)
tree.insert(77)
tree.insert(92)
// 从根开始遍历
tree.inOrderTraverseNode(tree.root)
console.log(tree.tree) //[10, 22, 30, 56, 77, 81, 92]

代码实现非常简单就几行。

先序遍历

按照先序遍历的规则(中左右),想必大家如果看懂上面的中序遍历,先序遍历就是如鱼得水,唾手可及,快马加鞭,九牛一虎,勾股定理,杠杆原理...的事了。

  • ①: 第一次按照规则可以按规中左右则拆成三部分[56],[22,10,30],[81,77,92],如上图。

  • ②: 第二次拆分,第一部分,已经是叶节点了,就不用再拆了,直接拖下来[56],第二部分还有是内部节点,还可以按照规则拆分[22,10,30],第三部分,还是内部节点,还可以按照规则拆分[81,77,92],如上图。。

  • ③:第二次拆分完,全部节点都成立叶节点,就不需要再继续拆下去了,所以最终的中序遍历结果为:[56, 22, 10, 30, 81, 77, 92],如上图。

代码实现


class BinarySearchTree {
 ...
    // 先序遍历
    preOrderTraverseNode(node) {
      if (node !== null) {
        this.tree.push(node.key)
        this.preOrderTraverseNode(node.left)
        this.preOrderTraverseNode(node.right)
     }
    }
}

let tree = new BinarySearchTree()
tree.insert(56)
tree.insert(22)
tree.insert(81)
tree.insert(10)
tree.insert(30)
tree.insert(77)
tree.insert(92)
// 从根开始遍历
tree.postOrderTraverse(tree.root)
console.log(tree.tree) //[56, 22, 10, 30, 81, 77, 92]

先序遍历跟先中序遍历代码都是大同小异的。

后序遍历

如果上面的两种遍历都看懂了,那么后序遍历就是...的事了。

  • ①: 第一次按照规则可以按规左右中则拆成三部分[22,10,30],[81,77,92],[56],如上图。

  • ②: 第二次拆分,第一部分,还有是内部节点,还可以按照规则拆分[10,30,22],第二部分还是内部节点,还可以按照规则拆分[77,92,81],第三部分,已经是叶节点了,就不用再拆了,直接拖下来[56],如上图。

  • ③:第二次拆分完,全部节点都成立叶节点,就不需要再继续拆下去了,所以最终的中序遍历结果为:[10, 30, 22, 77, 92, 81, 56],如上图。

二叉树的搜索

  • 搜索最大节点

  • 搜索最小节点

  • 搜索某个节点是否存在

搜索最大节点

没错还是以这个图为例,惊喜不。

按照二叉树的规则,小值在左,大值在右。那么最大节点肯定就是在最右底脚的那个叶节点了。

代码实现


class BinarySearchTree {
 ...
    maxNode(node) {
      // 一直往右边找,直到找到最右边的叶节点
      while (node.right !== null) {
        node = node.right
      }
      return node
    }
}
...
let tree = new BinarySearchTree()

tree.maxNode(tree.tree) // 92

实现代码也非常简单。

搜索最小节点

按照二叉树的规则,小值在左,大值在右。那么最小节点肯定就是在最左底脚的那个叶节点了,刚好跟最大节点相反。

代码实现


class BinarySearchTree {
 ...
    minNode(node) {
      // 一直往左边找,直到找到最左边的叶节点
      while (node.left !== null) {
        node = node.left
      }
      return node
    }
}
...
let tree = new BinarySearchTree()

tree.minNode(tree.tree) // 10

搜索某个特定的节点

搜索某个特定的节点,也是从根节点开始,先当前节点是否跟指定节点相同,相同就返回true;不同就看指定节点比当前节点大还是小,小继续往左边找,大就往右边找,一直到找到或者为null为止。

代码实现


class BinarySearchTree {
 ...
    searchNode(node, key) {
      if (node === nullreturn false
      if (node.key === key) {
        return true
      } else {
        return node.key > key ? this.searchNode(node.left, key) : this.searchNode(node.right, key)
      }
    }
}
...
let tree = new BinarySearchTree()
// 从根开始找,指定找199,
let res = tree.searchNode(tree.root, 199)
console.log(res) // false

删除某个特定节点

为什么把删除节点放在最后呢?其实一开始不打算写这一部分的,因为这部分是比较难理解的,也不知道自己能不能描述清楚,但是写完文章之后,总觉得不加上这部分,文章不完整,缺了点什么。

节点删除有三种情况

  • ①:要删除的节点没有左右节点,这种比较好处理,直接将要删除的节点置为null,或者直接返回null

  • ②:要删除的节点左右节点有其中一个,这种情况,就要把左节点或者右节点返回给上一个父节点就行。

  • ③:要删除的节点有左右节点,这种是最复杂的情况了,首先找到要删除的节点,再找到要删除节点的右侧最小节点,或者左侧最大节点,来替换要删除的节点,最后,再把刚刚找到的那个最大节点(最小节点)删除。

代码实现



class BinarySearchTree {
  ...
  removeNode(node,key){
    if (node === nullreturn null
    if (node.key === key) {
      // 情况一
      if(node.left === null && node.right === null){
        return null
      // 情况二
      }else if(node.left === null || node.right === null){
        let key = node.left ? 'left' : 'right'
        return node[key]
      // 情况三
      }else{
        let aux =this.minNode(node.right)
        node.key = aux.key
        node.right = this.removeNode(node.right, aux.key)
        return node
      }
    } else {
      let nodeKey = node.key > key ? "left" : "right"
      node[nodeKey] = node.key > key ? this.removeNode(node.left, key) : this.removeNode(node.right, key)
      return node
    }
  }
}

完整代码


class Node {
  constructor(key) {
    this.key = key
    this.left = null
    this.right = null
  }
}

class BinarySearchTree {
  constructor() {
    this.root = null
    this.tree = []
  }

  insert(key) {
    if (this.root === null) {
      this.root = new Node(key)
    } else {
      this.insertNode(this.root, key)
    }
  }

  insertNode(node, key) {
    if (node.key > key) {
      node.left === null ? node.left = new Node(key) : this.insertNode(node.left, key)
    } else {
      node.right === null ? node.right = new Node(key) : this.insertNode(node.right, key)
    }
  }

  inOrderTraverseNode(node) {
    if (node !== null) {
      this.inOrderTraverseNode(node.left)
      this.tree.push(node.key)
      this.inOrderTraverseNode(node.right)
    }
  }

  preOrderTraverseNode(node) {
    if (node !== null) {
      this.tree.push(node.key)
      this.preOrderTraverseNode(node.left)
      this.preOrderTraverseNode(node.right)
    }
  }

  postOrderTraverse(node) {
    if (node !== null) {
      this.postOrderTraverse(node.left)
      this.postOrderTraverse(node.right)
      this.tree.push(node.key)
    }
  }

  minNode(node) {
    while (node.left !== null) {
      node = node.left
    }
    return node
  }

  maxNode(node) {
    while (node.right !== null) {
      node = node.right
    }
    return node
  }

  searchNode(node, key) {
    if (node === nullreturn false
    if (node.key === key) {
      return true
    } else {
      return node.key > key ? this.searchNode(node.left, key) : this.searchNode(node.right, key)
    }
  }
  
  removeNode(node,key){
    if (node === nullreturn null
    if (node.key === key) {
      if(node.left === null && node.right === null){
        return null
      }else if(node.left === null || node.right === null){
        let key = node.left ? 'left' : 'right'
        return node[key]
      }else{
        let aux =this.minNode(node.right)
        node.key = aux.key
        node.right = this.removeNode(node.right, aux.key)
        return node
      }
    } else {
      let nodeKey = node.key > key ? "left" : "right"
      node[nodeKey] = node.key > key ? this.removeNode(node.left, key) : this.removeNode(node.right, key)
      return node
    }
  }

}


重组二叉树

重组二叉树什么意思?也就是说现在不是给你一颗二叉树,让你找出它的先、中、后序遍历了,而是给你先,中,后反推成一颗二叉树。

某大厂的一道面试题:根据先序[1,2,4,7,3,5,6,8]和中序[4,7,2,1,5,3,8,6],重组二叉树。

题目分析:

  • 这里说的是重组的是二叉树,不是BST(二叉查找树),所以没有小在左,大在右的概念。

  • 重组二叉树,还是可以按先,中,后的遍历规则

  • ①:先序的第一个肯定是根节点(也可以说是中,父节点)

  • ②:在中序列表找到根位置,然后根据这个位置,找出左节点和右节点的先序和中序

  • 递归①,②步,直到节点为null/undefinde。

代码实现


class Node {
  constructor(key) {
    this.key = key
    this.left = null
    this.right = null
  }
}

let preOrder = [1,2,4,7,3,5,6,8]

let inOrder = [4,7,2,1,5,3,8,6]

class regroupTree{
  constructor(){
    this.root = null
  }
  sliceTree(preOrder,inOrder){
    let node = preOrder[0]
    //  判断根节点存不存在
    if(node){
      // 找到根节点在中序列表的位置
      let index = inOrder.indexOf(node)
      // 通过根节点位置,找到左节点的中序
      let inOrderLeft = inOrder.slice(0,index)
      // 通过根节点位置,找到右节点的中序
      let inOrderRight = inOrder.slice(index+1)
      // 通过根节点位置,找到左节点的先序
      let preOrderLeft = preOrder.slice(1,index+1)
      // 通过根节点位置,找到右节点的先序
      let preOrderRight = preOrder.slice(index+1)
      let root = new Node(node)
      root.left = this.sliceTree(preOrderLeft,inOrderLeft)
      root.right = this.sliceTree(preOrderRight,inOrderRight)
      return root
    }
  }
  buildTree(preOrder,inOrder){
    this.root = this.sliceTree(preOrder,inOrder)
  }
}

let tree = new regroupTree()
tree.buildTree(preOrder,inOrder)
console.log(tree.tree)

加两个方法(先序遍历,中序遍历)验证一下


let preOrder = [1,2,4,7,3,5,6,8]

let inOrder = [4,7,2,1,5,3,8,6]

class regroupTree{
  constructor(){
   ...
    this.tree = []
  }
  ...
  inOrderTraverseNode(node) {
    if (node) {
      this.inOrderTraverseNode(node.left)
      this.tree.push(node.key)
      this.inOrderTraverseNode(node.right)
    }
  }

  preOrderTraverseNode(node) {
    if (node) {
      this.tree.push(node.key)
      this.preOrderTraverseNode(node.left)
      this.preOrderTraverseNode(node.right)
    }
  }
}

let tree = new regroupTree()
tree.buildTree(preOrder,inOrder)
tree.preOrderTraverseNode(tree.root) // [1,2,4,7,3,5,6,8]
// tree.preOrderTraverseNode(tree.root) [4,7,2,1,5,3,8,6]

结尾

看完希望你对二叉树概念,遍历规则,找最大节点,最小节点,找特点节点,删除特定节点,二叉树重组都有一个更深的理解,希望你这一趟没有白点进来🤡