[数据结构与算法]前端js与二叉树

二叉排序树

(1) 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值（查找最小值就是查找最左的节点）
(2) 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值（查找最大值就是查找最右节点了）
(3) 它的左、右子树也分别为二叉查找树

function BinarySearchTree(keys){


  //Node构造函数
  let Node = function (key){
     this.key = key //值
     this.left = null//左值
     this.right = null//右值
  }

  let root = null

  let insertNode = (node,newNode)=>{
     if(newNode.key < node.key){//若是newNode的值大于跟节点node，就插入左边
       if(node.left === null){//若是左节点直接为空，就直接赋值为左节点
         node.left = newNode
       }else {
         insertNode(node.left,newNode)//若不是空，就继续插入到左节点处
       }
     }else {若是newNode的值小于跟节点node，就插入右边
       if (node.right === null) {
         node.right = newNode
       }else {
         insertNode(node.right,newNode)
       }
     }
  }

  this.insert = (key)=>{
     let newNode = new Node(key)//将数组传进来的值作为新值组成一个新的节点
     if (root === null) {//若是根节点为空
       root = newNode//新值为新节点
     }else {
       insertNode(root,newNode)//插入到遍历方法insertNode里面去
     }
  }
  
  keys.forEach((key)=>{
   this.insert(key)//遍历值，将值插入到root里面。
  })
  return root//返回二叉排序树
}


const keys = [8,3,10,1,6,14,4,7,13]
BinarySearchTree(keys)

中序遍历
左根右按顺序遍历

//在原来二叉树函数的基础上继续补充
    function BinaryTree(){
        // 中序遍历函数封装
        var inOrderTraverseNode = function(node,callback){//接收根节点的值和回调函数
            if(node !== null){  //若二叉树根节点不为空
                inOrderTraverseNode(node.left,callback);
                //先调用自身遍历左孩子
                
                callback(node.key);
                //输出当前的值（也就是左右根的 根 的值）
                
                inOrderTraverseNode(node.right,callback);
                //再调用自身遍历右孩子
            }
        }
        // 增加遍历的api接口
        this.inOrderTraverse = function(oRoot,callback){//后期调用
            inOrderTraverseNode(oRoot,callback);
         //接口内，调用中序遍历函数，并且传入当前的根节点的值和回调函数。传oRoot是因为要从根节点开始。
        }
    };

 
    var callback = function(key){// 增加遍历的自定义效果的回调函数
  
        console.log(key);//每次遍历后输出当前的遍历值。
    };
 
    binaryTree.inOrderTraverse(oRoot,callback);// 并且传入当前的根节点的值和回调函数 调用封装好的遍历方法api，以实现遍历二叉树的目标。

前序遍历
根左右按顺序遍历

后序遍历
左右根按顺序遍历