나 무 를 옮 겨 다 니 는 TJUACM 3988 Password

나무의 옮 겨 다 니 는 것 은 데이터 구조의 가장 기본 적 인 문제 중의 하나 이다.
앞 순 서 를 옮 겨 다 니 기: 뿌리 노드 를 먼저 옮 겨 다 니 기 - > 왼쪽 아이 - > 오른쪽 아이 (뿌리 좌우)
왼쪽 아이 - > 뿌리 노드 옮 겨 다 니 기 - > 오른쪽 아이 (왼쪽 오른쪽)
다음 순서 옮 겨 다 니 기: 왼쪽 아이 - > 오른쪽 아이 -> 마지막 으로 루트 노드 옮 겨 다 니 기 (왼쪽, 오른쪽)
재 귀 하 는 모든 단 계 는 하나의 문제 이다. 즉, 나 무 는 뿌리 와 왼쪽 나무, 오른쪽 나무 로 구성 되 고 잎 노드 는 좌우 나무 가 없다.
 
천진대학 교 ACM 3988 Password 가 요구 하 는 문 제 는:
어떤 나무의 앞 순 서 를 정 하고 가운데 순 서 를 옮 겨 다 니 며 이 나무의 뒤 순 서 를 찾 습 니 다.
해법: 앞 순 서 를 따라 뿌리 를 옮 겨 다 니 며 중간 순 서 를 옮 겨 다 니 는 서열 의 위 치 를 확인 하여 뿌리 결점 의 좌우 서브 트 리 를 확인 할 수 있 습 니 다.
중간 순서 에 따라 좌우 하위 트 리 의 길 이 를 옮 겨 다 니 며 좌우 하위 트 리 가 앞 순서 에 있 는 위 치 를 확인 할 수 있 습 니 다.
그리고 왼쪽 나무 와 오른쪽 나 무 는 각각 나무 입 니 다. 지금 은 이 두 나무의 앞 순서 와 중간 순 서 를 가 져 오 면 이 문 제 를 재 귀적 으로 완성 할 수 있 습 니 다.
참조 코드 는 다음 과 같 습 니 다.

 1 #include 
 2 #define size 27
 3 int N, T;
 4 char pre[size];
 5 char ino[size];
 6 
 7 struct node{
 8     node* left;
 9     node* right;
10     char data;
11     node(int info) :data(info), left(NULL), right(NULL){};
12 };
13 
14 void partition(char s1[], char s2[], int len, node *rootNode){
15     char root = rootNode->data;
16     int left, right;
17     char left1[size], left2[size];
18     if (len > 0){
19         for (left = 0; left){
20             if (s2[left] == root)    break;
21             left2[left] = s2[left];
22         }
23         if (left>0){
24             for (int i = 1; i <= left; i++)
25                 left1[i - 1] = s1[i];
26             node *Left = new node(left1[0]);
27             rootNode->left = Left;
28             partition(left1, left2, left, Left);
29         }
30         right = len - left - 1;
31         char right1[size], right2[size];
32         if (right > 0){
33             for (int i = left + 1; i < len; i++){
34                 right1[i - left - 1] = s1[i];
35                 right2[i - left - 1] = s2[i];
36             }
37             node *Right = new node(right1[0]);
38             rootNode->right = Right;
39             partition(right1, right2, right, Right);
40         }
41     }
42 }
43 
44 void postrav(node *rootNode){
45     if (rootNode->left != NULL)
46         postrav(rootNode->left);
47     if (rootNode->right != NULL)
48         postrav(rootNode->right);
49     printf("%c", rootNode->data);
50 }
51 
52 int main(void){
53     freopen("input.txt", "r", stdin);
54     while (scanf("%s
%s
", &pre, &ino) != EOF){
55         for (N = 0; N < size; N++)
56         if (pre[N] == '\0') break;
57         node *Root = new node(pre[0]);
58         partition(pre, ino, N, Root);
59         postrav(Root);
60         printf("
");
61     }
62     return 0;
63 }

이 문 제 는 나 무 를 만 들 지 않 고 재 귀적 으로 결 과 를 출력 할 수도 있다.

 1 #include 
 2 char preOrder[27], inOrder[27], postOrder[27];
 3 void getPostOrder(int preIndex, int inIndex, int length){
 4     if (length <= 0)return;
 5     if (length == 1){
 6         printf("%c", preOrder[preIndex]);
 7         return;
 8     }
 9     int i = 0;
10     while (preOrder[preIndex] != inOrder[inIndex + i])i++;
11     getPostOrder(preIndex + 1, inIndex, i);
12     getPostOrder(preIndex + i + 1, inIndex + i + 1, length - i - 1);
13     printf("%c", preOrder[preIndex]);
14 }
15 int getlen(char *Order){
16     int i = 0;
17     while (Order[i] != '\0')i++;
18     return i;
19 }
20 int main(){
21     while (scanf("%s%s", &preOrder, &inOrder) != EOF){
22         getPostOrder(0, 0, getlen(preOrder));
23         printf("
");
24     }
25     return 0;
26 }

이상 의 연습 을 통 해 이 진 트 리 의 역 사 를 비교적 깊이 이해 할 수 있다.그러나 실제 사용 에서 서로 다른 유형의 나 무 는 다양한 기능 을 실현 할 수 있 고 서로 전환 할 수 있다.
결점 의 정 보 는 변화 가 생 길 수 있 지만, 옮 겨 다 니 는 사상 은 변 하지 않 는 다.
예 를 들 어 가지 가 제한 이 없 는 나무 가 있 고 어떤 경우 에는 이 진 트 리 로 바 뀌 어야 하 며 결점 정 보 는 형제 결점 이 되 고 첫 번 째 아 이 는 결점 이 된다.
이때 K 노드 와 그 하위 나 무 를 옮 겨 다 닐 때 K 노드 를 옮 겨 다 닌 다음 K 의 첫 아이 부터 앞 순 서 를 옮 겨 다 닌 다.K 결점 의 형제 결점 은 K 의 아버지의 아이 결점 이기 때문에 널리 퍼 져 서 는 안 된다.
그러나 K 의 첫 아이 부터 형 제 는 잎 이 맺 힐 때 까지 널리 퍼 져 야 한다.
이 인 스 턴 스 는 Filesystem Implementation 의 진 제 를 볼 수 있 고 '진제 해석' 분류 에서 볼 수 있 습 니 다.
노드 의 관건 적 인 정 보 를 Hash 처리 한 후 일반 트 리 를 이 진 트 리 로 바 꾸 는 것 은 빈 메모 리 를 줄 이 고 검색 효율 을 높이 기 위 한 것 이다.
실제로 모든 노드 의 아 이 를 링크 로 저장 하 는 것 으로 이해 할 수 있다.
파일 감염 은 매우 추천 하 는 확장 문제 로 트 리 의 데이터 삭제 와 검 사 는 모두 연습 이 있다.
 
다음으로 전송:https://www.cnblogs.com/proscientist/p/8330904.html