【数据结构与算法】二叉搜索树的简单封装

Joyce99
284 阅读9分钟

零、我想说

这是在对二叉搜索树的学习过程中的小记录， 如果有错误的地方，欢迎大家和我一起讨论学习，一起进步~

一、 二叉搜索树的结构

【代码实现】

class Node{
      constructor(data, lChild, rChild) {
        this.data = data     //节点保存的数据
        this.lChild = lChild //节点的左孩子
        this.rChild = rChild //节点的右孩子
      }
    }
    class BinarySearchTree {
      constructor () {
        this.root = null    //二叉搜索树的根节点
      }
    }

二、二叉搜索树插入节点

【思路】

  1. 新建待插入节点
  2. 定义插入方法（根据二叉搜索树的特点：对于任意一个结点，其左子树中最大关键字都不超过x.data，其右子树中最小关键字都不小于x.data）
  3. 如果根节点为空的话，将插入节点赋值给根节点，否则递归调用步骤2中的插入方法

【代码实现】

  insert(data) {
    //1.新建节点
    let newNode = new Node(data, null, null)
    //2.定义插入的方法(根据二叉搜索树的特点)：
    //给方法插入两个参数：开始查找的节点，待插入节点
    /*
       2.1 如果待插入节点比当前节点小的话，
    *      如果当前节点的左孩子为空，则直接赋值给当前节点的左孩子，
           否则递归调用插入方法，也就是找到空的左节点
           注意开始查找的节点应该是当前节点的左孩子
        
       2.1 如果待插入节点比当前节点大的话，
    *      如果当前节点的右孩子为空，则直接赋值给当前节点的右孩子，
           否则递归调用插入方法，也就是找到空的右节点
           注意开始查找的节点应该是当前节点的右孩子
    */
    let insertNode = (currentNode, newNode) => {
      if (newNode.data < currentNode.data) {
        if (currentNode.lChild === null) {
          currentNode.lChild = newNode
        } else {
          insertNode(currentNode.lChild, newNode)
        }
      } else {
        if (currentNode.rChild === null) {
          currentNode.rChild = newNode
        } else {
          insertNode(currentNode.rChild, newNode)
        }
      }
    }
    //3.如果根节点为空，直接赋值给空节点
    if (this.root === null) {
      this.root = newNode
    } else {
      //否则调用插入节点的方法
      insertNode(this.root, newNode)
    }
  }

【测试代码】

let bst = new BinarySearchTree()
bst.insert(5);
bst.insert(3);
bst.insert(6);
bst.insert(2);
bst.insert(4);
bst.insert(8);
console.log(bst)

【测试结果】

三、二叉树的遍历

遍历二叉树，就是以某种方式逐个“访问”二叉树的每一个节点。
“访问”是指对节点的进行某种操作，例如输出节点的值。根据访问树根的顺序，
我们有三种方式遍历二叉树：

  1. 前序遍历：树根->左子树->右子树

  2. 中序遍历：左子树->树根->右子树

  3. 后序遍历：左子树->右子树->树根

1.先序遍历

【思路】
  1. 用数组保存结果
  2. 定义一个方法：如果是空节点则return fase否则按顺序树根->左子树->右子树递归调用该方法
  3. 自动调用：从根节点开始访问
  4. 返回结
【代码实现】
  preOrder() {
    let result = []    //用于保存结果
    let preOrderNode = (node) => {
      if (node === null) return false
      result.push(node.data)   //访问节点的data，将data放入result数组中
      preOrderNode(node.lChild)//节点的左孩子 递归调用该遍历的方法
      preOrderNode(node.rChild)//节点的右孩子 递归调用该遍历的方法
    } 
    preOrderNode(this.root) // 自动调用：从根节点开始访问
    return result
  }

【代码测试】

let bst = new BinarySearchTree()
bst.insert(5);
bst.insert(3);
bst.insert(6);
bst.insert(2);
bst.insert(4);
bst.insert(8);
console.log(bst.preOrder())

【测试结果】

2.中序遍历

【思路】
  1. 用数组保存结果
  2. 定义一个方法：如果是空节点则return fase否则按顺序左子树->树根->右子树递归调用该方法
  3. 自动调用：从根节点开始访问
  4. 返回结果
【代码实现】
  midOrder() {
    let result = []    //用于保存结果
    let midOrderNode = (node) => {
      if (node === null) return false
      midOrderNode(node.lChild)//节点的左孩子 递归调用该遍历的方法
      result.push(node.data)   //访问节点的data，将data放入result数组中
      midOrderNode(node.rChild)//节点的右孩子 递归调用该遍历的方法
    } 
    midOrderNode(this.root) // 自动调用：从根节点开始访问
    return result
  }

【代码测试】

let bst = new BinarySearchTree()
bst.insert(5);
bst.insert(3);
bst.insert(6);
bst.insert(2);
bst.insert(4);
bst.insert(8);
console.log(bst.midOrder())

【测试结果】

3.后序遍历

【思路】
  1. 用数组保存结果
  2. 定义一个方法：如果是空节点则return fase否则按顺序左子树->右子树->树根递归调用该方法
  3. 自动调用：从根节点开始访问
  4. 返回结果
【代码实现】
  lastOrder() {
    let result = []    //用于保存结果
    let lastOrderNode = (node) => {
      if (node === null) return false
      lastOrderNode(node.lChild)//节点的左孩子 递归调用该遍历的方法
      lastOrderNode(node.rChild)//节点的右孩子 递归调用该遍历的方法
      result.push(node.data)   //访问节点的data，将data放入result数组中
    } 
    lastOrderNode(this.root) // 自动调用：从根节点开始访问
    return result
  }

【代码测试】

let bst = new BinarySearchTree()
bst.insert(5);
bst.insert(3);
bst.insert(6);
bst.insert(2);
bst.insert(4);
bst.insert(8);
console.log(bst.lastOrder())

【测试结果】

四、根据data查找节点

【思路】

  1. 定义一个查找的方法:
    方法有两个参数：一个是开始查找的节点，另一个是查找的data
    如果查找的值比当前值小的话，就递归调用该方法(注意用查找节点的左孩子开始查找)，否则从查找节点的右孩子开始查找
  2. 自动调用方法

【代码实现】

  searchNodeByData(data) {
    //定义一个查找的方法
    //方法有两个参数：一个是开始查找的节点，另一个是查找的data
    const search = (fromNode, data) => {
      console.log(fromNode)
      if (fromNode === null) return false  //递归结束条件
      if (fromNode.data === data) return fromNode  //如果找到,则返回节点
      //如果查找的值比当前值小的话，就递归调用该方法(注意用查找节点的左孩子开始查找)，否则从查找节点的右孩子开始查找
      return search((data  < fromNode.data ? fromNode.lChild: fromNode.rChild), data)
    }
    return search(this.root, data) //自动调用方法
  }

【测试代码】

   let bst = new BinarySearchTree()
   bst.insert(5);
   bst.insert(3);
   bst.insert(6);
   bst.insert(2);
   bst.insert(4);
   bst.insert(8);
   console.log(bst.searchNodeByData(0))
   console.log(bst.searchNodeByData(5))
   console.log(bst.searchNodeByData(4))

【测试结果】

五、二叉树查找最值

1.查找最大值

【思路】

根据二叉搜索树的特点，最右边的孩子就是最大的节点

【代码实现】

  maxFrom(node) {
    //定义查找最大节点的的方法
    const maxNode = node => {
      if (node === null) return false  //递归结束的条件
      if (node.rChild == null) return node //该节点没有右孩子了
      return maxNode(node.rChild)  //否则一直递归查找右孩子
    }
    return maxNode(node || this.root) //如果没有指定从哪个节点找起的话，默认从根节点开始查找
  }

【测试代码】

let bst = new BinarySearchTree()
bst.insert(5);
bst.insert(3);
bst.insert(6);
bst.insert(2);
bst.insert(4);
bst.insert(8);
console.log(bst.maxFrom())

【测试结果】

1.查找最小值

【思路】

根据二叉搜索树的特点，最左边的孩子就是最小的节点

【代码实现】

  minFrom(node) {
    //定义查找最小节点的的方法
    const minNode = node => {
      if (node === null) return false   //递归结束的条件
      if (node.lChild === null) return node //该节点没有左孩子了
      return minNode(node.lChild)  //否则一直递归查找右孩子
    }
    return minNode(node || this.root) //如果没有指定从哪个节点找起的话，默认从根节点开始查找
  }

【测试代码】

let bst = new BinarySearchTree()
bst.insert(5);
bst.insert(3);
bst.insert(6);
bst.insert(2);
bst.insert(4);
bst.insert(8);
console.log(bst.minFrom())

【测试结果】

六、我的代码

 class Node{
      constructor(data, lChild, rChild) {
        this.data = data     //节点保存的数据
        this.lChild = lChild //节点的左孩子
        this.rChild = rChild //节点的右孩子
      }
    }
    class BinarySearchTree {
      constructor () {
        this.root = null    //二叉搜索树的根节点
      }
      insert(data) {
        //1.新建节点
        let newNode = new Node(data, null, null)
        //2.定义插入的方法(根据二叉搜索树的特点)：
        //给方法插入两个参数：开始查找的节点，待插入节点
        /*
           2.1 如果待插入节点比当前节点小的话，
        *      如果当前节点的左孩子为空，则直接赋值给当前节点的左孩子，
               否则递归调用插入方法，也就是找到空的左节点
               注意开始查找的节点应该是当前节点的左孩子
            
           2.1 如果待插入节点比当前节点大的话，
        *      如果当前节点的右孩子为空，则直接赋值给当前节点的右孩子，
               否则递归调用插入方法，也就是找到空的右节点
               注意开始查找的节点应该是当前节点的右孩子
        */
        let insertNode = (currentNode, newNode) => {
          if (newNode.data < currentNode.data) {
            if (currentNode.lChild === null) {
              currentNode.lChild = newNode
            } else {
              insertNode(currentNode.lChild, newNode)
            }
          } else {
            if (currentNode.rChild === null) {
              currentNode.rChild = newNode
            } else {
              insertNode(currentNode.rChild, newNode)
            }
          }
        }
        //3.如果根节点为空，直接赋值给空节点
        if (this.root === null) {
          this.root = newNode
        } else {
          //否则调用插入节点的方法
          insertNode(this.root, newNode)
        }
      }
      //前序遍历
      preOrder() {
        let result = []    //用于保存结果
        let preOrderNode = (node) => {
          if (node === null) return false
          result.push(node.data)   //访问节点的data，将data放入result数组中
          preOrderNode(node.lChild)//节点的左孩子 递归调用该遍历的方法
          preOrderNode(node.rChild)//节点的右孩子 递归调用该遍历的方法
        } 
        preOrderNode(this.root) // 自动调用：从根节点开始访问
        return result
      }
      //中序遍历
      midOrder() {
        let result = []    //用于保存结果
        let midOrderNode = (node) => {
          if (node === null) return false
          midOrderNode(node.lChild)//节点的左孩子 递归调用该遍历的方法
          result.push(node.data)   //访问节点的data，将data放入result数组中
          midOrderNode(node.rChild)//节点的右孩子 递归调用该遍历的方法
        } 
        midOrderNode(this.root) // 自动调用：从根节点开始访问
        return result
      }
      //后续遍历
      lastOrder() {
        let result = []    //用于保存结果
        let lastOrderNode = (node) => {
          if (node === null) return false
          lastOrderNode(node.lChild)//节点的左孩子 递归调用该遍历的方法
          lastOrderNode(node.rChild)//节点的右孩子 递归调用该遍历的方法
          result.push(node.data)   //访问节点的data，将data放入result数组中
        } 
        lastOrderNode(this.root) // 自动调用：从根节点开始访问
        return result
      }
      //根据data查找节点
      searchNodeByData(data) {
        //定义一个查找的方法
        //方法有两个参数：一个是开始查找的节点，另一个是查找的data
        const search = (fromNode, data) => {
          if (fromNode === null) return false  //递归结束条件
          if (fromNode.data === data) return fromNode  //如果找到,则返回节点
          //如果查找的值比当前值小的话，就递归调用该方法(注意用查找节点的左孩子开始查找)，否则从查找节点的右孩子开始查找
          return search((data  < fromNode.data ? fromNode.lChild: fromNode.rChild), data)
        }
        return search(this.root, data) //自动调用方法
      }
      maxFrom(node) {
        //定义查找最大节点的的方法
        const maxNode = node => {
          if (node === null) return false  //递归结束的条件
          if (node.rChild == null) return node //该节点没有右孩子了
          return maxNode(node.rChild)  //否则一直递归查找右孩子
        }
        return maxNode(node || this.root) //如果没有指定从哪个节点找起的话，默认从根节点开始查找
      }
      minFrom(node) {
        //定义查找最小节点的的方法
        const minNode = node => {
          if (node === null) return false   //递归结束的条件
          if (node.lChild === null) return node //该节点没有左孩子了
          return minNode(node.lChild)  //否则一直递归查找右孩子
        }
        return minNode(node || this.root) //如果没有指定从哪个节点找起的话，默认从根节点开始查找
      }
    }
avatar
文章
阅读
粉丝