【5.1】二叉树的概念

一、二叉树的定义

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

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

二叉树的五种基本形态

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

二叉树相关术语

结点：

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

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

路径、路径长度：

• 除结点 k0外的任何结点 k∈K，都存在一个结点 序列 k0，k1，…，ks，使得 k0 就是树根，且 ks=k，其中有序对 <ki-1，ki>∈ 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层上最多有 2ⁱ 个结点(i≥0)
• 性质2. 深度为 k 的二叉树至多有 2^k+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

思考

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

参考资料

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