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

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)
  })

文章归类于: 码不停蹄

文章标签: #Javascript#数据结构与算法

版权声明: 自由转载-署名-非商用

18条评论

提示:

评论会在审核通过后显示在下方

昵称必填,用于展示在评论中

邮箱必填,不会公开展示,方便及时收到回复

网址选填,方便看到的人去访问,请完整填写,例如(http://www.brandhuang.com)

item.from_uname
2020-01-25 09:59
item.from_uname重庆崽儿Brand
2020-01-25 09:48

前端暂时还没打算研究这么多🌚

好吧😂

回复
item.from_uname重庆崽儿Brand
2020-01-25 09:48
item.from_uname
2020-01-24 18:33

红黑树有吗

前端暂时还没打算研究这么多🌚

回复
item.from_uname
2020-01-24 18:33

红黑树有吗

回复
item.from_unameshenlan
2020-01-19 09:26

简单易懂 留个脚印

回复
item.from_uname重庆崽儿Brand
2019-09-05 15:38
item.from_unamerepostone
2019-09-05 15:34

非技术的路过。

👏欢迎  欢迎🌚

回复
item.from_unamerepostone
2019-09-05 15:34

非技术的路过。

回复
item.from_uname三毛
2019-08-28 11:16

这个写的不错嘛🐴

回复
item.from_uname重庆崽儿Brand
2019-08-28 07:41
item.from_uname三毛
2019-08-27 11:07

大佬的 blog,比我的好看

🙉开玩笑了,反正我是跟你学到,跟不上你的步伐

回复
item.from_uname三毛
2019-08-27 11:07

大佬的 blog,比我的好看

回复
  • 1
  • 2