昨天讲了二叉查找树的概念，现在咱们来完成一个自己的二叉树:
首要应该界说一个根特点root用来表明二叉查找树的根

    constructor(){
      root = null
    }

然后便是开端刺进节点，这儿要判别刺进节点时根特点是否为空，假如为空那么就将这个节点作为根节点，假如不为空就执行刺进非空二叉树的操作(insertNode)。

   // 刺进节点
   insert(key) {
     //创立一个新的节点对象
     const newNode = {
       key,
       left: null
       right: null
     }
     // 判别根节点是否为空
     if(root === null) {
       root = newNode
     } else {
       insertNode(root, newNode)  
     }
   }

刺进非空二叉树操作

    // 将新节点刺进到非空二叉查找树中
      insertNode(node, newNode) {
        // 假如新节点的键值小于当时节点的键值，则向当时节点的左子树刺进新节点
        if (newNode.key < node.key) {
          if (node.left === null) {
            node.left = newNode
          } else {
            insertNode(node.left, newNode)
          }
        } else {
          // 假如新节点的键值大于当时节点的键值，则向当时节点的右子树刺进新节点
          if (node.right === null) {
            node.right = newNode
          } else {
            insertNode(node.right, newNode)
          }
        }
      }

接下来现实遍历操作，一般常见的遍历查找二叉树的方法有三种：

先序遍历
后序遍历
中序遍历

先序遍历

先序遍历指的是先遍历根节点，然后遍历左子树，再遍历右子树，如下图：

遍历次序为：11->7->5->3->6->9->8->10-15->13->12->14->20->18->25，具体代码完成：

    // 先序遍历
      preOrder(node = this.root) {
        if (node !== null) {
          console.log(node.key)
          this.preOrder(node.left)
          this.preOrder(node.right)
        }
      }

这儿了解起来或许会有一点困难，便是连续运用递归来完成遍历。实际上这个进程便是不断的向函数调用栈中压入和弹出函数的进程，先压入参数为root.left的prevOrderTraversalNode的函数，直到下一个root.left为null时，从函数调用栈中弹出当时函数，接着开端压入参数为root.right的prevOrderTraversalNode的函数，直到下一个root.left为null时，回来上一个函数，如此循环就可以按次序从左子树到右子树遍历得到每一个节点的值。

中序遍历

咱们了解了先序遍历后，中序遍历就很好了解了,即先遍历左子树，再遍历根节点，最终遍历右子树。

遍历次序为：3->5->6->7->8->9->10->11-15->12->13->14->18->20->25，代码完成便是把先序遍历的代码打印次序倒置一下：

    // 中序遍历
  inOrder(node = this.root) {
    if (node !== null) {
      this.inOrder(node.left)
      console.log(node.key)
      this.inOrder(node.right)
    }

后序遍历

这个就不用再解说了吧，先遍历右子树，再遍历根节点，最终遍历左子树。直接贴图和代码了：

    // 后序遍历
  postOrder(node = this.root) {
    if (node !== null) {
      this.postOrder(node.left)
      this.postOrder(node.right)
      console.log(node.key)
    }
  }

二叉查找树的极值

求二叉查找树的最大值和最小值，其实咱们在上面遍历的时分就现已找到了，要害点便是判别下一个左节点或许右节点是否为空。但是要注意先判别是否为空树，假如为空树直接回来null。

    // 最大值
  max() {
    // 判别根节点是否为空
    if (this.root === null) {
      return null
    }
    const node = this.root
    while (node.right !== null) {
      node = node.right
    }
    return node.key
  }
  // 最小值
  min() {
    // 判别根节点是否为空
    if (this.root === null) {
      return null
    }
    const node = this.root
    while (node.left !== null) {
      node = node.left
    }
    return node.key
  }

查找指定的值

仍是拿一幅图来解说:

我想判别3或许25或许恣意一个数是否在这颗二叉查找树里要怎么办?肉眼判别(手动狗头)。还记得~~你说家是唯一的城堡~~二分法查找吗，这儿也相同适用。首要相同判别是否为空树，是的话直接回来false。再判别方针数字是否大于根节点11，大于往右找，小于往左找，等于直接回来，然后重复这一操作。代码表明为:

    // 查找
  search(key) {
    // 判别根节点是否为空
    if (this.root === null) {
      return false
    }
    // 创立一个临时变量，用于存储当时节点
    let current = this.root
    // 判别当时节点是否为空
    while (current !== null) {
      // 假如当时节点的键值小于要查找的键值，则向右子树查找
      if (current.key < key) {
        current = current.right
      } else if (current.key > key) {
        // 假如当时节点的键值大于要查找的键值，则向左子树查找
        current = current.left
      } else {
        // 假如找到了要查找的键值，则回来当时节点
        return current
      }
    }
    // 假如没有找到要查找的键值，则回来 null
    return null
  }

删去操作

删去操作相对于其他操作来说，略微复杂了亿点点，要分四种情况。

假如要删去的节点没有左右子节点，即删去的节点是叶节点，则直接删去。
假如要删去的节点只要一个左子节点，则用左子节点替换要删去的节点。
假如要删去的节点只要一个右子节点，则用右子节点替换要删去的节点。
假如要删去的节点有两个子节点，则用右子节点的最小值替换要删去的节点。

    // 删去
  remove(key) {
    let current = this.root
    let parent = null
    let isLeftChild = false
    // 查找要删去的节点
    while (key != current) {
      parent = current
      if (key < current.key) {
        isLeftChild = true
        current = current.left
      } else {
        isLeftChild = false
        current = current.right
      }
      if (current == null) {
        return false
      }
    }
    // 假如要删去的节点没有左右子节点，则直接删去
    if (current.left == null && current.right == null) {
      if (current == this.root) {
        this.root = null
      } else if (isLeftChild) {
        parent.left = null
      } else {
        parent.right = null
      }
    }
    // 假如要删去的节点只要一个左子节点，则用左子节点替换要删去的节点
    else if (current.right == null) {
      if (current == this.root) {
        this.root = current.left
      } else if (isLeftChild) {
        parent.left = current.left
      } else {
        parent.right = current.left
      }
    }
    // 假如要删去的节点只要一个右子节点，则用右子节点替换要删去的节点
    else if (current.left == null) {
      if (current == this.root) {
        this.root = current.right
      } else if (isLeftChild) {
        parent.left = current.right
      } else {
        parent.right = current.right
      }
    }
    // 假如要删去的节点有两个子节点，则用右子节点的最小值替换要删去的节点
    else {
      let successor = this.getSuccessor(current)
      if (current == this.root) {
        this.root = successor
      } else if (isLeftChild) {
        parent.left = successor
      } else {
        parent.right = successor
      }
      successor.left = current.left
    }
  }

以上是具体代码，进程略微有亿点点长，耐心看吧。最终贴上完好代码。

    class BinarySearchTree {
      constructor() {
        // 根特点
        this.root = null
      }
      // 刺进节点
      insert(key) {
        // 创立一个新的节点
        const newNode = {
          key,
          left: null,
          right: null
        }
        // 假如根节点为空，则将新节点作为根节点
        if (this.root == null) {
          this.root = newNode
        } else {
          // 假如根节点不为空，则将新节点刺进到二叉查找树中
          this.insertNode(this.root, newNode)
        }
      }
      // 将新节点刺进到非空二叉查找树中
      insertNode(node, newNode) {
        // 假如新节点的键值小于当时节点的键值，则向当时节点的左子树刺进新节点
        if (newNode.key < node.key) {
          if (node.left === null) {
            node.left = newNode
          } else {
            this.insertNode(node.left, newNode)
          }
        } else {
          // 假如新节点的键值大于当时节点的键值，则向当时节点的右子树刺进新节点
          if (node.right === null) {
            node.right = newNode
          } else {
            this.insertNode(node.right, newNode)
          }
        }
      }
      // 先序遍历
      preOrder(node = this.root) {
        if (node !== null) {
          console.log(node.key)
          this.preOrder(node.left)
          this.preOrder(node.right)
        }
      }
      // 中序遍历
      inOrder(node = this.root) {
        if (node !== null) {
          this.inOrder(node.left)
          console.log(node.key)
          this.inOrder(node.right)
        }
      }
      // 后序遍历
      postOrder(node = this.root) {
        if (node !== null) {
          this.postOrder(node.left)
          this.postOrder(node.right)
          console.log(node.key)
        }
      }
      // 最大值
      max() {
        // 判别根节点是否为空
        if (this.root === null) {
          return null
        }
        const node = this.root
        while (node.right !== null) {
          node = node.right
        }
        return node.key
      }
      // 最小值
      min() {
        // 判别根节点是否为空
        if (this.root === null) {
          return null
        }
        const node = this.root
        while (node.left !== null) {
          node = node.left
        }
        return node.key
      }
      // 查找
      search(key) {
        // 判别根节点是否为空
        if (this.root === null) {
          return false
        }
        // 创立一个临时变量，用于存储当时节点
        let current = this.root
        // 判别当时节点是否为空
        while (current !== null) {
          // 假如当时节点的键值小于要查找的键值，则向右子树查找
          if (current.key < key) {
            current = current.right
          } else if (current.key > key) {
            // 假如当时节点的键值大于要查找的键值，则向左子树查找
            current = current.left
          } else {
            // 假如找到了要查找的键值，则回来当时节点
            return current
          }
        }
        // 假如没有找到要查找的键值，则回来 null
        return null
      }
      // 删去
      remove(key) {
        let current = this.root
        let parent = null
        let isLeftChild = false
        // 查找要删去的节点
        while (key != current) {
          parent = current
          if (key < current.key) {
            isLeftChild = true
            current = current.left
          } else {
            isLeftChild = false
            current = current.right
          }
          if (current == null) {
            return false
          }
        }
        // 假如要删去的节点没有左右子节点，则直接删去
        if (current.left == null && current.right == null) {
          if (current == this.root) {
            this.root = null
          } else if (isLeftChild) {
            parent.left = null
          } else {
            parent.right = null
          }
        }
        // 假如要删去的节点只要一个左子节点，则用左子节点替换要删去的节点
        else if (current.right == null) {
          if (current == this.root) {
            this.root = current.left
          } else if (isLeftChild) {
            parent.left = current.left
          } else {
            parent.right = current.left
          }
        }
        // 假如要删去的节点只要一个右子节点，则用右子节点替换要删去的节点
        else if (current.left == null) {
          if (current == this.root) {
            this.root = current.right
          } else if (isLeftChild) {
            parent.left = current.right
          } else {
            parent.right = current.right
          }
        }
        // 假如要删去的节点有两个子节点，则用右子节点的最小值替换要删去的节点
        else {
          let successor = this.getSuccessor(current)
          if (current == this.root) {
            this.root = successor
          } else if (isLeftChild) {
            parent.left = successor
          } else {
            parent.right = successor
          }
          successor.left = current.left
        }
      }
}

数据结构-树结构(二叉树的封装)

先序遍历

中序遍历

后序遍历

二叉查找树的极值

查找指定的值

删去操作

作者信息

数据结构-树结构(二叉树的封装)

先序遍历

中序遍历

后序遍历

二叉查找树的极值

查找指定的值

删去操作

相关文章

如何在Shell脚本中传递一个命名参数？

目标检测模型的评价标准-AP与mAP

matplotlib基本图形的绘制操作

安卓开发基础——实现音频文件的播放

作者信息