이진 트리의 주어진 선행 순서와 inorder 순회가 트리를 고유하게 정의한다는 것을 알고 있습니다. 일반적인 트리 즉 두 개 이상의 자식이있는 트리는 선주문과 inorder 순회를 수행합니다 나무 구조에 일대일로 대응하십시오.두 개 이상의 자식이있는 트리의 선행 순서와 순서가 없음
다른 말로하면 일반 트리의 튜플 (preorder, inorder)이 일반 트리에 고유하거나 선주문 및 inorder 순회와 동일한 튜플을 가진 많은 트리가있을 수 있습니까?
간단히 일반 트리를 이진 트리 (here을보고)로 바꾼 다음 트래버스 할 수 있습니다.
비 순차 트리 (왼쪽 하위 트리 방문, 루트 방문, 오른쪽 하위 트리 방문)가 비 2 진 트리 (왼쪽 및 오른쪽 하위 트리가 없음)에 대해 정의되지 않았습니다.
분명히 선주문은 트리를 고유하게 정의하지 않습니다. 경로 A, B, C과 루트 A 및 하위 B 및 C이있는 트리 사이에는 차이가 없습니다.
그러나 선주문과 사후 주문의 조합은 모든 노드가 고유 한 경우 트리를 고유하게 정의합니다. 우리는 유도에 의해 이것을 보여줄 수 있습니다. 분명히 빈 문자열은 빈 트리를 고유하게 정의합니다.
비어 있지 않은 선주문 및 후행 문자열이 주어지면 선주문 문자열의 첫 번째 노드 (그리고 후순위의 마지막 노드)는 트리의 루트 R입니다. . 지금 우리가해야 할 일은 R의 자식을 근간으로하는 하위 트리 (상응하는 선매 주문 및 주문 후 문자열)를 찾아내는 것입니다. 왜냐하면 유도 가설로 그 구조를 찾을 수 있기 때문입니다.
RAaaaaaBbbbbb을 선주문 문자열로하고 aaaaaAbbbbbBR 포스트 오더 문자열 (a 및 b은 임의의 노드 임)을 사용하십시오. 분명히 A은 R의 첫 번째 하위 항목의 루트이며 선주문 문자열의 첫 번째 후임이기 때문에 분명합니다. 후순위에서는 해당 하위 트리가 A에서 끝납니다 (포스트 오더의 정의에 따라). 우리는 그 부분을 자르고 R의 두 번째 자식이 B이어야 함을 확인합니다. B이 포스트 오더 문자열의 마지막 노드이므로 R의 아이는 더 이상 존재하지 않습니다. 우리는 이제 두 개의 작은 하위 문제, 즉 , aaaaaA 및 Bbbbbb, bbbbbB을가집니다. 우리는 유도 가설에 의해 이것들을 풀 수있다.
이것이 [CS.SE] (http://cs.stackexchange.com)의 질문이라고 생각합니다. 어쨌든, 비 - 바이너리 트리에 대해 선주문 및 순차 트래버스를 정의해야합니다. –
inorder tree 일반 트리의 순회는 트리의 깊이를 처음으로 탐색하여 그에 따라 노드를 인쇄하는 것을 의미합니다. – ABHISHEK
@ABHISHEK 의미가 없습니다. 선주문 traversal과 post-order traversal을 같은 방식으로 설명 할 수 있습니다 (선주문은 DFS를 수행하고 후속 작업은 DFS를 처리하고 종료시 인쇄합니다). 순차적이란 의미는 왼쪽 하위 트리 이후와 오른쪽 하위 트리 이전에 루트를 방문한다는 의미입니다. 이를 임의의 나무로 일반화하는 논리적 인 방법은 없습니다. –