데이터 구조 절 대 진 할머니 판 제4 장
19413 단어 데이터 구조
질문 찾기:
이 진 트 리
이 진 트 리 가 비어 있 지 않 을 때 성질:
typedef struct TreeNode *BinTree;//
typedef BinTree Position;// Position
struct TreeNode{
ElementType Data;
BinTree Left;
BinTree Right;
}
두 갈래 검색 트 리 찾기 동작: Find
사고의 방향
Position Find(ElementType X, BinTree BST)
{
if(!BST)
return NULL;//
if(X > BTS->Data)
return Find(X, BTS->Right);// ,
Else if(X < BTS->Data)
return Find(X, BTS->Left);//
else//X == BTS->Data
return BST;// ，
}
비 귀속 함수 의 집행 효율 이 더욱 높 아 '꼬리 귀속' 함 수 를 순환 함수 로 바 꿀 수 있다
Position IterFind(ElementType X, BinTree BST)
{
while(BST){
if(X > BST->Right);
BST = BST->Right;// ，
else if(X < BST->Data)
BST = BST->Left;// ，
else
return BST;// ，
}
return NULL;//
}
최대 와 최소 요 소 를 찾 습 니 다.
Position FindMin(BinTree BST)
{
if(!BST)
return NULL;// ， NULL
else if(!BST->)
return BST;//
else
return FindMin(BST->Left);//
}
//
Position FinMax(BinTree BST)
{
if(!BST)
return NULL;
else if(!BST->Right)
return BST;
else
return FinMax(BST->Right);
}
//
Position FindMax(BinTree BST)
{
if(BST)
while(BST->Right)
BST = BST->Right;// ，
return BST;
}
두 갈래 검색 트 리 삽입
사고: 요소 가 삽입 해 야 할 위 치 를 찾 습 니 다.Find 와 유사 한 방법 을 사용 할 수 있 습 니 다.
BinTree Insert(ElementType X, BinTree BST)
{
if(!BST)// ，
{
BST = malloc(sizeof(struct TreeNode));//
BST->Data = X;// X
BST-Left = BST->Right = NULL;// NULL
}
else
if(X < BST->Data)
BST->Left = Insert(X, BST->Left);
else if(X > BST->Data)
BST->Right = Insert(X, BST->Right);
return BST;
}
두 갈래 검색 트 리 삭제
세 가지 상황:
//
BinTree Delete(ElementType X, BinTree BST)
{
Position tmp;
if(!BST)
printf("not find");
else if(X < BST->Data)
BST->Left = Delete(X, BST->Left);//
else if(X > BST->Data)
BST->Right = Delete(X, BST->Right);//
else//
{
if(BST->Left && BST->Right)//
{
tmp = FindMin(BST->Right);//
BST->Data = tmp->Data;
BST->Right = Delete(BST->Data, BST->Right);//
}
else{//
tmp = BST;
if(!BST->Left)//
BST = BST->Right;
else if(!BST->Right)
BST = BST->Left;
free(tmp);
}
}
return BST;
}
밸 런 스 이 진 트 리
밸 런 스 이 진 트 리 가 뭐야?
노드 가 다른 삽입 순 서 는 서로 다른 깊이 와 서로 다른 검색 효율 및 평균 검색 길이 ASL 을 가 져 옵 니 다.
평형 인자 (Balance Factor BF): BF (T) = hL - h_R, 그 중 hL，h_R 은 각각 T 의 좌우 자목 높이 다.
밸 런 스 이 진 트 리 (밸 런 스 이 진 트 리):
빈 트 리, 또는 임의의 노드 좌우 하위 트 리 높이 차 의 절대 치 는 1 을 초과 하지 않 습 니 다. 즉, * * | BF (T) | < = 1 * * *
균형 이 잡 힌 이 진 트 리 의 높이
피 보 나치 수열:
밸 런 스 이 진 트 리 조정
RR 회전
LL 회전
LR 회전
RL 회전
특집: 같은 두 갈래 검색 트 리 인지 아 닌 지 판별
typedef struct TreeNode *Tree;
struct TreeNode{
int v;//
Tree Left, Right;
int flag;// ； 0； 1
};
검색 트 리 만 들 기
같은 두 갈래 검색 트 리 가 아 닙 니 다.
typedef struct TreeNode *Tree;
struct TreeNode{
int v;//
Tree Left, Right;
int flag;// ； 0； 1
};
검색 트 리 만 들 기
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 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에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
