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

发表于 阅读次数：

Javascript版数据结构与算法学习

1、树

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

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

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

2、二叉树

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

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

二叉树的遍历分为：

  • 前序遍历：先访问父节点本身，再访问左子节点，最后访问右子节点
  • 中序遍历：先访问左子节点，再访问父节点本身，最后访问右子节点（输出结果是升序的）
  • 后序遍历：先访问左子节点，再访问右子节点，最后访问父节点本身

树的层数称为「树的深度」

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

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

3、js构建以一颗二叉树

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

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

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

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

3.1 创建一个二叉树对象

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

1
2
3
4
5
6
7
8
function binaryTree(){
    let Node = function (key){
        this.key = key      // 节点值
        this.left = null    // 该节点的左节点
        this.right = null   // 该节点的右节点
    }
    let root = null         // 根结点，初始值为null
}

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

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
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 构建一个二叉树

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

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

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

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

感谢你的阅读

完整代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
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)
  })