이진탐색트리에서
연분홍
2024.12.07
데이터값이 정수로 이루어진 이진탐색트리가 있다고 가정하고.
특정 정수를 키보드로부터 입력받아서
그 정수보다 크거나 작은 값들을 출력하려고할때.
이진탐색트리를 전위순회를 하든, 후위순회를 하든, 중위순회를 하든, 트리의 모든 노드를 들린다음 입력받은 값과 비교해서 참일경우 출력하는 방법이 정석적인 방법인가요?
아니면 좀더 나은 방법이나 정석적인 방법이 있나요?
-
총알탄 2024-12-07
정렬일 경우를 기준으로...
중위순회로 큰값은 upper bound까지 왼쪽자식먼저, 작은 값은 lower bound까지 오른쪽자식먼저 탐색해나가면 원하는 값들만 구할 수 있습니다... -
LimeTree 2024-12-07
..............4
....3...................7
.1.....2.............5....9 -
찬슬 2024-12-07
이진트리로 하는 이유가 검색을빠르게 하기위해서 이기때문에..
보통 이진트리가 같는 값들은 루트를 기준으로 작은값은 왼쪽 큰값은 오른쪽에 위치하게됩니다.
같은값도 갖지게 합니다.
그렇게 레벨이 증가할때도 똑같이 부모노드보다 작은값은 왼쪽 큰값은 오른쪽으로 하게되면...
검색시 루트보다 큰가 작은가 같은가 비교하고
작은가 큰가 비교하고....... 이런식으로 비교해서 같으면 출력하고 아님 못찾은거고...
이런식이기때문에 모든 노드를 거칠 필요가없습니다.
| 번호 | 제 목 | 글쓴이 | 날짜 |
|---|---|---|---|
| 2679679 | 이거 도저히 모르겠네요 | 시내 | 2024-12-26 |
| 2679655 | 구조체 안에 구조체 수정해서 질문드려봅니다 | 새밝 | 2024-12-26 |
| 2679628 | 조건만족이 안됬는데 반복문이 실행됩니다. | 정훈 | 2024-12-26 |
| 2679603 | 라이브러리 추가에 관한 질문입니다 | 별햇님 | 2024-12-26 |
| 2679553 | in- order방식인데요. | 아이 | 2024-12-25 |
| 2679527 | 출력프로그램 만들기 질문요 | 레온 | 2024-12-25 |
| 2679503 | 네트워크프로그래밍질문이요... (1) | 나리 | 2024-12-25 |
| 2679474 | 알고리즘 질문... | 안다미로 | 2024-12-24 |
| 2679444 | system 함수 관련 질문 드립니다 (4) | 천사 | 2024-12-24 |
| 2679416 | c언어 숙제인데 좀 봐주세요 | 인1형녀 | 2024-12-24 |
| 2679387 | atoi 함수 쓸때 빈칸이 있으면요 (1) | HotPink | 2024-12-24 |
| 2679357 | 뇌를 자극하는 알고리즘 중에서..ㅜ | 발랄한그1녀 | 2024-12-23 |
| 2679307 | 궁금해서 그러는데요 기초적인건데 잘 모르겠어요 ㅠ (2) | 참이삭 | 2024-12-23 |
| 2679280 | 회원가입 함수와 로그인 함수를 만들었는데요.. (6) | 꺄홋 | 2024-12-23 |
| 2679247 | 다차원 배열과 포인터에 관한 질문입니다. (4) | 터전 | 2024-12-22 |
| 2679218 | c언어 문제질문요. | 옆집언니 | 2024-12-22 |
| 2679189 | 숫자를 거꾸로 출력하기.... 어떻게짜야할지..생각이안떠올라용. (7) | 주인님 | 2024-12-22 |
| 2679164 | 구조체 인데요..잘 안나와서 질문이요.. (1) | 하늘이 | 2024-12-22 |
| 2679140 | 쉬프트 연산자 사용이유? (2) | 핫블랙 | 2024-12-21 |
| 2679112 | 간단한질문-정렬을 쓰지 않고 n번째 작은수 구하기(!?!?)(Quick sort) | 화가마 | 2024-12-21 |