Charonyu's Profile

Breath-First Tree Traversal (寬度)

Depth-First Tree Traversal (PreOrder)

Depth-First Tree Traversal (InOrder)

Depth-First Tree Traversal (PostOrder)

BinarySearchTree

Worst Performance O(n) Best Performance O(1) Average Performance O(log n)


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

class BinarySearchTree {
  constructor() {
    this.root = null;
    this.path = "";
    this.queue = [];
  }

  treeInsert(z) {
    let y = null;
    let x = this.root;
    while (x !== null) {
      y = x;
      if (z.key < x.key) {
        x = x.left;
      } else {
        x = x.right;
      }
    }
    if (y == null) {
      this.root = z;
    } else if (y.key > z.key) {
      y.left = z;
    } else {
      y.right = z;
    }
  }

  searchRecursively(x, key) {
    if (x === null || key === x.key) return x;
    if (x.key > key) {
      return this.searchRecursively(x.left, key);
    } else {
      return this.searchRecursively(x.right, key);
    }
  }

  searchItertively(x, key) {
    while (x !== null && key !== x.key) {
      if (x.key > key) {
        x = x.left;
      } else {
        x = x.right;
      }
    }
    return x;
  }

  preOrder(n) {
    if (n != null) {
      this.path += n.key + " ";
      this.preOrder(n.left);
      this.preOrder(n.right);
    }
  }
  inOrder(n) {
    if (n != null) {
      this.inOrder(n.left);
      this.path += n.key + " ";
      this.inOrder(n.right);
    }
  }
  postOrder(n) {
    if (n != null) {
      this.postOrder(n.left);
      this.postOrder(n.right);
      this.path += n.key + " ";
    }
  }

  bftt(n) {
    if (n != null) {
      this.queue.push(n);
      for (let i = 0; i < this.queue.length; i++) {
        const currentNode = this.queue[i];
        if (currentNode.left) {
          this.queue.push(currentNode.left);
        }
        if (currentNode.right) {
          this.queue.push(currentNode.right);
        }
      }
    }
  }
}

let bst = new BinarySearchTree();
bst.treeInsert(new Node(15));
bst.treeInsert(new Node(6));
bst.treeInsert(new Node(5));
bst.treeInsert(new Node(1));
bst.treeInsert(new Node(13));
bst.treeInsert(new Node(-7));
bst.treeInsert(new Node(3));

bst.bftt(bst.root);
const result = bst.searchItertively(bst.root, 13);
console.log(result)