阅读 23

Javascript 数据结构与算法——二叉树

原文地址:www.brandhuang.com/article/156…

1、树

一棵树最上面的节点:根结点

一个节点下面连接多个节点,那个这个节点称「为父节点」,它下面的节点称为「子节点」,没有任何子节点的节点称为「叶子节点」。

一个节点可以有多个子节点

2、二叉树

二叉树是一种特殊的树,子节点数不超过「2个」。

以某种特定的顺序访问树中所有的节点称为树的遍历

树的层数称为「树的深度

一个父节点的两个子节点分别称为「左节点」和「右节点

二叉查找树」(又称二叉排序树)是一种特殊的二叉树。++相对较小的值保存在左节点中,相对较大的值保存在右节点中++

3、js构建以一颗二叉树

用代码构建二叉树前,先要在脑中不断的重复二叉树的重要特点:

  1. 二叉树有一个父节点和左右两个子节点;
  2. 每个节点有一个值,称为节点值;
  3. 左节点的值小于父节点的值,右节点的值大于父节点值。

明白了这三点,我们就可以开始写代码了

构建二叉树的完整代码请看文末

3.1 创建一个二叉树对象

创建一个二叉树对象,定义一个对象来保存节点的值和其子节点

function binaryTree(){
    let Node = function (key){
        this.key = key      // 节点值
        this.left = null    // 该节点的左节点
        this.right = null   // 该节点的右节点
    }
    let root = null         // 根结点,初始值为null
}
复制代码

3.2 创建一个构建二叉树的函数

在binaryTree中创建一个insert方法,通过insert方法向树中添加新节点

function binaryTree(){
    let Node = function (key){
        this.key = key      // 节点值
        this.left = null    // 该节点的左节点
        this.right = null   // 该节点的右节点
    }
    let root = null         // 根结点,初始值为null
    
    
    let insertNode = function(node, newNode){
        if (newNode.key < node.key) { // 如果新节点的key值小于原来节点的key值,则该新节点作为原节点的左节点加入
        if (node.left) { // 如果原节点的左节点已经存在,则继续执行insertNode方法
          insertNode(node.left, newNode)
        } else { // 如果原节点的左节点不存在,则将新节点作为原节点的左节点
          node.left = newNode
        }
      } else { // 如果新节点的key值大于原来节点的key值,则作为原节点的右节点加入
        if (node.right) {
          insertNode(node.right, newNode)
        } else {
          node.right = newNode
        }
      }
    }
    
    this.insert = function(key){
        let newNode = new Node(key)  // 插入节点时创建一个Node对象来保存节点的数据
      if (root) {
        insertNode(root, newNode) // 如果根结点已经存在,则通过insertNode方法进行插入
      } else {
        root = newNode  // 如果根结点为空,则把该节点作为根结点
      }
    }
}
复制代码

3.3 构建一个二叉树

  let nodes = [8, 3, 10, 1, 6, 14, 4, 7, 13]
  let tree = new binaryTree()
  nodes.forEach(function (key) {
    tree.insert(key)
  })
复制代码

至此,一个二叉树构建完毕

其实,只要你了解了二叉树的三个重要特点,构建一棵二叉树是不是还是比较容易的呢?

可以将代码复制到自己的文件中进行单步调试,看看执行的结果是不是和前面描述的二叉树的特点相同。

感谢你的阅读

完整代码:

function binaryTree(){
    let Node = function (key){
        this.key = key      // 节点值
        this.left = null    // 该节点的左节点
        this.right = null   // 该节点的右节点
    }
    let root = null         // 根结点,初始值为null
    
    
    let insertNode = function(node, newNode){
        if (newNode.key < node.key) { // 如果新节点的key值小于原来节点的key值,则该新节点作为原节点的左节点加入
        if (node.left) { // 如果原节点的左节点已经存在,则继续执行insertNode方法
          insertNode(node.left, newNode)
        } else { // 如果原节点的左节点不存在,则将新节点作为原节点的左节点
          node.left = newNode
        }
      } else { // 如果新节点的key值大于原来节点的key值,则作为原节点的右节点加入
        if (node.right) {
          insertNode(node.right, newNode)
        } else {
          node.right = newNode
        }
      }
    }
    
    this.insert = function(key){
        let newNode = new Node(key)  // 插入节点时创建一个Node对象来保存节点的数据
      if (root) {
        insertNode(root, newNode) // 如果根结点已经存在,则通过insertNode方法进行插入
      } else {
        root = newNode  // 如果根结点为空,则把该节点作为根结点
      }
    }
}

let nodes = [8, 3, 10, 1, 6, 14, 4, 7, 13]
  let tree = new binaryTree()
  nodes.forEach(function (key) {
    tree.insert(key)
  })

复制代码