N-ary 트리의 동형

동형은 동일하거나 거울상 구조를 갖는 두 개의 나무로 정의됩니다. 미러 구조의 경우 왼쪽 노드의 데이터는 항상 오른쪽 노드와 일치합니다. 예를 들어, 가장 가까운 거울 이미지인 숫자를 선택하고 그 반대가 무엇인지 살펴보겠습니다. 이것이 바로 동형사상의 진정한 개념입니다.

이 기사에서는 두 개의 서로 다른 이진 트리가 동형인지 확인합니다.

N-ary 트리의 동형사상을 예로 들어보겠습니다-

L은 왼쪽 노드를 나타내고 R은 오른쪽 노드를 나타냅니다

왼쪽에서 두 번째로 가장 왼쪽에 있는 파티션에 있는 P 및 Q 트리의 거울 구조

이 두 다이어그램은 네 가지 일치 조건(P와 Q의 루트 노드)이 어떻게 서로 동형인지 보여줍니다.

• 왼쪽-왼쪽 노드가 일치할 수 있습니다.

• 어느 쪽이든 오른쪽-오른쪽 노드와 일치할 수 있습니다.

• 왼쪽 노드와 오른쪽 노드 모두 일치할 수 있습니다.

• 또는 오른쪽과 왼쪽이 일치하지 않습니다.

문법

다음 구문은 프로그램에서 사용됩니다 −

매개변수

• struct − 이 키워드는 구조 데이터 유형을 나타내는 데 사용됩니다.

• name_of_structure − 구조에 대한 이름을 제공합니다.

• 구조체는 다양한 관련 변수를 한 곳에 모아 놓은 것입니다.

알고리즘

• 'iostream'이라는 헤더 파일로 프로그램을 시작하겠습니다.

• 우리는 정수 유형 'd'과 초기화된 포인터 변수(왼쪽 및 오른쪽 하위 노드의 데이터를 나타내는 'l' 및 'r')를 포함하는 'tree_node'라는 구조를 만들고 있습니다. 각기.

• 이제 루트 노드의 값을 지정하기 위해 'data'라는 매개변수를 받아들이는 'create_node()'라는 함수를 사용하여 또 다른 구조를 만듭니다. 동시에 'tree_node'라는 포인터를 생성하고 주어진 데이터를 사용하여 왼쪽 및 오른쪽 하위 노드 포인터를 null로 초기화하고 루트 노드를 반환합니다. 이 함수를 사용하여 왼쪽 자식 노드와 오른쪽 자식 노드의 노드를 삽입합니다.

• 우리는 부울 데이터 유형을 사용하고 두 개의 tree_node 포인터 p 및 q를 입력 매개변수로 사용하고 부울 값을 반환하는 'check_isomorphism_tree 라는 함수를 만들고 있습니다. 여기서는 p의 데이터가 q의 데이터와 같은지 확인하기 위해 "if 문"을 두 번 만듭니다.

• p와 q가 모두 null인지 확인하고, 그렇다면 트리가 동형이므로 true를 반환합니다.

• p 또는 q 중 하나가 null인지 확인하고, 그렇다면 두 트리가 동형이 아니므로 false를 반환합니다.

• 'check_isomorphism_tree' 함수에서는 논리 연산자 "&&" 및 "||"를 사용하여 노드 'p' 및 'q'의 가능한 모든 왼쪽 및 오른쪽 하위 노드 조합을 재귀적으로 확인합니다.

• main 함수에서 시작하여 두 개의 트리 노드 "p"와 "q"를 생성하여 정보를 제공합니다.

• 메인 함수에서는 if 문을 사용하여 'check_isomorphism_tree' 함수를 호출하고 주어진 매개변수 p와 q를 전달하여 이러한 정수 값이 동형인지 확인합니다. 동형인 경우 인쇄 문은 "이 주어진 노드 정보는 동형 트리를 생성합니다"이고, 그렇지 않으면 그 반대입니다.

Example

Example

이 프로그램에서는 두 이진 트리가 동형인지 확인합니다.

출력

결론

이 프로그램에서는 N-ary 트리의 동형사상 개념을 이해합니다. 구조를 사용하여 트리 노드를 표현하고 왼쪽-왼쪽 노드, 오른쪽-왼쪽 노드, 왼쪽-오른쪽-왼쪽 노드 등을 사용하여 트리를 만드는 방법을 살펴보았습니다. 다음 작업은 트리의 동형 특성을 충족하는 데 도움이 됩니다.

위 내용은 N-ary 트리의 동형의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!