두 갈래 나무 위

1722 단어

나무.

  • 노드의 높이 = 노드에서 잎 노드까지의 최대 경로(변수)
  • 노드의 깊이 = 뿌리 노드가 이 노드에 이르는 변의 개수
  • 노드의 층수 = 노드의 깊이 +1
  • 나무의 높이 = 뿌리 노드의 높이

    • 두 갈래 나무


    두 갈래 나무는 말 그대로 각 노드에 최대 두 개의'포크'가 있는데 그것이 바로 두 개의 자 노드인데 각각 왼쪽 노드와 오른쪽 자 노드이다.

    두 갈래 나무가 가득하다


    잎 노드는 모두 맨 밑에 있는데 잎 노드를 제외하고 각 노드는 좌우 두 개의 자 노드가 있는데 이런 두 갈래 나무를 만 두 갈래 나무라고 부른다.

    완전 두 갈래 나무


    잎 노드는 모두 맨 아래 두 층에 있고 마지막 층의 잎 노드는 모두 왼쪽으로 배열되며 마지막 층을 제외하고 다른 층의 노드 개수는 모두 최대에 달한다. 이런 두 갈래 나무를 완전 두 갈래 나무라고 부른다.

    어떻게 두 갈래 나무를 표현합니까?

  • 하나는 바늘이나 인용을 바탕으로 하는 이차 체인식 저장법이다
  • 하나는 수조에 기초한 순서 저장법이다

    • 두 갈래 나무가 두루 다니다

  • 앞의 순서를 반복하는 것은 나무의 임의의 노드에 대해 이 노드를 먼저 인쇄한 다음에 왼쪽 트리를 인쇄한 다음에 오른쪽 트리를 인쇄하는 것을 말한다
  • 중서적 반복은 나무의 임의의 노드에 대해 먼저 왼쪽 트리를 인쇄한 다음에 그 자체를 인쇄하고 마지막에 오른쪽 트리를 인쇄하는 것을 말한다
  • 뒷차례 훑어보는 것은 나무의 임의의 노드에 대해 먼저 왼쪽 트리를 인쇄한 다음에 오른쪽 트리를 인쇄하고 마지막에 이 노드 자체를 인쇄하는 것을 말한다

    • 위조 코드

     ：
preOrder(r) = print r->preOrder(r->left)->preOrder(r->right)

 ：
inOrder(r) = inOrder(r->left)->print r->inOrder(r->right)

 ：
postOrder(r) = postOrder(r->left)->postOrder(r->right)->print r

    코드

    void preOrder(Node* root) {
  if (root == null) return;
  print root //  ，  root  
  preOrder(root->left);
  preOrder(root->right);
}

void inOrder(Node* root) {
  if (root == null) return;
  inOrder(root->left);
  print root //  ，  root  
  inOrder(root->right);
}

void postOrder(Node* root) {
  if (root == null) return;
  postOrder(root->left);
  postOrder(root->right);
  print root //  ，  root  
}

    시간 복잡도: O(n)

    Python을 사용하여 Lasso 구현
    [검지 Offer] 32.위에서 아래로 두 갈래 나무를 인쇄하다

    좋은 웹페이지 즐겨찾기

    개발자 우수 사이트 수집

    개발자가 알아야 할 필수 사이트 100선 추천 우리는 당신을 위해 100개의 자주 사용하는 개발자 학습 사이트를 정리했습니다
    best100-homepage