二叉树的顺序插入

forsigner 发布于2019-08-21 17:08 / 913人阅读

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

模拟过程

插入根节点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))

私有云 idc机房托管二叉树的遍历二叉树的存储二叉树的存储结构 java二叉树的构建

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

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

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

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

muddyway 2019-08-16 11:15 评论0 收藏0
数据结构与算法:二叉树算法

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

Little_XM 2019-08-22 11:09 评论0 收藏0
树及其外部存储

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

_Dreams 2019-08-15 15:58 评论0 收藏0
基础数据结构和算法概念

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

fsmStudy 2019-08-23 11:52 评论0 收藏0