最新公告
  • 欢迎您光临起源地模板网，本站秉承服务宗旨 履行“站长”责任，销售只是起点 服务永无止境！立即加入钻石VIP
    • 10年
    专注帝国cms二次开发
    升级SVIP
    站长资源平台
    当前位置：站长学院 > 综合教程 > 人人都能看懂的数据结构 | 二叉树

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

    正文概述 掘金(时樾同学)   2021-01-11   382

    概述

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

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

    创建一棵BST（二叉查找树）

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

    需求分析

    代码实现

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

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

    插入节点需求分析

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

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

    • ①第一次进来，还是一棵空树，也就是还没有根节点；假设，现在要插入一个节点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

    搜索某个特定的节点

    代码实现

    
class BinarySearchTree {
	...
    searchNode(node, key) {
      if (node === null) return 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 === null) return 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 === null) return 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 === null) return 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]

    结尾

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


    起源地下载网 » 人人都能看懂的数据结构 | 二叉树

    常见问题FAQ

    免费下载或者VIP会员专享资源能否直接商用？
    本站所有资源版权均属于原作者所有，这里所提供资源均只能用于参考学习用，请勿直接商用。若由于商用引起版权纠纷，一切责任均由使用者承担。更多说明请参考 VIP介绍。
    提示下载完但解压或打开不了？
    最常见的情况是下载不完整: 可对比下载完压缩包的与网盘上的容量，若小于网盘提示的容量则是这个原因。这是浏览器下载的bug，建议用百度网盘软件或迅雷下载。若排除这种情况，可在对应资源底部留言，或 联络我们.。
    找不到素材资源介绍文章里的示例图片？
    对于PPT，KEY，Mockups，APP，网页模版等类型的素材，文章内用于介绍的图片通常并不包含在对应可供下载素材包内。这些相关商业图片需另外购买，且本站不负责(也没有办法)找到出处。 同样地一些字体文件也是这种情况，但部分素材会在素材包内有一份字体下载链接清单。
    模板不会安装或需要功能定制以及二次开发？
    请QQ联系我们
    掘金(时樾同学)

    掘金(时樾同学) SVIP

    分享到：

    相关推荐

    发表评论

    还没有评论，快来抢沙发吧！

    如需帝国cms功能定制以及二次开发请联系我们

    联系作者

    请选择支付方式

    ×
    迅虎支付宝
    迅虎微信
    支付宝当面付
    余额支付
    ×
    微信扫码支付 0 元