Tree 탐색

Tree탐 색의 대표적인 방법 두가지는 BFS와 DFS가 있다.
DFS와 BFS는 모든 정점을 한번만 방문한다는 공통점이 있지만, 사용 목정에 따른 장단점이 있기때문에 상황에 맞는 탐색방법을 사용해야 한다.

BFS(breadth first serch)

너비 우선 탐색;BFS 는 가장 가까운 정점부터 우선 탐색 하는 방식이다. 같은 거리의 정점을 모두 확인한 후 다음 거리의 정점을 모두 확인 하는 순서로 진행된다. 이진트리를 예로 다음과 같은 순서로 탐색이 진행된다.

DFS(deep firs serach)

깊이 우선 탐색;DFS 는 하나의 정점의 경로 끝까지 모두 탐색 후, 다음 정점을 탐색하는 순서로 진행된다. 이진트리를 예로 다음과 같은 순서로 탐색이 진행된다.

순회순서

깊이 우선 탐색에서 트리의 모든 노드를 한번씩 방문하는것을 트리 순회라 한다.
트리 순회순서는 3 종류로 구분할 수 있다.

전위 순회

노드의 루트부터 순차적으로 순회(왼쪽부터)하며 제일 깊은 자식노드가 없는 노드(리프)까지 확인 후, 리프의 상위노드의 다른 자식노드를 확인 하는 순서로 순회.
서브트리로만 보자면, 부모노드 -> 자식노드 -> 형제노드, 전위라는 말을 부모노드를 먼저라고 생각할수 있겠다.

중위순회

루트를 지나치고 가장 깊숙한 리프부터(왼쪽부터) 순회를 시작하는 방식으로 리프 -> 리프의 부모노드 -> 리프 부모의 자식노드를 확인하는 순서로 진행된다.
서브트로만 보자면, 자식노드 -> 부모노드 ->순회하지 않은 자식노드, 중위라는 말을 부모노드를 중간에라고 생각할수 있겠다.

후위순회

-> 루트를 지나치고 가장 깊숙한 리프부터(왼쪽부터)순회를 시작하는데 리프 순회후 형제리프를 순회, 형제모두 순회후 부모노드를 순회 -> 부모의 형제노드 순회하는 방식으로 진행.
서브트리로만 보자면, 자식노드 -> 형제노드 -> 부모노드, 후위라는 말을 부모노드를 마지막에라고 생각할수 있겠다.

코드 복습

2개의 Promise 타입의 JSON 데이터를 받아서 두개의 객체를 인자로 갖는 배열을 만드는 코드.
조건으로 반환되는 배열은 Promise 타입이어야 한다.

promise.all

const user1Path = (use1에 관련된 정보를 담은 객체의 파일경로)
const user2Path = (use2에 관련된 정보를 담은 객체의 파일경로)

// 해당 파일경로의 객체를 Promise타입으로 JSON 포맷을 반환하는 함수.
const getDataFromFilePromise = (filePath) => {
  return new Promise((resolve, reject) => { //함수의 리턴 값으로 Promise타입을 반환
    fs.readFile(filePath, 'utf8', (err, data) => {
      if (err) {
        reject(err);
      }
      resolve(data);
    });
  });
};

//1번 코드
const readAllUsers1 = () => {
  
  // 첫번째 결과를 변수에 할당한다.
  let newPr1 = new Promise((resolve, reject) => {
    getDataFromFilePromise(user1Path).then((user1Data) => {
      //첫번째 경로에서 Promise 타입 JSON 파일을 만든다. Promise chaning을 이용하여 결과값을 다음 함수에 넘겨준다.
      resolve(JSON.parse(user1Data)); // 넘겨받은 데이터를 객체형테로 변형시킨다.
    });
  });
  
  // 두번째 결과를 첫번재 방식과 동일하게 변수에 할당한다.
  let newPr2 = new Promise((resolve, reject) => {
    getDataFromFilePromise(user2Path).then((user2Data) => {
      resolve(JSON.parse(user2Data));
    });
  });
  return Promise.all([newPr1, newPr2]);
  // Promise.all을 이용하여 배열로 Promise타입 배열로 반환한다.
};


//2번 코드
const readAllUsers = () => {
  //1번 코드에서 중복되는 작업인 JSON.parse를 함수로 만들어 코드 중복을 제거한다.
  const parsing = function (data) {
    return JSON.parse(data);
  };

  let a = new Promise((resolve, reject) => {
    getDataFromFilePromise(user1Path).then((data) => {
      resolve(parsing(data));
    });
  });
  let b = new Promise((resolve, reject) => {
    getDataFromFilePromise(user2Path).then((data) => {
      resolve(parsing(data));
    });
  });

  return Promise.all([a, b]);
  //1번코드와 동일하지만 여전히 중복되는 코드가 많음을 확인 할 수 있다.
};

//3번 코드
const readAllUsers3 = () => {
  const parsing = function (data) {
    return JSON.parse(data);
  };
  
  const paths = [user1Path, user2Path];// 가저올 매개변수를 배열로 만든다.
  const promises = paths.map((path) => getDataFromFilePromise(path));
  // map 메서드를 이용하여 인자를 봐꺼가며 해당 함수를 실행시켜 배열의 형태로 반환 받는다.
  
  return Promise.all(promises).then((jsons) => jsons.map(parsing));
  //Promise.all은 매개변수로 배열을 받기때문에 해열이 할당된 promises를 매개변수로 받는다.
  // 그결과 값의 배열의 인자는 stirng타입이기 때문에 객체로 변환시켜주는 작업을 진행한다.
  // jsons.map(parsing)에서 콜백함수에 전달되는 배개변수와 jsons의 인자가 동일하기 때문에
  // ((el) => parsing(el))을 (parsing)으로 간략하게 작성 가능하다.
}

async/await

const readAllUsersAsyncAwait = async () => { 
  // async를 통해 함수를 Promise 타입으로 변환시킨다.
  
  // await는 async 키워드가 사용된 함수 내부에서 사용가능하며
  // await 키워드가 사용된 콜백함수의 실행이 완료될때까지 다음 코드가 실행되지않도록한다.  
  let user1 = await getDataFromFilePromise(user1Path).then((user1) => {
  return JSON.parse(user1); 
  });
  
  let user2 = await getDataFromFilePromise(user2Path).then((user2) => {
  return JSON.parse(user2);
  });

  return [user1, user2];
}