js 二叉树

class Node {
  constructor (data, left, right) {
    this.data = data
    this.left = left
    this.right = right
  }
}

class Tree {
  constructor () {
    this.root = null
  }

  insert(data) {
    const newNode = new Node(data, null, null)

    if (!this.root) {
      this.root = newNode
    } else {
      let cur = this.root

      while(1) {
        if (cur.data < data) {
          if (!cur.right) {
            cur.right = newNode
            break
          }

          cur = cur.right
        } else {
          if (!cur.left) {
            cur.left = newNode
            break
          }

          cur = cur.left
        }
      }
    }
  }

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

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

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

// 广度遍历
  guangdu() {
    const queue = []

    const pushChild = (node) => { 
      if (node.left) {
        queue.unshift(node.left)
      }
      if (node.right) {
        queue.unshift(node.right)
      }
    }

    queue.push(this.root)

    while(queue.length) {
      const c = queue.pop()
      console.log(c.data)
      pushChild(c)
    }
  }

  // 深度遍历
  shendu() {
    const queue = []

    const pushChild = (node) => { 
      if (node.left) {
        queue.push(node.left)
      }
      if (node.right) {
        queue.push(node.right)
      }
    }

    queue.push(this.root)

    while(queue.length) {
      const c = queue.pop()
      console.log(c.data)
      pushChild(c)
    }
  }

  // 取得最小值
  getMin (node) {
    node = node ? node : this.root 

    if (!node.left) {
      return node
    } else {
      return this.getMin(node.left)
    }
  }

  // 取得最大值
  getMax (node) {
    node = node ? node : this.root

    if (!node.right) {
      return node
    } else {
      return this.getMax(node.right)
    }
  }

  // 查找节点
  find (data) {
    let cur = this.root

    while (cur) {
      if (data < cur.data) {
        cur = cur.left
      } else if (data > cur.data) {
        cur = cur.right
      } else {
        return cur
      }
    }
  }

  // 移除节点
  remove (node, data) {
    if (node === null) {
      return null
    }

    if (data < node.data) {
      node.left = this.remove(node.left, data)
      return node
    } else if (data > node.data) {
      node.right = this.remove(node.right, data)
      return node
    } else {
      if (node.left === null && node.right === null) {
        return null
      }
      else if (node.left === null) {
        return node.right
      } 
      else if (node.right === null) {
        return node.left
      } 
      else {
        // 右子树的最左节点
        // const _node = this.getMin(node.right)
        // node.data = _node.data
        // node.right = this.remove(node.right, node.data)
        
        // 左子树的最右节点
        const _node = this.getMax(node.left)
        node.data = _node.data
        node.left = this.remove(node.left, node.data)

        return node
      }
    }
  }
}

const tree = new Tree()
tree.insert(2)
tree.insert(1)
tree.insert(8)
tree.insert(4)
tree.insert(6)
tree.insert(3)
tree.insert(2)
tree.insert(9)
tree.insert(5)
tree.insert(7)
tree.insert(10)

tree.remove(tree.root, 8)

console.log(tree)
// tree.nextOrder(tree.root)
// console.log(tree.getMin())
// console.log(tree.getMax())
// console.log(tree.find(3))

同样的一串数字，插入的先后顺序不同，那么形成的二叉树排列也不同

说一下删除节点，被删除节点如果两个子树都存在：

1. 选取左子树的最右节点的值替换掉被删除节点的值
2. 删除左子树的最右节点
   同理，用右子树的最左节点去做上面两步也是可以的

为什么要左子树的最右节点呢？
因为要选取一个其它节点换到被删除节点的位置，这个节点要比被删除节点的左子树的根节点要大，比右子树的根节点要小，那么可以从左子树的右子树中选择，这个右子树中有很多节点啊，选谁都可以，但是为了方便起见，我们取一个最大值，即是左子树中的最右节点，因为末端节点可能只有一个子树或者没有子树，删除最右节点时，将子树的值替换到最右节点的位置即可。

删除节点后树的排列方式只有一种吗？
不是

1. 按照上面两种利用左子树的最右节点或者右子树的最左节点，最少是两种方式
2. 上面说了，为了方便起见，我们使用了左子树的最右节点，如果不考虑方便，有很多节点都可以考虑，排列方式又是不一样的

1.jpg

遍历：
前序遍历：根-左-右
中序遍历：左-根-右
后续遍历：左-右-根
看出规律了吧！
还有这种遍历顺序不仅仅是针对整个二叉树，其实也针对每个局部的子树
类似动态规划，将大问题拆解成小问题，从整体看局部

22.jpg

拿中序遍历举例：

23.jpg

可以看出，这个步骤是可以通过递归来完成的
我们先去递归左子树，然后直接输出根元素，然后再去递归右子树
对于左子树，重复上述过程
对于左子树的左子树，重复上述过程
...
同理，对于右子树也是上述过程

可能，同学们对于上述遍历的递归写法还是有点不太理解，那么分析一下：

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

意思是：如果节点不为 null，那么先去递归左子树，输出根节点值，递归右子树
左边递归不走完的话，console.log 是永远不会执行的
递归有递归的终止条件，不然就会无限递归，这个条件就是 node == null
那么左递归停止，就代表上一次递归的子树没有左节点，直接输出子树的根节点
然后开始递归该子树的右子树，同理，对于右子树的每一个节点，也是先开始递归左子树，输出根节点值，递归右子树

所以，对于一棵树中的所有节点，都要走这个递归的3个过程。一个节点完全递归完毕，就是左子树递归完毕，输出根节点值，右子树递归完毕。即递归到叶子节点的时候，因为叶子节点没有左子树，也没有右子树，最终输出该叶子节点的值。

24.jpg