어떻게 층 층 이 이 진 트 리 한 그루 를 세 웁 니까?

5112 단어 데이터 구조
《 양 파 》: 내 마음 을 한 층 한 층 벗 기 고 싶다 면 눈물 을 흘 릴 것 이다. 내 가 바로 네가 오랫동안 잃 어 버 린 이 진 나무 다 ~
몇 가지 요점: 1.whales
struct XXX * p = / 구조 체 지침 유형 (struct XXX *) / 구조 체 지침 유형 malloc (sizeof (struct XXX) / / 구조 체 크기 로 강제 변환;
2. 2015 년 데이터 구조 연합 고사 복습 지도
n 개의 결점 이 있 는 만 이 진 트 리 는 약속 번 호 는 뿌리 결점 부터 (뿌리 결점 번 호 는 1), 위 에서 아래로, 왼쪽 에서 오른쪽으로, 각 결점 은 하나의 번호 에 대응 하고 번호 가 i 인 결점 에 대해 부모 가 있 으 면 부모 의 결점 은 9493 ° i / 2 * 9497 ° (아래 에서 정리) 이 며 왼쪽 아이 가 있 으 면 왼쪽 아 이 는 2i 이 고 오른쪽 아이 가 있 으 면 오른쪽 아 이 는 2i + 1 이다.
3.
이른바 한 층 한 층 에 이 진 트 리 를 가득 세 우 는 것 은 왼쪽, 오른쪽 아이 포인터 와 데이터 필드 가 있 는 결점 을 정의 한 다음 에 이 결점 을 한 배열 에 채 우 는 것 이다. 매번 결점 을 교체 할 때마다 좌우 아이 지침 을 수정 하 는 것 이다. 그 규칙 은 바로 앞에서 말 한 결점 번호 의 규칙 이다.교체 수정 을 실현 하기 위해 서 는 두 개의 카운터 i 와 j 가 필요 합 니 다. i 는 노드 번 호 를 기록 하고 j 는 오른쪽 아이의 지침 을 수정 할 때마다 + 1 입 니 다.예 를 들 어 i = 3 의 결점 은 j = 3mod 2 = 1, 즉 다음 층 의 아버지 결점 이다.
다음은 구체 적 으로 실 현 된 코드 입 니 다.
structlib.h
#include 
#include 
#include 
#include

//      
typedef char ElemType;

//         
typedef struct THREAD{
    ElemType data;    //    
    struct THREAD *lchild, *rchild;    //       
}Thread, *ThreadPoint;

main.c
#include "structlib.h"

int len;
int i=0,j=0;        //  
ThreadPoint tp[1024];

//    :          
int  createBinaryTree(ElemType *branch){

    ThreadPoint curr;

    curr = (ThreadPoint)malloc(sizeof(Thread));
    curr->data = *branch;       //    
    curr->lchild = NULL;        //     
    curr->rchild = NULL;        //     

    tp[i] = curr;       //    

    if (i == 0){
        ++i;
        createBinaryTree(branch + 1);
    }

    if (i % 2 == 0 && i != 0){
        ++j;        //       ,j+1, tp[j]            
        tp[j]->rchild = curr;       //   
    }   
    else if (i % 2 == 1){
        tp[j]->lchild = curr;       //   
    }

    if (i == (len - 1)){
        return 1;       // i        ,    
    }

    i++;        //              
    createBinaryTree(branch + 1);       //   


}

//      
void visit(ThreadPoint tp){
    printf("%c",tp->data);
}



void main(){
    ElemType * branch;

    branch = (ElemType *)malloc(sizeof(ElemType));      //               

    printf("             【 :AEBCD】:");
    scanf("%s",branch);        //     

    len = strlen(branch);           //     

    createBinaryTree(branch);       //    

    printf("  ,         :");
    for (int i = 0; i < len; i++){
        visit(tp[i]);
    }
    printf("
"
); }

Done!

좋은 웹페이지 즐겨찾기