什么是“内部节点”在二叉搜索树中？ [英] What is an "internal node" in a binary search tree?

问题描述

我在为内部节点这个术语的定义进行了互联网的淘汰。我找不到简洁的定义。我所看到的每一个源都使用这个术语而不定义它，而且使用率并不能正确地定义内部节点实际上是什么。

I'm scouring the internet for a definition of the term "Internal Node." I cannot find a succinct definition. Every source I'm looking at uses the term without defining it, and the usage doesn't yield a proper definition of what an internal node actually is.

这里是我主要看过两个地方：
http://planetmath.org/encyclopedia/ExternalNode。 html 假定内部节点是具有两个不为空的子树的节点，但不说原始树中的节点是内部的还是外部的。

Here are the two places I've been mainly looking: http://planetmath.org/encyclopedia/ExternalNode.html assumes that internal nodes are nodes that have two subtrees that aren't null, but doesn't say what nodes in the original tree are internal vs. external.

http://www.math.bas.bg/~nkirov/2008/NETB201/slides/ch06/ch06-2.html 似乎暗示内部节点只存在于

http://www.math.bas.bg/~nkirov/2008/NETB201/slides/ch06/ch06-2.html seems to insinuate that internal nodes only exist in proper binary trees and doesn't yield much useful information about them.

实际上是一个内部节点！

What actually is an internal node!?

推荐答案

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

如图所示，内部节点是位于树根和叶子之间的节点。请注意，root也是一个内部节点，除非是树的唯一节点。

As the wonderful picture shows, internal nodes are nodes located between the root of the tree and the leaves. Note that the root is also an internal node except in the case it's the only node of the tree.

在其中一个站点上有关于内部节点的说明必须有两个孩子是为树做一个完整的二叉树，不是为了节点内部。

What is said in one of the sites about an internal node having to have two children is for the tree to be a complete binary tree, not for the node to be internal.

这篇关于什么是“内部节点”在二叉搜索树中？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！