데이터 구조 - 이 진 트 리 총화
47773 단어 데이터 구조 DS
두 갈래 나무 가 널 려 있다.
이 진 트 리 의 옮 겨 다 니 는 것 은 일정한 순 서 를 통 해 이 진 트 리 의 모든 결점 을 방문 하 는 것 을 말한다.옮 겨 다 니 는 방법 은 보통 네 가지 가 있 습 니 다. 먼저 옮 겨 다 니 기, 중간 순서 옮 겨 다 니 기, 뒤의 순서 옮 겨 다 니 기, 그리고 차원 옮 겨 다 니 기, 그 중에서 앞의 세 가 지 는 보통 깊이 우선 검색 (DFS) 으로 이 루어 지고 차원 옮 겨 다 니 기 는 보통 넓 은 범위 우선 검색 (BFS) 으로 이 루어 집 니 다.또 앞의 세 가지 도 재 귀 를 통 해 이 루어 질 수 있다.
재 귀적 으로 선, 중, 후 순 서 를 옮 겨 다 니 는 것 을 실현 하 다.
：
void preOrder1(BinTree *root) //
{
if(root!=NULL)
{
cout<<root->data<<" ";
preOrder1(root->lchild);
preOrder1(root->rchild);
}
}
：
void inOrder1(BinTree *root) //
{
if(root!=NULL)
{
inOrder1(root->lchild);
cout<<root->data<<" ";
inOrder1(root->rchild);
}
}
：
void postOrder1(BinTree *root) //
{
if(root!=NULL)
{
postOrder1(root->lchild);
postOrder1(root->rchild);
cout<<root->data<<" ";
}
}
반복 되 지 않 음
선서, 중 서, 후 서 는 스 택 을 통 해 비 재 귀 를 실현 하 는 것 이다.계층 사 이 를 옮 겨 다 니 는 것 은 대기 열 을 통 해 이 루어 집 니 다.
우선 순위 비 재 귀
void preOrder2(BinTree *root) //
{
stack<BinTree*> s;
BinTree *p=root;
while(p!=NULL||!s.empty())
{
while(p!=NULL)
{
cout<<p->data<<" ";
s.push(p);
p=p->lchild;
}
if(!s.empty())
{
p=s.top();
s.pop();
p=p->rchild;
}
}
}
중간 순서 비 재 귀
void inOrder2(BinTree *root) //
{
stack<BinTree*> s;
BinTree *p=root;
while(p!=NULL||!s.empty())
{
while(p!=NULL)
{
s.push(p);
p=p->lchild;
}
if(!s.empty())
{
p=s.top();
cout<<p->data<<" ";
s.pop();
p=p->rchild;
}
}
}
후 순 비 재 귀
여기에 두 가지 사고방식 이 있다.첫 번 째 는 뿌리 결산 점 이 왼쪽 아이 와 오른쪽 아이 가 방문 한 후에 야 방문 할 수 있 도록 하 는 것 이 므 로 어떤 결산 점 P 에 대해 서 는 먼저 창고 에 넣 어야 한다.P 가 왼쪽 아이 와 오른쪽 아이 가 존재 하지 않 는 다 면 직접 방문 할 수 있 습 니 다.또는 P 는 왼쪽 아이 나 오른쪽 아이 가 존재 하지만 왼쪽 아이 와 오른쪽 아이 가 모두 방문 되 었 으 면 이 노드 를 직접 방문 할 수 있 습 니 다.상기 두 가지 상황 이 아니라면 P 의 오른쪽 아이 와 왼쪽 아 이 를 순서대로 창고 에 넣 으 면 창고 꼭대기 요 소 를 찾 을 때마다 왼쪽 아이 가 오른쪽 아이 앞에서 방문 되 고 왼쪽 아이 와 오른쪽 아 이 는 모두 뿌리 노드 앞에서 방문 된다.
void postOrder3(BinTree *root) //
{
stack<BinTree*> s;
BinTree *cur; //
BinTree *pre=NULL; //
s.push(root);
while(!s.empty())
{
cur=s.top();
if((cur->lchild==NULL&&cur->rchild==NULL)||
(pre!=NULL&&(pre==cur->lchild||pre==cur->rchild)))
{
cout<<cur->data<<" "; //
s.pop();
pre=cur;
}
else
{
if(cur->rchild!=NULL)
s.push(cur->rchild);
if(cur->lchild!=NULL)
s.push(cur->lchild);
}
}
}
두 번 째 사고방식 은 임의의 결점 P 에 대해 창고 에 넣 은 다음 에 왼쪽 나 무 를 따라 왼쪽 아이의 결점 이 없 을 때 까지 계속 아래로 수색 하 는 것 이다. 이때 이 결점 은 창고 꼭대기 에 나타 나 지만 이 때 는 창고 에서 나 와 방문 할 수 없 기 때문에 오른쪽 아 이 는 방문 할 수 있다.그 다음 에 똑 같은 규칙 에 따라 오른쪽 트 리 를 똑 같이 처리 하고 오른쪽 아 이 를 방문 할 때 이 결산 점 은 스 택 꼭대기 에 나타 나 면 스 택 에서 나 와 방문 할 수 있 습 니 다.이렇게 하면 정확 한 방문 순 서 를 보장 할 수 있다.이 과정 에서 모든 결산 점 이 두 번 씩 스 택 꼭대기 에 나타 나 고 두 번 째 로 스 택 꼭대기 에 나타 날 때 만 방문 할 수 있 음 을 알 수 있다.따라서 이 결점 이 창고 꼭대기 에 처음 나타 난 것 인지 변 수 를 하나 더 설정 해 야 한다.
void postOrder2(BinTree *root) //
{
stack<BTNode*> s;
BinTree *p=root;
BTNode *temp;
while(p!=NULL||!s.empty())
{
while(p!=NULL) // ，
{
BTNode *btn=(BTNode *)malloc(sizeof(BTNode));
btn->btnode=p;
btn->isFirst=true;
s.push(btn);
p=p->lchild;
}
if(!s.empty())
{
temp=s.top();
s.pop();
if(temp->isFirst==true) //
{
temp->isFirst=false;
s.push(temp);
p=temp->btnode->rchild;
}
else //
{
cout<<temp->btnode->data<<" ";
p=NULL;
}
}
}
}
층 차 를 편력 하 다
void LevelorderTraversal ( BinTree BT )
{
Queue Q;
BinTree T;
if ( !BT ) return; /* */
Q = CreatQueue(); /* Q */
AddQ( Q, BT );
while ( !IsEmpty(Q) ) {
T = DeleteQ( Q );
printf("%d ", T->Data); /* */
if ( T->Left ) AddQ( Q, T->Left );
if ( T->Right ) AddQ( Q, T->Right );
}
}
이 진 트 리 복원
이 진 트 리 복원 은 이 진 트 리 의 옮 겨 다 니 는 서열 에 따라 이 진 트 리 를 구성 하 는 것 을 말한다.이 진 트 리 를 복원 하 는 데 는 한 가지 결론 이 있다. 중 서 서열 은 선 서 서열, 후 서 서열, 차원 서열 중의 임 의 하나 와 유일한 이 진 트 리 를 구축 할 수 있 고 후 세 가 지 는 두 가 지 를 조합 하거나 세 가 지 를 함께 해도 유일한 이 진 트 리 를 구축 할 수 없다.그 이 유 는 먼저 순서, 후 순서, 차원 이 모두 뿌리 노드 를 제공 하고 역할 이 똑 같 으 며 모두 중간 순서 로 좌우 자 수 를 구분 해 야 하기 때문이다.
선착순
//
Node preIn(int preL,int preH, int inL,int inH)
{
if(preL>preH)return NULL; // ，
Node root = new node;
root->data = pre[preL];
int k=inL;
for(k=inL;k<=inH;k++)
{
if(in[k]==pre[preL])
{
break;
}
}
// [preL+1,preL+k-inL], [inL,k-1]
root->left = preIn(preL+1,preL+k-inL,inL,k-1);
// [preL+k-inL+1,preH], [k+1,inH].
root->right = preIn(preL+k-inL+1,preH,k+1,inH);
return root;
}
int num=0;
void postPrint(Node root)
{
if(root==NULL)return;
postPrint(root->left);
postPrint(root->right);
post[num++]=root->data;
return;
}
뒷 차례
//
Node postIn(int inL,int inH,int postL,int postH)
{
if(postL>postH)return NULL;
Node root = new node;
root->data = post[postH];
int k= inL;
for(k = inL;k<=inH;k++)
{
if(in[k]==post[postH])
{
break;
}
}
// [inL,k-1], [postl,postL+k-inL-1]
root->left = postIn(inL,k-1,postL,postL+k-inL-1);
// [k+1,inH] , [postL+k-inL,postH-1]
root->right = postIn(k+1,inH,postL+k-inL,postH-1);
return root;
}
void prePrint(Node root) //num initiate 0
{
if(root==NULL)return;
pre[num++]=root->data;
prePrint(root->left);
prePrint(root->right);
return;
}
계층
//
Node levelIn(vector<int>layer,int inL,int inH)
{
if(layer.size()==0)return NULL;
Node root = new node;
root->data = layer[0];
int k;
for(k=inL;k<=inH;k++)
{
if(in[k]==layer[0])
{
break;
}
}
vector<int>layerLeft;
vector<int>layerRight;
for(int i=1;i<layer.size();i++)
{
bool isLeft = false;
for(int j=inL;j<k;j++)
{
if(layer[i]==in[j])
{
isLeft = true;
break;
}
}
if(isLeft)
{
layerLeft.push_back(layer[i]);
}
else
{
layerRight.push_back(layer[i]);
}
}
root->left = levelIn(layerLeft,inL,k-1);
root->right = levelIn(layerRight,k+1,inH);
return root;
}
이 진 트 리 응용
이 진 트 리 의 응용 은 주로 이 진 트 리 (BST), 균형 이 진 트 리 (AVL), 하 프 만 트 리, 쌓 기 및 집합 이 있다.
두 갈래 찾기 트 리
이 진 트 리 (Binary Search Tree) 는 특수 한 이 진 트 리 로 정렬 이 진 트 리, 이 진 트 리, 이 진 트 리 정렬 트 리 라 고도 부른다.그 재 귀 정 의 는 다음 과 같다. ① 또는 두 갈래 로 나 무 를 찾 는 것 은 빈 나무 이다.② 또는 이 진 트 리 는 뿌리 노드, 왼쪽 트 리, 오른쪽 트 리 로 구성 되 어 있 습 니 다. 그 중에서 왼쪽 트 리 와 오른쪽 트 리 는 모두 이 진 트 리 입 니 다. 그리고 왼쪽 트 리 의 모든 노드 의 데이터 도 메 인 은 뿌리 노드 의 데이터 도 메 인 보다 작 거나 같 습 니 다. 오른쪽 트 리 의 모든 노드 의 데이터 도 메 인 은 뿌리 노드 의 데이터 도 메 인 보다 큽 니 다.그 중에서 주의해 야 할 것 은 같은 숫자 라 도 삽입 순서 가 다 르 면 마지막 에 생 성 된 이 진 트 리 도 다르다 는 것 이다.또한, 이 진 트 리 는 실 용적 인 성질 을 가지 고 있 습 니 다. 이 진 트 리 를 중간 순서 로 옮 겨 다 니 며 옮 겨 다 니 는 결 과 는 질서 가 있 습 니 다.
밸 런 스 이 진 트 리 (AVL 트 리)
밸 런 스 이 진 트 리 는 옛 소련 의 두 수학자 가 제안 한 것 으로 AVL 트 리 라 고도 부른다.AVL 나 무 는 여전히 두 갈래 로 나 무 를 찾 고 있 으 며, 그 기초 위 에 '균형' 이라는 요 구 를 추 가 했 을 뿐이다.밸 런 스 란 AVL 트 리 의 임 의 결점 에 있어 서 왼쪽 트 리 와 오른쪽 트 리 의 높이 차 이 는 절대 1 을 넘 지 않 으 며, 이 가운데 좌우 트 리 의 높이 차 이 는 이 결점 의 밸 런 스 인자 라 고 한다.균형 인 자 는 서브 나무의 높이 를 빌려 간접 적 으로 구 할 수 있다.AVL 트 리 를 삽입 할 때 균형 을 맞 추기 위해 노드 를 조정 해 야 합 니 다. 구체 적 인 조정 상황 은 다음 과 같 습 니 다 (BF 는 균형 요 소 를 표시 합 니 다).
나무형
판정 조건
조정 방법
LL
BF(root)=2,BF(root->lchild)=1
루트 우회전
LR
BF(root)=2,BF(root->lchild)=-1
루트 - > lchild 를 좌회전 하고 루트 를 우회전 합 니 다.
RR
BF(root)=-2,BF(root->rchild)=-1
루트 좌회전
RL
BF(root)=-2,BF(root->rchild)=1
루트 - > rchild 를 우회전 하고 루트 를 좌회전 합 니 다.
병 찰 집
그리고 집합 을 찾 는 것 은 집합 을 유지 하 는 데이터 구조 로 다음 과 같은 두 가지 조작 을 지원 합 니 다. ① 합병, 두 개의 집합 을 합 칩 니 다. ② 찾기: 두 요소 가 하나의 집합 에 있 는 지 판단 하고 집합 을 찾 는 것 은 하나의 배열 을 통 해 이 루어 집 니 다. 즉, int father [N] 입 니 다. 그 중에서 father [i] 는 요소 i 의 아버지 결점 을 나타 내 고 아버지 결점 자체 도 이 집합 안의 요소 입 니 다. 만약 father [i] 가= = i 는 원소 i 가 이 집합의 뿌리 결점 임 을 설명 하지만, 같은 집합 에 있어 서 는 하나의 뿌리 결점 만 존재 할 수 있 고, 이 를 소속 집합의 표식 으로 삼 을 수 있다. 또한 집합의 한 성질 을 조사한다. 같은 집합 에 서 는 반드시 고리 가 생기 지 않 는 다. 즉, 집합 이 발생 하 는 모든 집합 은 하나의 나무 이다.
쌓다
더 미 는 완전 이 진 트 리 로 나무 에 있 는 모든 노드 의 값 이 작 지 않다 (또는 크 지 않다).그 좌우 아이의 결점 의 값 은 이런 무 더 기 를 큰 무더기 라 고 부른다. 이때 모든 결점 의 값 은 그것 을 뿌리 결점 으로 하 는 자나무 의 최대 값 이다. 만약 에 아버지 결점 의 값 이 아이 결점 의 값 보다 작 거나 같 으 면 이런 무 더 기 를 작은 무더기 라 고 부른다. 이때 모든 결점 의 값 은 그것 을 뿌리 결점 으로 하 는 자나무 의 최소 값 이다.
하프 만 나무
루트 노드 에서 임의의 노드 까지 의 경로 길이 (지나 간 변수) 와 이 노드 의 가중치 곱 하기 를 이 노드 의 대역 권 경로 길이 라 고 합 니 다. 트 리 의 모든 잎 노드 의 대역 권 경로 길이 와 이 트 리 의 대역 권 경로 길이 (WPL) 라 고 합 니 다.. N 개의 잎 사 귀 노드 를 포함 하 는 이 진 트 리 중 권한 경로 길이 가 가장 작은 이 진 트 리 를 하 프 만 트 리 라 고도 부 르 고 가장 좋 은 이 진 트 리 라 고도 부른다.
참고 자료
좋은 웹페이지 즐겨찾기
