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);