이진 트리에서 동일한 값을 가진 리프를 삭제하십시오.

Question

각 노드의 값을 가진 이진 트리 T를 사용하여 동일한 값을 가진 형제가있는 모든 리프를 검색하고 삭제하는 의사 코드가 필요합니다. 최적의 복잡성 의사 코드가 필요합니다.

나는 그것을 맞이

deleteCopy(TREE T) 
if T != nil then 
    if T.left = null and T.right = null 
    if T.parent.right.left = null and T.parent.right.right = null 
     if T.parent.left.value = T.parent.right.value then 
     delete T 
    deleteCopy(T.left()) 
    deleteCopy(T.right()) 

처럼 samething 수 shouls 것 같아요?

Answer 1

저는이 문제에 익숙하지 않지만 순회 알고리즘을 사용해야합니다.

inOrderSearch(Node n) 
    inOrderSearch(n.left) 
    check(n) 
    inOrderSearch(n.right) 

check(Node n) 
    right = n.right 
    left = n.left 
    if right.left == null && right.right == null && left.left == null && left.right == null 
     if right.value == left.value 
      n.left = null 

내가 순서 순회를 선택했지만이 경우 레벨 순서가 더 좋습니다. 그들은 잎 두 경우 문, 그것은 확인 여부를 확인 서브 루틴에서 ,

1. 두 형제 (노드의 아이들) 처음에
2. 를 얻을.
3. 두 번째 if 문에서 일치하면
4. 을 확인합니다. 동일하면 왼쪽 노드를 삭제합니다. 너하기에 달렸다.

루트 노드로 검색을 시작할 수 있습니다.