javascript二叉树

javascript中的二叉树一（binary tree）

　　毕业也快2年了，毕业之后就没有认真写过博客了，都是那里学习一下，这里弄一下。学习了也不做笔记，过后就忘记了。我对这种状态打从心里是讨厌的。

　　进入正题，今天的笔记是记录javascript二叉树的学习，是非常基本的知识加上一些自己的认识。适合想了解javascript二叉树的萌新，大神请绕路走，当然如果发现有什么理解上的错误，还望不吝赐教。

　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　===================漂亮的分割线===================

　　首先说下我对二叉树的理解：

　　　　1，二叉树是由一系列有规则的节点构成

　　　　2，二叉树每一个节点可以看成为对象，必有key（节点值），可以有left（节点），right（节点）这三个属性

　　　　3，每个节点的left节点的key必定小于当前key值

　　　　4，每个节点的right节点的key必定大于当前的key值

　　那么假如我们要把一个数组构成二叉树，需要哪些代码？很简单，记住上面的几点，我们来一步一步把数组变成二叉树形式

　　一，

　　　　1，二叉树是由一系列有规则的节点构成，

　　　 2，二叉树每一个节点可以看成为对象，必有key（节点值），可以有left（节点），right（节点）这三个属性

　　　　思考：数组的每一个值将变成二叉树的节点（先不管这个节点怎么排序），那么我们在循环数组的时候，是不是都要处理下？

　　　　答：我定义下面一个类，到时候就可以依次实例化为节点了。看下好不好理解...

//节点类
class Node {
    constructor(key) {
        this.left = null
        this.right = null
        this.key = key
    }
}

进一步解释：当循环数组的时候，就可以把每一个数组项，实例化为节点，类似这样new Node(数组Item)

　　二，

　　　　3，每个节点的left节点的key必定小于当前key值

　　　　4，每个节点的right节点的key必定大于当前的key值

　　　　这2点是生成二叉树的规则。那我们是不是应该有一个二叉树类呢？

    //二叉树类
    class BinaryTree{

    }

　　思考：二叉树类要哪些东西呢？补充类看下是不是应该这些

//二叉树类
class BinaryTree {
    constructor() {
        this.root = null  //二叉树根节点
    }
    insert (key) {  //插入节点的方法
    }
}

解释：每一个二叉树实例应该都有一个根节点，然后暴露一个可以插入节点的方法（先不管插入规则，后续讲解）

接下来就是重点了：如何实现插入逻辑能实现上面3,4两点规则呢？

　　第一点：我们要确定一个根节点，然后在根节点基础上实现二分法

　　完善insert方法如下：

class BinaryTree {
    constructor() {
        this.root = null
    }
    insert (key) {
        const newNode = new Node(key) // 这里也可以在数组那里执行，但这里可以避免多次实例操作
        if (this.root === null) {
            this.root = newNode
        } else {
            this.inOrderTraversNode(this.root, newNode)
        }
    }
    inOrderTraversNode (node, newNode) {
    }
}

解释：当调用insert方法的时候都先确定root的值，然后在根节点为入口进行二分。inOrderTraversNode方法就负责二分法。

思考： inOrderTraversNode方法怎么样实现二分法？

答：该方法为一个递归方法。功能为：有2个参数，一个是当前已经存在的节点，后一个是要插入的新节点，就是把新节点插入到当前节点的正确的（左节点或者右节点）位置。

比如：当根节点确定之后，调用该方法插入一个新左节点，此时形成了2个节点的二叉树。此时若又一个左节点需要插入，我们就能可以递归调用该方法实现了。

//二叉树类
class BinaryTree {
    constructor() {
        this.root = null
    }
    insert (key) {
        const newNode = new Node(key)
        if (this.root === null) {
            this.root = newNode
        } else {
            this.inOrderTraversNode(this.root, newNode)
        }
    }
    inOrderTraversNode (node, newNode) {
        if (newNode.key < node.key) { // 左插
            if (node.left === null) {
                node.left = newNode
            }else{
                this.inOrderTraversNode(node.left, newNode)
            }    
        } else { // 右插
            if (node.right === null) {
                node.right = newNode
            } else {
                this.inOrderTraversNode(node.right, newNode)
            }
        }
    }
}

所有代码在这里，可以好好理解下

const node = [8, 1, 3, 10, 12, 6, 13, 15, 18, 7]

//节点类
class Node {
    constructor(key) {
        this.left = null
        this.right = null
        this.key = key
    }
}

//二叉树类
class BinaryTree {
    constructor() {
        this.root = null
    }
    insert (key) {
        const newNode = new Node(key)
        if (this.root === null) {
            this.root = newNode
        } else {
            this.inOrderTraversNode(this.root, newNode)
        }
    }
    inOrderTraversNode (node, newNode) {
        if (newNode.key < node.key) { // 左插
            if (node.left === null) {
                node.left = newNode
            }else{
                this.inOrderTraversNode(node.left, newNode)
            }    
        } else { // 右插
            if (node.right === null) {
                node.right = newNode
            } else {
                this.inOrderTraversNode(node.right, newNode)
            }
        }
    }
}

const binaryTree = new BinaryTree()
node.map(function(item) {
    binaryTree.insert(item)
})

console.log(binaryTree.root)