데이터 구조 면접 의 6 - 이 진 트 리 의 흔 한 조작 2 (재 귀적 옮 겨 다 니 기 & 이 진 트 리 가 아 닌)
제목: 는 관련 연습 문제 가 있 지만 생각 이 상대 적 으로 뚜렷 하지 않 고 조판 에 오류 가 있 습 니 다. 저 자 는 이에 대해 관련 서적 과 자신의 관점 을 참고 하여 재 작성 하여 여러분 께 참고 하도록 하 였 습 니 다.
6. 이 진 트 리 의 기본 작업 (재 귀적 으로 옮 겨 다 니 지 않 음) & 이 진 트 리 의 작업
다음 절 다섯 번 째 부분 을 연결 하여 주로 이 진 트 리 의 비 재 귀적 옮 김 과 이 진 트 리 의 조작 을 분석 합 니 다.
1. 비 재 귀적 중간 순서 로 옮 겨 다 니 기
/ / 1. 루트 의 왼쪽 하위 트 리 를 lchild = NULL 까지 차례로 스 택 에 넣 고 2 를 실행 합 니 다.
/ 2. 스 택 의 요 소 를 스 택 에서 꺼 내 고 방문 합 니 다. 현재 포인터 가 노드 의 rchild 를 가리 키 며 순환 합 니 다. 스 택 이 비 어 있 을 때 까지!
template<typenameelemType>
voidbinaryTreeType<elemType>::noRecursionInorderTraversal() //
{
cout<< "noRecursionInorderTraversal--------------------------->"<< endl;
linkedStackType<nodeType<elemType>* > stack;
nodeType<elemType>*current = root;
while(current!= NULL || !stack.isEmptyStack()) // ||
{
if(current!= NULL)
{
stack.push(current);
current= current->llink;
}
else
{
stack.pop(current);
cout<< current->info << "\t"; //
current= current->rlink;
}
}
cout<< endl;
cout<< "<------------------------noRecursionInorderTraversal"<< endl;
}2. 비 재 귀적 우선 순위 옮 겨 다 니 기
//중간 순 서 를 옮 겨 다 니 는 토대 에서 방문 순서 가 달라 집 니 다.
//먼저 순서대로 옮 겨 다 니 려 면 먼저 뿌리 노드 를 하나씩 옮 겨 다 닌 다음 에 왼쪽, 오른쪽 아이의 노드 를 순서대로 처리 해 야 한다.
template<typenameelemType>
voidbinaryTreeType<elemType>::noRecursionPreorderTraversal() //
{
cout<<"noRecursionPreorderTraversal--------------------------->"<< endl;
linkedStackType<nodeType<elemType>* > stack;
nodeType<elemType>*current = root;
while(current!= NULL || !stack.isEmptyStack()) // ||
{
if(current!= NULL)
{
cout<< current->info << "\t"; //
stack.push(current);
current= current->llink;
}
else
{
stack.pop(current);
current= current->rlink;
}
}
cout<< endl;
cout<< "<------------------------noRecursionPreorderTraversal"<< endl;
}3. 비 재 귀적 후 순차 옮 겨 다 니 기
방문 순 서 는 먼저 왼쪽 트 리, 그 다음 에 오른쪽 트 리, 마지막 노드 입 니 다. 또한 모든 노드 에 대해 상기 작업 을 하기 때문에 모든 역대로 현재 노드 유형 이 뿌리 (상대) 임 을 식별 해 야 합 니 다.왼쪽 아이 노드, 오른쪽 아이 노드 입 니 다. 따라서 flag 태그 변 수 를 설정 하 였 습 니 다. flag = 0 초기 태그, 노드 가 스 택 에 들 어가 지 않 았 습 니 다. 왼쪽 아 이 를 방문 하기 전에 flag 를 1 로 설정 하고 오른쪽 아 이 를 방문 하기 전에 flag 를 2 로 설정 하 였 으 며 오른쪽 아 이 를 방문 한 후에 flag 를 0 으로 설정 하 였 습 니 다.
//뒷 순 서 는 재 귀적 이지 않 고 옮 겨 다 니 는 것 이 비교적 복잡 하 다.
template<typenameelemType>
voidbinaryTreeType<elemType>::noRecursionPostorderTraversal() //
{
cout<<"noRecursionPostorderTraversal--------------------------->"<< endl;
linkedStackType<nodeType<elemType>* > stack;
linkedStackType<int>intStack; // .
nodeType<elemType>*current = root;
intnflag = 0; // 0.
if(current== NULL)
{
cout<< "The Stack is Empty!" << endl;
}
else
{
//1. ,
stack.push(current);
intStack.push(1);
current = current->llink; // ******
while(!stack.isEmptyStack()&& !intStack.isEmptyStack())
{
if(current!= NULL && nflag == 0)
{
stack.push(current);
intStack.push(1); // 1,[ ， 1]。
current = current->llink;
}
else
{
stack.pop(current);
intStack.pop(nflag); // ,
if(nflag== 1) // .
{
stack.push(current); // ，
intStack.push(2); // [ ， 2]。
current= current->rlink; // ，
nflag= 0; // 0
}
else
{
cout<< current->info << " "; // 。
}
}
}
cout<< endl;
cout<< "<------------------------noRecursionPostorderTraversal"<< endl;
}
}4. 두 갈래 정렬 트 리 검색 작업
개념 을 명 확 히 하고 국내, 외국 의 저서 에서 언급 한 다음 세 가지 개념 등가, 이 진 검색 트 리 = 이 진 검색 트 리 = 이 진 정렬 트 리.
/ / 두 갈래 정렬 트 리 찾기 에는 다음 과 같은 몇 가지 상황 이 있 습 니 다.
/ / 1. 링크 가 비어 있 습 니 다. 힌트 를 주 고 되 돌려 줍 니 다.
/ / 2. 링크 가 비어 있 지 않 습 니 다. 포인터 가 비어 있 을 때 까지 반복 적 으로 찾 아야 합 니 다. 존재 하면 bfound = true 입 니 다. 그렇지 않 으 면 마지막 bfound = 결 성 false 를 찾 아야 합 니 다.
template <class elemType>
boolbSearchTreeType<elemType>::search(const elemType& searchItem)
{
nodeType<elemType>*current = new nodeType<elemType>;
boolbFound = false;
if(root== NULL)
{
cout<< "The bSearchTree is NULL
"; //case1: !
returnfalse;
}
else
{
current= root;
while(current!= NULL && !bFound) //case2: , 、 .
{
if(current->info== searchItem)
{
bFound= true;
}
elseif(current->info > searchItem)
{
current= current->llink; //
}
elseif(current->info < searchItem)
{
current= current->rlink; //
}
}
}
returnbFound;
}5. 두 갈래 정렬 트 리 의 삽입 에는 다음 과 같은 몇 가지 상황 이 존재 합 니 다.
/ 1. 링크 가 비어 있 고 요 소 를 삽입 하면 루트 노드 입 니 다.
/ / 2. 링크 가 비어 있 지 않 습 니 다. 삽입 위 치 를 찾 아 삽입 해 야 합 니 다.
/ / 2.1 삽입 요소 가 이미 존재 하면 오류 가 발생 했 음 을 알려 줍 니 다.
/ / 2.2 항상 특정한 노드 보다 크 거나 작은 위 치 를 찾 고 trailcurrent 가 삽입 작업 을 완성 하 는 것 을 기록 합 니 다.
template <class elemType>
voidbSearchTreeType<elemType>::insert(const elemType& insertItem)
{
nodeType<elemType>*newNode = new nodeType<elemType>;
nodeType<elemType>*current;
nodeType<elemType>*trailCurrent;
newNode->info= insertItem;
newNode->llink= NULL;
newNode->rlink= NULL;
if(root== NULL)
{
root= newNode; //case1: .
}
else
{
current= root;
while(current!= NULL) //case2,3,4 !
{
trailCurrent= current;
if(current->info== insertItem)
{
cout<< "the elem is already exist!
"; //case2:
return;
}
else
{
if(current->info> insertItem)
{
current= current->llink; //case3: ...
}
else
{
current= current->rlink; //case4: ...
}
}
}//endwhile
//case3,4
if(trailCurrent->info< insertItem)
{
trailCurrent->rlink= newNode;
}
else
{
trailCurrent->llink= newNode;
}
}//end else
}6.
두 갈래 정렬 트 리 의 삭 제 는 다음 과 같은 몇 가지 상황 이 존재 합 니 다.
/ / 노드 를 삭제 하려 면 먼저 요소 값 이 이 진 트 리 에 존재 하 는 지 판단 해 야 합 니 다.
/ / 존재 하지 않 으 면 되 돌려 줍 니 다.
/ / 존재 할 경우 해당 위 치 를 1 개의 노드, 2 개의 노드, 3 의 나머지 노드 로 잠 가 야 합 니 다.
/ / 삭제 할 노드 에 좌우 하위 트 리 가 있 는 지 에 따라 4 가지 상황 으로 나 누 어 고려 합 니 다.
/ / deleteFromTree () 함수 참조.
template <class elemType>
voidbSearchTreeType<elemType>::deleteNode(const elemType& deleteItem)
{
//1.
//2.1 ， ;
//2.2 ， ，
nodeType<elemType>*current;
nodeType<elemType>*trailCurrent;
boolbFound = false;
if(root== NULL)
{
cout<< "Can't delete an Empty BST" << endl;
return;
}
else
{
current= root;
trailCurrent= root;
while(current != NULL && !bFound)
{
if(current->info== deleteItem)
{
bFound= true;
}
elseif(current->info > deleteItem)
{
trailCurrent= current;
current= current->llink; //
}
else
{
trailCurrent= current;
current= current->rlink; //
}
}//endwhile
if(current== NULL)
{
cout<< deleteItem << " is not Exist in the BST!
" <<endl;
}
elseif(bFound)
{
if(current== root)
{
deleteFromTree(root); //
}
elseif(trailCurrent->info > deleteItem)
{
deleteFromTree(trailCurrent->llink);// ， trailCurrent
}
elseif(trailCurrent->info < deleteItem)
{
deleteFromTree(trailCurrent->rlink); // ， trailCurrent
}
}//endif bFound
}//end else
}/ / [원리]: 특정한 노드 의 앞 구 조 는 이 노드 왼쪽 서브 트 리 의 가장 오른쪽 노드 (중간 순서 로 옮 겨 다 니 는 결과) 입 니 다.
template <class elemType>
voidbSearchTreeType<elemType>::deleteFromTree(nodeType<elemType>*&p)
{
nodeType<elemType>*temp;
nodeType<elemType>*current;
nodeType<elemType>*trailCurrent;
if(p== NULL)
{
cout<< "The BST is NULL!" << endl;
return;
}
if(p->llink== NULL && p->rlink == NULL) // 1, （ ）
{
temp= p;
p= NULL;
deletetemp;
}
elseif( p->rlink == NULL) // 2, ，
{
temp= p;
p= temp->llink;
deletetemp;
}
elseif(p->llink == NULL) // 3, ，
{
temp= p;
p= temp->rlink;
deletetemp;
}
else // 4, [ ]
{
current= p->llink;
trailCurrent= NULL;
while(current->rlink!= NULL)
{
trailCurrent= current; //trailCurrent
current= current->rlink;
}
p->info= current->info; //
if(trailCurrent== NULL) //
{
p->rlink = current->llink;
}
else
{
trailCurrent->rlink= current->llink; //
}
deletecurrent;
}
}이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 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에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
