资讯专栏INFORMATION COLUMN

二叉树的顺序插入

forsigner / 1011人阅读

摘要:每次插入的新节点都会入列。同时,若新节点被插入到父节点的右下方,则该父节点出列。

模拟过程

插入根节点A

在父节点A的左下方插入子节点B

在父节点A的右下方插入子节点C

在父节点B的左下方插入子节点D

在父节点B的右下方插入子节点E

在父节点C的左下方插入子节点F
...

分析过程

每次插入节点需明确被插入的父节点以及被插入的位置(左右)

明确被插入的父节点

第1步中,需将A存储,因为A在第2,3步中被取出,作为插入操作的父节点
第2步中,需将B存储,因为B在第4,5步中被取出,作为插入操作的父节点
第3步中,需将C存储,因为C在第6步中被取出,作为插入操作的父节点,与此同时,A在被执行右下方的插入操作后,A不能再被插入子节点
...
第5步中,需将E存储,其在后续的操作中会被取出,作为插入操作的父节点,与此同时,B与A一样,在被执行右下方的插入操作后,B不能再被插入子节点
建个队列,将后续操作中会被取出的节点存储,不会再被取出的节点移除。每次插入的新节点都会入列。同时,若新节点被插入到父节点的右下方,则该父节点出列。

明确被插入的位置

被插入的位置可以通过插入的次数来判断,若是第1次插入,则是根节点,若是第n(n>1)次插入,n为偶,则插入左边,n为奇,则插入右边
故用个变量存储插入的次数

代码

运行环境node v8.4

function Node(value) {
  this.value = value
  this.left = null
  this.right = null
}

function BinaryTree() {
  this.root = null // 树根
  this.queue = [] // 存储会被使用的父节点
  this.insertNum = 0 // 记录插入操作的次数
}

BinaryTree.prototype.insert = function (value) {
  this.insertNum++ // 插入次数加1
    let node = new Node(value)
  if (!this.root) { // 判断根节点是否存在
    this.root = node // 插入根节点
    this.queue.push(this.root) // 新节点入列
  } else { // 插入非根节点
    let parent = this.queue[0] // 被插入的父节点
    if (!(this.insertNum % 2)) { // 通过插入次数判断左右
      parent.left = node // 插入左边
      this.queue.push(parent.left) // 新节点入列
    } else {
      parent.right = node // 插入右边
      this.queue.push(parent.right) // 新节点入列
      this.queue.shift() // 当前父节点parent 已经不可能再插入子节点,故出列
    }
  }
  return this
}

let binaryTree = new BinaryTree()
binaryTree.insert("A")
  .insert("B")
  .insert("C")
  .insert("D")
  .insert("E")
  .insert("F")

console.log(JSON.stringify(binaryTree.root, null, 4))

插入空节点

首先需要判断插入的节点是否为空节点
若是空节点,其不会作为父节点被执行插入操作,故不用入列

改进代码
BinaryTree.prototype.insert = function (value) {
  this.insertNum++ // 插入次数加1
    let node = (!value && typeof value === "object") ? null : new Node(value) // 判断是否为空节点

  if (!this.root) { // 判断根节点是否存在
    this.root = node // 插入根节点
    node && this.queue.push(this.root) // 非空节点入列
  } else { // 插入非根节点
    let parent = this.queue[0] // 被插入的父节点
    if (!(this.insertNum % 2)) { // 通过插入次数判断左右
      parent.left = node // 插入左边
      node && this.queue.push(parent.left) // 非空节点入列
    } else {
      parent.right = node // 插入右边
      node && this.queue.push(parent.right) // 非空节点入列
      this.queue.shift() // 当前父节点parent 已经不可能再插入子节点,故出列
    }
  }
  return this
}

let binaryTree = new BinaryTree()
binaryTree.insert("A")
  .insert("B")
  .insert("C")
  .insert("D")
  .insert("E")
  .insert(null)
  .insert("F")
  .insert("G")

console.log(JSON.stringify(binaryTree.root, null, 4))

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

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

相关文章

  • Java数据结构与算法——叉树及操作(包括叉树遍历)

    摘要:本篇主要介绍二叉树的概念二叉树的表示二叉树的操作三种遍历方式实现求二叉树的子树求节点的父节点二叉树高度,可能是考试中的,也可能是面试中的。通常二叉树的遍历根据根节点的遍历次序分为先根遍历中根遍历后根遍历。 声明:码字不易,转载请注明出处,欢迎文章下方讨论交流。 前言:Java数据结构与算法专题会不定时更新,欢迎各位读者监督。本篇主要介绍二叉树的概念、二叉树的表示、二叉树的操作(三种遍历...

    muddyway 评论0 收藏0
  • 数据结构与算法:叉树算法

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

    Little_XM 评论0 收藏0
  • 树及其外部存储

    摘要:切记,红黑树在旋转和颜色变换的过程中,必须遵守红黑树的几条规则。树的外部存储磁盘布局计算机中的机械磁盘是由磁头和圆盘组成,每个圆盘上划分为多个磁道,每个磁道又划分为多个扇区。 术语 showImg(https://segmentfault.com/img/bVbai3r?w=643&h=407); 根     树最顶端的节点称为根,一棵树只有一个根 父节点     每个节...

    _Dreams 评论0 收藏0
  • 基础数据结构和算法概念

    摘要:数据结构程序数据结构算法数据结构基本概念数据的逻辑结构反映数据元素之间的关系的数据元素集合的表示。这两部分信息组成数据元素的存储映象,称为结点。 本文涉及更多的是概念,代码部分请参考之前写过的 2 篇博客 基于 Javascript 的排序算法 基于 javascript 的基本数据结构和查找算法 本文主要是基础的数据结构和算法概念,可能部分地方会涉及更高级的算法和算法,具体内容以...

    fsmStudy 评论0 收藏0

发表评论

0条评论

最新活动
阅读需要支付1元查看
<