두 갈래 나무의 전순, 중순과 후순의 상호 구문
3343 단어 두 갈래 나무중간 순서후순앞 순서전-중-후서 상호 구하기
1. 우선, 우리는 앞, 중간, 뒤의 반복적인 특성을 살펴본다.
앞의 순서 반복: 먼저 루트 노드를 방문하고, 그 다음에 왼쪽 트리를 방문하고, 마지막으로 오른쪽 트리를 방문한다.왼쪽, 오른쪽 나무를 훑어볼 때, 뿌리 노드를 먼저 방문한 다음, 왼쪽 나무를 훑어보고, 마지막에 오른쪽 나무를 훑어본다.(루트->왼쪽->오른쪽)
중차 반복: 먼저 왼쪽 트리를 방문하고, 그 다음에 루트 노드를 방문하고, 마지막으로 오른쪽 트리를 방문한다.왼쪽, 오른쪽 나무를 두루 돌아다닐 때, 여전히 먼저 왼쪽 나무를 두루 돌아다녔고, 다시 뿌리 결점을 방문하여 마지막으로 오른쪽 나무를 두루 돌아다녔다.(왼쪽-.>뿌리->오른쪽) 뒷걸음질: 먼저 왼쪽 트리를 방문하고, 그 다음에 오른쪽 트리를 방문하고, 마지막으로 루트 노드를 방문한다.왼쪽, 오른쪽 나무를 두루 훑어볼 때, 여전히 먼저 왼쪽 나무를 두루 훑어본 다음에 오른쪽 나무를 두루 훑어보고, 마지막에 뿌리 결점을 두루 훑어본다.(왼쪽->오른쪽->루트)
A
/ \
B C
/ \ / \
D E F J
위 그림 앞의 순서: ABDECFJ
：DBEAFCJ
：DEBFJCA
2. 이미 알고 있는 전차 역과 중차 역, 후차 역행을 구하다
만약 앞의 순서가 ABDECFJ이고 중간의 순서가 DBEAFCJ인 것을 알고 있다면, 뒤의 순서를 묻는 결과는?
이런 문제에 대해 우리는 먼저 나무 한 그루를 그린 다음에 그것을 뒤돌아다닐 것을 선택했다.
어떻게 나무를 그리는가: 첫걸음: 앞의 순서에 따라 훑어보는 특징에 따라 우리는 뿌리 결점이 A라는 것을 안다
A
STEP 2: DBEAFCJ를 관찰합니다.그 중에서 루트 노드 A 왼쪽의 DBE는 루트의 왼쪽 트리이고 G 오른쪽의 FCJ는 루트의 오른쪽 트리이다.
A
/ \
(DBE) ( FCJ)
세 번째 단계, 왼쪽 트리 DBE를 관찰하면 앞의 순서에서 큰 나무의 루트의 leftchild는 루트 다음, 즉 A 뒤에 있기 때문에 왼쪽 트리의 뿌리 노드는 B이다.
A
/
B
네 번째, 같은 이치로 루트의 오른쪽 트리 노드 FCJ의 뿌리 노드도 앞의 순서를 통해 두루 구할 수 있다.앞의 순서에서 루트와 루트의 모든 왼쪽 트리 노드를 다 훑어본 후에야 오른쪽 트리를 훑어볼 수 있고 훑어보는 왼쪽 트리의 첫 번째 노드는 왼쪽 트리의 뿌리 노드이다.같은 이치로 두루 돌아다니는 오른쪽 나무의 첫 번째 노드는 오른쪽 나무의 뿌리 노드이기 때문에 C는 오른쪽 나무의 굽이 노드이다.
A
/ \
B C
다섯 번째 단계는 B 왼쪽의 D는 왼쪽 나무, E는 B의 오른쪽 나무, 동리 F는 C의 왼쪽 나무, J는 C의 오른쪽 나무를 중순으로 훑어본다.
A
/ \
B C
/ \ / \
D E F J
마지막으로 관찰한 결과 위의 과정은 차례차례 귀속된 것이다.먼저 현재 나무의 뿌리 노드를 찾은 다음에 왼쪽 나무, 오른쪽 나무로 구분한 다음에 왼쪽 나무에 들어가 위의 과정을 반복하고 오른쪽 나무에 들어가 위의 과정을 반복한다.마지막으로 나무 한 그루를 복원할 수 있다.이로부터 상기 두 갈래 나무의 뒷 순서는 DEBFJCA이다
3. 이미 알고 있는 중서 역과 후서 역은 전서 역행을 구한다.
만약 중차 역행 결과가 DBEAFCJ이고 후차 역행 결과가 DEBFJCA인 것을 알고 있다면, 전차 역행 결과를 묻겠습니다.우리는 여전히 먼저 나무 한 그루를 그린 다음에 그것을 뒤돌아다닐 것을 선택했다.
첫 번째 단계는 뒷차례 역력의 특징에 따라 우리는 뒷차례 역력의 마지막 결점이 바로 뿌리 결점, 즉 뿌리 결점이 A라는 것을 안다.
A
두 번째 단계는 DBEAFCJ를 살펴보는 것입니다.그 중에서 루트 노드 G 왼쪽의 DBE는 루트의 왼쪽 트리이고 G 오른쪽의 FCJ는 루트의 오른쪽 트리이다.
A
/ \
(DBE) (FCJ)
세 번째 단계, 왼쪽 트리 DBE를 관찰하면 뒷 순서에서 루트 왼쪽 트리의 순서는 DEB이고 뒷 순서에서 루트 왼쪽 트리는 leftchild의 루트 노드, 즉 루트의 왼쪽 트리임을 알 수 있다.
A
/
B
네 번째 단계는 오른쪽 트리 FCJ를 같은 이치로 관찰하고 뒷 순서에서 루트 오른쪽 트리의 순서는 FJC이기 때문에 C는 루트의 오른쪽 트리이다.
A
/ \
B C
다섯 번째 단계는 D, E가 각각 B의 좌우 자목이고 F, J가 C의 좌우 자목이라는 것을 중순으로 훑어본다.
A
/ \
B C
/ \ / \
D E F J
다섯 번째 단계, 관찰 결과 위의 과정은 귀속적이다.먼저 현재 나무의 뿌리 노드를 찾은 다음에 왼쪽 나무, 오른쪽 나무로 구분한 다음에 왼쪽 나무에 들어가 위의 과정을 반복하고 오른쪽 나무에 들어가 위의 과정을 반복한다.마지막으로 나무 한 그루를 복원할 수 있다.이로써 상기 수의 앞순서는 ABDECFJ로 옮겨갔다
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
java 데이터 구조 2차원 트리의 실현 코드일.두 갈래 트리 인터페이스 2 노드 클래스 3. 두 갈래 나무 구현 이 글을 통해 여러분께 도움이 되었으면 좋겠습니다. 본 사이트에 대한 지지에 감사드립니다!...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
