数据结构课上笔记10

桃扇骨 2022-04-18 06:29 204阅读 0赞

# 树 #

树的定义：树(Tree)是 n(n≥0)个结点的有限集。若 n=0，称为空树；若 n > 0，则它满足如下两个条件：

(1) 有且仅有一个特定的称为根 (Root) 的结点；

(2) 其余结点可分为 m (m≥0) 个互不相交的有限集 T1, T2, T3, …, Tm， 其中每一个集合本身又是一棵树，并称为根的子树 (SubTree)。

显然，树的定义是一个递归的定义。

树的一些术语：

*  结点的度（Degree）：结点的子树个数；
 *  树的度：树的所有结点中最大的度数；
 *  叶结点（Leaf）：度为0的结点；
 *  父结点（Parent）：有子树的结点是其子树的根节点的父结点；
 *  子结点/孩子结点（Child）：若A结点是B结点的父结点，则称B结点是A结点的子结点；
 *  兄弟结点（Sibling）：具有同一个父结点的各结点彼此是兄弟结点；
 *  路径和路径长度：从结点n1到nk的路径为一个结点序列n1，n2，...，nk。ni是ni+1的父结点。路径所包含边的个数为路径的长度；
 *  祖先结点（Ancestor）：沿树根到某一结点路径上的所有结点都是这个结点的祖先结点；
 *  子孙结点（Descendant）：某一结点的子树中的所有结点是这个结点的子孙；
 *  结点的层次（Level）：规定根结点在1层，其他任一结点的层数是其父结点的层数加1；
 *  树的深度（Depth）：树中所有结点中的最大层次是这棵树的深度；

将树中节点的各子树看成从左至右是有次序的（即不能互换），则称为该树是**有序树**，否则称为**无序树**。

森林(forest)是 m (m≥0) 棵互不相交的树的集合。

#  #

# 二叉树 #

在计算机科学中，二叉树是每个结点最多有两个子树的树结构。通常子树被称作“左子树”（left subtree）和“右子树”（right subtree）。二叉树常被用于实现二叉查找树和二叉堆。

虽然二叉树与树概念不同，但有关树的基本术语对二叉树都适用。

二叉树结点的子树要区分左子树和右子树，即使只有一 棵子树也要进行区分，说明它是左子树，还是右子树。树当 结点只有一个孩子时，就无须区分它是左还是右。

注意：尽管二叉树与树有许多相似之处，但二叉树不是树的特殊情形。

一些性质：

在二叉树的第 i 层上至多有 ![2018110916563489.png][] 个结点 (i ≥1)。

证明：每个节点至多两个孩子，每一层至多比上一层多一倍的结点，根为1.

深度为 k 的二叉树至多有![20181109165849404.png][] 个结点（k ≥1)。

证明：把每一层最大节点加起来即可

对任何一棵二叉树 T，如果其叶子数为 n0，度为 2的结点数为 n2，则 n0 = n2 + 1。

证明：对于一个只有根的树，n0 = n2 + 1成立。1=0+1

我们把一个叶子节点换成度为2的结点：

![2018110917030729.png][]

黑色节点原来为叶子节点

我们发现，度为2的结点数加1（黑色节点）；叶子节点数加1（原来的去掉，新增两个）；对于式子n0 = n2 + 1没影响，还是成立。

我们把叶子节点换成度为1的结点，比如没有右孩子。

我们发现，度为2的结点数没变。叶子节点数没变（减了一个加了一个）

所以，不管你怎么换，公式都成立。（佛系证明）

[2018110916563489.png]: /images/20220418/3e5cbaf1cf1c4b8eb4ffa38307c1d1bf.png
[20181109165849404.png]: /images/20220418/2d4458712977493eaa5259568dc5d384.png
[2018110917030729.png]: /images/20220418/29372e99c5804d8fb251cd4c47690b81.png