Javascript編程訓練
一彬向、前言
本篇開發(fā)環(huán)境
1兼贡、操作系統(tǒng)： windows 10 x64
2、編輯器：VS Code
實驗目的
熟悉JavaScript語法
二娃胆、實驗準備
查看JavaScript教程：
https://www.liaoxuefeng.com/wiki/001434446689867b27157e896e74d51a89c25cc8b43bdb3000
安裝和運行：http://nodejs.cn/ 下載node.js
三遍希、實驗內容
制作一個二叉樹Tree，實現(xiàn)樹節(jié)點的插入里烦，刪除凿蒜，前序遍歷等操作汪疮。同時把該數(shù)據(jù)保存為json格式的文件盾似；并能從文件讀取到內存中疼约；
可以基于其他語言的代碼進行修改寸五；但盡量采用面向對象的編程方法。
四靖避、實驗步驟
1.首先我們建立一個二叉查找樹（二叉排序樹），從開始節(jié)點作為根節(jié)點，對其遍歷插入触趴，具體代碼如下：
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.實現(xiàn)二叉排序樹的前序遍歷，在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.實現(xiàn)刪除值為x的結點
注：二叉樹中刪除節(jié)點有三種情況
1渴肉、葉結點
2冗懦、有一個子節(jié)點的結點
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.將二叉樹的數(shù)據(jù)寫入到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數(shù)據(jù)格式賦給mJSON
tree = mJSON.MyTree;//將json文件中的數(shù)組賦給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數(shù)據(jù)格式賦給mJSON
tree = mJSON.MyTree;//將json文件中的數(shù)組賦給tree
var binaryTree = new BinaryTree();
tree.forEach(function(key){binaryTree.insert(key);});//插入tree數(shù)組中的數(shù)據(jù)
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);
