Javascript编程训练
一、前言
本篇开发环境
1、操作系统： windows 10 x64
2、编辑器：VS Code
实验目的
熟悉JavaScript语法
二、实验准备
查看JavaScript教程：
https://www.liaoxuefeng.com/wiki/001434446689867b27157e896e74d51a89c25cc8b43bdb3000
安装和运行：http://nodejs.cn/ 下载node.js
三、实验内容
制作一个二叉树Tree，实现树节点的插入，删除，前序遍历等操作。同时把该数据保存为json格式的文件；并能从文件读取到内存中；
可以基于其他语言的代码进行修改；但尽量采用面向对象的编程方法。
四、实验步骤
1.首先我们建立一个二叉查找树（二叉排序树），从开始节点作为根节点，对其遍历插入，具体代码如下：
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);
}
};
}
2.实现二叉排序树的前序遍历，在function里面加入以下程序：
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);
}
3.实现删除值为x的结点
注：二叉树中删除节点有三种情况
1、叶结点
2、有一个子节点的结点
3、有两个孩子的结点（需要用到下面的minNode方法）。
var minNode = function(node)
{
while(node && node.left !== null)
{
node=node.left;
}
return node.key;
}
this.min = function()
{
return minNode(root);
}
var removeNode = function(node, key)
{
if(node === null)
{
return null;
}
if(node.key > key)
{
node.left = removeNode(node.left,key);
return node;
}
else if(node.key < key)
{
node.right = removeNode(node.right,key);
}
else
{
if(node.left === null && node.right==null)
{
node = null;
return node;
}
if(node.right === null)
{
node = node.right;
return node;
}
else if(node.left === null)
{
node = node.left;
return node;
}
var minNode = minNode(node.right);
node.key = minNode.key;
node.right = removeNode(node.right,key);
return node;
}
}
this.remove = function(key)
{
return removeNode(root,key);
}
4.将二叉树的数据写入到json文件里，再用js读取它到内存中
json文件:
{
"MyTree":[1,3,7,2,4,8,5]
}
js代码:
var tree = null;
var fs=require('fs');
var mJSON = JSON.parse(fs.readFileSync("2.3.json"));//打开json文件，将内容以json数据格式赋给mJSON
tree = mJSON.MyTree;//将json文件中的数组赋给tree
以上两块相加效果等同于
var tree = [1,3,7,2,4,8,5];
5.全部代码
json:
{
"MyTree":[1,3,7,2,4,8,5]
}
javascript:
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 minNode = function(node)
{
while(node && node.left !== null)
{
node=node.left;
}
return node.key;
}
this.min = function()
{
return minNode(root);
}
var removeNode = function(node, key)
{
if(node === null)
{
return null;
}
if(node.key > key)
{
node.left = removeNode(node.left,key);
return node;
}
else if(node.key < key)
{
node.right = removeNode(node.right,key);
}
else
{
if(node.left === null && node.right==null)
{
node = null;
return node;
}
if(node.right === null)
{
node = node.right;
return node;
}
else if(node.left === null)
{
node = node.left;
return node;
}
var minNode = minNode(node.right);
node.key = minNode.key;
node.right = removeNode(node.right,key);
return node;
}
}
this.remove = function(key)
{
return removeNode(root,key);
}
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);
}
}
var tree = null;
var fs=require('fs');
var mJSON = JSON.parse(fs.readFileSync("2.3.json"));//打开json文件，将内容以json数据格式赋给mJSON
tree = mJSON.MyTree;//将json文件中的数组赋给tree
var binaryTree = new BinaryTree();
tree.forEach(function(key){binaryTree.insert(key);});//插入tree数组中的数据
var callback = function(key){console.log(key);}
console.log("PreorderTraverse:");
binaryTree.preOrderTraverse(callback);
console.log("Remove Node 2");
binaryTree.remove(2);
console.log("PreorderTraverse:");
binaryTree.preOrderTraverse(callback);
