Giới thiệu

Trees Traversal (duyệt cây) là cách để lấy tất cả các node của cây. Không như các kiểu dữ liệu linear như linked list, array, queue, stack chỉ lấy dữ liệu theo một chiều, trees có thể lấy tất cả các node theo nhiều cách khác nhau.

Có 2 cách duyệt cây:

• Depth First traversal (DFS)
  • Preorder traversal
  • Inorder traversal
  • Postorder traversal
• Breadth First traversal (BFS)

Tiếp tục các đoạn code trong phần [DSA] Binary Search Trees ta tiến hành các cách duyệt cây nhị phân (Trees traversal)

Bread first traversal (BFS)

  BFS() {
    let data = [];
    let queue = [];
    let node = this.root;

    queue.push(node);

    while (queue.length) {
      node = queue.shift();
      data.push(node.value);
      if (node.left) {
        queue.push(node.left);
      }

      if (node.right) {
        queue.push(node.right);
      }
    }

    return data;
  }

Depth first traversal

Preorder

  DFSPreOrder() {
    var data = [];
    function traversal(node) {
      data.push(node.value);
      if (node.left) {
        traversal(node.left);
      }
      if (node.right) {
        traversal(node.right);
      }
    }

    traversal(this.root);
    return data;
  }

Postorder

  DFSPostOrder() {
    var data = [];
    function traversal(node) {
      if (node.left) {
        traversal(node.left);
      }
      if (node.right) {
        traversal(node.right);
      }
      data.push(node.value);
    }
    traversal(this.root);
    return data;
  }

Inorder

  DFSInOrder() {
    var data = [];
    function traversal(node) {
      if (node.left) {
        traversal(node.left);
      }
      data.push(node.value);
      if (node.right) {
        traversal(node.right);
      }
    }
    traversal(this.root);
    return data;
  }