摘要:每次插入的新节点都会入列。同时,若新节点被插入到父节点的右下方,则该父节点出列。
模拟过程
插入根节点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数据结构与算法专题会不定时更新,欢迎各位读者监督。本篇主要介绍二叉树的概念、二叉树的表示、二叉树的操作(三种遍历...
摘要:因此,根据题目给出的先序遍历和中序遍历,可以画出二叉树选参考数据结构与算法描述实现二叉树算法浅谈数据结构二叉树慕课网实现二叉树算法前端树控件腾讯软件开发面试题 内容衔接上一章 数据结构与算法:常见排序算法 内容提要 什么是树 - 为什么使用树 二叉树 二叉查找树 红黑树 B、B+树 堆 伸展树 树 可以点击链接感受下笔者用d3.js画的tree https://codepen...
摘要:数据结构程序数据结构算法数据结构基本概念数据的逻辑结构反映数据元素之间的关系的数据元素集合的表示。这两部分信息组成数据元素的存储映象,称为结点。 本文涉及更多的是概念,代码部分请参考之前写过的 2 篇博客 基于 Javascript 的排序算法 基于 javascript 的基本数据结构和查找算法 本文主要是基础的数据结构和算法概念,可能部分地方会涉及更高级的算法和算法,具体内容以...
阅读 3541·2021-09-24 09:48
阅读 1042·2021-09-10 10:51
阅读 3245·2019-08-30 13:03
阅读 3276·2019-08-30 12:51
阅读 1366·2019-08-30 11:22
阅读 1017·2019-08-29 18:38
阅读 2012·2019-08-29 16:41
阅读 3088·2019-08-29 15:32