Js 实现二叉树

• Js 实现二叉树
  • 定义
  • 二叉树特点
  • 简单代码的实现与运用
    • 定义树
    • 定义节点
    • 测试Js的代码
  • 其他
    • 关于二叉树.net扩展

定义

二叉树是n(n>=0)个节点的有限集合，该集合或者为空集（称为空二叉树），或者由一个根节点和两棵互不相交的、分别称为根节点的左子树和右子树组成。
下列图展示了一棵普通二叉树：

二叉树特点

由二叉树定义以及图示分析得出二叉树有以下特点：
1）每个节点最多有两颗子树，所以二叉树中不存在度大于2的节点。
2）左子树和右子树是有顺序的，次序不能任意颠倒。
3）即使树中某节点只有一棵子树，也要区分它是左子树还是右子树。

简单代码的实现与运用

定义树

tree.js

function Tree(){
    this.root=null;
}
//添加根节点
Tree.prototype.addNode = function(val){
    var n = new Node(val);
    if (this.root == null) {
        this.root = n;
    }else{
        this.root.addNode(n);
    }
}
//执行树的遍历函数
Tree.prototype.traverse = function(){
    this.root.visit();
}
//查找节点
Tree.prototype.search = function(val){
    let SearchOne = this.root.search(val);
    return SearchOne;
}

定义节点

node.js

//添加节点
function Node(val) {
    this.value = val;
    this.left = null;
    this.right = null;
}
//遍历节点
Node.prototype.visit = function(){
    if (this.left !=null) {
        this.left.visit();
    }
    console.log(this.value);
    if (this.right != null) {
        this.right.visit();
    }
}
//查找节点
Node.prototype.search = function(val){
    if(this.value == val){
        return this;
    }else if(val < this.value && this.left != null){
        return this.left.search(val);
    }else if(val > this.value && this.right != null){
        return this.right.search(val);
    }
    return null;
}
//添加子节点
Node.prototype.addNode = function(n){
    if(n.value < this.value){
        if(this.left==null){
            this.left=n;
        }else{
            this.left.addNode(n);
        }
    }else if(n.value > this.value){
        if(this.right==null){
            this.right=n;
        }else{
            this.right.addNode(n);
        }
    }
}

测试Js的代码

sketch.js

var tree;
function setup() {
    tree = new Tree();
    for (var i = 0; i < 10; i++) {
        tree.addNode(Math.floor(Math.random(0,100)*100));
    }
    console.log(tree);
    tree.traverse();
}

其他

关于二叉树.net扩展

写得不好，大家不要笑哈哈哈哈！
Nuget地址：https://www.nuget.org/packages/AiDaSi_BinaryTree/
项目地址：https://github.com/AiDaShi/GeekTimeLearning/tree/master/BinaryTree