第五章——树与二叉树

~ 树是n（n≥0）个结点的有限集合，n = 0时，称为空树，这是一种特殊情况。在任意一棵非空树中应满足：
1）有且仅有一个特定的称为根的结点。
2）当n > 1时，其余结点可分为m（m > 0）个互不相交的有限集合T1, T2,…, Tm，其中每个集合本身又是一棵树，并且称为根结点的子树。

空树——结点数为0的树
非空树的特性：

结点的层次（深度）——从上往下数
结点的高度——从下往上数
树的高度（深度）——总共多少层
结点的度——有几个孩子（分支）
树的度——各结点的度的最大值
有序树——逻辑上看，树中结点的各子树从左至右是有次序的，不能互换
无序树——逻辑上看，树中结点的各子树从左至右是无次序的，可以互换
森林：森林是m（m≥0）棵互不相交的树的集合
考点：森林和树相互转化问题

常见考点1：结点数=总度数+1
结点的度——结点有几个孩子（分支）
常见考点2：度为m的树、m叉树 的区别

常见考点3：度为m的树第 i 层至多有 m的i次方-1 个结点（i≥1）
m叉树第 i 层至多有 mi-1 个结点（i≥1）

常见考点6：具有n个结点的m叉树的最小高度为 【logm(n(m - 1) + 1)】

二叉树是n（n≥0）个结点的有限集合：
① 或者为空二叉树，即n = 0。
② 或者由一个根结点和两个互不相交的被称为根的左子树和右子树组成。左子树和右子树又分别是一棵二叉树。
特点：①每个结点至多只有两棵子树 ②左右子树不能颠倒（二叉树是有序树）

满二叉树：一棵高度为h，且含有2h - 1个结点的二叉树
特点：
①只有最后一层有叶子结点
②不存在度为 1 的结点
③按层序从 1 开始编号，结点 i 的左孩子为 2i，右孩子为 2i+1；结点 i 的父节点为【i/2】（如果有的话）

完全二叉树：当且仅当其每个结点都与高度为h的满二叉树中编号为1～n的结点一一对应时，称为完全二叉树。
特点：
①只有最后两层可能有叶子结点
②最多只有一个度为1的结点
③按层序从 1 开始编号，结点 i 的左孩子为 2i，右孩子为 2i+1；结点 i 的父节点为【i/2】（如果有的话）
④ i≤ n/2 为分支结点， i> n/2 为叶子结点
完全二叉树：如果某结点只有一个孩子，那么一定是左孩子，若只有右孩子，而没有左孩子，那么，则不为完全二叉树。
二叉排序树。一棵二叉树或者是空二叉树，或者是具有如下性质的二叉树：
左子树上所有结点的关键字均小于根结点的关键字；
右子树上所有结点的关键字均大于根结点的关键字。
左子树和右子树又各是一棵二叉排序树。
左子树和右子树又各是一棵二叉排序树。

常见考点1：设非空二叉树中度为0、1和2的结点个数分别为n0、n1和n2，则 n0 = n2 + 1
（叶子结点比二分支结点多一个）
假设树中结点总数为 n，则
① n = n0 + n1 + n2
② n = n1 + 2n2 +1（树的结点数=总度数+1 ）
② - ①：n0 = n2 + 1
常见考点2：二叉树第 i 层至多有 2的i-1次方个结点（i≥1）
m叉树第 i 层至多有 m的i-1次方个结点（i≥1）
常见考点3：高度为h的二叉树至多有 2的ℎ次方 − 1个结点（满二叉树）

常见考点1：具有n个（n > 0）结点的完全二叉树的高度h。
高为 h 的满二叉树共有 2的ℎ次方 − 1 个结点
高为 h-1 的满二叉树共有 2的h-1次方− 1个结点
常见考点2：对于完全二叉树，可以由的结点数 n 推出度为0、1和2的结点个数为n0、n1和n2
完全二叉树最多只有一个度为1的结点，即n1=0或1
n0 = n2 + 1→n0 + n2 一定是奇数
若完全二叉树有2k个（偶数）个结点，则必有 n1=1， n0 = k， n2 = k-1
若完全二叉树有2k-1个（奇数）个结点，则必有 n1=0， n0 = k， n2 = k-1

二叉树：
• n0 = n2 + 1
• 第 i 层至多有 2i-1 个结点（i≥1）
• 高度为h的二叉树至多有 2ℎ − 1个结点
完全二叉树：
• 具有n个（n > 0）结点的完全二叉树的高度h为log2(n + 1)或log2n+ 1
• 对于完全二叉树，可以由的结点数 n 推出为0、1和2的结点个数为n0、n1
和n2（突破点：完全二叉树最多只会有一个度为1的结点）

先序遍历（PreOrder）的操作过程如下：

中序遍历（InOrder）的操作过程如下：

后序遍历（InOrder）的操作过程如下：

算法思想：
①初始化一个辅助队列
②根结点入队
③若队列非空，则队头结点出队，访问该结点，并将其左、右孩子插入队尾（如果有的话）
④重复③直至队列为空

重要考点

树是n（n≥0）个结点的有限集合，n = 0时，称为空树，这是一种特殊情况。在任意一棵非
空树中应满足：
1）有且仅有一个特定的称为根的结点。
2）当n > 1时，其余结点可分为m（m > 0）个互不相交的有限集合T1, T2,…, Tm，其中每个集合本身又是一棵树，并且称为根结点的子树。

将树转化为二叉树，左孩子右兄弟

将树转化为二叉树，左孩子右兄弟。

先根遍历。若树非空，先访问根结点，再依次对每棵子树进行先根遍历。

后根遍历。若树非空，先依次对每棵子树进行后根遍历，最后再访问根结点。

层次遍历（用队列实现）
①若树非空，则根节点入队
②若队列非空，队头元素出队并访问，同时将该元素的孩子依次入队
③重复②直到队列为空

先序遍历森林。
若森林为非空，则按如下规则进行遍历：
访问森林中第一棵树的根结点。
先序遍历第一棵树中根结点的子树森林。
先序遍历除去第一棵树之后剩余的树构成的森林。

中序遍历森林。
若森林为非空，则按如下规则进行遍历：
中序遍历森林中第一棵树的根结点的子树森林。
访问第一棵树的根结点。
中序遍历除去第一棵树之后剩余的树构成的森林。

二叉排序树，又称二叉查找树（BST，Binary Search Tree）
一棵二叉树或者是空二叉树，或者是具有如下性质的二叉树：
左子树上所有结点的关键字均小于根结点的关键字；
右子树上所有结点的关键字均大于根结点的关键字。
左子树和右子树又各是一棵二叉排序树。

平衡二叉树——树上任一结点的左子树和右子树的深度之差不超过1。
查找长度——在查找运算中，需要对比关键字的次数称为查找长度。

每次调整的对象都是“最小不平衡子树”

1）LL平衡旋转（右单旋转）。

由于在结点A的左孩子（L）的左子树（L）上插入了新结点，A的平衡因子由1增至2，导致以A为根的子树失去平衡，需要一次向右的旋转操作。将A的左孩子B向右上旋转代替A成为根结点，将A结点向右下旋转成为B的右子树的根结点，而B的原右子树则作为A结点的左子树。
2）RR平衡旋转（左单旋转）。

由于在A的左孩子（L）的右子树（R）上插入新结点，A的平衡因子由1增至2，导致以A为根的子树失去平衡，需要进行两次旋转操作，先左旋转后右旋转。先将A结点的左孩子B的右子树的根结点C向左上旋转提升到B结点的位置，然后再把该C结点向右上旋转提升到A结点的位置
4）RL平衡旋转（先右后左双旋转）。

给定n个权值分别为w1, w2,…, wn的结点，构造哈夫曼树的算法描述如下：
1）将这n个结点分别作为n棵仅含一个结点的二叉树，构成森林F。
2）构造一个新结点，从F中选取两棵根结点权值最小的树作为新结点的左、右子树，并且将新
结点的权值置为左、右子树上根结点的权值之和。
3）从F中删除刚才选出的两棵树，同时将新得到的树加入F中。
4）重复步骤2）和3），直至F中只剩下一棵树为止。

固定长度编码——每个字符用相等长度的二进制位表示

二叉树是一种特殊的树吗?
答：树和二叉树的2个主要差别：1、树中结点的最大度数没有限制，而二叉树结点的最大度数为2；2、树的结点无左、右之分，而二叉树的结点有左、右之分。……注意：尽管二叉树与树有许多相似之处，但二叉树不是树的特殊情形。一棵深度为k，且有2^k-1个结点的二叉树，称为满二叉树。这种树的特点是...

什么是二叉树,举一个二叉树的例子
答：树是一种重要的非线性数据结构，直观地看，它是数据元素（在树中称为结点）按分支关系组织起来的结构，很象自然界中的树那样。树结构在客观世界中广泛存在，如人类社会的族谱和各种社会组织机构都可用树形象表示。树在计算机领域中也得到广泛应用，如在编译源程序如下时，可用树表示源源程序如下的语法...

数据结构大学计算机必学非线性结构
答：二叉树是树的特殊一种,具有如下特点:·每个结点最多有两颗子结点。·左子树和右子树是有顺序的,次序不能颠倒。·即使某结点只有一个子树,也要区分左右子树。 散列表 散列表, 也叫哈希表, 是根据关键码和值(key和value) 直接进行访问的数据结构, 通过key和value 来映射到集合中的一个位置,这样就可以很快找到...

度为2的树和二叉树的区别 一个度为2的树和二叉树的区别
答：分支不同，度为2的树有两个分支，但分支没有左右之分；一棵二叉树也有两个分支，但有左右之分，左右子树的次序不能随意颠倒。次序不同，度为2的树从形式上看与二叉树很相似，但它的子树是无序的，而二叉树是有序的。即，在一般树中若某结点只有一个孩子，就无需区分其左右次序，而在二叉树中...

为什么树的后根遍历对应二叉树的中序遍历
答：1、先根遍历：先访问树的根节点，再依次先根遍历子树；2、后根遍历：先依次后根遍历子树，再访问树的根节点。因为树并不一定是二叉树，‘中’的概念不好定义，比如对于一个拥有3个子树的根节点来说，根节点除了先根和后根两种遍历方式之外还有另外两种次序。如一种次序是先遍历根节点的第一棵子树...

如何构造排序树和完全二叉树?
答：1.由同一关键字集合构造的各棵二叉排序树的形态，平均查找长度相同吗？为什么？对于含有同样一组结点的表，由于结点插入的先后次序不同，所构成的二叉排序树的形态和深度也可能不同。在二叉排序树上进行查找时的平均查找长度和二叉树的形态有关：①在最坏情况下，二叉排序树是通过把一个有序表的n个结点...

红黑树和二叉树的区别
答：1、红黑树放弃了追求完全平衡，追求大致平衡，在与平衡二叉树的时间复杂度相差不大的情况下，保证每次插入最多只需要三次旋转就能达到平衡，实现起来也更为简单。2、平衡二叉树追求绝对平衡，条件比较苛刻，实现起来比较麻烦，每次插入新节点之后需要旋转的次数不能预知。

二叉树和二叉树排序不同
答：⑨无序树：如果树中各棵子树的次序没有先后次序，则称该树为无序树[5] 。⑩森林：由m（m≥0）棵互不相交的树构成一片森林。如果把一棵非空的树的根结点删除，则该树就变成了一片森林，森林中的树由原来根结点的各棵子树构成[5] 。二叉树性质 性质1：二叉树的第i层上至多有2i-1（i≥1...

+20 c语言- (求)树,二叉树,二叉查找树区别和用他们做的C语言简单编成...
答：二叉树是指结点的度最大为2，也就是一个结点最多只有两个分支。二叉树与度为2的树的区别是二叉树是顺序树，即有严格的左右之分，而度为2的树却没有这种要求。二叉排序树是在二叉树的基础上面将小于结点的分支都放在该结点的左边，而大于该结点的分支都放在右边的树，这样很便于查找。我只给你写...

二叉树的五种形态分别是什么呢?
答：而且二叉树的存储结构及其算法都较为简单，因此二叉树显得特别重要。二叉树特点是每个节点最多只能有两棵子树，且有左右之分。二叉树是n个有限元素的集合，该集合或者为空、或者由一个称为根（root）的元素及两个不相交的、被分别称为左子树和右子树的二叉树组成，是有序树。当集合为空时，称该二叉...