이진탐색트리에서
연분홍
2024.12.07
데이터값이 정수로 이루어진 이진탐색트리가 있다고 가정하고.
특정 정수를 키보드로부터 입력받아서
그 정수보다 크거나 작은 값들을 출력하려고할때.
이진탐색트리를 전위순회를 하든, 후위순회를 하든, 중위순회를 하든, 트리의 모든 노드를 들린다음 입력받은 값과 비교해서 참일경우 출력하는 방법이 정석적인 방법인가요?
아니면 좀더 나은 방법이나 정석적인 방법이 있나요?
-
총알탄 2024-12-07
정렬일 경우를 기준으로...
중위순회로 큰값은 upper bound까지 왼쪽자식먼저, 작은 값은 lower bound까지 오른쪽자식먼저 탐색해나가면 원하는 값들만 구할 수 있습니다... -
LimeTree 2024-12-07
..............4
....3...................7
.1.....2.............5....9 -
찬슬 2024-12-07
이진트리로 하는 이유가 검색을빠르게 하기위해서 이기때문에..
보통 이진트리가 같는 값들은 루트를 기준으로 작은값은 왼쪽 큰값은 오른쪽에 위치하게됩니다.
같은값도 갖지게 합니다.
그렇게 레벨이 증가할때도 똑같이 부모노드보다 작은값은 왼쪽 큰값은 오른쪽으로 하게되면...
검색시 루트보다 큰가 작은가 같은가 비교하고
작은가 큰가 비교하고....... 이런식으로 비교해서 같으면 출력하고 아님 못찾은거고...
이런식이기때문에 모든 노드를 거칠 필요가없습니다.
| 번호 | 제 목 | 글쓴이 | 날짜 |
|---|---|---|---|
| 2690486 | 문자열과 문자형이요 ~ | 다스리 | 2025-04-05 |
| 2690344 | 일본어 주석 깨짐 문제 (3) | 연하얀 | 2025-04-04 |
| 2690314 | 암호문 만들기 -비제네르- | 이퓨리한나 | 2025-04-03 |
| 2690292 | 왕초보자의 질문!!!!!! 도와주세요 (1) | 하랑 | 2025-04-03 |
| 2690269 | 정올 문제 인데.. 흠 | 반월 | 2025-04-03 |
| 2690237 | sizeof에서 short형을 썻는데 왜 4byte가 나올까요? (1) | 바나나 | 2025-04-03 |
| 2690183 | 문자열과 포인트 비교 (2) | 미즈 | 2025-04-02 |
| 2690154 | a -48 ? | 희미한눈물 | 2025-04-02 |
| 2690094 | 테트리스 질문요. | 지후 | 2025-04-01 |
| 2690066 | 문자열비교!! (1) | 매디 | 2025-04-01 |
| 2689888 | 좀도와주세요;; ㅠㅠ | 사람 | 2025-03-30 |
| 2689856 | 메뉴 그리는 거 질문 | 나라빛 | 2025-03-30 |
| 2689831 | c언어 프로그램 추천 | 하연 | 2025-03-30 |
| 2689801 | c언어 time.h에서 작동이 중지되었습니다. | 하람 | 2025-03-30 |
| 2689772 | 2차원 배열의 배열명에 대해서.. | 옆집꼬마야 | 2025-03-29 |
| 2689740 | 게임 TCP소켓 질문 (2) | 불꾼 | 2025-03-29 |
| 2689711 | 반복문 모래시계 | 한뎃집 | 2025-03-29 |
| 2689685 | 경우의 수에 따른 결과 처리 질문드립니다. (2) | 다흰 | 2025-03-29 |
| 2689655 | .exe에 아이콘 넣는 법좀 알려주세요 | 연하얀 | 2025-03-28 |
| 2689631 | #define 전처리문에 대해서 (2) | 사랑은아픔 | 2025-03-28 |