algorithm
나무

비고

소개

나무 는 좀 더 일반적인 노드 - 에지 그래프 데이터 구조의 하위 유형입니다.

나무가 되려면 그래프가 다음 두 가지 요구 사항을 충족해야합니다.

• 그것은 비순환 적이다. 사이클 (또는 "루프")이 없습니다.
• 그것은 연결되어 있습니다. 그래프의 주어진 노드에 대해 모든 노드에 도달 할 수 있습니다. 모든 노드는 그래프의 한 경로를 통해 도달 할 수 있습니다.

트리 데이터 구조는 컴퓨터 과학에서 매우 일반적입니다. 나무는 일반적인 이진 나무, 빨강 검정 나무, B 나무, AB 나무, 23 나무, 힙 및 시도와 같은 다양한 알고리즘 데이터 구조를 모델링하는 데 사용됩니다.

다음과 같은 방법으로 트리를 Rooted Tree 라고 부르는 것이 일반적입니다.

choosing 1 cell to be called `Root`
painting the `Root` at the top
creating lower layer for each cell in the graph depending on their distance from the root -the bigger the distance, the lower the cells (example above)

나무에 대한 일반적인 기호 : T

전형적인 anary 트리 표현

일반적으로 우리는 이진 트리 (노드 당 정확히 두 개의 자식이있는 것)와 같은 anary 트리 (노드 당 잠재적으로 무한대의 자식이있는 트리)를 나타냅니다. "다음"자녀는 형제로 간주됩니다. 트리가 바이너리 인 경우이 표현은 추가 노드를 만듭니다.

우리는 형제를 반복하고 아이들을 되풀이합니다. 대부분의 나무는 상대적으로 얕기 때문에 어린이는 많이 있지만 계층 구조는 몇 가지 수준 밖에 없으므로 효율적인 코드가 생성됩니다. 인간 계보는 예외입니다 (많은 조상 수준, 한 수준 당 소수의 어린이).

필요한 경우 백 포인터를 유지하여 트리를 오름차순으로 유지할 수 있습니다. 이것들은 유지하기가 더 어렵습니다.

루트를 호출하는 함수와 여분의 매개 변수를 가진 재귀 함수 (이 경우에는 트리 깊이)를 갖는 것이 일반적입니다.

  struct node
  {
     struct node *next;
     struct node *child;
     std::string data;
  }

  void printtree_r(struct node *node, int depth)
  {
     int i;

     while(node)
     {
         if(node->child)
         {
            for(i=0;i<depth*3;i++)
                printf(" ");
            printf("{\n"):
            printtree_r(node->child, depth +1);
            for(i=0;i<depth*3;i++)
                printf(" ");
            printf("{\n"):
    
            for(i=0;i<depth*3;i++)
               printf(" ");
             printf("%s\n", node->data.c_str());

             node = node->next;
          }
      }
  }

  void printtree(node *root)
  {
     printree_r(root, 0);
  }

두 이진수가 같거나 같은지 확인하려면

1. 예를 들어 입력이 다음과 같은 경우 :

예 : 1

에이)

비)

출력은 true 여야합니다.

예 : 2

입력이 다음과 같은 경우 :

에이)

비)

출력은 false 여야합니다.

동일을위한 의사 코드 :

boolean sameTree(node root1, node root2){

if(root1 == NULL && root2 == NULL)
return true;

if(root1 == NULL || root2 == NULL)
return false;

if(root1->data == root2->data 
     && sameTree(root1->left,root2->left)
        && sameTree(root1->right, root2->right))
return true;

}