更新时间:2022-10-18 08:22:59
一本书中的声明:离散数学及其应用 - 第7版Rosen说,
有孩子的顶点称为内部顶点。根是一个内部顶点,除非它是图中唯一的顶点,在这种情况下它是一个叶。
支持定理:
对于任何正整数n,如果T是具有n个内部顶点的完整二叉树,则T
具有n + 1个叶子和总共2n + 1个顶点。
案例1:
O / \
OO
案例2:平凡树
O
So I've looked around the web and a couple of questions here in *** here are the definition:
I was about to conclude that the root is also an internal node but there seems to be some ambiguity on its definition as seen here:
What is an "internal node" in a binary search tree?
If we follow that definition then the root node isn't going to be counted as an internal node. So is a root node an internal node or not?
Statement from a book : Discrete Mathematics and Its Applications - 7th edition By Rosen says,
Vertices that have children are called internal vertices. The root is an internal vertex unless it is the only vertex in the graph, in which case it is a leaf.
Supportive Theorem:
For any positive integer n, if T is a full binary tree with n internal vertices, then T has n + 1 leaves and a total of 2n + 1 vertices.
case 1:
O <- 1 internal node as well as root
/ \
O O <- 2 Leaf Nodes
case 2: Trivial Tree
O <- 0 internal vertices (no internal vertices) , this is leaf