数据结构之⑰二叉树

二叉树...



二叉树的定义

定义

二叉树是由n(n >= 0)个节点组成的有限集合，该集合或者为空，或者是由一个根结点加上两颗分别称为左子树和右子树的、互不相交的二叉树组成。

基本形态

二叉树具有五种基本形态：

• 空二叉树
• 只有一个根结点
• 根结点只有左子树
• 根结点只有右子树
• 根结点既有左子树又有右子树

特殊二叉树

满二叉树

如果二叉树中所有分支结点都存在左子树和右子树，且叶子结点都在用一层次上，则称这类二叉树为满二叉树

满二叉树的特点：

• 叶子结点只能出现在最下面一层
• 非叶子结点的度一定是2
• 在同样深度的二叉树中，满二叉树的结点个数，叶子结点个数最多

完全二叉树

如果一颗具有n个结点的高度为k的二叉树，如果高度为id结点与同样深度的满二叉树中编号为i的结点在二叉树中的位置完全相同，则称这颗二叉树为完全二叉树。

完全二叉树的特点：

• 叶子结点仅出现在最下面两层
• 同样结点数的二叉树，完全二叉树的高度最小

二叉树结构模型



孩子兄弟表示法

• 每个树结点包含一个数据指针和两个结点指针
[list]
• 数据指针：指向保存于书中的数据
• 孩子结点指针：指向第一个孩子
• 兄弟结点指针：指向第一个右兄弟

孩子兄弟表示法的特点

• 能够表示任意的数据结构
• 每个结点中有且仅有三个指针域

二叉树的性质

性质1

在二叉树的第i层中最多有2i - 1个结点。(i >= 1)

• 第一层最多有21 - 1 = 1个结点
• 第二层最多有22 - 1 = 2个结点
• 第三层最多有23 - 1 = 4个结点

性质2

深度为k的二叉树最多有2k - 1个结点 (k >= 0)

• 如果有一层，最多有1 = 21 - 1 = 1个结点
• 如果有二层，最多有1 + 2 = 22 - 1 = 3个结点
• 如果有三层，最多有1 + 2 + 4 = 23 - 1 = 7个结点

性质3

对任何一颗二叉树，如果其叶结点(度为0的结点)有n0个，度为2的结点有n2个，则有n0 = n2 + 1。

性质4

具有n个结点的完全二叉树的高度为[log2n] + 1。([x]表示不大于x的最大整数)

性质5

对一颗有n个结点的完全二叉树(高度为[log2n] + 1)的结点按按层次编号，对任意结点i有：

• 如果i = 1，则结点是二叉树的根
• 如果i > 1,则其双亲结点是[i / 2]
• 如果2in，则结点i无左孩子
• 2i + 1n，则结点i无右孩子

    关注 刘涤生