순회 / 자료검색 ( autocomplete )

순회

1. 전위순회
2. 중위순회
3. 후위순회

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

class Tree {
  constructor(node) {
    this.root = node;
  }

  preorder(tree) {
    //전위순회
    if (!tree) {
      return
    }
    process.stdout.write(String(tree.value)+' ')
    this.preorder(tree.left);
    this.preorder(tree.right);

  }

  inorder(tree) {
    //중위순회
    if (!tree) {
      return;
    }
    this.inorder(tree.left);
    process.stdout.write(String(tree.value)+' ')
    this.inorder(tree.right);
  }

  postorder(tree) {
    //후위순회
    if (!tree) {
      return;
    }
    this.postorder(tree.left);
    this.postorder(tree.right);
    process.stdout.write(String(tree.value)+' ')
  }
}

const tree = new Tree(new Node(0));
tree.root.left = new Node(1);
tree.root.right = new Node(2);
tree.root.left.left = new Node(3);
tree.root.left.right = new Node(4);
tree.root.right.left = new Node(5);
tree.root.right.right = new Node(6);
tree.root.left.left.left = new Node(7);
tree.root.left.left.right = new Node(8);
tree.root.left.right.left = new Node(9);
tree.root.left.right.right = new Node(10);
tree.root.right.left.left = new Node(11);

tree.preorder(tree.root);
console.log()
tree.inorder(tree.root);
console.log()
tree.postorder(tree.root);

• 결과

0 1 3 7 8 4 9 10 2 5 11 6 
7 3 8 1 9 4 10 0 11 5 2 6 
7 8 3 9 10 4 1 11 5 6 2 0 

가로로 결과를 출력하기 위해 console.log가 아닌 process.stdout.write 사용

자료검색

class Node {
  constructor(value = "") {
    this.value = value; //값을 위한 value 설정
    this.isEnd = false; //마지막 문자열 값인지 체크
    this.children = new Map();
  }
}

class Trie {
  constructor() {
    this.root = new Node();
    this.preorderArr = [];
  }

  insert(string) {
    let currentNode = this.root;

    for (const value of string) {
      if (!currentNode.children.has(value)) {
        //해당 노드가 없다면 노드 생성
          currentNode.children.set(
            value,
            new Node(currentNode.value + value)
          );
      }
      currentNode = currentNode.children.get(value);
    }

    currentNode.isEnd = true;   //for문이 끝나면 마지막 노드값이므로 isEnd 설정
  }

  autocomplete(string) {
    const result = [];
    let currentNode = this.root;
    for (const char of string) {
      if (!currentNode.children.has(char)) return;
      currentNode = currentNode.children.get(char);
      if (currentNode.value == string) this.order(currentNode,result); //원하는 문자열과 같은 지점이 있다면 order함수 실행
    }
    return result;
  }

  order(tree,result) {
    if (tree.isEnd) {
      result.push(tree.value);
    } //마지막 문자열이라면 해당 tree의 value를 배열에 넣는다.

    [...tree.children.entries()].forEach(([_ , val]) => {
      this.order(val , result); // 존재하는 자식이 있다면 순회를 반복한다.
    });
  }
}

const trie = new Trie();

trie.insert("micc");
trie.insert("mic");
trie.insert("micccc");
trie.insert("miccccc");
trie.insert("miccccccccccccccccccccccccc");
console.log(trie.autocomplete("mi"));   //[ 'mic', 'micc', 'micccc', 'miccccc', 'miccccccccccccccccccccccccc' ]

trie.insert("cat");
trie.insert("can");
trie.insert("cap");
trie.insert("code");
trie.insert("coworker");
trie.insert("cookieeeeee");
trie.insert("cookie");

console.log(trie.autocomplete("co"));    //[ 'code', 'coworker', 'cookie', 'cookieeeeee' ]

문자열의 끝을 체크하기 위해 isEnd를 사용
autocomplete 함수로 원하는 문자열을 찾은 후
order 함수를 실행하여 해당 문자열부터 해당하는 자동검색이 되도록 진행