数据结构 -- 树和二叉树

树和二叉树

树的定义和基本术语

基本概念

树是n(n≥0)个结点的有限集。当n=0时，称为空树。在任意一棵非空树中应满足：

1)有且仅有一个特定的称为根的结点。

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

前驱和后继：C结点是G的前驱和A的后继，G结点是C的后继

空树：结点数为0的树

非空树的特性：有且只有一个根结点，且根结点没有前驱结点

没有后继的结点称为“叶子结点”（或终端结点）

有后继的结点（除根结点外）称为“分支结点”（或非终端结点）

除根结点外，其他结点有且只有一个前驱

（用于区分树和图）

树是一种递归定义的结构：任何一颗树都可以看成是由根结点和若干个互不相交的子树组成的

基本术语

节点之间的关系描述：

祖先结点：对于树中所有的非根结点来说，根结点就是祖先节点

子孙节点：对于根结点而言，所有非根结点都是它的子孙节点

双亲结点（父节点）：一个结点的直接前驱就是它的父节点

孩子结点：一个结点的直接后继就是它的孩子结点

兄弟结点：有着相同直接前驱的结点互为兄弟结点

堂兄弟结点：处于同一层的任意两个结点，如果不为兄弟节点关系，那么它们互为堂兄弟结点（使用频率很低）

两个节点之间的路径：（单向的，只能从上往下）树中两个结点之间的路径是由这两个结点之间所经过的结点序列构成的

路径长度：（经过几条边）路径上所经过的边的个数

结点、树的属性描述

层次（深度、从上往下数）：结点的层次默认从1开始，但是有时也会将根结点作为第0层

结点的高度（从下往上数）

树的高度（深度、一共多少层）

结点的度：树中一个结点的孩子个数称为该结点的度

树的度：树中结点的最大度数称为树的度

有序树VS无序树

有序树：逻辑上看，树中结点的各子树从左至右是有次序的，不能互换

无序树：逻辑上看，树中结点的各子树从左至右是无次序的，可以互换

树VS森林

森林是m(m≥0)棵互不相交的树的集合。森林的概念与树的概念十分相近，因为只要把树的根结点删去就成了森林。反之，只要给m棵独立的树加上一个结点，并把这m棵树作为该结点的子树，则森林就变成了树。

[考点]

森林和树的相互转换

树的常考性质

考点1：结点数 = 总度数 + 1

考点2：度为m的树、m叉树的区别

树的度 – 各节点的度的最大值 m叉树 – 每个节点最多只能有m个孩子的树

考点3：度为m的树第i层至多有m^i-1个结点(i≥1)，至少有i+m-1个

第1层至多有1个结点(根结点),第2层至多有m个结点，第3层至多有m2个结点，以此类推。使用数学归纳法可推出第i层至多有m^i-1个结点。

考点4：高度为h的m叉树至多有(m^h-1)/(m-1)个结点，最少有h个

考点5：度为m、具有n个结点的树的最小高度h为[logn(n(m-1)+1)]

高度最小的情况：所有结点都有m个孩子

二叉树

二叉树是一种特殊的树形结构，其特点是每个结点至多只有两棵子树(二叉树中不存在度大于2的结点),并且二叉树的子树有左右之分，其次序不能任意颠倒（二叉树是有序树）。

二叉树是n(n≥0)个结点的有限集合：

①或者为空二叉树，即n=0。

②或者由一个根结点和两个互不相交的被称为根的左子树和右子树组成。左子树和右子树

又分别是一棵二叉树。

二叉树的五种状态

①空二叉树 ②只有根节点 ③只有左子树 ④只有右子树 ⑤左右子树都有

几种特殊的二叉树：

①满二叉树

一颗高度为h，并含有2^h-1个结点的二叉树

特点：①只有最后一层有叶子结点 ②不存在度为1的结点

③按层序从1开始编号，结点i的左孩子为2i，右孩子为2i+1；i的父节点为[i/2]（如果有）

②完全二叉树

高度为h、有n个结点的二叉树，当且仅当其每个结点都与高度为h的满二叉树中编号为1~n的结点一一对应时，称为完全二叉树

特点：

①只有最后两层可能有叶子结点

②最多只有一个度为1的结点

③按层序从1开始编号，结点i的左孩子为2i，右孩子为2i+1；i的父节点为[i/2]（如果有）

④i ≤ [n/2]为分支节点，i > [n/2]为叶子结点

满二叉树是一种特殊的完全二叉树

③二叉排序树

一棵二叉树或空二叉树，并具有以下的性质：

①左子树上所有结点的关键字均小于根节点的关键字；

②右子树上所有结点的关键字均大于根结点的关键字；

③左子树和右子树又各是一棵二叉排序树。

④平衡二叉树

树中任意一个结点的左子树和右子树的高度之差的绝对值不超过1。

平衡二叉树具有更高的搜索效率

二叉树的常考性质

二叉树的常考性质

考点1：

设非空二叉树中度为0、1和2的结点个数分别是n0、n1和n2，则n0 = n2 + 1（叶子结点比二分支节点多一个）

假设树中结点总数为n，则

①n = n0 + n1 + n2

②n = n1 + 2n2 + 1

考点2：

非空二叉树的第k层最多有 2^(k-1) 个结点(k≥1)

考点3：

高度为h的二叉树至多有 2^h-1 个结点(h≥1)

完全二叉树的常考性质

考点1：

具有n个(n>0)结点的完全二叉树的高度为[log2(n+1)]或[log2n]+I

考点2：

对于完全二叉树，可以由结点数n推出度为0、1和2的结点个数为n0、n1和n2

完全二叉树最多只有一个度为1的结点，即n1 = 0或1

n0 = n2 + n1 → n0+n2一定是奇数

如果完全二叉树有2k个（偶数个）结点，则必有n1 = 1，n0 = k，n2 = k-1

如果完全二叉树有2k-1个（奇数个）结点，则必有n1 = 0，n0 = k，n2 = k-1