C 언어 이 진 트 리 의 옮 겨 다 니 기

나 무 는 비교적 중요 한 데이터 구조, 특히 이 진 트 리 이다.이 진 트 리 는 특수 한 나무 로 이 진 트 리 의 각 노드 에 최대 두 개의 키 노드 가 있 는데 보통 왼쪽 노드 와 오른쪽 노드 (또는 왼쪽 아이 와 오른쪽 아이) 라 고 부 르 고 이 진 트 리 의 서브 나 무 는 좌우 의 구분 이 있 으 며 그 다음 에 순서 가 임의로 바 뀌 어 서 는 안 된다.이 진 트 리 는 재 귀적 으로 정 의 된 것 이기 때문에 이 진 트 리 와 관련 된 문 제 는 대체적으로 재 귀적 사상 으로 해결 할 수 있다. 물론 일부 문 제 는 재 귀적 해법 도 파악 해 야 한다. 예 를 들 어 재 귀적 으로 노드 를 옮 겨 다 니 지 않 는 등 이다.이 진 트 리 를 잘 배 우려 면 재 귀적 인 기 교 를 어느 정도 익 혀 야 하 며 평소의 축적 이 필요 하 다.다음은 이 진 트 리 를 만 들 고 이 진 트 리 를 옮 겨 다 니 며 이 진 트 리 의 결점 을 만 드 는 구조 체 를 소개 합 니 다.
typedef struct tree
{
    int data;              //           ,                int  data
    struct tree *l,*r;
}TREE;

이 진 트 리 노드 를 만 드 는 함수
이 진 트 리 를 만 드 는 함수
4. 567913. 다음은 이 진 트 리 를 옮 겨 다 니 는 거 예요.
우선 선착순 으로 옮 겨 다 니 는 코드 를 써 드 리 겠 습 니 다.
TREE* create_node(int data)            //      ,         
{
    TREE* root = malloc(sizeof(TREE)); //             
    root->data = data;                 //      
    root->l = root->r = NULL;
    return root;
}

중간 순서 로 옮 겨 다 닌 다.
TREE* create_tree(int n)              //          ,        
{
    TREE *root = create_node(n);
    if(2*n<10)
        root->l=create_tree(2*n);
    if(2*n+1<10)
	root->r=create_tree(2*n+1);
    return root;
}

뒤 순 서 를 옮 겨 다 닌 다.
void show_tree_pre(TREE *root)       //    ,                 
{
    if(root == NULL)                 //    
	return;
    printf("%d-",root->data);        //  :         
    show_tree_pre(root->l);          //       
    show_tree_pre(root->r);          //       
}

이상 은 이 진 트 리 의 세 가지 기본 적 인 옮 겨 다 니 는 방식 이다.
다음 에 주 함 수 를 쓰 시 오
void show_tree_mid(TREE *root)       //    ,                     
{
    if(root == NULL)
	return;
    show_tree_mid(root->l);
    printf("%d-",root->data);            //     
    show_tree_mid(root->r);
}

출력 결과
1-2-4-8-9-5-3-6-7- 8-4-9-2-5-1-6-3-7- 8-9-4-5-2-6-7-3-1-
끝, 우선 순 서 는 뿌리 - > 왼쪽 나무 - > 오른쪽 나무 
                   중 서 는 왼쪽 나무 - > 뿌리 - > 오른쪽 나무
                   뒤 순 서 는 왼쪽 나무 - > 오른쪽 나무 - > 뿌리
위의 세 가지 방식 으로 재 귀 하면 이 진 트 리 전 체 를 옮 겨 다 닐 수 있다.

좋은 웹페이지 즐겨찾기