이진 검색 트리의 "내부 노드"란 무엇입니까?

"내부 노드"라는 용어의 정의를 인터넷으로 수색하고 있습니다. 간결한 정의를 찾을 수 없습니다. 내가보고있는 모든 소스는 정의하지 않고 용어를 사용하며, 사용법은 내부 노드가 실제로 무엇인지에 대한 적절한 정의를 산출하지 못한다.이진 검색 트리의 "내부 노드"란 무엇입니까?

여기서 주로보고있는 두 곳의 위치는 다음과 같습니다. http://planetmath.org/encyclopedia/ExternalNode.html은 내부 노드가 null이 아닌 두 개의 하위 트리가 있고 원래 트리의 노드가 내부 대 외부 노드라고 가정하지 않는다고 가정합니다. .

http://www.math.bas.bg/~nkirov/2008/NETB201/slides/ch06/ch06-2.html은 내부 노드가 적절한 이진 트리에만 존재하며 그 노드에 대한 유용한 정보를 제공하지 않는다는 것을 암시하는 것처럼 보입니다.

실제로 은 내부 노드입니다!?

출처

2008-11-05 evizaer

라고 자식 노드가있어 잎 노드 또는 루트와 리프 노드 사이의 중간 노드가 아닌 트리의 모든 노드 루트 노드입니다 내부 노드? –

 I   ROOT (root is also an INTERNAL NODE, unless it is leaf) 
/ \ 
    I  I  INTERNAL NODES 
/ /\ 
o  o o EXTERNAL NODES (or leaves)

훌륭한 그림처럼 내부 노드는 트리 루트와 잎 사이에있는 노드입니다. 루트가 트리의 유일한 노드를 제외하고는 내부 노드이기도합니다.

두 개의 자식이 있어야하는 내부 노드에 대한 사이트 중 하나에서 말하는 것은 내부 트리가 아닌 전체 바이너리 트리가되는 것입니다.

출처

2008-11-05 16:50:02

다이어그램에서 내부 노드 중 하나에 자식 하나만 만들 수 있습니까? 이것은 정의를 명확히하는 데 도움이 될 것입니다. –

멋진 - 이것은 현재 가장 높은 등급의 답변보다 훨씬 뛰어납니다. –

이것은 처음의 직관 이었지만 나는 교수와 책에 동의하지 않습니다. – evizaer

내가 이해하는 한, 잎이 아닌 노드입니다.

출처

2008-11-05 16:48:07 Alphager

그것은 내부 노드에 대한 나의 이해이기도합니다. 아마도 루트를 포함하지 않을 수도 있습니다. –

내부 노드는 루트를 제외합니다. –

내부 노드 나 내부 노드는 자식 노드 을 가지고 있으며, 따라서 잎 노드가 아닌 나무의 노드입니다. 루트와 사이의 중간 노드는 이고 리프 노드는 노드라고합니다.

자료 : http://en.wikipedia.org/wiki/Tree_data_structure

출처

2008-11-05 16:51:54 tvanfosson

+1 또한 루트는 내부 노드입니다. 유일한 시간은 루트가 내부가 아니라는 것입니다. 루트가되는 하나의 노드로 트리가 구성되어있을 때 (리프이므로 외부가됩니다). – Hengameh

일반적으로, 내부 노드는 잎 (자녀가없는 노드)가 아닌 임의의 노드입니다.

확장 된 이진 트리 (비교 트리)에서는 각 내부 노드가 비교되어야하기 때문에 내부 노드는 모두 두 개의 자식이 있습니다 [TAoCP (Art of Computer Programming) vol.3 정렬 및 검색, 토론 및 5.3.1, p.181 (ed.2)의 그림. 그런데 제거 토너먼트에 대한 페어링 (및 바이)을 나타 내기 위해이 나무를 사용하는 것은이 자료의 5.4.1 절에서 다루어집니다.]

Vinko의 다이어그램은 루트 노드가 항상 이러한 구분을 반영하지만 내부 노드 또는 리프 노드뿐만 아니라 부모가없는 유일한 노드입니다.

크 누스가 나무의 정보 구조와 속성을 다루는 데있어 폭 넓은 토론이 있습니다 [TAoCP vol.1 Fundamental Algorithms, 2.3.4.5 절의 나무에서 길의 길이에 대한 설명, p. 399-406 (ed.3), 연습 문제 포함).

내부 노드가 단일 값과 최대 두 개의 자식을 갖는 바이너리 검색 트리가 다소 다릅니다 [TAoCP vol.3, section 6.2.2]. 그래도 명명법은 작동합니다.

출처

2008-11-05 23:40:10 orcmid

철저한 개요 및 출처를 철저히 조사해 주셔서 감사합니다! 그러므로 +1. –

하나 이상의 자식이있는 노드입니다.

출처

2008-12-04 04:29:41 Rich

내부 노드에 루트가 포함되어 있지 않습니다. 그리고 용어로 완전한 이진 트리는 각 내부 노드가 정확히 2 개의 노드를 가져야한다고 알려줍니다. 그러나 간단한 이진 트리에서 각 내부 노드는 최대 2 개의 노드를 갖습니다. 즉, 2 개 이상의 노드를 포함 할 수는 없지만 2는 허용되지 않습니다.

출처

2010-03-10 16:43:57 suraj

이진 트리는 0 개, 하나의 노드를 가질 수 있으며 최대 두 개의 노드를 가질 수 있습니다. 이진 트리는 자체적으로 왼쪽 노드와 오른쪽 노드를 가지고 있습니다.

출처

2010-11-25 08:15:53