이 진 트 리체인 메모리두루

요약

정의 와 데이터 구조

초기 화 및 할당

옮 겨 다 니 는 방식

정의 와 데이터 구조

이 진 트 리 (Binary Tree) 를 정의 하 는 것 은 하나의 나무 구조 로 각 노드 마다 두 그루 의 나무 (즉 이 진 트 리 에 2 이상 의 결점 이 존재 하지 않 음) 가 있 고 이 진 트 리 의 자 나 무 는 좌우 의 구분 이 있 으 며 그 다음 순서 가 마음대로 뒤 바 뀌 어 서 는 안 된다 는 것 이 특징 이다.

데이터 구조

typedef struct BiTNode
{
    ElemType data;
    struct BiTNode *lchild, *rchild;
} BiTNode, *BiTree;

이 결점 은 이 진 트 리 에서 가장 기본 적 인 요소 로 데이터 필드 와 포인터 필드 를 포함한다.
초기 화 및 할당
초기 화

BiTree myBiTree; //                

InitTree(&myBiTree); //       

우 리 는 이 진 트 리 뿌리 의 결점 을 가리 키 는 지침 을 사용 하여 이 진 트 리 를 표시 한다.주의해 야 할 것 은 이 진 트 리 의 초기 화 InitTree 는 포인터 가 가리 키 는 내용 이 아니 라 루트 포인터 자체 의 내용 을 바 꾸 었 기 때문에 파 라 메 터 를 전달 할 때 포인터 로 전달 하고 루트 포인터 의 지침, 즉 루트 포인터 의 주 소 를 전달 합 니 다.

    Status InitTree(BiTree *T)
    {
        // *T              .
        if (*T == NULL) //       ,     ,   .
        {
            return ERROR;
        }

        *T = NULL; //        NULL.

        return OK;
    } // InitTree

값 을 부여 하 다
선번 순서에 따라 이 진 트 리 결점 대 입 입 입 니 다.

// ! *T         , **T       .
void CreateTree(BiTree *T, FILE *fp)
{
    char ch = 0;

    ch = fgetc(fp); //             .

    if (ch == '^') //   '^'     .
    {
        *T = NULL;
    }
    else
    {
        //                 .
        *T = (BiTNode *)malloc(sizeof(BiTNode));
        if (!*T)
        {
            exit(OVERFLOW);
        }

        (*T)->data = ch;
        CreateTree(&((*T)->lchild), fp); //         .
        CreateTree(&((*T)->rchild), fp); //          .
    }
} // CreateTree

Create Tree 를 정의 할 때 두 겹 의 바 를 사용 하지 않 아 도 되 지만 InitTree 와 같은 이 유 는:

일치 성 을 유지 하고 이 진 트 리 를 수정 하 는 작업 과 관련 된 모든 지침 을 전달 합 니 다.

나중에 이 진 트 리 를 수정 하 는 작업 이 이 진 트 리 지침 자체 에 대한 수정 과 관련 이 있다 면 번 거 로 움 을 줄 일 수 있다.실제로 Create Tree 의 *T = NULL 이해 하기 가 &T = NULL 보다 편리 하 다.

스 트 리밍 방식
이 진 트 리 를 수정 하지 않 고 직접 지침 을 전달 합 니 다.
앞 순서

Status PreOrderTraverse(BiTree T, Status (*Visit)(ElemType e))
{
    if (T)
    {
        if (Visit(T->data))
        {
            if (PreOrderTraverse(T->lchild, Visit))
            {
                if (PreOrderTraverse(T->rchild, Visit))
                {
                    return OK;
                }
            }
        }
        return ERROR;
    }
    else
    {
        return OK;
    }
} // PreOrderTraverse

중간 순서

Status InOrderTraverse(BiTree T, Status (*Visit)(ElemType e))
{
    if (T)
    {
        if (InOrderTraverse(T->lchild, Visit))
        {
            if (Visit(T->data))
            {
                if (InOrderTraverse(T->rchild, Visit))
                {
                    return OK;
                }
            }
        }
        return ERROR;
    }
    else
    {
        return OK;
    }
} // InOrderTraverse

후서

Status PostOrderTraverse(BiTree T, Status (*Visit)(ElemType e))
{
    if (T)
    {
        if (PostOrderTraverse(T->lchild, Visit))
        {
            if (PostOrderTraverse(T->rchild, Visit))
            {
                if (Visit(T->data))
                {
                    return OK;
                }
            }
        }
        return ERROR;
    }
    else
    {
        return OK;
    }
} // PostOrderTraverse