선행 순서 및 순서가 지정된 문자열을 사용하여 이진 트리가 다른 이진 트리의 하위 트리인지 확인합니다.

Question

이진 트리 T2가 이진 트리 T1의 하위 트리인지 여부를 확인하고자합니다. 나는 을 선주문 및 순서 순회를 사용하여 T2 및 T1에 대한 문자열 표현을 구축 할 수 있으며, T2 문자열이 T1 문자열의 하위 문자열 인 경우 T2는 T1의 하위 트리임을 읽을 수 있습니다.

이 방법으로는 다소 혼란스럽고 정확성에 대해서는 확신 할 수 없습니다.

위키에서 : "T의 하위 트리는 T의 노드와 T의 하위 노드로 구성된 트리입니다." 다음 예에서

:

T2: 
    1 
/\ 
2 3 

T1: 
    1 
/\ 
2 3 
    \ 
     4 

우리가 T2와 T1의 문자열을 빌드하는 경우 :

전순 T2 : "1,2,3"
전순 T1 : "1,2, 3,4 "T2 중위
"2,1,3 "
T1 중위"2,1,3,4 '

T2 문자열 따라서 문자열 정합 방법 D를 사용하여, T1의 문자열이다 위에서 설명했듯이, 우리는 T2가 T1의 하위 트리라고 결론을 내려야합니다.

그러나 정의에 의한 T2는 T1의 루트 노드의 모든 자손을 가지지 않으므로 T1의 하위 트리가 아니어야합니다.

관련 토론이 있습니다. here은 방법이 정확하다고 판단하는 것 같습니다.

여기에 뭔가가 있습니까?

Answer 1

매우 흥미로운 질문입니다. 너는 옳은 것 같다. math (graph theory)의 하위 트리와 컴퓨터 과학의 정의가 다르기 때문에 언급 한 문제가 발생한다고 생각합니다. 그래프 이론에서 T2는 T1의 적절한 하위 트리입니다.

Answer 2

트리의 하위 트리 정의는 문자열의 하위 문자열 정의와 동일해야합니다. 이것을 다음과 같이 생각하십시오 : 1. sub-string은 begin-with, contains 및 ends-with가 있습니다. 2. 트리도 동일한 정의를 가지지 만 트리 데이터 구조에 맞게 일반화되어야합니다. 3. 일반화는 문자열의 경우 1 차원에서 트리의 경우 2 차원입니다.

Answer 3

나는 같은 책을 읽고 그 해결책도 의심했다. 나는 사용자 icepack이 (모든 자손을 반드시 필요로하지 않는 하위 트리의) 잠재적 인 해석에 해당하지 않는 또 다른 반대 사례를 생각해 냈습니다.

는 다음 나무를

T2: 
    B 
/\ 
A C 

T1: 
    C 
/\ 
    B C 
/
A 

전순 T2를 고려해 'BAC'
전순 T1 'CBAC'T2 중위
: T1 중위 'ABC'
'ABCC'

다시 말하지만, T2 문자열은 T1 대응 문자열의 하위 문자열이지만 T2는 T1의 하위 트리가 아닙니다. 아마 저자가 중복을 배제하고 구체적으로 하위 트리에 대한 자신의 정의를 언급했지만 그 정보를 남겨두면 선택의 여지가 없지만 잘못된 해결책이라고 생각할 수 있습니다.

Answer 4

Na ...이 방법은 정확하지 않습니다. 다른 트리는 동일한 순회를 가질 수 있습니다. 예를 들어 여기에 주어진 예에서, 나무가

  26 
     / \ 
     10  3 
    / \  \ 
    4  6  3 
    \ 
    30 

을하고 후보 하위 트리가

10 
/\ 
4 6 
\ 
30 

및

30 
/\ 
4 10 
\ 
6 

이다 4,30,10로 통과 중위 같은이, 6 하지만 두 번째 것은 서브 트리가 아닙니다

Answer 5

"Crac King Coding Interview "에서 저자는 또한 동일한 값을 가진 노드를 구별하기 위해 Null 값을 출력해야한다고 언급했습니다. "1, 2, 널, 3, NULL, NULL, NULL" :

이것은 또한 (또한이 책에 설명 된대로 올바른) 하위 트리의 정의

전순 T2와 함께 문제를 해결할 것 T1,232 : null, 2, null, 1, null, 3, null "T1 : null, 2, null, null, 3, null, 4, null, null" 4, 널, 3, 널 (null), 1, 널 (null),

당신이 볼 수 있듯이 "널 (null), T2는 즉,

가