분 치 법 과 귀속

분할 알고리즘 의 기본 사상 은 하나의 규모 가 N 인 문 제 를 K 개의 규모 가 작은 하위 문제 로 분해 하 는 것 이다. 이런 하위 문 제 는 서로 독립 되 고 원래 의 문제 와 성질 이 같다.하위 문제 의 해 를 구하 면 원래 문제 의 해 를 얻 을 수 있다.
분 치 법 은 각 층 의 순환 에 있어 세 가지 절차 가 있다.
4. 567917. 분해: 원래 의 문 제 를 몇 개의 규모 가 작고 서로 독립 되 며 원래 의 문제 형식 과 똑 같은 서브 문제 로 분해 합 니 다
4. 567917. 해결: 만약 에 서브 문제 의 규모 가 작고 해결 되 기 쉬 우 면 직접 해결 하고 그렇지 않 으 면 각 서브 문 제 를 재 귀적 으로 해결한다
4. 567917. 합병: 각 하위 문제 의 해 를 원래 문제 의 해 로 합 친다
그것 의 일반적인 알고리즘 디자인 모델 은 다음 과 같다.  Divide-and-conquer(P)   1. if |P|≤n0   2. then return(ADHOc(P))   3. P 를 작은 하위 문제 P1, P2,..., Pk 로 분해   4. for i←1 to k   5. do yi ← Divide - and - conquer (Pi) △ 귀속 해결 Pi   6. T ← MERGE (y1, y2,..., yk) △ 합병 서브 문제   7. return(T)  그 중에서 | P | 문제 P 의 규 모 를 나타 낸다.n0 은 한도 값 으로 문제 P 의 규모 가 n0 을 초과 하지 않 을 때 문 제 는 쉽게 풀 리 고 더 이상 분해 할 필요 가 없다 는 것 을 나타 낸다.ADHOC (P) 는 이 분 치 법의 기본 서브 알고리즘 으로 소 규모 문제 P 를 직접 푸 는 데 사용 된다.따라서 P 의 규모 가 n0 을 초과 하지 않 을 때 알고리즘 ADHOc (P) 로 직접 해답 을 구한다.알고리즘 MERGE (y1, y2,. 
 
여기 서 두 가지 알고리즘 의 예 를 들 어 재 귀 와 분 치 법의 응용 을 살 펴 보 자.
 
1. 정수 하나 와 이원 나 무 를 입력 하 세 요.나무의 뿌리 결점 부터 아래로 내 려 가서 잎 결점 이 지나 가 는 모든 결점 이 하나의 경 로 를 형성한다.입력 정수 와 같은 모든 경 로 를 출력 합 니 다.예 를 들 어 정수 22 와 다음 이원 트 리 를 입력 하 십시오.  10     / /     5 12     / /     47 은 두 가지 경 로 를 출력 한다. 10, 12, 10, 5, 7.
2. 이원 찾기 트 리 를 입력 하고 이원 찾기 트 리 를 정렬 된 양 방향 링크 로 변환 합 니 다.새로운 노드 를 만 들 수 없고 포인터 의 방향 만 조정 하 라 고 요구 합 니 다.      10  / / 6 14 / / / /4 8 12 16     양 방향 링크 로 전환 4 = 6 = 8 = 10 = 12 = 14 = 16.
 
분석: 이 두 문제 에 대해 모두 여러 가지 방법 으로 해결 할 수 있다. 여기 서 우 리 는 첫 번 째 문제 에 대해 재 귀 방법 으로 두 번 째 문제 에 대해 분 치 법 을 사용한다.
struct BSTreeNode

{

    int m_nValue;

    BSTreeNode* m_leftchild;

    BSTreeNode* m_rightchild;

}; //      

/*

    1.         total   

*/

List<BSTreeNode*> nodeList;

void printResult()

{

    for (int i = 0; i < nodeList.size(); ++i)

    {

        if (nodeList.at(i))

            cout << nodeList.at(i)->m_nValue << " " ;

    }

    cout<<endl;

}

void CalcPath(BSTreeNode* root,int total)

{

    if(root)

    {

        if(root->m_nValue == total)

        {

            if(root->m_leftchild == NULL && root->m_rightchild == NULL)

            {

                nodeList.append(root);

                printResult();

                nodeList.pop_back();

            }

        }

        else if(root->m_nValue < total)

        {

            nodeList.append(root);

            CalcPath(root->m_leftchild,total - root->m_nValue);

            CalcPath(root->m_rightchild,total - root->m_nValue);

            nodeList.pop_back();

        }

        else

        {

            return;

        }

    }

    return;

}
/**

    2.   2         

                 ，                  ，        

**/

BSTreeNode* convertTree2dblink(BSTreeNode* root)

{

    if(root == NULL)

    {

        return NULL;

    }

    BSTreeNode* left = convertTree2dblink(root->m_leftchild);

    BSTreeNode* right = convertTree2dblink(root->m_rightchild);

    while(left && left->m_rightchild)

    {

        left = left->m_rightchild;

    }

    root->m_leftchild = left;

    while(right && right->m_leftchild)

    {

        right = right->m_leftchild;

    }

    root->m_rightchild = right;

    if(left)

        left->m_rightchild = root;

    if(right)

        right->m_leftchild = root;

    return root;

}

BSTreeNode* getdblink(BSTreeNode* root)

{

    BSTreeNode* p = convertTree2dblink(root);

    BSTreeNode* head = p;

    while(head && head->m_leftchild) head = head->m_leftchild;

    return head;

}