이진 트리 선형 함수 검색

Question

검색 이진 트리를 사용하는 작은 프로그램을 수행하려고합니다.

각 노드에 대해 계산 :

• 두 기능 함수 L (U) 및 R (U) L이 (U)에 뿌리 좌측 서브 트리의 노드 키의 합인
• u
• R (u)는 오른쪽 하위 트리의 합계입니다. 프로그램은 출력으로서 가져야

는 :

• 이 속성 L을 만족 키 노드 (U) ※ K < R (U)는
• 는 K는 키의 오름차순 프린트 입력 된 정수.

문제는 함수가 선형 복잡성을 가져야하며 n^2보다 작게 만들 수 없다는 점입니다.

누군가 나를 도울 수 있습니까?

Answer 1

기본적으로 하위 트리의 키 합계를 계산해야합니다. 그것은 잘 알려진 문제입니다.

func calc(node): 
    if node is null: 
     return 0 
    node.lval = calc(node.left) # L(u) 
    node.rval = calc(node.right) # R(u) 
    return node.key + node.lval + node.rval 

경우 lval 및 rval 먼저 0으로 초기화.

이제 나무를 걷고 (처음 왼쪽, 오른쪽보다) 상태를 확인해야합니다.

func print(node): 
    if has left child: 
     print(node.left) 
    if node.lval*k < node.rval: 
     output node.key 
    if has right child: 
     print(node.right)