이 진 트 리 의 각 결점 의 자손 수 를 구하 다.

《 데이터 구 조 》 엄 울 민 판 연습 문제 6.55
이 진 링크 의 결산 점 에 DescNum 역 을 추가 하여 이 결산 점 의 자손 수 를 표시 합 니 다.이 진 트 리 의 모든 노드 의 자손 수 를 구하 고 DescNum 필드 에 저장 하 는 알고리즘 을 만 듭 니 다.
생각:

방안 1. 재 귀 를 이용 하여 뿌리 노드 부터 모든 노드 에 한 번 씩 함 수 를 호출 하여 각 노드 의 자손 수량 이 뚜렷 하고 재 귀 호출 이 느 릴 것 이다. 왜냐하면 스 택 탄 스 택 을 계속 누 르 기 때문이다.

방안 2 는 방안 1 의 옮 겨 다 니 는 방향 과 반대로 맨 아래 의 잎 결점 부터 각 결점 의 자손 수 를 계산 한 다음 에 부모 노드 에 대해 좌우 아이의 DescNum 역 을 합치 면 된다.그렇다면 이런 '먼저 아 이 를 낳 은 부모' 의 순 서 를 만족 시 킬 수 있 는 것 은 무엇 일 까?후속 이 죠.다음은 프로젝트 2 의 c + + 코드

를 드 립 니 다.

/*
          
*/
#include "bitree.h"

typedef struct myTNode
{
    int data;
    int descendant;
    struct myTNode* lchild;
    struct myTNode* rchild;
}myBiTree, *pmyBiTree;


void mycreat_tree(pmyBiTree &rt)
{
    char ch;
    ch=getchar();
    if('#'==ch)
    {
        rt=NULL;
    }
    else
    {
        rt=(pmyBiTree)malloc(sizeof(myBiTree));
        rt->data=ch;
        rt->descendant = 0;
        mycreat_tree(rt->lchild);        //     
        mycreat_tree(rt->rchild);    //     
    }
}

void DescNumber(pmyBiTree &rt)
{
    if(!rt)
        return;
    stack s;
    pmyBiTree cur = rt;
    pmyBiTree pre = NULL;

    while(!s.empty() || cur != NULL)
    {
        while(cur)
        {
            s.push(cur);
            cur = cur->lchild;
        }
        cur = s.top();
        if(cur->rchild == NULL || cur->rchild == pre)
        {
            if(cur->lchild)
                cur->descendant += cur->lchild->descendant + 1;
            if(cur->rchild)
                cur->descendant += cur->rchild->descendant + 1;
            pre = cur;
            cur = NULL;
            s.pop();
        }
        else
        {
            cur = cur->rchild;
        }
    }
}

void PreOrderPrintDesc(pmyBiTree &rt)
{
    cout << "PreOrderPrintDesc: " << endl;
    if(!rt)
        return;
    stack s;
    s.push(rt);
    while(!s.empty())
    {
        pmyBiTree cur = s.top();
        cout << (char)(cur->data) << " Desc: " << cur->descendant << endl;
        s.pop();
        if(cur->rchild)
            s.push(cur->rchild);
        if(cur->lchild)
            s.push(cur->lchild);
    }
    cout << '@' << endl;
}

int main(int argc, char const *argv[])
{
    pmyBiTree root;
    mycreat_tree(root);
    DescNumber(root);
    PreOrderPrintDesc(root);
    return 0;
}

함수 void DescNumber(pmyBiTree &rt) 는 이 진 트 리 rt 의 모든 결점 의 DescNum 역 을 계산 합 니 다.이 는 후속 적 으로 옮 겨 다 니 는 사고방식 을 이용 하여 차이 점 은 바로 현재 결점 을 인쇄 해 야 할 때 좌우 결점 이 존재 하 는 지 에 따라 본 결점 의 자손 수 를 계산한다.이 문 제 는 이 진 트 리 의 3 중 옮 겨 다 니 는 방법의 중요성 을 충분히 설명 하고 많은 문 제 를 재 귀적 이지 않 아 도 되 고 복잡 하지 않 아 도 해결 할 수 있다.이 알고리즘 은 복잡 도가 O (n) 입 니 다.