JavaScript实现二叉树

定义: 二叉树是每个结点最多有两个子树的树结构

如图, 这表示一个二叉树的一部分, 每个二叉树有一个起点(根节点), 这个节点除了记录它本身的数据外, 还记录它的2个子节点是谁, 它左边的子节点上的数据会比它自身的数据小, 右边的会比它自身的数据大(或等于)

image.png

我们用下面的这个类来表示二叉树的组成部分(节点)

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

在实例化的时候, 它会记录本身的数据, 以及左/右子节点的引用值, 左右节点也是一个 Node 的实例, 同时, 它还有一个 show 方法, 用于展示自己的数据

那么, 如果生成一个二叉树呢?
分成以下几步

1. 在初始化时, 可以先假定一个 null 作为它的根节点
2. 如果有一个数据需要放进这个二叉树, 那么先将这个数据实例成 Node 类型的节点, 为了方便后面的描述, 我们把这个节点命名为 n, 然后判断这个二叉树的根节点是否为 nul:
   • 如果为null, 就将根节点的值设置为这个数据;
   • 如果不为null, 就开始一个循环, 首先是根节点:
     • 如果这个数据比根节点小, 那么看一下 左节点是否为 null, 如果是null, 则就地赋值为 n, 并停止循环
     • 反之, 看一下 右节点是否为 null, 如果是null, 则就地赋值为 n, 并停止循环
       • 如果在上面 2 条执行过程中, 左节点或者右节点不为 null, 则把 该节点当成 之前的根节点, 继续这一过程

上面的循环就是一个迭代的过程, 理清思路之后, 代码就可以写出来了

class BST {
  constructor() {
    this.root = null 
  }
  insert(data) {
    const n = new Node(data, null, null)
    if (this.root === null) {
      this.root = n
    } else {
      let current = this.root
      while (1) {
        if (data < current.data) {
          if (current.left === null) {
            current.left = n
            break 
          }
          current = current.left
        } else {
          if (current.right === null) {
            current.right = n 
            break
          }
          current = current.right
        }
      }
    }
  }
}

未完待续

inOrder(node) { 
  if (node !== null) {
    this.inOrder(node.left)
    console.log('inOrder', node.show())
    this.inOrder(node.right)
  }
}
preOrder(node) {
  if (node !== null) {
    console.log('preOrder', node.show())
    this.preOrder(node.left)
    this.preOrder(node.right)
  }
}
postOrder(node) {
  if (node !== null) {
    this.postOrder(node.left)
    this.postOrder(node.right)
    console.log('postOrder', node.show())
  }
}
getMin() {
  let current = this.root 
  while (current.left !== null) {
    current = current.left 
  }
  return current.data 
}
getMax() {
  let current = this.root 
  while (current.right !== null) {
    current = current.right
  }
  return current.data 
}
getSmallest(node) {
  let current = node 
  while (current.right !== null) {
    current = current.right
  }
  return current.data 
}
find(data) {
  let current = this.root 
  while (current !== null) {
    if (current.data === data) {
      return current 
    } else if (data < current.data) {
      current = current.left 
    } else {
      current = current.right 
    }
  }
  return null 
}
remove(data) { 
  return this.removeNode(this.root, data)
}
removeNode(node, data) {
  if (node === null) {
    return null
  }
  if (data === node.data) {
    if (node.left === null && node.right === null) {
      return null 
    }
    if (node.left === null) {
      return node.right 
    }
    if (node.right === null) {
      return node.left
    }
    const tempNode = this.getSmallest(node.right)
    node.data = tempNode.data
    node.right = this.removeNode(node.right, data)
    return node
  } else if (data < node.data) {
    node.left = this.removeNode(node.left, data)
    return node
  } else {
    node.right = this.removeNode(node.right, data)
    return node
  }
}