C 언어 이 진 트 리 와 더미 의 개념 과 실현
자연계 에 나무 가 많아 요.이렇게 돼 있어 요.
그런데 저희 눈 에는 이렇게 보 여요.
분명 한 것 은 나무의 특징 은 한 쌍 이 많다 는 것 이다.우 리 는 이 한 쌍 의 많은 특징 을 이용 하여 프로 그래 밍 중의 문 제 를 잘 해결 할 수 있다.나무 에서 가장 기본 적 인 이 진 트 리 는 우리 의 중점 연구 대상 이다.
신기 한 정렬 된 동적 그림 을 보고 있 습 니 다.
일 을 하려 면 먼저 옳 은 것 을 구하 고,교묘 한 것 을 추구 해 야 한 걸음 한 걸음 성취 할 수 있 으 니,우리 기초 부터 시작 합 시다!
나무의 기본 성질 과 묘사
나 무 는 한 쌍 이 넘 는 특수 한 데이터 형식 으로 나무의 뿌리 는 위의 잎 에 있다.일생 2,2,3,3 생 만물 의 느낌 이 든다.
나무의 기본 특징
나 무 는 뿌리 가 하나 있 고 뿌리 는 후계 점 이 없다.
나 무 는 서로 교차 하지 않 는 다.
ps:그림 은 폐쇄 회로 가 구성 되 지 않 으 면 교차 하지 않 는 다 는 것 을 알 수 있다.
모든 결점 은 하나의 나무 로 나 눌 수 있다.
나무의 정 의 는 나무 가 정 의 를 내 릴 때 나무의 개념 을 사용 하 는 재 귀적 인 정의 이다.그 는 나무의 고유 한 특성 을 말 했다.
트 리 키워드 분석
나무 에 큰 키워드 가 있어 서 골 치 아파 요.
결점 의 분류:
ps：
결점 의 도:결점 이 가지 고 있 는 서브 트 리 수 를 결점 의 도 라 고 한다.도가 0 인 점 은 잎 노드 나 단말기 결점 이 되 고 도가 0 이 아 닌 노드 를 비 단말기 결점 이 라 고 한다.나무의 도 는 나무 안의 각 결점 의 최대 치 이다.이 그림 D 는 가장 큰 결점 입 니 다.
결점 의 차원:뿌리 부터 1 층 으로 순서대로 증가한다.
단순 대비 트 리 구조 와 선형 구조:
나무의 표시 방법
양친 표현법
typedef struct
{
int data;
int parent; //
}PtNode;
typedef struct
{
PtNode nodes[10];
int root ;
int n;
}PTree;
이 그림 의 숫자 는 아버지의 결점 을 나타 낸다.
'아버지의 하 표'를 통 해 아버지의 위 치 를 찾 을 수 있다.
주:
부모님 을 찾 는 시간 복잡 도 O(1);아들 을 찾 으 려 면 나 무 를 옮 겨 다 녀 야 한다.
데이터 의 첨삭 과 수정.
왼쪽 아이 오른쪽 형제
typedef struct CSNode
{
int data;
struct CSNode* firstchild, * rightsib;
};
이런 표현법 은 우리 가 자주 사용 하 는 표현법 이다.
이 진 트 리 의 개념 구조
이 진 트 리
이 진 트 리 는 특수 한 나무 로 그의 특징 은 뿌리 노드 두 개의 키 노드 이 고 이 두 개의 키 노드 는 각각 왼쪽 나무 와 오른쪽 나무 라 고도 부른다.
주의 하 다.
이 진 트 리 의 도 는 이 진 트 리 의 좌우 자 수 를 초과 하지 않 고 이 진 트 리 가 있 으 며 한 개의 나무 만 있 을 때 도 좌우 로 구분 해 야 한다.
특수 이 진 트 리
두 갈래 로 된 나무
이 진 트 리 는 층 마다 가득 차 있다.그러면 이 이 진 트 리 는 이 진 트 리 가 가득 하 다.이 진 트 리 의 층수 가 k 이 고 결점 총 수 는(2^k)-1 입 니 다.
완전 이 진 트 리
완전 이 진 트 리 의 앞 k 층 은 모두 가득 찬 k 층 이 불만 을 가 질 수 있 지만 반드시 연속 적 이 고 왼쪽 과 오른쪽 을 만족 시 켜 야 한다.
주의 하 다.
이 진 트 리 는 완전히 이 진 트 리 일 것 이 고,그렇지 않 으 면 옳지 않다.완전 이 진 트 리 는 반드시 먼저 왼쪽 과 오른쪽 이 고,아래 그림 과 같 으 면 맞지 않 는 다.
완전 이 진 트 리 잎의 결점 은 모두 마지막 두 층 에 있 고 왼쪽 은 마지막 k 층 의 잎 에 집중 되 며 오른쪽 은 k-1 층 의 잎 에 집중 된다.
이 진 트 리 의 성질
이 진 트 리 의 i 층 에는 기껏해야 2^(i-1)의 결점 i>0 이 있다.
깊이 가 k 인 이 진 트 리 는 많아야 2^k-1 개의 결점 이 있다
모든 이 진 트 리 T 에 대해 터미널 노드 트 리 가 n0 이 고 도 2 의 노드 트 리 가 n2 이면 no=n2+1 입 니 다.
n 개의 결점 을 가 진 완전 이 진 트 리 의 깊이 는 log 2(n)+1 이다.
n 개의 결점 을 가 진 완전 이 진 트 리 에 대해 위 에서 아래로 왼쪽 에서 오른쪽 순서 로 0 부터 번 호 를 매기 면 번호 와 i 의 결점 이 있다.
1.i>0 이면 i 위치 결점 의 부모 번 호 는(i-1)/2 이다.
2.만약 에 2i+1
3.만약 2i+2
parent， leftchild， ringhtchild。
： leftchild=parent*2+1
rightchild=parent*2+2
2n 개의 결점 을 가 진 완전 이 진 나무 에서 잎의 결점 개 수 는?
완전 이 진 트 리 에 풀 려 있 고 3 가지 경우 만 있 습 니 다.
도 0
도 는 0 이다.즉,뿌리 결점 잎의 결점 개수 만 n 이다.
1 도 1 의 결점 만 있다.
x 는 2 로 읽 는 결 점 수 를 설정 하고 y 는 잎 노드 수 x+y+1=2n 과 같 으 며 잎 수 는 2 로 읽 는 더하기 1 득 y=x+1
득 y=n
도 1 의 결점 이 없다
그림 에서 알 수 있 듯 이 짝수 의 결점 을 구성 하여 버 릴 수 없다.
다시 말 하면 잎 노드 의 개 수 는 n 이다.
완전 이 진 트 리 를 가 진 노드 수 는 531 개 입 니 다.그러면 이 나무의 높이 는?
해:공식 을 직접 가지 고 10.
767 개의 결점 을 가 진 완전 이 진 트 리 의 잎 노드 개 수 는?
앞의 결론 에서 알 수 있 듯 이 이 진 트 리 는 반드시
그래서 쌍 결점 을 x 잎 을 y=x+1 로 설정 하고 y+y-1=767 해 를 y=384 로 설정 합 니 다.
도 2 인 나무 와 이 진 나 무 는 어떤 차이 가 있 습 니까?
해:
도 2 의 나 무 는 무질서 한 나무 로 좌우 가 구분 되 지 않 으 며,이 진 트 리 는 왼쪽,오른쪽 이 어야 한다.도 2 의 나 무 는 반드시 하나의 결점 도 2 이 고,이 진 트 리 는 없 을 수 있다.
k 포크 나무 에 가득 한 잎 매듭 포인트 n0 과 비 잎 매듭 포인트 n1 숨 기기*n0=(k-1)n1+1 증명
우선,우 리 는 이 진 트 리 가 가득 하 다 는 것 을 알 게 되 었 다.이 진 트 리 는 n 층 이상 의 모든 결점 의 도 는 k 이다.
총 분기 결산 포인트=k 배의 n1
총 결 포인트=n0+n1
총 분기 결산 포인트+1=총 결산 포인트
kn1+1=no+n1
이 진 트 리 의 저장 구조
이 진 트 리 의 저장 소 는 위 에서 아래로 왼쪽 에서 오른쪽으로 정렬 된다.
이 두 갈래 나 무 를 배열 에 저장 하면 얻 을 수 있 습 니 다.
두 갈래 나무 와 더미
더 미 는 특수 한 수,즉 완전 이 진 트 리 이다.
이 나 무 를 관찰 하면 그의 아버지 결점 은 모두 자 결점 보다 작다.우 리 는 그것 을 최소 더미 라 고 부른다.반대로 모든 아버지 결점 이 자 결점 보다 크 면 이런 완전 이 진 나 무 는 최대 더미 가 된다.
주의:
더 미 는 완전 이 진 트 리 더미 이 고 큰 더미 와 작은 더미 두 가지 만 있 습 니 다.
쌓 인 실현
다음 배열 이 있 습 니 다.
int arr[] = { 23,2,5,12,7,17,25,19,36,99,22,28,46,92 };어떻게 그것 을 최소 더미 로 조정 합 니까?
그림 에서 알 수 있 듯 이 가장 작은 무더기 의 특징 은 아버지 가 아들 보다 작 고 이 나무 가 둘 러 싼 곳 은 아들 이 아버지 보다 크기 때문에 우 리 는 가장 작은 아들 을 바 꿔 야 한다.
바 꿔 보니까 저희 가 만족 하지 않 아서 바 꿔 야 돼 요.
원 을 그 리 는 곳 에 있 는 이 두 갈래 나 무 는 만족 하지 않 고 한 번 만 더 교환 하면 가장 작은 더미 이다.
이때 이 진 트 리 는 최소 더 미 를 만족 시 켰 다.
이 과정의 알고리즘 을 우 리 는 아래로 조정 하 는 알고리즘 이 라 고 부 릅 니 다.만약 우리 가 이 진 트 리 를 구분 하면...
아래로 조정 하 는 본질은 먼저 위의 것 을 만족 시 키 고 아래 의 것 을 만족 시 키 는 것 이다.
주의:
아래로 알고리즘 을 조정 합 니 다.원 소 를 조정 하 는 좌우 트 리 는 모두 최소 더미 여야 합 니 다.아래로 알고리즘 을 조정 하고 잎 이 맺 힐 때 멈 출 수 있 습 니 다.어린 아이 가 아버지 보다 때 리 면 처리 할 필요 가 없습니다.나무 전체 가 가장 작은 더미 입 니 다.
코드 를 첨부 하 다
#include<stdio.h>
void AdjustDown(int a[], int n, int parent)
{
int child = 2 * parent + 1;//
while (child < n)
{
if (child+1<n&&a[child] > a[child + 1])
{
child++;
}
if (a[parent] > a[child])
{
int tmp = a[child];
a[child] = a[parent];
a[parent] = tmp;
parent = child;
child = 2 * parent + 1;
}
else
{
break;
}
}
}
int main()
{
int arr[14] = { 23,2,5,12,7,17,25,19,36,99,22,28,46,92 };
int n = 14;
AdjustDown(arr, n, 0);
return 0;
}
그렇다면 더 일반적인 상황 에 서 는 좌우 나무 가 작은 더미 가 아 닌 데 어떻게 조정 할 것 인가?
우 리 는 단지 아래 에서 위로,작은 나무 더미 에서 큰 나무 더미 로 바 뀌 어야 한다.
먼저 만족 하고 아래 는 만족 하 는 것 이다.
먼저 아래 의 것 을 만족 시 키 고 만족 위 에 쌓 으 면 함수 에 모든 아버지 결점 을 차례대로 전달 하면 됩 니 다.
#include<stdio.h>
void AdjustDown(int a[], int n, int parent)
{
int child = 2 * parent + 1;
while (child < n)
{
if (child+1<=n && a[child] >a[child + 1])
{
child++;
}
if (a[parent] < a[child])
{
int tmp = a[child];
a[child] = a[parent];
a[parent] = tmp;
parent = child;
child = 2 * parent + 1;
}
else
{
break;
}
}
}
int main()
{
int arr[14] = { 23,2,5,12,7,17,25,19,36,99,22,28,46,92 };
int n = 14;
int tmp = 0;
int i = (n - 1 - 1) / 2;
for (i; i >= 0; i--)
{
AdjustDown(arr, n, i);
}
return 0;
}
상승 순 서 를 예 로 들 면,우 리 는 먼저 작은 무 더 기 를 생각 하지만,작은 무 더 기 는 적합 하지 않다.보다
우 리 는 쌓 아 올 리 는 요소 가 반드시 가장 작 을 것 이라는 것 을 안다.그러면 우 리 는 순서대로 쌓 아 올 리 는 것 만 가 져 가 야 한다.
저희 가 2 를 가 져 가면 7 이 쌓 여 있어 요.
쌓 인 지붕 을 제거 한 후 다음 요 소 는 작은 더 미 를 채 워 서 저장 되 지 않 고 순서 가 모두 어 지 러 워 졌 다.그래서 작은 무 더 기 는 오름차 순 에 적합 하지 않다.
무더기 의 상승 순 서 는 또 어떻게 해 야 합 니까?
이때 우 리 는 10 과 80 을 바 꾸 고 80 을 쌓 아 올 리 지 않 으 면 된다.
그렇다면 코드 실현 은 어 떨 까?
전체 코드 첨부
#include<stdio.h>
void AdjustDown(int a[], int n, int parent)
{
int child = 2 * parent + 1;
while (child < n)
{
if (child+1<n && a[child] <a[child + 1])
{
child++;
}
if (a[parent] < a[child])
{
int tmp = a[child];
a[child] = a[parent];
a[parent] = tmp;
parent = child;
child = 2 * parent + 1;
}
else
{
break;
}
}
}
int main()
{
int arr[14] = { 23,2,5,12,7,17,25,19,36,99,22,28,46,92 };
int n =14 ;
int tmp = 0;
int i = (n - 1 - 1) / 2;
for (i; i >= 0; i--)
{
AdjustDown(arr, n, i);
}
int end = n - 1;
while (end > 0)
{
int tmp = arr[0];
arr[0] = arr[end];
arr[end] = tmp;
AdjustDown(arr, end, 0);
end--;
}
return 0;
}
쌓 인 총 결:
물리 구 조 는 하나의 배열 이다논리 구 조 는 완전 이 진 트 리무더기 와 작은 무더기 의 관계
더미 정렬
요소 삽입
4.567917.최대 또는 최소 찾기쌓 인 기능 실현
더미 삽입
삽입여기 서 우 리 는 더미 의 상 향 조정 을 도입 한다.
그러면 코드 는 어떻게 실현 합 니까?아래 정렬 과 유사
코드 를 첨부 하 다
void AdjustUp(int* a, int n, int child)
{
int parent = (child - 1) / 2;
while (child>0)
{
if (a[parent] < a[child])
{
Swap(&a[parent], &a[child]);
child = parent;
parent = (child - 1) / 2;
}
else
{
break;
}
}
}
아래로 정렬 할 수도 있 지만 귀 찮 습 니 다.
TOPK 문제
TopK 문제 의 본질은 작은 무 더 기 를 취하 여 무 더 기 를 만 든 다음 에 무 더 기 를 만 드 는 것 이다.심지어 너 는 하나의 순서 라 고 할 수 있다.앞의 네 개 를 다른 배열 에 넣다.그러나 정렬 은 시간의 복잡 도가 가중 되 는 것 을 의미 하 므 로 독자 들 은 지식 을 쌓 고 데 이 터 를 쌓 는 방식 으로 최소 데 이 터 를 얻 고 여기 서 문제 와 답 을 제시 해 주 십시오.
* Note: The returned array must be malloced, assume caller calls free().
*/
/* */
void swap(int* a, int* b) {
int tmp = *a;
*a = *b;
*b = tmp;
}
/* ， */
void swim(int* nums, int k) {
while (k > 1 && nums[k] > nums[k / 2]) {
swap(&nums[k], &nums[k / 2]);
k /= 2;
}
}
/* ， */
void sink(int* nums, int k, int numsSize) {
while (2 * k < numsSize) {
int child = 2 * k;
if (child < numsSize && nums[child] < nums[child + 1]) {
child++;
}
if (nums[k] > nums[child]) {
break;
}
swap(&nums[k], &nums[child]);
k = child;
}
}
/* */
typedef struct Heap {
int* data;
int szie;
int capacity;
}T_Heap, *PT_Heap;
/* */
PT_Heap createHeap(int k) {
PT_Heap obj = (PT_Heap)malloc(sizeof(T_Heap));
obj->data = (int*)malloc(sizeof(int) * (k + 1));
obj->szie = 0;
obj->capacity = k + 1;
return obj;
}
/* */
bool isEmpty(PT_Heap obj) {
return obj->szie == 0;
}
/* */
int getHeapSize(PT_Heap obj) {
return obj->szie;
}
/* */
void pushHeap(PT_Heap obj, int elem) {
/* */
obj->data[++obj->szie] = elem;
/* , */
swim(obj->data, obj->szie);
}
/* */
int getHeapTop(PT_Heap obj) {
return obj->data[1];
}
/* */
int popHeap(PT_Heap obj) {
/* */
int top = obj->data[1];
/* , */
swap(&obj->data[1], &obj->data[obj->szie--]);
/* INT_MIN */
obj->data[obj->szie + 1] = INT_MIN;
/* */
sink(obj->data, 1, obj->szie);
return top;
}
int* getLeastNumbers(int* arr, int arrSize, int k, int* returnSize){
/* 、 k 0， NULL */
if (arrSize == 0 || k == 0) {
*returnSize = 0;
return NULL;
} else {
*returnSize = k;
}
/* k */
int* ret = (int*)calloc(k, sizeof(int));
/* k */
PT_Heap heap = createHeap(k);
/* k */
for (int i = 0; i < k; i++) {
pushHeap(heap, arr[i]);
}
/* ， k */
for (int i = k; i < arrSize; i++) {
if (arr[i] < getHeapTop(heap)) {
popHeap(heap);
pushHeap(heap, arr[i]);
}
}
/* */
for (int i = 0; i < k; i++) {
ret[i] = popHeap(heap);
}
return ret;
}
두 갈래 나무의 옮 겨 다 니 기
1.선착순 옮 겨 다 니 기
이 진 트 리 가 비어 있 으 면 비어 있 습 니 다.그렇지 않 으 면
루트 노드 접근 하기;
먼저 왼쪽 트 리 를 옮 겨 다 니 세 요.
오른쪽 하위 트 리 를 먼저 옮 겨 다 니 기;
2.중간 순서 로 옮 겨 다 니 기
이 진 트 리 가 비어 있 으 면 비어 있 습 니 다.그렇지 않 으 면
왼쪽 하위 트 리 를 중앙 순서 로 옮 겨 다 니 기
루트 노드 접근 하기;
오른쪽 하위 트 리 를 중간 순서 로 옮 겨 다 니 기;
3.후 순 옮 겨 다 니 기
뒤 순 서 는 왼쪽 하위 트 리 를 옮 겨 다 닌 다.
오른쪽 하위 트 리 를 옮 겨 다 니 기;
루트 노드 접근 하기;
코드 구현
void PrevOrder(BTNode* root)
{
if (root == NULL)
{
printf(" NULL ");
return;
}
printf(" %c ", root->data);
PrevOrder(root->left);
PrevOrder(root->right);
}
void InOrder(BTNode* root)
{
if (root == NULL)
{
printf("NULL");
return;
}
InOrder(root->left);
printf(" %c ", root->data);
InOrder(root->right);
}
void PostOrder(BTNode* root)
{
const BTNode* a = root;
if (root == NULL)
{
printf(" NULL ");
return;
}
PostOrder(root->left);
PostOrder(root->right);
printf(" %c ", root->data);
}
본 제 를 예 로 들다
이 세 줄 의 코드 순서 가 바 뀌 면 옮 겨 다 니 는 방식 도 달라 지 는 이 유 는 무엇 일 까?
우선 함수 의 출구 는 루트 가 비어 있 습 니 다
PostOrder(root->left);왼쪽 나무 방향 으로 쭉 갑 니 다.언제 까지 다음 문장 을 진행 합 니까?끝까지 가면 그림 과 같다.
이때 함수 출구 에 따라
return ；위 층 으로 돌아 갑 니 다.그림 과 같 습 니 다.
이때 입장
PostOrder(root->right);그림 참조.
이때 함수 출구 를 만족 시 켰 습 니 다.
총결산
C 언어 이 진 트 리 와 쌓 기 에 관 한 이 글 은 여기까지 소개 되 었 습 니 다.더 많은 C 언어 이 진 트 리 와 쌓 기 내용 은 우리 의 이전 글 을 검색 하거나 아래 의 관련 글 을 계속 찾 아 보 세 요.앞으로 많은 응원 부 탁 드 리 겠 습 니 다!
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
c 언어 간단한 파일 r/w 조작 방법데이터의 입력과 출력은 거의 모든 C 언어 프로그램과 수반된다. 입력이란 원본에서 데이터를 얻는 것이다. 출력은 단말기에 데이터를 쓰는 것으로 이해할 수 있다.이곳의 원본은 키보드, 마우스, 하드디스크, 시디, 스캐...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
