综合编程

[disambiguation系列 之二] 二叉树:complete和full

微信扫一扫,分享到朋友圈

[disambiguation系列 之二] 二叉树:complete和full
0

二叉树(binary tree)是一种数据结构,它有唯一的根节点,并且每个节点都有0个,1个或者2个子节点。它的(至多)两个子节点被区分为左子节点和右子节点。

为了更准确地讨论二叉树的性质,我们在二叉树中定义节点的深度(depth)和子树/节点的高度(height)的概念。

[定义: 深度
高度
] 对二叉树中的任意一个节点,我们递归地定义它的深度为:

  • 根节点的深度为0;
  • 一个非根节点的深度为其父节点深度加1。

基于深度的概念,我们可以定义二叉树的高度:

  • 一棵二叉树的高度就是该树中节点深度的最大值;
  • 一个节点的高度我们定义为以该节点为根的子树的高度。

基于节点深度的概念,我们经常将所有节点分层(level):所有深度为k的节点被称之为 第k层

的节点。

有多种特殊结构的二叉树在算法设计与分析中应用广泛,我们需要把它们明确定义出来。这主要包括完全二叉树(complete binary tree)和满二叉树(full binary tree)这两个概念。注意到这两个概念在形成过程中产生了一些歧义,不同文献中这些概念的含义有时会有不同。为此这里我们采用一套无歧义的术语来定义各种类型的二叉树,并且我们会基于我们的定义说明完全二叉树和满二叉树的常见含义。

[定义: 2-tree
] 我们称一棵二叉树为2-tree,如果它的每个节点的子节点个数均为2或者0。我们将子节点数为2的节点称为内部节点(internal node),将子节点数为0的节点成为外部节点(external node)。

一般 满二叉树
(full binary tree)的概念就是指2-tree。

[定义: 完美二叉树
] 我们称一棵二叉树为完美二叉树,如果它是一棵2-tree,且所有叶节点的深度相同。

[定义: 堆结构
] 我们称一棵二叉树满足“堆结构”这一性质如果:它是完美二叉树;或者它仅比一棵完美二叉树在最底层(深度最大的层)少若干节点,并且最底层的节点从左向右依次排列。

完全二叉树(complete binary tree)有时候指完美二叉树,有时候指具有堆结构特性的二叉树。

阅读原文...


Avatar

IT Security Risk Control Management: An Audit Preparation Plan - PUBLISHED!

上一篇

JuliaCon 2016

下一篇

您也可能喜欢

评论已经被关闭。

插入图片
[disambiguation系列 之二] 二叉树:complete和full

长按储存图像,分享给朋友