AVL 트리 샘플 설명

Question

내가 AVL 나무와 구현의 일부에 대한 몇 가지 샘플 소스 코드를 읽고있다

이 다음과 같은 기능입니다 다음과 같이

AvlTree MakeEmpty(AvlTree T) 
{ 
    if(T != NULL) 
    { 
     MakeEmpty(T->Left); 
     MakeEmpty(T->Right); 
     free(T); 
    } 
    return NULL; 
} 

주요 기능에서, 그것은 사용됩니다

int main() 
{ 
    AvlTree T; 

    T = MakeEmpty(NULL); 

주 기능은 AVL 트리에 삽입 번호로 이동합니다. 내 주요 질문은

입니다. a) MakeEmpty 함수의 목적은 무엇입니까? 나는 이것이 재귀 함수라는 것을 이해하지만 그 목적을 이해하지 못한다.

b) NULL 값이이 함수에 전달되는 이유는 무엇입니까?

감사합니다.

struct AvlNode 
{ 
    ElementType Element; 
    AvlTree Left; 
    AvlTree Right; 
    int  Height; 
}; 

Answer 1

여기 코드에 대한 이해입니다 :

"는 MakeEmpty 기능의 목적은 무엇인가 나는 그것이 재귀 함수임을 이해하지만, 나는 그것의 목적을 이해하지 않습니다."

, 기본적으로는 AvlTree 개체를 만들 수 있습니다. MakeEmpty이 널 당신이 빈 트리 노드를 원하는 때문에 전달 된 이유) (주 INT 권리와 왼쪽 어린이 내부에 정의되지 않은.

나. 왜 Null은 재귀를 종료합니다. 아이디어가 정의되지 않은 자식 노드가 Null을 통과하는 빈 트리를 만드는 것이므로 "emtpy 개체"를 만듭니다.

이 코드의 전체 내용은 다음과 같습니다. 내가 알 수있는 한 null AvlTree를 만듭니다. HTH. 감사합니다.

Answer 2

이 C 스타일 ctor 및 AvlNode에 대한 dtor과 같습니다

또한, AVLTree이 구조체에 대한 포인터이다. 대신 C++에서

, 당신은

struct AvlNode 
{ 
    ElementType Element; 
    AvlTree Left; 
    AvlTree Right; 
    int  Height; 

    AvlNode() 
     : Left(NULL), Right(NULL), Height(0) 
    {} 

    ~AvlNode() 
    { 
     // free node 
    } 
}; 

뭔가를 할 수 있습니다하지만 당신은 그래서 기본적으로 MakeEmpty 그냥 두 포인터를 임의의 주소를 가리 키지 않는다는 것을 확인하기 위해 C로이 작업을 수행 할 수 있지만, NULL을 가리 킵니다.

Answer 3

a) MakeEmpty 기능의 목적은 무엇입니까? 나는 이것이 재귀 함수라는 것을 이해하지만 그 목적을 이해하지 못한다.

makeEmpty() 모든 노드에 대해 사용 가능한 메모리 기능을 제공하며 그 이름대로 포스트 오더로 이동합니다. 노드가 처리되면 노드를 처리 한 후에 포스트 패쓰 트래커에서 노트를 다시 참조하지 않으므로 해제 된 노드가 다시 참조가 아니어야하므로 모든 노드의 포스트 순서가 올 바릅니다.

b) NULL 값이이 함수에 전달되는 이유는 무엇입니까?

에 대한 대칭적인 방법은 T를 NULL로 초기화했습니다. 알림 MakeEmpty(NULL);은 null이 전송되므로 null을 반환합니다.

 T = MakeEmpty(NULL); 
==  T = NULL 

편집 MakeEmpty()가 작동하는 방법

? (의견 읽기)

AvlTree MakeEmpty(AvlTree T) 
{ 
    if(T != NULL) 
    { 
     MakeEmpty(T->Left); // but in stack 
     MakeEmpty(T->Right); // but in stack 
     free(T);    // free node 
    } 
    return NULL; // if T is passed NULL then it returns NULL 
} 

(대답) (대답) T = MakeEmpty(NULL);는 NULL을 반환합니다.

Answer 4

a) 트리를 비우는 것 - 즉 모든 노드를 해제하는 것.

b) 재귀 함수이기 때문에 리프에 도달하면 null을 전달하므로 다음에 나오기 전에 null을 쉽게 확인할 수 있지만 재귀 호출