두 갈래 나무(3)------뒷순서 반복, 귀속과 비귀속 방식
2671 단어 두 갈래 나무
typedef struct BTreeNodeElement_t_ {
void *data;
} BTreeNodeElement_t;
typedef struct BTreeNode_t_ {
BTreeNodeElement_t *m_pElemt;
struct BTreeNode_t_ *m_pLeft;
struct BTreeNode_t_ *m_pRight;
} BTreeNode_t;
2. 후순 두루
정의: 뿌리 노드를 정하고 먼저 왼쪽 트리를 훑어본 다음에 오른쪽 트리를 훑어보고 마지막으로 뿌리 노드를 훑어본다.
(1) 귀속 실현
루트가 비어 있으면 되돌아옵니다.
만약 뿌리 노드가 비어 있지 않다면 먼저 왼쪽 트리를 훑어본 다음에 오른쪽 트리를 훑어보고 마지막에 뿌리 노드를 훑어본다.
void PostorderTraverse( BTreeNode_t *pRoot){
if( pRoot == NULL ){
return;
}
PostorderTraverse( pRoot->m_pLeft);
PostorderTraverse( pRoot->m_pRight);
Visit(pRoot);
}
(2) 비귀속 방식
첫 번째 단계: pRoot을 정하고 pRoot이 NULL인지 판단한다.NULL이 아닌 경우 두 번째 단계를 수행합니다.NULL인 경우 3단계를 수행합니다.
2단계: pRoot을 창고에 넣고 pRoot의 왼쪽 결점을 pRoot에 부여하여 첫 번째 단계를 실행한다.
3단계: 창고가 비어 있지 않으면 창고 꼭대기 요소를 pRoot에 부여하여 pRoot이 오른쪽 트리와 오른쪽 트리에 접근했는지 판단한다.오른쪽 트리가 없거나 오른쪽 트리에 접근한 적이 있으면 pRoot을 방문하고 창고를 나간 다음 첫 번째 단계를 실행합니다.오른쪽 트리가 있고 오른쪽 트리가 아직 접근하지 않았다면, pRoot의 오른쪽 결점을 pRoot에 부여하고 첫 번째 단계를 실행합니다.
void PostorderTraverse( BTreeNode_t *pRoot ){
if( pRoot == NULL )
return NULL;
stack <BTreeNode_t *> st;
BTreeNode_t *visitedNode = NULL;
while( pRoot != NULL || !st.empty() ){
while( pRoot != NULL ){
st.push( pRoot );
pRoot = pRoot->m_pLeft;
}
if( !st.empty()){
pRoot = st.top();
if( pRoot->m_pRight == NULL || pRoot->m_pRight == visitedNode){
Visited( pRoot);
st.pop();
pRoot = NULL; // , NULL,
} else {
pRoot = pRoot->m_pRight; //
}
}
}
}
(3) 비귀속 방식: 더블 창고법 사용
참조:http://blog.csdn.net/hackbuteer1/article/details/6583988
먼저 루트 pRoot을 스택에 넣습니다. 1:
1단계: 창고 1의 창고 꼭대기 요소를 pRoot에 부여한 다음 pRoot을 창고 2에 입고한다.그리고 먼저 pRoot 왼쪽 결점을 창고 1에 넣은 다음에 pRoot 오른쪽 결점을 창고 1에 넣으면 순서가 틀리지 않습니다.
2단계: 출고 2 후 순서를 획득합니다
void PostorderTraverse( BTreeNode_t *pRoot){
if( pRoot == NULL )
return;
stack <BTreeNode_t *> st1;
stack <BTreeNode_t *> st2;
st1.push( pRoot);
while( !st1.empty() ){
pRoot = st1.top();
st1.pop();
st2.push( pRoot);
if( pRoot->m_pLeft)
st1.push( pRoot->m_pLeft);
if( pRoot->m_pRight)
st1.push( pRoot->m_pRight);
}
while( !st2.empty(){
pRoot = st2.top();
st2.pop();
Visite( pRoot );
}
return;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
java 데이터 구조 2차원 트리의 실현 코드일.두 갈래 트리 인터페이스 2 노드 클래스 3. 두 갈래 나무 구현 이 글을 통해 여러분께 도움이 되었으면 좋겠습니다. 본 사이트에 대한 지지에 감사드립니다!...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.