두 갈래 나무(1)-----선순 두루두루두루(전순 두루두루두루), 귀속과 비귀속 방식 실현

1531 단어 두 갈래 나무
1. 두 갈래 나무 노드 정의
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) 귀속 실현
루트 노드가 NULL이면 로 돌아갑니다.
루트 노드가 NULL이 아닌 경우 루트 노드에 액세스한 다음 왼쪽 트리에 액세스하고 오른쪽 트리에 액세스합니다.
void  PreorderTraverse( BTreeNode_t *pRoot){
    if( pRoot == NULL )
        return ;

    Visit( pRoot);
    PreorderTraverse( pRoot->m_pLeft );
    PreorderTraverse( pRoot->m_pRight);
    return;
}

(2) 비귀속 실현
STL 스택으로 구현
1단계: 먼저 pRoot이 비어 있는지 판단하고 비어 있지 않으면 2단계를 진행한다.비어 있으면 3단계로 이동합니다.
두 번째 단계: pRoot에 방문한 후 pRoot을 창고에 넣고 pRoot의 왼쪽 결점을 pRoot에 부여한 다음 새 pRoot에 대한 첫 번째 단계를 진행한다.
3단계: 창고가 비어 있는지 판단하고 비어 있지 않으면 창고 꼭대기 요소를 꺼내 창고에서 나온 다음에 창고 꼭대기 요소의 오른쪽 결점을 pRoot에 부여하고 첫 번째 단계를 진행한다.pRoot이 NULL이고 스택이 비어 있으면 끝납니다.
void  PreorderTraverse( BTreeNode_t *pRoot){
    if( pRoot == NULL )
        return ;

    stack <BTreeNode_t *>  st;
    while( pRoot != NULL || !st.empty() ){
        while( pRoot != NULL ){
            Visit( pRoot );
            st.push( pRoot );
            pRoot = pRoot->m_pLeft;
        }

        if( !st.empty() ){
            pRoot = st.top();
            st.pop();
            pRoot = pRoot->m_pRight;
        }
    }

    return;
}

좋은 웹페이지 즐겨찾기