JavaScript 数据结构：二叉搜索树

[fantasticit]

二叉搜索树

二叉树中的节点最多只能有 2 个子节点：左侧子节点 和 右侧子节点。 二叉搜索树是二叉树的一种，但是它只允许在左侧子节点存储比父节点小的值，在右侧子节点存储大于等于父节点的值。

class Node {
  constructor(value) {
    this.left = null;
    this.value = value;
    this.right = null;
  }
}

class BinarySearchTree {
  constructor() {
    this.root = null;
  }

  /**
   * 插入节点
   * @param {} value
   */
  insert(value) {
    const newNode = new Node(value);

    if (!this.root) {
      this.root = newNode;
    } else {
      let root = this.root;
      insertNode(root, newNode);

      function insertNode(node, newNode) {
        if (node.value < newNode.value) {
          if (node.right === null) {
            node.right = newNode;
          } else {
            insertNode(node.right, newNode);
          }
        } else {
          if (node.left === null) {
            node.left = newNode;
          } else {
            insertNode(node.left, newNode);
          }
        }
      }
    }

    return true;
  }

  /**
   * 按值查找节点
   * @param {*} value
   */
  search(value) {
    const _search = (node, value) => {
      if (node === null) {
        return false;
      }

      if (node.value > value) {
        return _search(node.left, value);
      } else if (node.value < value) {
        return _search(node.right, value);
      } else {
        return node;
      }
    };

    return _search(this.root, value);
  }
}

先序遍历

先序遍历的顺序是：根 -> 左 -> 右。

递归版

function preTraverse(bsTree) {
  const traverse = (node, queue) => {
    if (!node) {
      return queue;
    } else {
      queue.push(node);
      traverse(node.left, queue);
      traverse(node.right, queue);
    }
  };
  const queue = [];
  traverse(bsTree.root, queue);
  return queue;
}

循环版

function preTraverse(bsTree) {
  let stack = [];
  let queue = [];
  let node = bsTree.root;

  stack.push(node);

  while (stack.length > 0) {
    let currentNode = stack.pop();
    queue.push(currentNode);

    if (currentNode.right) {
      stack.push(currentNode.right);
    }

    if (currentNode.left) {
      stack.push(currentNode.left);
    }

  }

  return queue;
}

中序遍历

中序遍历的顺序是：左 -> 根 -> 右。

递归版

function inorderTraverse(bsTree) {
  const traverse = (node, queue) => {
    if (!node) {
      return;
    }
    traverse(node.left, queue);
    queue.push(node);
    traverse(node.right, queue);
  };
  const queue = [];
  traverse(bsTree.root, queue);
  return queue;
}

循环版

function inorderTraverse(bsTree) {
  const stack = [];
  const queue = [];
  let currentNode = bsTree.root;

  while (currentNode || stack.length > 0) {
    if (currentNode != null) {
      stack.push(currentNode);
      currentNode = currentNode.left;
    } else {
      currentNode = stack.pop();
      queue.push(currentNode);
      currentNode = currentNode.right;
    }
  }

  return queue;
}

循环版的思路：

1. 首先将所有左节点压入栈中
2. 将栈弹出到队列中
3. 当前节点回归到跟节点，依次入列右节点

function inorderTraverse(bsTree) {
  const stack = [];
  const queue = [];
  let currentNode = bsTree.root;

  while (currentNode) {
    currentNode = currentNode.left;
    stack.push(currentNode);
  }

  while (stack.length) {
    queue.push(stack.pop());
  }

  currentNode = bsTree.root;

  while (currentNode) {
    queue.push(currentNode);
    currentNode = currentNode.right;
  }

  return queue;
}

后序遍历

后序遍历的顺序是：左 -> 右 -> 根。

递归版

function postorderTraverse(bsTree) {
  const traverse = (node, queue) => {
    if (!node) {
      return;
    }

    traverse(node.left, queue);
    traverse(node.right, queue);
    queue.push(node);
  };
  const queue = [];
  traverse(bsTree.root, queue);
  return queue;
}

循环版

function postorderTraverse(bsTree) {
  let stack = []
  let queue = []
  let node = bsTree.root
  stack.push(node)
  
  while (stack.length) {
    node = stack.pop()
    if (node.left) {
      stack.push(node.left)
    }
    if (node.right) {
      stack.push(node.right)
    }
    queue.unshift(node)
  }
  
  return queue
}

题目

1. 层级遍历

问题描述

给定一个二叉树，返回其按层次遍历的节点值。 （即逐层地，从左到右访问所有节点）。

例如:

          11
       /      \
      7       15
     / \     /  \
    3   6   12  16

层级遍历结果:

[
  [11],
  [7, 15],
  [3, 6, 12, 16]
]

解题思路

• 建立一个queue
• 先把根节点放进去，这时候找根节点的左右两个子节点
• 去掉根节点，此时queue里的元素就是下一层的所有节点
• 用for循环遍历，将结果存到一个一维向量里
• 遍历完之后再把这个一维向量存到二维向量里
• 以此类推，可以完成层序遍历

function levelTraverse(bsTree) {
  let queue = []
  let ret = []
  let node = bsTree.root
  queue.push(node)
  
  while (queue.length) {
    const count = queue.length
    const subRet = []
    
    while (count > 0) {
      node = queue.pop()
      subRet.push(node)
      if (node.left) queue.push(node.left)
      if (node.right) queue.push(node.right)
    }
    
    ret.push(subRet)
  }
  
  return subRet
}