二叉树

作者: coolheadedY | 来源:发表于2017-09-18 22:29 被阅读13次

二叉树

class Node { // Node有左右区分,本身值
  constructor (data, right = null, left = null) {
    this.data = data
    this.right = right
    this.left = left
  }
}

class BST {
  constructor () {
    this.root = null // bst的起始顶部是null
  }

  add (data) {
    const node = this.root
    if (node === null) {
      this.root = new Node(data) // 如果没有root node,那就创建这个这个root new Node
      return '创建rootNode'
    } else { // 如果不是顶部节点,创建递归函数找到它在哪
      const searchTree = function (node) { // 递归
        if (data < node.data) { // 如果添加值小于当前节点的值,那它应该从左搜索
          if (node.left === null) { // 如果节点left是空,添加值就为节点left
            node.left = new Node(data)
            return '创建lfetNode'
          } else if (node.left !== null) {
            return searchTree(node.left)
          }
        } else if (data > node.data) {
          if (node.right === null) {
            node.right = new Node(data)
            return '创建rightNode'
          } else if (node.right !== null) {
            return searchTree(node.right)
          }
        } else {
          return null // 相等责不再增加
        }
      }
      return searchTree(node)
    }
  }

  findMin () { // 最小的为最左边的
    let current = this.root
    while (current.left !== null) {
      current = current.left
    }
    return current.data
  }

  findMax () {
    let current = this.root
    while (current.right !== null) {
      current = current.right
    }
    return current.data
  }

  find (data) {
    let current = this.root
    while (current.data !== data) {
      if (data < current.data) current = current.left
      if (data > current.data) current = current.right
      if (current === null) return null // ?
    }
    return current
  }

  isPresent (data) {
    let current = this.root
    while (current) {
      if (data === current.data) return true
      if (data < current.data) current = current.left
      if (data > current.data) current = current.right
    }
    return false
  }

  remove (data) {
    const removeNode = function (node, data) {
      if (node === null) return null
      if (data === node.data) {
        // node 没有子节点
        if (node.left === null && node.right === null) return null
        // node 没有left
        if (node.left === null) return node.right
        // node 没有right
        if (node.right === null) return node.left
        // node 有两个节点
        let tempNode = node.right
        while (tempNode.left !== null) { // 替换最接近当前需删除的节点 比如当前5 左边1 右边9,那么9的left会是 9 8 7 6, 1的right会是 2, 3, 4
          tempNode = tempNode.left
        }
        node.data = tempNode.data
        node.right = removeNode(node.right, tempNode.data) // 从right开始找到替换的节点位置进行删除,对它的子节点进行替换,直到替换为无子节点的情况
        return node
      } else if (data < node.data) { // 如果data小于当前值,从左边查找并删除
        node.left = removeNode(node.left, data)
        return node
      } else if (data > node.data) {
        node.right = removeNode(node.right, data)
        return node
      }
    }
    removeNode(this.root, data)
  }

  isBalanced () {
    return (this.heightFromMin() >= this.heightFromMax() - 1) // 从两边计算,只要其中一边算都高度 >= 另一边 - 1 那么就算均衡的
  }

  heightFromMin (node = this.root) { // 从最左边最小值开始计算高度
    if (node === null) return -1 // 先确定到最末尾都节点
    let left = this.heightFromMin(node.left)
    let right = this.heightFromMin(node.right)
    if (left < right) return left + 1 // 从left最小值开始计算高度
    else return right + 1
  }

  heightFromMax (node = this.root) {
    if (node === null) return -1
    let left = this.heightFromMax(node.left)
    let right = this.heightFromMax(node.right)
    if (left < right) return right + 1 // 从right最大值开始计算高度
    else return left + 1
  }

  inOrder () { // 中序遍历
    if (this.root === null) return null
    else {
      const result = []
      const traverseInOrder = function (node) {
        node.left && traverseInOrder(node.left)
        result.push(node.data)
        node.right && traverseInOrder(node.right)
      }
      traverseInOrder(this.root)
      return result
    }
  }

  preOrder () { // 前序遍历
    if (this.root === null) return null
    else {
      const result = []
      const traversePreOrder = function (node) {
        result.push(node.data)
        node.left && traversePreOrder(node.left)
        node.right && traversePreOrder(node.right)
      }
      traversePreOrder(this.root)
      return result
    }
  }

  postOrder () { // 后序遍历
    if (this.root === null) return null
    else {
      const result = []
      const traversePostOrder = function (node) {
        node.left && traversePostOrder(node.left)
        node.right && traversePostOrder(node.right)
        result.push(node.data)
      }
      traversePostOrder(this.root)
      return result
    }
  }

  levelOrder () { // 按层次遍历
    let result = []
    let queue = []
    if (this.root === null) return null
    else {
      queue.push(this.root)
      while (queue.length > 0) {
        let node = queue.shift()
        result.push(node.data)
        if (node.left !== null) {
          queue.push(node.left)
        }
        if (node.right !== null) {
          queue.push(node.right)
        }
      }
      return result
    }
  }
}

const bst = new BST()

相关文章

  • 数据结构与算法-二叉树02

    二叉树的定义 二叉树的特点 二叉树的五中基本形态 其他二叉树 斜二叉树 满二叉树 完全二叉树图片.png满二叉树一...

  • 二叉树

    二叉树 高度 深度真二叉树 满二叉树 完全二叉树 二叉树遍历前序 中序 后序层序遍历 翻转二叉树 递归法...

  • 二叉树 基础操作

    二叉树的使用 二叉树结构 先序创建二叉树 DFS 先序遍历二叉树 中序遍历二叉树 后序遍历二叉树 BFS 层次遍历...

  • 树与二叉树

    **树 ** 二叉树 满二叉树 完全二叉树 三种遍历方法 树与二叉树的区别 二叉查找树 平衡二叉树 红黑二叉树

  • 二叉树的宽度优先搜索(层次遍历,BFS)

    二叉树结构: 二叉树宽度优先搜索: 按照二叉树的层数依次从左到右访问二叉树的节点;例如:给定一个二叉树: 按照宽度...

  • 剑指 offer:39、平衡二叉树

    39. 平衡二叉树 题目描述 输入一棵二叉树,判断该二叉树是否是平衡二叉树。 解题思路: 平衡二叉树:Wiki:在...

  • Algorithm小白入门 -- 二叉树

    二叉树二叉树构造二叉树寻找重复子树 1. 二叉树 基本二叉树节点如下: 很多经典算法,比如回溯、动态规划、分治算法...

  • 14-树&二叉树&真二叉树&满二叉树

    一、树 二、二叉树 三、真二叉树 四、满二叉树

  • 二叉树的应用

    完美二叉树(满二叉树) 除了最下一层的节点外,每层节点都有两个子节点的二叉树为满二叉树 完全二叉树 除二叉树最后一...

  • 12.树Tree(2)

    目录:1.二叉树的基本概念2.二叉树的性质3.二叉树的创建4.二叉树的遍历 1.二叉树的基本概念 2.二叉树的性质...

网友评论

      本文标题:二叉树

      本文链接:https://www.haomeiwen.com/subject/budisxtx.html