N 진 트리 깊이 및 차수 알고리즘

Question

트리의 최대 차수 (노드의 최대 수)와 깊이 (가장 긴 분기의 길이)를 반환해야하는 몇 가지 알고리즘에 몇 가지 문제가 있습니다. 일부 나무 구조에서는 작동하지만 일부에서는 그렇지 않습니다. 누군가 내가 코드에 문제가 있는지 말해 줄 수 있습니까?

내 트리 구조는

public class Tree<T> { 

    public Node<T> root; 

    public Tree() { 
    root = null; 
    } 

내 노드 구조는 다음과 같습니다

public class Node<T>{ 
    public T elem; 
    private Node<T> father; 
    private Node<T> child; 
    private Node<T> sibling; 
    private T epsilon; 

public Node(T elem){ 
    this.elem = elem; 
    this.father = null; 
    this.child = null; 
    this.sibling = null; 
} 

정도의 알고리즘은 마지막으로

public int degree(){ 
int breadth = 0; 
int max = 0; 
return auxDegree(this.root, breadth, max); 
} 

public int auxDegree(Node<T> node, int count, int maxChild){ 
if(node!=null){ 
    if(node.getChild()!=null){ 
    maxChild = Math.max(auxDegree(node.getChild(), 0, maxChild), auxDegree(node.getSibling(), 0, maxChild)); 
    count = countSibling(node.getChild()) + 1; 
    return (count>maxChild) ? count : maxChild; 
    }else return maxChild; 
}else return maxChild; 
} 

, 깊이 알고리즘 :

public int depth(){ 
    int deepness = 0; 
    return auxDepth(this.root, deepness); 
} 

public int auxDepth(Node<T> node, int maxDepth){ 
    if(node!=null){ 
    if(node.getChild()!=null){ 
     maxDepth = Math.max(maxDepth, auxDepth(node.getChild(), maxDepth)); 
     maxDepth = maxDepth + 1; 
     return maxDepth; 
    }else{ 
     return maxDepth; 
    } 
    }else return maxDepth; 
} 

,

삽입 코드는 다음과 같습니다

public Node<T> search(T key){ 
    return searchAux(this.root, key); 
} 

private Node<T> searchAux(Node<T> node, T key){ 
    if(node == null) 
    return null; 
    else{ 
    while(node.getChild() != null && key != node.getElem()){ 
     node = node.getChild(); 
     searchAux(node.getSibling(), key); 
    } 
    } 
    return node; 
} 

public void insert(T father_key, T child_key){ 
    if(IsEmpty()) 
    this.root = new Node<T>(child_key); 
    else{ 
    Node<T> node = new Node<T>(child_key); 
    Node<T> father = search(father_key); 
    if(father.getChild() == null){ 
     father.setChild(node); 
     node.setParent(father); 
    }else{ 
    if (father.getChild() != null){ 
     Node<T> brother = father.getChild(); 
     while(brother.getSibling() != null){ 
     brother = brother.getSibling(); 
     } 
     brother.setSibling(node); 
     node.setParent(father); 
     } 
    } 
    } 
} 

작동하지 않는 구조는 다음과 같습니다

가

public void Test_Depth(){ 
    tree.insert(null, e2); 
    tree.insert(e2, e3); 
    tree.insert(e2, e1); 
    tree.insert(e3, e4); 
    tree.insert(e4, e5); 
    tree.insert(e5, e6); 
    tree.insert(e6, e7); 
    assertEquals(6,tree.depth()); 
} 

이이 3 만 수익률을 반환해야 5 반환하지만 6

public void Test_Depth(){ 
    tree.insert(null, e1); 
    tree.insert(e1, e2); 
    tree.insert(e1, e3); 
    tree.insert(e3, e4); 
    tree.insert(e3, e5); 
    tree.insert(e3, e6); 
    assertEquals(3,tree.degree()); 
} 

를 반환해야 2

e1 내지 e7은 정수이다.

Answer 1

두 가지.

먼저 무엇보다도 searchAux 기능이 잘못되었습니다. 반환 값이 무시되기 때문에 다음 줄은 쓸모가 : 아이 노드가 잘못된 부모에 할당하는

searchAux(node.getSibling(), key); 

또한, while 루프가 있습니다. 조건

node.getChild() != null && key != node.getElem() 

키 값에 관계없이 방문중인 노드에 자식이 없으면 false입니다. 즉, 반환 할 노드가을 찾고있는 부모 노드가 아니더라도 다음에 나오는 return node; 명령어가 실행될 수 있습니다.

예를 들어 두 번째 예에서 발생합니다. 지금까지 너무 좋아

e1 
| 
e2--e3 

:이 처음 세 insert의 (수직선 = 부모 - 자식, 수평선 = 형제) 후 상황이다. 그러나 tree.insert(e3, e4)으로 전화를 걸면 e3는 방문했지만 무시됩니다. e2가 그 대신에 반환됩니다 (코드를 통해 시도해보십시오). 따라서 :

e1 
| 
e2--e3 
| 
e4 
| 
e5 
| 
e6 

둘째 :

e1 
| 
e2--e3 
| 
e4 

이 두 번째 나무가 그렇고, 결국 모습입니다 최초의 나무에도 불구하고, 지금까지 내가 말할 수있는, 정확한 당신의 검색 알고리즘이 잘못되었습니다.그것의 깊이 (루트 노드의 깊이가 제로) 5,하지 6 인 : 측면에 (

private Node<T> searchAux(Node<T> node, T key){ 
    if(node == null) 
     return null; 
    if (node.getElem() == key) 
     return node; 
    if (node.getChild() != null) { 
     Node<T> foundNode = searchAux(node.getChild(), key); 
     if (foundNode != null) 
      return foundNode; 
    } 
    return searchAux(node.getSibling(), key); 
} 

:

말했다되고 그건

0: e2 
    | 
1: e3--e1 
    | 
2: e4 
    | 
3: e5 
    | 
4: e6 
    | 
5: e7 

이 여기 재귀 깊이 우선 검색을위한 빠른 초안의 참고, else 초 후에 returns.)