이진 트리 순회, 1부
6206 단어 picolispalgorithmsfunctionallisp
일
Implement a binary tree where each node carries an integer, and implement:
- pre-order,
- in-order,
- post-order, and
- level-order traversal.
Use those traversals to output the following tree:
1
/ \
/ \
/ \
2 3
/ \ /
4 5 6
/ / \
7 8 9
The correct output should look like this:
preorder: 1 2 4 7 5 3 6 8 9
inorder: 7 4 2 5 1 8 6 9 3
postorder: 7 4 5 2 8 9 6 3 1
level-order: 1 2 3 4 5 6 7 8 9
작업에 대한 몇 가지 생각
가장 먼저 명확히 해야 할 것은 "preorder", "inorder", "postorder"및 "level-order"의 의미입니다. 이 Wikipedia article이 도움이 될 수 있습니다.
preorder: 현재 노드를 방문하고, 왼쪽 하위 트리를 순회하고, 오른쪽 하위 트리를 순회합니다.
inorder 왼쪽 하위 트리 탐색, 현재 노드 방문, 오른쪽 하위 트리 탐색.
후위 순회 왼쪽 하위 트리, 오른쪽 하위 트리 순회, 현재 노드 방문.
레벨 순서("너비 우선 검색"이라고도 함) 트리는 다음 깊이로 이동하기 전에 가능한 한 확장됩니다.
이진 트리의 주요 특징 중 하나는 "큰"이진 트리가 "작은"트리의 반복적인 패턴으로 구성된다는 것입니다. 이것은 우리에게 매우 편리합니다. 즉, 재귀를 사용하여 매우 간단한 방법으로 위의 네 가지 규칙을 정의할 수 있음을 의미합니다.
1단계. 트리 정의
이전 게시물에서 이진 트리는 구문이
(root (left-child) right-child) 인 중첩 목록으로 표현된다는 것을 배웠습니다. 전역 변수 *Tree을 목록으로 설정해 보겠습니다.(setq *Tree
(1
(2 (4 (7)) (5))
(3 (6 (8) (9))) ) )
(view <var>) 을 사용하여 REPL의 트리 구조를 다시 확인할 수 있습니다.질문: 이전 게시물에서 배운
idx 함수를 사용하지 않은 이유는 무엇입니까? - 작업의 트리가 검색 트리가 아니기 때문입니다. 검색 트리에서 왼쪽 자식은 더 작고 오른쪽 자식은 루트보다 큽니다.이진 트리의 재귀적 특성
이제 이진 트리의 특성에 대해 조금 생각해볼 필요가 있습니다. 앞에서 큰 이진 트리는 작은 이진 트리의 구성이라고 말했습니다. 정확히 무엇을 의미합니까?
위의 이진 트리 예제를 보고 루트를 "잘라내십시오". 당신은 무엇을 얻습니까? 두 개의 새로운 이진 트리!
이진 트리가 실제로 목록으로 구현된다는 사실과 함께 이것은 매우 편리한 특성입니다. 목록에서 우리는
car 함수를 사용하여 첫 번째 목록 요소에 액세스할 수 있고 나머지는 cdr -function을 사용하여 액세스할 수 있습니다. (이유를 잊은 경우 List and Strings post으로 돌아가십시오).: (car *Tree)
-> (1)
: (cdr *Tree)
-> -> ( (2 (4 (7)) (5)) (3 (6 (8) (9))) )
이제 우리는
2, 4, 7, 5이 하나의 하위 트리를 형성하고 3, 6, 8, 9이 또 다른 하위 트리를 형성한다는 것을 알고 있습니다. 이는 (cdr *Tree) : ( (subtree 2-4-7-5) (subtree 3-6-8-9) 의 출력에 해당합니다.즉,
car 에서 cdr 및 (cdr *Tree) 을 수행하면 양쪽에서 하위 트리를 얻을 수 있습니다.car (cdr ...) 대신 cadr 을 쓸 수 있고, cdr (cdr ..) 대신 cddr 을 쓸 수 있습니다. 이것을 사용합시다:: (cadr *Tree)
-> (2 (4 (7)) (5))
: (cddr *Tree)
-> ((3 (6 (8) (9))))
오른쪽 하위 트리의 경우:
Looks almost good, only one minor modification is needed.cddr returns a **list with only one item**. In order to get this single item, let's take the car of cddr , in short caddr
: (caddr *Tree)
-> (3 (6 (8) (9)))
One last thing to mention is that the car and cdr functions do not modify the original Tree. We merely move the pointers around. This means, these functions are **not destructive *:
`
: *Tree
-> (1 (2 (4 (7)) (5)) (3 (6 (8) (9))))
`
...그리고 재귀!
우리 트리의 재귀 특성을 다시 확인합시다. 왼쪽 하위 트리인 2-4-7-5를 살펴보겠습니다. 다시, 자동차로 노드를, cadr로 왼쪽 하위 트리를, caddr로 오른쪽 하위 트리를 얻습니다.
: (자동차 (cadr *나무))
-> 2
: (cadr (cadr *트리))
-> (4(7))
: (cadr (cadr *트리))
-> (5)
존재하지 않는 위반에 액세스하려고 하면 NIL을 얻습니다.
: (cadr(cadr(cadr *트리))))
-> 없음
2단계. 기능 정의
이제 흥미로운 부분이 있습니다. 이 재귀적 특성을 사용하여 사전 주문 작업을 해결하는 방법은 무엇입니까? 음, 위의 정의는 이미 우리에게 어떻게 하는지 알려줍니다.
preorder: 현재 노드를 방문하고, 왼쪽 하위 트리를 순회하고, 오른쪽 하위 트리를 순회합니다.
인수 Tree(우리가 지금 알고 있는 목록임)를 사용하여 함수 선주문을 정의해 봅시다. Tree가 정의되어 있으면 루트를 인쇄해 보겠습니다.
(de 선주문(Tree)
(printsp(자동차 트리)
....
이제 "왼쪽 하위 트리를 탐색"하고 왼쪽 하위 트리가 있으면 인쇄합니다. 그런 다음 가능한 경우 왼쪽 자식을 다시 가져옵니다. 왼쪽 자식이 없으면 NIL을 반환하고 다음에 오른쪽을 시도합니다. 글쎄요, 그게 이미 할 일의 전부입니다.
(de 선주문(Tree)
(트리
(printsp(자동차 트리))
(선주문(cadr 트리) )
(선주문(caddr 트리) ) ) )
이 함수는 1 2 4 7 5 3 6 8 9를 반환합니다.
이제 inorder와 postorder를 쉽게 정의할 수 있습니다. 기본적으로 순서의 변형일 뿐입니다.
inorder: 왼쪽 하위 트리 순회, 현재 노드 방문, 오른쪽 하위 트리 순회.
(de inorder(트리)
(트리
(inorder(cadr 트리))
(printsp(자동차 트리))
(inorder(caddr 트리)) ) )
postorder: 왼쪽 하위 트리 순회, 오른쪽 하위 트리 순회, 현재 노드 방문.
(de postorder(트리)
(트리
(사후 주문(cadr 트리))
(사후 주문(caddr 트리))
(printsp(자동차 트리)) ) )
3단계. 함수 호출
마지막 단계는 함수를 호출하고 출력을 얻는 것입니다.
`
(printsp '선주문:)
(선주문 *트리)
(원칙)
(printsp 'inorder:)
(중순 *트리)
(원칙)
(printsp '포스트오더:)
(포스트오더 *트리)
(원칙)
`
Reference
이 문제에 관하여(이진 트리 순회, 1부), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://dev.to/miatemma/binary-tree-traversal-part-1-2m0m텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
우수한 개발자 콘텐츠 발견에 전념
(Collection and Share based on the CC Protocol.)
좋은 웹페이지 즐겨찾기
