DS冲刺整理做题定理（一）二叉树专题

（只总结博主自己记得不熟的~）?

• 数据结构是计算机存储、组织数据的方式。数据结构是指相互之间存在一种或多种特定关系的数据元素的集合。通常情况下，精心选择的数据结构可以带来更高的运行或者存储效率。数据结构往往同高效的检索算法和索引技术有关。
• 数据结构(data structure)是带有结构特性的数据元素的集合，它研究的是数据的逻辑结构和数据的物理结构以及它们之间的相互关系，并对这种结构定义相适应的运算，设计出相应的算法，并确保经过这些运算以后所得到的新结构仍保持原来的结构类型。简而言之，数据结构是相互之间存在一种或多种特定关系的数据元素的集合，即带“结构”的数据元素的集合。“结构”就是指数据元素之间存在的关系，分为逻辑结构和存储结构。
• 数据的逻辑结构和储存结构是数据结构的两个密切相关的方面，同一逻辑结构可以对应不同的存储结构。算法的设计取决于数据的逻辑结构，而算法的实现依赖于指定的存储结构。
• 数据结构的研究内容是构造复杂软件系统的基础，它的核心技术是分解与抽象。通过分解可以划分出数据的3个层次；再通过抽象，舍弃数据元素的具体内容，就得到逻辑结构。类似地，通过分解将处理要求划分成各种功能，再通过抽象舍弃实现细节，就得到运算的定义。上述两个方面的结合可以将问题变换为数据结构。这是一个从具体（即具体问题）到抽象（即数据结构）的过程。然后，通过增加对实现细节的考虑进一步得到存储结构和实现运算，从而完成设计任务。这是一个从抽象（即数据结构）到具体（即具体实现）的过程。

一.树的基础

1.度：结点所拥有的孩子结点的个数，树中结点的最大结点度数被称为树的度。

2.高度从下向上，深度自顶向下

3.树的节点数等于所有结点的度数之和+1

4.度为m的树中，第i层之至多有m^i-1个节点

5.高度为h的m叉树至多有（m^h-1)/(m-1)个节点

6.具有n个结点的m叉树的最小高度为[logm(n(m-1)+1)]

二.二叉树的概念

1.满二叉树：高度为h且含有2^h-1个节点的二叉树称为满二叉树,除了叶子节点度数均为2

2.完全二叉树：可以理解为满二叉树的顺序缩略版（序号不能间断~）

3.二叉排序树：左子树上所有节点的关键字均小于根节点的关键字，右子树均大于；此外，左子树和右子树又各是一棵二叉排序树

4.平衡二叉树：树上任意结点的左子树和右子树的深度之差不超过1~

5.叶子节点数：度为2的节点数+1

6.第k层至多有2^（k-1）个节点

7.高度为k的二叉树至多有2^k-1个节点

8.节点i所在的层次（深度）为（log2i）+1

（存储结构稍微看看就行，一般不是考察重点~）

三.树的遍历

1.NLR：先序遍历，根左右

2.LNR：中序遍历，左根右

3.LRN：后序遍历，左右根

（实现方式有递归和非递归两种~）

4.层次遍历：按最高层依次往下遍历~

5.线索二叉树：存放着额外的指针域，来存放左子树or右子树，亦或前驱或后继结点~

四.森林

1.双亲表示法：本质上用顺序结构来存储树的结点

2.孩子表示法：单链表

3.孩子兄弟表示法：本质为树和二叉树的转换~

五.应用?

1.哈夫曼树：又被叫做最优二叉树，即带权路径长度WPL最小的二叉树~

2.并查集：本质就是让某一棵树成为另一棵树的孩子~