트리 두 노드를 바꿀 수있는 순회

Question

방금이 문제를 보았고 올바른 해결책을 제시 할 수 있는지 궁금합니다. 이 문제는 가치뿐만 아니라 노드별로 이진 트리의 두 노드를 교환하는 과정에서 발생합니다. 그래서 이것은 우리가 오른쪽과 왼쪽의 값을 변경해야한다는 것을 의미합니다.

그래서 우리는 위의 이미지와 같은 이진 트리 뭔가를 말할 수 있습니다. 처음에 생각한 것은 노드의 inorder 순회를 만들어서 트리를 평탄화시킨 다음 요소를 교체 한 다음 스왑 된 목록에서 트리를 재구성하는 것입니다. 그래서 말 그대로 해결책이

같은 것이 위에서 언급 한 나무의 경우, 중위 순회 이런 목록

1,3,4,6,7,8,10,13,14를 생성하는 것이다 간다. 나는 나무를 평평 이후

지금 나는 여기에 8

=> 1,3,4,6,7,13,10,8,14

(13) 그러나 문제를 교환 이제는 재구성하려고 할 때, 특정 노드가 왼쪽 서브 칠드인지 또는 루트인지 여부와 같은 개별 노드의 위치를 ​​알지 못하기 때문에 그렇게 할 수 없습니다. 따라서 문자 그대로 처음에는 교체 된 노드와 마찬가지로 트리를 재생성 할 수 없습니다.

이제 질문은 내가 각 노드의 위치 정보를 보유하도록 내 순회 알고리즘을 수정할 수 있는지 여부입니다. 그러면 요소를 교체하고 원하는 노드가 교체 된 동일한 이진 트리가 생성되도록 재구성 할 수 있습니까? inorder traversal 중에 개별 노드의 상태/위치를 저장할 수 있습니까?

추신. 포스트 오더를 수행하면 첫 번째 노드와 마지막 노드가 바뀌는 목록을 만들 수 있지만 두 노드를 바꿔야 할 필요는 루트와 오른쪽 요소 일 필요는 없습니다. 두 노드가 될 수 있습니다.

Answer 1

질문에 모호한 점이 많습니다. BST에있는 예제의 트리 (BST는 이진 트리이기도 함)와 최종 응답은 BST 속성을 손상시킬 수 있습니다. 나는 그 대답이 무엇이 필요하다는 것을 추정한다. 내가 틀렸다면 나를 바로 잡아라.

답변에 관한 한 두 가지 해결책이 있습니다.

하나는 트래버스와 병합의 관점에서 말하면 하나의 순회만으로 트리를 다시 구성 할 수 없다고 생각합니다. 나무를 만들기 위해서는 2 개의 횡단이 필요합니다. 그것은 순서

포스트 위해

1. 사전 순서와 아래 중 하나가 될 수 있고 위해서는 순서
2. 레벨 순서대로와는

그래서 어떤에서 스와핑을 2 개의 횡단과 recontruct. 그 대답을해야합니다.

두 번째 솔루션은 Time Comp가 O (n)이기 때문에 훨씬 효율적이고 효율적인 솔루션입니다. 이 방법에서는 전체 트리를 순회하고 2 개의 후보 노드에 대한 참조 포인터를 얻습니다. 일단 참조 정보가 있으면 임시 변수를 사용하여 정보를 교환하십시오.이 방법은 복잡하지만 이전 방법보다 공간과 시간이 효율적입니다.

---

HW 질문이 아니라면 태그 달기 바랍니다.

예 :

  4 
     2  6 
     1 3 5 7 

이 나무의 순서 탐색은 다음과 같습니다 사전 : 4 2 1 3 6 5 7 중위 : 1 2 3 4 5 6 7

이제 당신이 알고 그 4는이 트리의 루트입니다 (루트는 Preorder의 첫 번째 요소로 인쇄되기 때문에). 4를 기반으로 트래버스를 분할합니다.

이제 왼쪽 하위 트리가 이됩니다. Pre : 2 1 3; Inorder : 1 2 3

오른쪽 하위 트리가 이됩니다. Pre : 6 5 7; Inorder : 5 6 7

재귀 적으로 계속하면 그 대답이됩니다!