【5.1】二叉树的概念

一、二叉树的定义

二叉树 (binary tree) 由结点的有限 集合构成

这个有限集合或者为空集 (empty),或者为由一个根结点 (root) 及两棵 互不相交、分别称作这个根的左子 树 (left subtree) 和右子树 (right subtree) 的二叉树组成的集合

二叉树的五种基本形态

二叉树可以是空集合,因此根可以有空的左子树或右子树,或 者左右子树皆为空

二叉树相关术语

结点:

  • 子结点、父结点、最左子结点
    • ∈ r,则称 k 是 k′ 的父结点(或“父 母”),而 k′ 则是 k 的 子结点 (或“儿子”、“子 女”)
  • 兄弟结点、左兄弟、右兄弟
    • 若有序对 ∈ r,则称 k′和 k′′ 互为兄弟
  • 分支结点、叶结点
    • 没有子树的结点称作 叶结点(或树叶、终端结点)
    • 非终端结点称为分支结点

边:两个结点的有序对,称作 边

路径、路径长度:

  • 除结点 k0外的任何结点 k∈K,都存在一个结点 序列 k0,k1,…,ks,使得 k0 就是树根,且 ks=k,其中有序对 ∈ r (1≤i≤s) 。 这样的结点序列称为从根到结点 k 的一条路径, 其路径长度为 s (包含的边数)

祖先、后代:

  • 若有一条由 k 到达 ks 的路径,则称 k 是 ks 的 祖先,ks 是 k 的 子孙

层数:根为第 0 层 D 。 其他结点的层数等于其父结点的层数加 1

深度:层数最大的叶结点的层数

高度:层数最大的叶结点的层数加 1

满二叉树

如果一棵二叉树的 任何 结点,或者是树叶,或者恰有两棵非空子树,则 此二叉树称作 满二叉树

完全二叉树

最多只有最下面的两层结点度数可以小于2

最下一层的结点都集中最左边

扩充二叉树

所有空子树,都增加空树叶

外部路径长度 E 和内部路径长度 I

* 满足:E = I + 2n (n 是内部结点个数)

二叉树的主要性质
  • 性质1. 在二叉树中,第i层上最多有 2i 个结点(i≥0)
  • 性质2. 深度为 k 的二叉树至多有 2k+1 -1个结点(k≥0), 其中深度(depth)定义为二叉树中层数最大的叶结点的层数
  • 性质3. 一棵二叉树,若其终端结点数为 n0,度为2的结点数为 n2, 则 n0=n2+1
  • 性质4. 满二叉树定理:非空满二叉树树叶数目等于其分支结点数加1
  • 性质5. 满二叉树定理推论:一个非空二叉树的空子树数目等于其结点数加1
  • 性质6. 有n个结点(n>0)的完全二叉树的高度为 [ log2 (n+1) ] ,深度为[log2 (n+1)] - 1

思考

  • 扩充二叉树和满二叉树的关系
  • 二叉树主要六个性质的关系

参考资料

北京大学 《数据结构与算法》 张铭、赵海燕、宋国杰、黄骏、邹磊、陈斌、王腾

个人公众号,比较懒,很少更新,可以在上面提问题,如果回复不及时,可发邮件给我: tiehan@sina.cn

Sam avatar
About Sam
专注生物信息 专注转化医学