IMOOC
IMOOC copied to clipboard
CruxF
JavaScript实现二叉树算法
前言
这篇文章的内容几乎全部来源于慕课网教程——《JavaScript实现二叉树》，教程内容值得一看，虽然最终的游戏代码那块讲述的并不完整，然而让人基本的认知到什么是二叉树这是讲的挺不错的，下面就来看看我的一些摘抄。
为什么是JavaScript和数据结构？
JavaScript自从诞生以来，经过多年的发展，目前已经成为几乎是最流行的语言，俗称为“互联网编程语言”。他的发展越来越快，并且将触角延伸到了各个领域，几乎有一统江湖之势。
从客户端而言，特使是web应用开发上，它是当之无愧的首选，结合各种强大的开发框架，运用JavaScript可以开发出功能相当强大的web桌面应用，例如像Gmail这种完全能媲美于原生桌面程序的web应用，就是通过JavaScript开发的。
从服务器而言，原本被C++，java等老牌语言占据着不可动摇的地位，当以JavaScript为开发语言的Node.js平台诞生后，老牌语言在服务器领域的地位在不断消亡，Node.js就像野火一样，在服务器开发领域熊熊燃烧。
最后，在移动开发领域，由于React Native，或lonic等移动开发框架的出现，使得运用JavaScript就能开发出同时运行在IOS和Android平台上的移动App。由此可见，学习和使用JavaScript这门编程语言是性价比最高的。
为什么要学习数据结构？
程序=算法+数据结构，计算机程序设计的本质是将业务逻辑转换为数理逻辑，通过逻辑推理以及数理运算解决客观世界存在的困难，而算法和数据结构就是数理逻辑的推演模式和展现方法。如果把编程语言比作文字，那么算法和数据结构就相当于语法，没有合理的语法，文字就无法准确的传达意义。
数据结构就相当于：我塞牙了，那么就要用到牙签这“数据结构”，当然你用指甲也行，只不过“性能”没那么好；我要拧螺母，肯定用扳手这个“数据结构”，当然你用钳子也行，只不过也没那么好用。学习数据结构，就是为了了解以后在IT行业里搬砖需要用到什么工具，这些工具有什么利弊，应用于什么场景。以后用的过程中，你会发现这些基础的“工具”也存在着一些缺陷，你不满足于此工具，此时，你就开始自己在这些数据结构的基础上加以改造，这就叫做自定义数据结构。而且，你以后还会造出很多其他应用于实际场景的数据结构。。你用这些数据结构去造轮子，不知不觉，你成了又一个轮子哥。
单步调试
概念： 单步调试是指程序开发中，为了找到程序的bug，通常采用的一种调试手段，一步一步跟踪程序执行的流程，根据变量的值，找到错误的原因。
Chrome浏览器单步调试步骤： 打开开发工具 —>点击sources—>点击要调试的文件—>点击某一条要调试的代码(左侧行数)—>刷新页面—>点击页面上的下一步来查看显示的结果是否和预期的一样。
排序二叉树
排序二叉树最大的功能就是能够快速有效的对很多数据进行排序。它的特点是左孩子的数值要小于根节点，右孩子的数值要大于根节点，详情请看下图。
什么是二叉树？
二叉树是一种具有层级特性的数据结构，一棵树包含多个节点（下图中的每一个圆圈），节点自身含有一个属性，就是它所代表的数值（圆圈中的数值）。节点与节点间有对应关系，一种叫做父子关系，例如图中，节点8引出一个箭头指向节点3，于是我们说，节点8是节点3的父亲，节点3是节点8的儿子；另外一种叫做兄弟关系，比如节点3和节点10，因为他们都有同一个父节点。
二叉树创建代码实现
<!DOCTYPE html>
<html>
<head>
<meta charset="UTF-8">
<title></title>
</head>
<body>
<script>
function BinaryTree() {
//创建一个节点
var Node = function (key) {
this.key = key;
this.left = null;
this.right = null;
};
//创建一个根节点
var root = null;
var insertNode = function (node, newNode) {
if (newNode.key < node.key) {
if (node.left === null) {
node.left = newNode;
} else {
insertNode(node.left, newNode);
}
} else {
if (node.right === null) {
node.right = newNode;
} else {
insertNode(node.right, newNode);
}
}
}
//创建一个函数用来插入节点
this.insert = function (key) {
var newNode = new Node(key);
if (root === null) {
root = newNode;
} else {
insertNode(root, newNode);
}
};
}
var nodes = [8, 3, 10, 1, 6, 14, 4, 7, 13];
var binaryTree = new BinaryTree();
nodes.forEach(function (key) {
binaryTree.insert(key);
});
</script>
</body>
</html>
二叉树中序遍历
遍历规则：左中右。比如上图中序遍历为：1、3、4、6、7、8、10、13、14
二叉树中序遍历核心代码
//中序遍历的方法
var inOrderTraverseNode = function (node, callback) {
if (node !== null) {
inOrderTraverseNode(node.left, callback);
callback(node.key);
inOrderTraverseNode(node.right, callback);
}
}
//中序遍历的接口
this.inOrderTraverse = function (callback) {
inOrderTraverseNode(root, callback);
}
二叉树前序遍历算法原理
使用前序遍历去赋值一颗二叉树效率是最高的。前序遍历规则是：中左右。比如上图前序遍历为：8、3、1、6、4、7、10、14、13
前序遍历核心代码
//前序遍历的方法
var preOrderTraverseNode = function (node, callback) {
if (node !== null) {
callback(node.key);
preOrderTraverseNode(node.left, callback);
preOrderTraverseNode(node.right, callback);
}
}
//前序遍历的接口
this.preOrderTraverse = function (callback) {
preOrderTraverseNode(root, callback);
}
二叉树后序遍历原理
后序遍历可以应用到操作系统的文件系统的遍历之中，遍历规则为：左右中。比如上图后序遍历为：1、4、7、6、3、13、14、10、8
二叉树后序遍历核心代码
//后序遍历的方法
var postOrderTraverseNode = function (node, callback) {
if (node !== null) {
postOrderTraverseNode(node.left, callback);
postOrderTraverseNode(node.right, callback);
callback(node.key);
}
}
//后序遍历的接口
this.postOrderTraverse = function (callback) {
postOrderTraverseNode(root, callback);
}
二叉树排序的相关应用
拓展
打起精神来，文章到这还没结束呢，这里不是讲解小游戏代码的实现原理，而是继续二叉树另外一个重要的概念“红黑树”！
偷下懒，下面给大家推荐一则十分良心有趣的漫画——什么是红黑树？
