C++ AVL 트리의 높이를 다시 계산합니다.

Question

im은 AVL 트리의 임 플리 멘 테이션 작업을하고 있으며, im은 높이 재 계산 기능에 문제가 있습니다. 내가 그것을 트리의 루트와 1의 값을 가진 변수를 통과 할 때 호출하고 그것을 통해 단계별로 한 번 while 루프에 도착하면 예상대로 preform하지만 이후에는 하나만 반환합니다. 당신은 그것을보고 제 잘못을보고 싶습니까? 필요한 경우 더 많은 코드를 게시 하겠지만 함수가 충분한 정보를 제공 할 것이라고 생각합니다. 감사합니다

void BinaryTree::recalculate(Node *leaf, int count) 
{ 
    if(leaf == NULL)//if we are at the root 
    { 
     return;//exit the function 
    } 

    if((leaf->getLeft() != NULL))//if we are not at the end of the subtree 
    { 
     recalculate(leaf->getLeft(), count);//advance to the next node and re-enter the function 

    } 

    if(leaf->getRight() != NULL)//if we are not at the end of the right subtree 
    { 
     recalculate(leaf->getRight(), count);//advance to the next node and re-enter the program 
    } 

    else 
    { 
     while(leaf->getParent() != NULL)//calculate each subtree until we are at the root 
     { 
      leaf = leaf->getParent();//get the parent node 
       count++;//increment the height   

      if(leaf->getLeft() != NULL)//if there is an item in the left 
      { 

       leaf->getLeft()->setHeight(count-1);//sets the hight of the left child 
      } 

      if(leaf->getRight() != NULL)//if there is an item in the right 
      { 
      leaf->getRight()->setHeight(count -1);//sets the height of the right child 

      } 
     } 

     return;//exit the function 
    } 
} 

Answer 1

이 함수는 이진 트리의 각 하위 트리의 높이를 계산하고 그 값을 해당 하위 트리의 루트 노드에 저장합니다. 표준적인 재귀 적 접근 방식을 선택했습니다. 이 방법에서는 왼쪽 및 오른쪽 하위 트리의 높이를 먼저 계산 한 다음 현재 노드에 대해 둘 다 높이를 계산해야합니다.

구현시 매개 변수로 전달 된 count 값을 재귀 호출에 사용합니다. 우리가 서브 노드에서 카운트를 가져오고, 서브 노드를 넘겨주지 않으면, 그 값의 목적은 무엇입니까? 당신이 경우

는 :

• recalculate 매개 변수에서 해당 값을 제거 적용
• 각 하위 노드 높이에서 recalculate 업데이 트를 현재 노드의 높이를 할 경우
• 두 아이에 첫 자체를 recalculate 메소드를 호출 한

그래야합니다. getHeight 방법이 사용될 수없는 경우

void BinaryTree::recalculate(Node *leaf) { 
    int count = 0; 
    if (leaf == NULL) { 
     return; 
    } 
    if (leaf->getLeft() == NULL && leaf->getRight() == NULL) { 
     // no child, the height is 0 
     setHeight(0); 
     return; 
    } 
    if (leaf->getLeft() != NULL) { 
     recalculate(leaf->getLeft()); 
     count = leaf->getLeft()->getHeight(); 
    } 
    if (leaf->getRight() != NULL){ 
     recalculate(leaf->getRight()); 
     count = max(count, leaf->getRight()->getHeight()); 
    } 
    // include leaf in the height 
    setHeight(count+1); 
} 

, 당신이 그것을 계산 된 높이를 반환 recalculate함으로써 대체 할 수있다 : 다음의 가능성이 알고리즘에 기초하여 실행된다.