二叉树(一)——基础

数据结构可基于数组或链表实现,就其效率而言,二者各有长短。具体来说,前一实现方式允许我们通过下标或者秩,在常数的时间内找到目标对象;然而,一旦需要对这类结构进行修改,那么无论是插入还是删除,都需要耗费线性的时间。反之,后一实现方式允许我们借助引用或位置对象,在常数的时间内插入或删除元素;但是为了找到居于特定次序的元素,我们却不得不花费线性的时间,对整个结构进行便利查找。能够将这两个结构的有点结合起来,并回避其不足呢?本系列所要讨论的树结构,将正面回答这一问题。

有趣的是,作为树的特例,二叉树实际上并不失一般性。无论就逻辑结构还是算法功能而言,任何有根有序的多叉树,都可等价地转化并实现为二叉树。

从图论的角度看,树等价与连通无环图。沿每个节点v到根root的唯一路径所经过的数目,称作v的深度。依据深度排序,可对所有节点做分层归类。特别地,约定根节点的深度为0,故属于第0层。

任一节点v在通往根节点所经过的每个节点都是祖先(ancestor),v是它们的后代(descendant)。特别的,v的祖先/后代包括其本身,而v本身以外的祖先/后代称作真祖先(proper ancestor)/真后代(proper descendant)。

无孩子的节点称作叶节点(leaf),包括根在内的其余节点皆为内部节点(internal node)。

树T中所有节点深度的最大值为该树的高度。特别地,仅含单个节点的树的高度为0,空树高度为-1。