乐趣区

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

jiezi

原文地址：http://www.brandhuang.com/article/1564967352592

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)
  })
退出移动版