논의된 개념의 시각적 표현은 아래 그림에 나와 있습니다.
이 가이드에서는 아래 언급된 섹션을 다루면서 이진 트리의 모든 리프 노드를 인쇄하는 과정을 설명합니다.
- 리프 노드를 식별하는 방법은 무엇입니까?
- JavaScript에서 이진 트리의 모든 리프 노드를 왼쪽에서 오른쪽으로 인쇄하는 방법은 무엇입니까?
- 보너스 팁: 오른쪽에서 왼쪽 방향으로 이진 트리의 리프 노드 인쇄
- 결론
리프 노드를 식별하는 방법은 무엇입니까?
“ 잎 ” 노드는 하위 노드가 없거나 구체적으로 “ 키 ' 의 ' 0 '. 노드에 ' 키 ' 보다 큰 ' 0 ” 그러면 해당 노드는 내부 노드 또는 루트 노드가 될 수 있습니다. “ 잎 ” 노드는 일반적으로 이 노드가 생성된 원본 소스를 식별하기 위해 역추적됩니다. 주로 오류나 문제의 원인을 찾기 위한 검색이나 오류 찾기 알고리즘에 사용됩니다.
JavaScript에서 이진 트리의 모든 리프 노드를 왼쪽에서 오른쪽으로 인쇄하는 방법은 무엇입니까?
두 가지 접근 방식이 있습니다.” 재귀적 ' 그리고 ' 반복적 인 '를 사용하여 원하는 '에서 제공된 이진 트리에서 사용 가능한 모든 리프 노드를 선택합니다. 왼쪽 ' 에게 ' 오른쪽 ' 방향. 이러한 접근 방식의 실제 구현은 아래 명시된 섹션에서 설명됩니다.
방법 1: 이진 트리의 모든 리프 노드를 왼쪽에서 오른쪽으로 재귀적으로 인쇄
재귀적 접근 방식은 모든 노드를 선택합니다. 깊이 우선 탐색 알고리즘 먼저 전체 왼쪽 노드를 통과한 다음 마지막에 중간 노드와 오른쪽 노드를 통과하는 방식입니다. 이 작업은 모든 노드에 대해 반복적으로 수행되며 ' 잎 ” 노드가 식별됩니다. 이 개념을 더 잘 이해하려면 아래 코드 조각을 방문하세요.
수업 마디{
건설자 ( )
{
이것 . 콘텐츠 = 0 ;
이것 . 왼쪽 = 없는 ;
이것 . 오른쪽 = 없는 ;
}
} ;
여기서 displayLeafNodes = ( 루트노드 ) =>
{
만약에 ( 루트노드 == 없는 )
반품 ;
만약에 ( 루트노드. 왼쪽 == 없는 && 루트노드. 오른쪽 == 없는 )
{
문서. 쓰다 ( 루트노드. 콘텐츠 + ' ' ) ;
반품 ;
}
만약에 ( 루트노드. 왼쪽 != 없는 )
디스플레이리프노드 ( 루트노드. 왼쪽 ) ;
만약에 ( 루트노드. 오른쪽 != 없는 )
디스플레이리프노드 ( 루트노드. 오른쪽 ) ;
}
샘플노드였음 = ( 발 ) =>
{
tempNode였습니다 = 새로운 마디 ( ) ;
tempNode. 콘텐츠 = 발 ;
tempNode. 왼쪽 = 없는 ;
tempNode. 오른쪽 = 없는 ;
반품 임시 노드 ;
}
루트 노드였습니다 = prov노드 ( 삼 ) ;
루트노드. 왼쪽 = prov노드 ( 6 ) ;
루트노드. 오른쪽 = prov노드 ( 9 ) ;
루트노드. 왼쪽 . 왼쪽 = prov노드 ( 12 ) ;
루트노드. 왼쪽 . 오른쪽 = prov노드 ( 열 다섯 ) ;
루트노드. 왼쪽 . 오른쪽 . 오른쪽 = prov노드 ( 24 ) ;
루트노드. 오른쪽 . 왼쪽 = prov노드 ( 18 ) ;
루트노드. 오른쪽 . 오른쪽 = prov노드 ( 이십 일 ) ;
디스플레이리프노드 ( 루트노드 ) ;
위의 코드 블록에 대한 설명은 다음과 같습니다.
- 먼저 '라는 클래스를 만듭니다. 마디 ”, 그러면 새 노드가 생성되고 해당 값이 “ 0 '. 첨부 된 ' 왼쪽 ' 그리고 ' 오른쪽 ' 사이드 노드는 '로 설정됩니다. 없는 ” 기본적으로 클래스 생성자를 사용합니다.
- 다음으로 “ 디스플레이리프노드() ”의 단일 매개변수를 받아들이는 함수 루트노드 '. 이 매개변수 값은 이진 트리의 현재 선택된 노드로 간주됩니다.
- 함수 내부에는 “ 만약에 ”문은 “ 루트노드 ”는 null이거나 아닙니다. “의 경우 없는 ” 해당 노드에 대한 추가 실행이 중지되었습니다. 다른 경우에는 rootNode “ 왼쪽 ' 그리고 ' 오른쪽 ' 측면 노드는 '에 대해 확인됩니다. 없는 '. 둘 다 null인 경우 해당 ' 마디 '가 인쇄됩니다.
- 만약 “ 왼쪽 ' 또는 ' 오른쪽 ' 노드가 'null'이 아닌 경우 노드의 해당 쪽을 ' 디스플레이리프노드() ” 재귀 연산을 위한 함수입니다.
- '라는 이름의 새 함수를 정의합니다. provNode() ”는 “의 단일 매개변수를 허용합니다. 발 '. 함수 내부에서 '의 새 인스턴스를 만듭니다. 마디 '라는 이름의 클래스 ' 임시 노드 '. 파라메트릭 '을 할당합니다. 발 ” 클래스 속성의 값으로 “ 콘텐츠 '를 설정하고 ' 왼쪽 ' 그리고 ' 오른쪽 ” 사이드 노드를 “ 없는 ' 기본적으로.
- 마지막으로 '라는 개체를 만듭니다. 루트노드 '에 대한' provNode() ” 함수를 실행하고 노드 값을 이 함수 매개변수로 전달합니다. '를 추가하여 왼쪽 및 오른쪽 노드를 만듭니다. 왼쪽 ' 그리고 ' 오른쪽 ' 키워드를 'rootNode'로 지정하고 동일한 함수를 사용하여 값을 할당합니다. provNode() '.
- “ 왼쪽 ”는 루트 노드의 왼쪽 위치를 의미하고 “ 왼쪽.왼쪽 ” 위치는 왼쪽의 왼쪽을 의미합니다. “의 경우에도 동일한 접근 방식이 적용됩니다. 오른쪽 ' 그리고 ' 오른쪽 ”
- 트리를 정의한 후 'rootNode'를 '에 대한 인수로 전달합니다. 디스플레이리드노드() ” 함수를 사용하여 생성된 트리의 모든 리프 노드를 선택하고 인쇄할 수 있습니다.
컴파일 후 생성된 출력은 제공된 트리의 리프 노드가 검색되어 콘솔을 통해 인쇄되었음을 확인합니다.
방법 2: 반복 접근법을 사용하여 이진 트리의 모든 리프 노드 인쇄
“ 반복적 인 ” 접근 방식은 가장 효율적인 접근 방식이며, “ 푸시 ' 그리고 ' 팝 '를 선택하려면 ' 잎 ” 노드. 이 접근 방식의 핵심 사항이나 작업은 다음과 같습니다.
수업 마디{
건설자 ( 값 )
{
이것 . 데이터 = 값 ;
이것 . 왼쪽 = 없는 ;
이것 . 오른쪽 = 없는 ;
}
} ;
여기서 displayLeafNodes = ( 루트노드 ) =>
{
만약에 ( ! 루트노드 )
반품 ;
목록을 보자 = [ ] ;
목록. 푸시 ( 루트노드 ) ;
~하는 동안 ( 목록. 길이 > 0 ) {
루트노드 = 목록 [ 목록. 길이 - 1 ] ;
목록. 팝 ( ) ;
만약에 ( ! 루트노드. 왼쪽 && ! 루트노드. 오른쪽 )
문서. 쓰다 ( 루트노드. 데이터 + ' ' ) ;
만약에 ( 루트노드. 오른쪽 )
목록. 푸시 ( 루트노드. 오른쪽 ) ;
만약에 ( 루트노드. 왼쪽 )
목록. 푸시 ( 루트노드. 왼쪽 ) ;
}
}
루트 노드였습니다 = 새로운 마디 ( 삼 ) ;
루트노드. 왼쪽 = 새로운 마디 ( 6 ) ;
루트노드. 오른쪽 = 새로운 마디 ( 9 ) ;
루트노드. 왼쪽 . 왼쪽 = 새로운 마디 ( 12 ) ;
루트노드. 왼쪽 . 오른쪽 = 새로운 마디 ( 열 다섯 ) ;
루트노드. 왼쪽 . 오른쪽 . 오른쪽 = 새로운 마디 ( 24 ) ;
루트노드. 오른쪽 . 왼쪽 = 새로운 마디 ( 18 ) ;
루트노드. 오른쪽 . 오른쪽 = 새로운 마디 ( 이십 일 ) ;
디스플레이리프노드 ( 루트노드 ) ;
위 코드에 대한 설명은 아래와 같습니다.
- 먼저 ' 마디 ” 단일 매개변수를 받는 클래스 “ 값 ”라는 값이 새로 생성된 노드의 값으로 설정되고, 왼쪽과 오른쪽은 null로 설정됩니다. 위의 예에서와 같습니다.
- 다음으로, “ 디스플레이리프노드() ”는 “라는 단일 매개변수를 허용합니다. 루트노드 '. 이 'rootNode'는 이진 트리로 간주되며 비어 있는지 먼저 확인합니다.
- 노드가 비어 있지 않으면 '라는 이름의 빈 목록이 생성됩니다. 목록 '가 생성되고 ' 루트노드 ” 매개변수는 “를 사용하여 여기에 삽입됩니다. 푸시() ' 방법.
- 그런 다음 “ 하는 동안() ”는 “의 길이까지 실행되는 데 사용됩니다. 목록 '. 루프 내부에서 트리의 맨 아래에 있는 요소 또는 ' 목록 '는 '를 사용하여 제거됩니다. 팝() ' 방법.
- 이제 '의 존재 왼쪽 ' 그리고 ' 오른쪽 'rootNode'의 측면을 확인하고, 양쪽이 모두 존재하지 않으면 자식 노드가 없음을 의미합니다. 그러면 이 노드가 화면 위에 표시되고 리프 노드로 식별됩니다.
- 왼쪽이나 오른쪽에 노드가 있으면 자식이 있다는 뜻입니다. 그 ' 왼쪽 ' 그리고 ' 오른쪽 ' 노드가 '로 푸시됩니다. 목록 리프 노드를 찾는 추가 작업을 위해 ”
- 마지막으로 노드 값을 '에 대한 매개변수로 전달하여 사용자 정의 이진 트리를 만듭니다. 마디 ” 클래스 생성자. 생성 후 트리 'rootNode'를 '에 대한 인수로 전달합니다. 디스플레이리프노드() ' 기능.
컴파일 후 생성된 출력은 제공된 트리의 리프 노드가 인쇄되었음을 보여줍니다.
보너스 팁: 오른쪽에서 왼쪽 방향으로 이진 트리의 리프 노드 인쇄
'에서 하위 노드가 없는 모든 리프 노드를 검색하려면 오른쪽 ' 에게 ' 왼쪽 ” 방향으로 접근하는 경우 재귀적 접근 방식이 간편하기 때문에 가장 권장됩니다. 예를 들어, 위 섹션에서 논의된 동일한 트리는 리프 노드를 검색하는 데 사용되지만 ' 오른쪽 ' 로 ' 왼쪽 ” 방향은 아래와 같습니다.
수업 마디{
건설자 ( 값 )
{
이것 . 데이터 = 값 ;
이것 . 왼쪽 = 없는 ;
이것 . 오른쪽 = 없는 ;
}
} ;
함수 표시LeafNodes ( 뿌리 )
{
만약에 ( 뿌리 == 없는 )
{
반품 ;
}
만약에 ( 뿌리. 왼쪽 == 없는 && 뿌리. 오른쪽 == 없는 )
{
문서. 쓰다 ( 뿌리. 데이터 + ' ' ) ;
반품 ;
}
만약에 ( 뿌리. 오른쪽 != 없는 )
{
디스플레이리프노드 ( 뿌리. 오른쪽 ) ;
}
만약에 ( 뿌리. 왼쪽 != 없는 )
{
디스플레이리프노드 ( 뿌리. 왼쪽 ) ;
}
}
루트 노드였습니다 = 새로운 마디 ( 삼 ) ;
루트노드. 왼쪽 = 새로운 마디 ( 6 ) ;
루트노드. 오른쪽 = 새로운 마디 ( 9 ) ;
루트노드. 왼쪽 . 왼쪽 = 새로운 마디 ( 12 ) ;
루트노드. 왼쪽 . 오른쪽 = 새로운 마디 ( 열 다섯 ) ;
루트노드. 왼쪽 . 오른쪽 . 오른쪽 = 새로운 마디 ( 24 ) ;
루트노드. 오른쪽 . 왼쪽 = 새로운 마디 ( 18 ) ;
루트노드. 오른쪽 . 오른쪽 = 새로운 마디 ( 이십 일 ) ;
디스플레이리프노드 ( 루트노드 ) ;
위에서 언급한 코드는 다음과 같이 작동합니다.
- 먼저 수업은 ' 마디 '는 기본 생성자를 사용하여 위 예제에서 수행된 링크와 마찬가지로 트리에 새 노드를 추가하는 생성됩니다.
- 다음으로는 “ 디스플레이리드노드() '라는 단일 매개변수를 허용하는 함수가 생성됩니다. 루트노드 '. 이 매개변수는 ' 없는 ” 조건은 “를 통해 만약에 ' 성명.
- 제공된 노드가 true가 아닌 경우 해당 노드는 “ 왼쪽 ' 그리고 ' 오른쪽 ' 측면 노드는 '에 대해 확인됩니다. 없는 ' 상태. 둘 다 null이면 노드는 ' 잎 ” 노드를 추가하고 웹페이지 위에 인쇄합니다.
- 그 후 “ 오른쪽 ' 그리고 ' 왼쪽 '의 노드 루트노드 ' 로 ' 디스플레이리프노드() ' 기능.
- “를 사용하여 인스턴스를 생성하여 각 노드의 위치를 할당합니다. 새로운 ' 키워드와 ' 마디() ” 생성자를 지정하고 위치를 생성자 매개변수로 지정합니다.
- “ 왼쪽 ”는 루트 노드의 왼쪽 위치를 의미하고 “ 왼쪽.왼쪽 ” 위치는 왼쪽 또는 왼쪽을 의미합니다. '의 경우에도 동일한 접근 방식이 적용됩니다. 오른쪽 ' 그리고 ' 오른쪽 '.
- 마지막으로 “ 루트노드 '에 대한 주장으로 디스플레이리프노드() ' 기능.
생성된 출력은 리프 노드가 오른쪽에서 왼쪽 방향으로 인쇄되는 것을 보여줍니다.
이는 이진 트리의 모든 리프 노드를 원하는 방향으로 인쇄하는 것입니다.
결론
이진 트리의 모든 리프 노드를 인쇄하려면 트리 노드에 값을 생성하고 할당하는 임의의 클래스를 만듭니다. 다음으로, 위에서 아래로 계층 구조에서 트리의 단일 노드를 허용하는 임의 함수를 만듭니다. 이 함수에는 여러 개의 ' 만약에 ”인지 확인하는 조건 마디 ”는 비어 있지 않으며 “에 노드가 없습니다. 왼쪽 ' 그리고 ' 오른쪽 ” 방향이면 해당 노드는 “ 잎 ” 노드이며 콘솔에 표시됩니다. 이 가이드에서는 이진 트리의 모든 리프 노드를 왼쪽에서 오른쪽으로 또는 오른쪽에서 왼쪽 방향으로 인쇄하는 절차를 설명했습니다.