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

shengguo 发布于2019-08-26 10:33 / 2764人阅读

摘要：一个节点可以有多个子节点二叉树二叉树是一种特殊的树，子节点数不超过个。以某种特定的顺序访问树中所有的节点称为树的遍历树的层数称为树的深度一个父节点的两个子节点分别称为左节点和右节点二叉查找树又称二叉排序树是一种特殊的二叉树。

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

1、树

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

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

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

2、二叉树

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

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

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

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

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

3、js构建以一颗二叉树

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

二叉树有一个父节点和左右两个子节点；

每个节点有一个值，称为节点值；

左节点的值小于父节点的值，右节点的值大于父节点值。

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

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

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

私有云服务器托管二叉树算法最优二叉树算法图二叉树的存储结构 c语言二叉树输入数据

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/106375.html

数据结构与算法:二叉树算法

摘要：因此，根据题目给出的先序遍历和中序遍历，可以画出二叉树选参考数据结构与算法描述实现二叉树算法浅谈数据结构二叉树慕课网实现二叉树算法前端树控件腾讯软件开发面试题内容衔接上一章数据结构与算法:常见排序算法内容提要什么是树　　- 为什么使用树二叉树二叉查找树红黑树Ｂ、Ｂ＋树堆伸展树树可以点击链接感受下笔者用d3.js画的tree https://codepen...

Little_XM 2019-08-22 11:09 评论0 收藏0
JavaScript 数据结构与算法之美 - 非线性表中的树、堆是干嘛用的？其数据结构是怎样的？

摘要：笔者写的数据结构与算法之美系列用的语言是，旨在入门数据结构与算法和方便以后复习。非线性表中的树堆是干嘛用的其数据结构是怎样的希望大家带着这两个问题阅读下文。其中，前中后序，表示的是节点与它的左右子树节点遍历访问的先后顺序。 showImg(https://segmentfault.com/img/bVbuvnj?w=900&h=250); 1. 前言想学好前端，先练好内功，内功不行，...

singerye 2019-08-26 10:09 评论0 收藏0
学习JavaScript数据结构与算法（四）：二叉搜索树

摘要：像刚才的这幅图，就是二叉搜索树。而我们本文要学习的内容，就是如何写一个二叉搜索树。但在二叉搜索树中，我们把节点成为键，这是术语。前端路漫漫，且行且歌的前端乐园原文链接寒假前端学习学习数据结构与算法四二叉搜索树本系列的第一篇文章: 学习JavaScript数据结构与算法（一），栈与队列第二篇文章：学习JavaScript数据结构与算法（二）：链表第三篇文章：学习JavaScript数据...

ingood 2019-08-19 17:26 评论0 收藏0
JavaScript算法之二叉搜索树

摘要：二叉搜索树的特性二叉搜索树由于其独特的数据结构，使得其无论在增删，还是查找，时间复杂度都是，为二叉树的高度。二叉搜索树的查找查找很简单，根据左子节点比该节点小，右子节点比该节点大的原则进行循环判断即可。什么是二叉树二叉树就是树的每个节点最多只能有两个子节点什么是二叉搜索树二叉搜索树在二叉树的基础上，多了一个条件，就是二叉树在插入值时，若插入值比当前节点小，就插入到左节点，否则插...

khlbat 2019-08-21 16:26 评论0 收藏0
数据结构与算法（树） --javascript语言描述

摘要：重建二叉树输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。所以先通过前序遍历找出根节点，然后将中序遍历分为左右子树两组，最后对于每个子树依次递归调用。重建二叉树输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}...

henry14 2019-08-26 11:44 评论0 收藏0