이진 트리 - 레벨의 노드 계산하기

Question

저는 이진 트리 클래스를 작성 중이며 levelCount 메소드를 사용하고 있습니다. 레벨 수의 노드 수를 계산해야합니다. 이 같은 클래스 및 방법 모양 뭔가 :

public class ConsTree<T> extends BinaryTree<T> 
{ 
    BinaryTree<T> left; 
    BinaryTree<T> right; 
    T data; 

    public int levelCount(int level) 
    { 
    } 
} 

그래서 아이디어는 각 트리 왼쪽의에 나무, 오른쪽 및 데이터에 대한 트리를 가지고 있다는 것입니다. 추상 클래스 binarytree가 있고 ConsTree와 EmptyTree라는 하위 클래스가 있습니다.

폭 넓은 첫 번째 검색을 사용하고 일단 해당 수준에 도달하면 노드 수를 계산해야한다고 생각하지만 시작하는 방법에 대해 고민하고 있습니다. 여기에 어떤 지침이 도움이 될 것입니다. 필요한 정보를 제공해 드릴 수 있습니다.

Answer 1

다음은 일반적인 접근 방식입니다.

당신은 정확히 트리를 탐색 평소처럼 (깊이 우선, 주문에서)하지만 당신은 단순히 함께뿐만 아니라 원하는 실제 수준을 물려 의사 코드 같은 :

def getCountAtLevel (node, curr, desired): 
    # If this node doesn't exist, must be zero. 
    if node == NULL: return 0 

    # If this node is at desired level, must be one. 
    if curr == desired: return 1 

    # Otherwise sum of nodes at that level in left and right sub-trees. 
    return getCountAtLevel (node.left, curr+1, desired) + 
      getCountAtLevel (node.right, curr+1, desired) 

####################################################################### 
# Get number of nodes at level 7 (root is level 0). 
nodesAtLevel7 = getCountAtLevel (rootNode, 0, 7) 

이 전체 트리를 실제로 통과하지 않습니다. 일단 원하는 레벨이되면, 그 아래의 모든 것을 무시할 수 있습니다.

#include <stdio.h> 

typedef struct _sNode { struct _sNode *left, *right; } tNode; 

// Node naming uses (t)op, (l)eft, and (r)ight. 
tNode t_l_l_l = {NULL,  NULL }; // level 3 
tNode t_l_l_r = {NULL,  NULL }; 
tNode t_r_l_l = {NULL,  NULL }; 
tNode t_r_l_r = {NULL,  NULL }; 
tNode t_r_r_r = {NULL,  NULL }; 
tNode t_l_l = {&t_l_l_l, &t_l_l_r}; // level 2 
tNode t_r_l = {&t_r_l_l, &t_r_l_r}; 
tNode t_r_r = {NULL,  &t_r_r_r}; 
tNode t_l  = {&t_l_l, NULL }; // level 1 
tNode t_r  = {&t_r_l, &t_r_r }; 
tNode t  = {&t_l,  &t_r }; // level 0 (root) 

static int getCAL (tNode *node, int curr, int desired) { 
    if (node == NULL) return 0; 
    if (curr == desired) return 1; 
    return getCAL (node->left, curr+1, desired) + 
      getCAL (node->right, curr+1, desired); 
} 

int main (void) { 
    for (int i = 0; i < 4; i++) 
     printf ("Level %d has %d node(s)\n", i, getCAL (&t, 0, i)); 
    return 0; 
} 

그것은 다음과 같은 형태의 트리 빌드 : 다음은이 행동으로 보여주는 완전한 C 프로그램의

 __X__ 
    / \ 
    X  X 
/ /\ 
    X  X X 
/\ /\ \ 
X X X X X 

은 다음 각 레벨의 노드 수를 제공합니다

Level 0 has 1 node(s) 
Level 1 has 2 node(s) 
Level 2 has 3 node(s) 
Level 3 has 5 node(s) 

을