이진 검색 트리

안녕 내가 {23,16,45,26,2,5,9} 처럼 몇 가지 숫자를 가지고 배열 목록을 가지고 있고이이 배열리스트와 이진 검색 트리를 만들고 싶어 "array"과 그 요소가 객체 2 필드, 1)digit2)level하지만, 여기 단지 그 digit 필드를 사용하고 싶습니다. 또한 dList은 DoublyLinkedList입니다. 이것은 내 코드이지만 exception.please가 도움이됩니다.이진 검색 트리

private void method(ArrayList<Element> array) { 
    DNode header = new DNode(null, null, null); 
    DNode trailer = new DNode(null, header, null); 
    header.next = trailer; 
    DNode node = new DNode(array.get(0), header, trailer); 
    dList.addLast(node); 
    header = node 
    for(int i = 1;i<array.size();i++){ 
    makeBST(node, array.get(i)); 
    } 
} 

private void makeBST(DNode node, Element e) { 

    if (!e.equals(node.getElement())) { 
     DNode nodeOne = new DNode(e, null, null); 
     if (node.getElement().getDigit() > e.getDigit()) { 
      node.prev = nodeOne; 
     } else if (node.getElement().getDigit() < e.getDigit()) { 
      node.next = node; 
     } 
    } 
    if (e.getDigit() < node.getElement().getDigit()) { 
     makeBST(node.prev, e); 
    } 
    makeBST(node.next, e); 
}

예외 :

Exception in thread "main" java.lang.StackOverflowError 
    at OBST.GreedyVersion.makeBST(GreedyVersion.java:43) 
    at OBST.GreedyVersion.makeBST(GreedyVersion.java:54) 
    at OBST.GreedyVersion.makeBST(GreedyVersion.java:54) 
    at OBST.GreedyVersion.makeBST(GreedyVersion.java:54)

예외의 첫 줄이 코드 라인이다

if (!e.equals(node.getElement()))

출처

2010-12-13 user472221

재귀 법 "개인 무효 makeBST (DNode 노드 요소 e)" 어떤 종류의 종료 조건 (그것이 자신을 부르지 못하게하는 흐름 경로)이 필요합니다. 그대로, 스택 오버플로 오류를 일으키는 자체를 재귀 적으로 계속 호출합니다.

출처

2010-12-13 15:33:55 Assaf

어떻게 재귀 호출을 완료 할 수 있습니까? – user472221

첫 번째 if 블록의 끝에 "return"이 필요하다고 생각합니다. 또는 동일한 결과로 재귀 makeBST 호출을 적절한 "else if"블록에 넣을 수 있습니다. – TToni

@ user472221, TToni와 iirekm는 올바르게했습니다. 재귀 적 종료 조건의 경우 재귀를 중지해야하는 시점을 생각해야합니다 (힌트 : 크기가 0이거나 크기가 1 인 트리가있는 경우 어떻게됩니까?). 그리고 그 조건에 도달하면 함수를 확인해야합니다 자체 호출을 중지합니다. – Assaf

당신은 StackOverflowError가 있습니다. StackOverflowError는 무한 (잠재적으로 적어도 잠재적으로) 재귀 오류를 가리 킵니다.

p.s. 왜 TreeMap<K,V>을 사용하지 않는가? 여기서 K는 데이터의 인덱스이고 V는 데이터 값입니까?

출처

2010-12-13 15:34:10

코드는 기본적으로 :

이

private void makeBST(DNode node, Element e) { 
    // ... (the rest of your code) 
    makeBST(node.next, e); 
}

그것은 거의 동등의 :

private void makeBST(DNode node, Element e) { 
    while(true) { 
     // ... (the rest of your code) 
     node = node.next; 
    } 
}

당신은 그냥 무한 루프를했다 (그러나 반면에,하지만 재귀와 함께). 스택 크기가 매우 제한적이기 때문에 일부 반복 후에는 StackOverflowError가 발생합니다.

하지만 어쨌든, 단지 교육적인 실험이라면 괜찮습니다. BST가 작동하기 만하면 java.util.TreeSet 또는 java.util.TreeMap을 사용하십시오.

출처

2010-12-13 15:49:42 iirekm

treeSet 또는 treeMap으로 어떻게 BST를 만들 수 있습니까?도와 줄래? – user472221

나는 당신이 노력하고있는 것을 볼 수 있지만, 당신은 솔루션에서 먼 길을 가고 있습니다.

재귀를 사용하고 있으므로 중지 사례가 필요합니다.

또한 아마해야하는 경우 ... 다른 경우 ... 오히려 당신이 가지고있는 것보다 (있는 경우 ... ... 경우) ...

if (!e.equals(node.getElement())) { 중 하나 말도 안돼 그 라인

바이너리 트리 및 바이너리 검색 트리에 대한 위키 백과 문서를 확인하십시오. 아마도 도움이 될 것입니다.

출처

2010-12-13 16:38:58

이진 검색 트리

답변

관련 문제