数据结构之二叉搜索树

在学习完二叉树的基本特性后，我们再增加一个限制就可以形成一个二叉搜索树。

二叉搜索树，又称二叉排序树或二叉查找树；

其的本质就是一颗二叉树，可以为空，当不为空时需满足以下要求：

1、非空左子树的所有键值小于其根结点的键值。

2、非空右子树的所有键值大于其根结点的键值。

3、左、右子树本身也都是二叉搜索树。

二叉树的常见操作

首先封装一个BinarySearchTree的类，来实现树的功能。

还要封装一个结点类，来存储结点数据，和分别指向左子树和右子树。

代码：

    //结点类 
    class Node{
            constructor(key){
                this.data=key
                this.left=null
                this.right=null
            }
        }
    //二叉树类
        class BinarySearchTree{
            constructor(){
                this.root=null
            }
 
        }

常见操作：

在BinarySerachTree类中封装：

添加新结点insert(key)

思路：1、首先 new 结点类得到一个新的结点

2、判断根结点是否为空，如果根结点为空，直接将新创建的结点加在根结点上

3、如果root不为空时，我们就要封装一个insertNode 方法判断新建的结点放在左子树还是右子树上，并且判断对应的结点是否为空，如果不为空继续自调用寻找位置插入。

代码实现：

         class Node {
            constructor(data) {
                this.left = null;
                this.data = data;
                this.right = null;
            }
        }
 
        class BinarySearchTree{
            constructor() {
                this.root = null;
            }
 
 
            //添加新结点
            insert(ele) {
                // 创建新节点
                let newnode = new Node(ele);
                // console.log(newnode);
                if (this.root == null) { // 空树
                    this.root = newnode
                } else {
                    this.insertNode(this.root, newnode)
                }
            }
 
 
            //封装判断加在左，还是右的方法
            insertNode(root,newnode){
                //根结点的值大于新结点的
                // console.log(root,newnode);
                if (newnode.datadata) {
                    if (root.left==null) {
                        root.left=newnode
                    }else{
                        //左子树不为空时,函数自调用再进行判断，当前左子树上的结点和新建的结点传入比较
                        this.insertNode(root.left,newnode)
                    }
                }else{
                //小于等于的情况 添加到右子树
                if (root.right==null) {
                    root.right=newnode
                }else{
                    this.insertNode(root.right,newnode)
                }
 
                }
            }
 
        }
 
        let bst=new BinarySearchTree()
        bst.insert(10)
        bst.insert(1)
        bst.insert(15)
        bst.insert(8)
        bst.insert(7)
        console.log(bst);

遍历二叉搜索树

二叉树的遍历常见的有三种方式: 先序遍历/中序遍历/后续遍历. (还有程序遍历, 使用较少, 可以使用队列来完成)

先序遍历步骤：1、访问根结点   2、先序遍历其左子树   3、先序遍历其右子树（根左右）

中序遍历步骤：1、中序遍历其左子树   2、访问根结点    3、中序遍历其右子树  （左根右）

后续遍历步骤：1、后序遍历其左子树    2、后序遍历其右子树   3、访问根结点   （左右根）

先序遍历代码：

          preOrderTraversal(){
                this.preOrderTranversalNode(this.root)
            }
 
            preOrderTranversalNode(root){
                if (root!=null) {
                    //根
                    console.log(root.data)
                    //左
                    this.preOrderTranversalNode(root.left)
                    //右
                    this.preOrderTranversalNode(root.right)
                }
            }

中序遍历代码：

            inOrderTraversal(){
                this.inOrderTraversalNode(this.root)
            }
 
            inOrderTraversalNode(root){
                if (root!=null) {
                   
                    //左
                    this.inOrderTraversalNode(root.left)
                     //根
                     console.log(root.data)
                    //右
                    this.inOrderTraversalNode(root.right)
                }
            }

后续遍历代码：

           postOrderTraversal(){
                this.postOrderTraversalNode(this.root)
            }
 
            postOrderTraversalNode(root){
                if (root!=null) {
                   
                    //左
                    this.postOrderTraversalNode(root.left)
                    
                    //右
                    this.postOrderTraversalNode(root.right)
 
                     //根
                     console.log(root.data)
                }
            }

获取最大值和最小值

获取搜索二叉树最值得方法非常简单，因为二叉树得结构为左中右的数值依次变大，即最左边最小，最右边最大。

求最小值只需要找到最左边那个，代码：

 min(){
       let node=this.root
         while(node.left!=null){
              node=node.left
          }
           return node.data
     }

求最大值只需要找到最大那个，代码：

 max(){
       let node=this.root
         while(node.right!=null){
              node=node.right
          }
           return node.data
     }

 

搜索特定值

二叉搜索树的查询效率非常的快，这里我们可以通过两种方式实现，1、递归  2、循环，具体用那种视情况而定

1、递归求特定值

 search(el){
              return  this.searchnode(this.root,el)
            }
            searchnode(root,el){
                //判断是否为空
                if (root==null) {
                    return false
                }
                //判断在左还是在右
                if (root.data>el) {
                    //左
                  return  this.searchnode(root.left,el)
                }else if (root.data
                    //右
                  return  this.searchnode(root.right,el)
                }else{
                    //找到了
                    return true
                }
            }

2、循环求值

            searchc(el){
                let node=this.root
 
                while (node!=null) {
                    if (node.data>el) {
                        //左
                        node=node.left
                    }else if(node.data
                        //右
                        node=node.right
                    }else{
                        //相等的情况
                        return true
                    }
                }
                return false
             }

二叉搜索树节点的删除

可分为三种情况：

1、该节点是叶结点(没有子节点, 比较简单) 没有子节点的根节点

2、该节点有一个子节点(也相对简单)

3、该节点有两个子节点.(情况比较复杂)

在删除节点之前，我们要先做一件事就是找到需要删除的节点，并且要让其的父节点断开连接，所以我们要定义的变量存放当前结点的父结点，因为二叉树没有办法直接取到父结点。

查找的代码：

  remove(el) {
                let current = this.root
                let parent = null
                let isLeftChild = null
 
                //判断根是否为空的情况
                if (this.root == null) {
                    return false
                }
                while (current.data != el) {
                    parent = current
                    if (key < current.data) {
                        isLeftChild = true
                        current = current.left
                    } else {
                        isLeftChild = false
                        current = current.right
                    }
 
                    // 如果发现current已经指向null, 那么说明没有找到要删除的数据
                    if (current === null) return false
                }
                //找到要删除的结点 current现在就指向该结点
                
            }

逐一编写

1、叶子节点的情况

直接将其父结点指向它的链指向为空

if (current.left === null && current.right === null) {
    if (current == this.root) {
        this.root == null
    } else if (isLeftChild) {
        parent.left = null
    } else {
        parent.right = null
    }
}

2、该节点有一个子节点

这个时候要将删除结点的父结点指向它改为指向它的子节点

else if (current.right === null) {
     //current存在左子树
    if (current == this.root) {
        this.root = current.left
    } else if (isLeftChild) {
        //current为左结点
        parent.left = current.left
    } else {
        parent.right = current.left
    }
} else if (current.left === null) {
        //current存在右子树
    if (current == this.root) {
        this.root = current.right
    } else if (isLeftChild) {
        parent.left = current.right
    } else {
        parent.right = current.right
    }
}

3、该节点有两个子节点

这种情况相对来说是有点复杂的，如果我们要删除的节点有两个子节点, 甚至子节点还有子节点, 这种情况下我们需要从下面的子节点中找到一个节点, 来替换当前的节点，使其任然符合二叉搜索树的规则。即非空左子树的所有键值小于其根结点的键值，非空右子树的所有键值大于其根结点的键值。

但是找到的这个节点有什么特征呢?

应该是current节点下面所有节点中最接近current节点的

这个节点怎么找呢?

比current小一点点的节点, 一定是current左子树的最大值。

比current大一点点的节点, 一定是current右子树的最小值。

而在二叉搜索树中, 这两个特别的节点, 有两个特别的名字

比current小一点点的节点, 称为current节点的前驱；

比current大一点点的节点, 称为current节点的后继。

那么删除有两个子节点的current, 要么找到它的前驱, 要么找到它的后继来代替current。

寻找后继的代码：

getsuccessor(delNode){
     var successorParent = delNode
    var current = delNode.right // 要从右子树开始找
 
    // 2.寻找节点
    while (current != null) {
        successorParent = current
        current = current.left
    }
 
    // 3.如果是删除结点的后续不为它的右结点时
    if ( current != delNode.right) {
        successorParent.left = current.right
         current.right = delNode.right
    }
    
    return current
}

将找到的后续结点返回给remove方法中有两个子节点的情况，代码：

else {
    // 1.获取后继节点
    var successor = this.getSuccessor(current)
    
    // 2.判断是否是根节点
    if (current == this.root) {
        this.root = successor
    } else if (isLeftChild) {
        parent.left = successor
    } else {
        parent.right = successor
    }
    
    // 3.将删除节点的左子树赋值给successor
    successor.left = current.left
}