자주 사용 하 는 데이터 구조 (5): 트 리
2908 단어 데이터 구조
이 진 트 리 의 모든 요소 의 도 는 2 보다 작 으 면 되 고 다른 추가 적 인 제한 이 없다.
이 진 트 리 의 높이 를 h 로 설정 하면 h 층 을 제외 하고 다른 각 층 (1 ~ h - 1) 의 결 점 수 는 모두 최대 개수 에 달 하고 h 층 의 모든 노드 는 연속 적 으로 가장 왼쪽 에 집중 된다. 이것 이 바로 완전 이 진 트 리 이다. 완전 이 진 트 리 는 통속 적 으로 말 하면 위 에 있 는 불만 이 아래 에 요 소 를 추가 할 수 없 는 나무 입 니 다. 좋 은 점 은 번호 로 지정 한 위치의 요 소 를 찾 을 수 있 고 쌓 는 것 은 완전 이 진 트 리 입 니 다.
이 진 트 리 는 깊이 가 h 이 고 2h - 1 개의 결점 이 있 는 이 진 트 리 입 니 다.
나 무 를 옮 겨 다 니 는 순서 중 순서 중 앞 뒤 는 현재 노드 의 값 을 말 하 며 한 층 씩 옮 겨 다 니 면 대기 열 로 이 루어 집 니 다.
나무의 높이 얻 기:
int getHeight(BinaryTreeNode t)
{
if(!t)return 0;//t
int lHeight=getHeight(t->leftChild);
int rHeight=getHeight(t->rightChild);
return (lHeigt>rHeight?lHeight:rHeight)++;
}
최대 더 미 는 모든 노드 의 값 이 하위 노드 의 값 보다 크 거나 같은 완전 이 진 트 리 를 말한다.
더미 에 요소 삽입:
//
void Insert(int x)
{
int i=++Size;//size
while(i!=1&&x>heap[i/2])
{
heap[i]=heap[i/2];
i=i/2;
}
heap[i]=x;
}
/ / 삭제: 루트 노드 를 삭제 하고 마지막 노드 를 추출 합 니 다.
//
int HeapDelete(int h[])
{
int x = h[1]; // ,
//------------- ---------------
int y = h[CurrSize--]; //
int i=1/* */,pi=2/*i */;
while(pi <= CurrSize)
{
if(pi < CurrSize && h[pi] < h[pi+1])
pi++; // , pi
// pi i
if(y >= h[pi]) break; //y h[i]
h[i] = h[pi]; //
i = pi; pi = pi*2; //
}
h[i] = y; //
return x; //
}
/*--- --- --- --- --- --- --- --- --- --- --- --- --- --- --- --- --
: , ,
,
--- --- --- --- --- --- --- --- --- --- --- --- --- --- --- --- --*/
void HeapInit(int h[],int cs,int ms)
{
int i,y,pi;
CurrSize = cs; MaxSize = ms;
for(i = CurrSize/2; i >= 1; i--)
{
y = h[i]; //
pi = 2*i; //
while(pi <= CurrSize) //
{
if(pi < CurrSize && h[pi] < h[pi+1])
pi++; // , pi
// pi i
if(y >= h[pi]) break; //y h[i]
h[pi/2] = h[pi]; //
pi = pi*2; //
}
h[pi/2] = y; //
}
}
왼쪽 고목 이나 하프 만 나무 같은 건 안 써 요.
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
정수 반전Udemy 에서 공부 한 것을 중얼거린다 Chapter3【Integer Reversal】 (예) 문자열로 숫자를 반전 (toString, split, reverse, join) 인수의 수치 (n)가 0보다 위 또는 ...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.