javascript二叉树
javascript中的二叉树一（binary tree）
毕业也快2年了，毕业之后就没有认真写过博客了，都是那里学习一下，这里弄一下。学习了也不做笔记，过后就忘记了。我对这种状态打从心里是讨厌的。
进入正题，今天的笔记是记录javascript二叉树的学习，是非常基本的知识加上一些自己的认识。适合想了解javascript二叉树的萌新，大神请绕路走，当然如果发现有什么理解上的错误，还望不吝赐教。
===================漂亮的分割线===================
首先说下我对二叉树的理解：
1，二叉树是由一系列有规则的节点构成
2，二叉树每一个节点可以看成为对象，必有key（节点值），可以有left（节点），right（节点）这三个属性
3，每个节点的left节点的key必定小于当前key值
4，每个节点的right节点的key必定大于当前的key值
那么假如我们要把一个数组构成二叉树，需要哪些代码？很简单，记住上面的几点，我们来一步一步把数组变成二叉树形式
一，
1，二叉树是由一系列有规则的节点构成，
2，二叉树每一个节点可以看成为对象，必有key（节点值），可以有left（节点），right（节点）这三个属性
思考： 数组的每一个值将变成二叉树的节点（先不管这个节点怎么排序），那么我们在循环数组的时候，是不是都要处理下？
答： 我定义下面一个类，到时候就可以依次实例化为节点了。看下好不好理解...
//节点类
class Node {
constructor(key) {
this.left = null
this.right = null
this.key = key
}
}
进一步解释： 当循环数组的时候，就可以把每一个数组项，实例化为节点，类似这样new Node(数组Item)
二，
3，每个节点的left节点的key必定小于当前key值
4，每个节点的right节点的key必定大于当前的key值
这2点是生成二叉树的规则。那我们是不是应该有一个二叉树类呢？
//二叉树类
class BinaryTree{ }
思考： 二叉树类要哪些东西呢？补充类看下是不是应该这些
//二叉树类
class BinaryTree {
constructor() {
this.root = null //二叉树根节点
}
insert (key) { //插入节点的方法
}
}
解释： 每一个二叉树实例应该都有一个根节点，然后暴露一个可以插入节点的方法（先不管插入规则，后续讲解）
接下来就是重点了： 如何实现插入逻辑能实现上面3,4两点规则呢？
第一点：我们要确定一个根节点，然后在根节点基础上实现二分法
完善insert方法如下：
class BinaryTree {
constructor() {
this.root = null
}
insert (key) {
const newNode = new Node(key) // 这里也可以在数组那里执行，但这里可以避免多次实例操作
if (this.root === null) {
this.root = newNode
} else {
this.inOrderTraversNode(this.root, newNode)
}
}
inOrderTraversNode (node, newNode) {
}
}
解释：当调用insert方法的时候都先确定root的值，然后在根节点为入口进行二分。inOrderTraversNode方法就负责二分法。
思考： inOrderTraversNode方法怎么样实现二分法？
答： 该方法为一个递归方法。功能为：有2个参数，一个是当前已经存在的节点，后一个是要插入的新节点，就是把新节点插入到当前节点的正确的（左节点或者右节点）位置。
比如：当根节点确定之后，调用该方法插入一个新左节点，此时形成了2个节点的二叉树。此时若又一个左节点需要插入，我们就能可以递归调用该方法实现了。
//二叉树类
class BinaryTree {
constructor() {
this.root = null
}
insert (key) {
const newNode = new Node(key)
if (this.root === null) {
this.root = newNode
} else {
this.inOrderTraversNode(this.root, newNode)
}
}
inOrderTraversNode (node, newNode) {
if (newNode.key < node.key) { // 左插
if (node.left === null) {
node.left = newNode
}else{
this.inOrderTraversNode(node.left, newNode)
}
} else { // 右插
if (node.right === null) {
node.right = newNode
} else {
this.inOrderTraversNode(node.right, newNode)
}
}
}
}
所有代码在这里，可以好好理解下
const node = [8, 1, 3, 10, 12, 6, 13, 15, 18, 7] //节点类
class Node {
constructor(key) {
this.left = null
this.right = null
this.key = key
}
} //二叉树类
class BinaryTree {
constructor() {
this.root = null
}
insert (key) {
const newNode = new Node(key)
if (this.root === null) {
this.root = newNode
} else {
this.inOrderTraversNode(this.root, newNode)
}
}
inOrderTraversNode (node, newNode) {
if (newNode.key < node.key) { // 左插
if (node.left === null) {
node.left = newNode
}else{
this.inOrderTraversNode(node.left, newNode)
}
} else { // 右插
if (node.right === null) {
node.right = newNode
} else {
this.inOrderTraversNode(node.right, newNode)
}
}
}
} const binaryTree = new BinaryTree()
node.map(function(item) {
binaryTree.insert(item)
}) console.log(binaryTree.root)
最新文章
- 绿色版的Linux.NET——“Jws.Mono”(续)
- SOA面向服务架构简述
- 在VMware的虚拟机平台上如何进行网络设置
- PySpark调用自定义jar包
- ubuntu14.04配置lnmp
- 在浏览器中使用jquery取得iframe中页面中指定元素的值的不同
- eclipse总是自动跳到ThreadPoolExecutor.java
- [Python]How to handle the exception in Python?
- HDU3988-Harry Potter and the Hide Story（数论-质因数分解）
- 转：web_url函数学习
- 第十一章：Python の 网络编程基础(三)
- BZOJ_2427_[HAOI2010]软件安装_tarjan+树形DP
- 一个优秀团队leader应该具备的几点素质
- Java基础——对象容器（顺序、集合、Hash）
- html5-常用的3个基本标签
- samba安装
- 一、Html5基础讲解以及五个标签
- VirtualBox安装增强工具时：Unable to install guest additions: unknown filesystem type 'iso9660'
- Java基础-面向接口编程-JDBC详解
- 002_Linux-Memory专题