关于javascript:javascript-数据结构之二叉搜索树

/**
 * @title 二叉排序树
 */
class BinaryTreeNode {constructor(key, value) {
    this.key = key;
    this.value = value;
    this.left = null;
    this.right = null;
    this.parent = null;
  }
}

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

  static createNode(key, value) {return new BinaryTreeNode(key, value);
  }

  insert(node) {
    // 如果没有根节点，则直接插入到根节点
    if (!this.root) {
      this.root = node;
      return;
    }

    let parent = this.root;
    while (true) {if (node.key < parent.key) {
        // 该节点比父节点小，则该节点在左子树
        if (parent.left) {
          parent = parent.left;
          continue;
        } else {
          parent.left = node;
          break;
        }
      } else {if (parent.right) {
          parent = parent.right;
          continue;
        } else {
          parent.right = node;
          break;
        }
      }
    }

    node.parent = parent;
  }

  search(key) {
    let currentNode = this.root;

    while (currentNode && key !== currentNode.key) {if (key < currentNode.key) {currentNode = currentNode.left;} else {currentNode = currentNode.right;}
    }

    return currentNode
  }

  traverse(){return [...this._traverse(this.root)]
  }

  *_traverse(node){if(!node){return;}
    yield* this._traverse(node.left);
    yield node;
    yield* this._traverse(node.right)
  }

}
const tree= new BinarySearchTree();

tree.insert(BinarySearchTree.createNode(10, 10))
tree.insert(BinarySearchTree.createNode(5, 5))
tree.insert(BinarySearchTree.createNode(16, 16))
tree.insert(BinarySearchTree.createNode(7, 7))
tree.insert(BinarySearchTree.createNode(20, 20))
list = [...tree.traverse(tree.root)];