1.树的概念及结构

1.1树的概念

树是一种非线性的数据结构，是由n个有限结点组成的一个具有层次关系的集合。

之所以称其为树，是因为它像一颗倒挂的树

形状：根朝上，叶朝下

具有一个特殊的节点——根节点

剩余的结点被分为n个互不相交的集合，每个集合又是类似树的结构，称为子树

树是由递归定义的

**子树之间不能有交集**

1.2树的相关概念

节点的度：一个节点所含有的子树的个数 如上图D的为3

叶节点（终端节点）：度为0的节点 如上图 F,G,H,I,J

分支节点（非终端节点）：度不为0的节点 如上图 B,C,D,E

父节点（双亲节点）：若某个节点含有至少一个子节点，则这个节点称作子节点的父节点 如上图 E是J的父节点

子节点（孩子节点）：某个节点含有的子树的根节点称作该节点的子节点 如上图J是E的子节点

亲兄弟节点：具有相同父节点的节点互称为兄弟节点 如上图 E和F

堂兄弟节点：双亲在同一层的节点互称为堂兄弟 如上图I和J

树的度：一颗树中，最大的节点的度称为树的度 如上图中，树的度为3

节点的层次：从根开始，根为第一层，根的子节点为第二层，以此类推

树的高度（深度）：树中节点的最大层次 如上图树的高度为4

节点的祖先：从根到该节点所经分支上的所有节点 如上图节点的祖先为A

子孙：以某节点为根的子树中任意节点都称为该节点的子孙 如上图 所有节点都是A的子孙

森林：由n棵互不相交的树所组成的集合称为森林

1.3树的表示

树结构既要保存数值，也要保存节点和节点之间的关系

树的最常见的表示方式为

左孩子右兄弟表示法：

父亲指向左边第一个孩子

孩子之间用兄弟指针链接起来

typedef int Datatype;
struct Node
{
  struct Node* child;//第一个孩子节点
  struct Node* brother;//指向其兄弟的节点
  Datatype data;//节点中的数值
};

2.二叉树的概念及结构

2.1概念

一颗二叉树是节点的一个有限集合

由一个根节点加上两棵称为左子树和右子树组成二叉树

可能为空

特点

二叉树不存在度大于2的节点

二叉树的子树由左右之分，次序不能颠倒，有序

任意二叉树都是由下面几种情况所组成的

2.2特殊的二叉树

满二叉树：二叉树如果每层的节点数都达到最大值，则这个二叉树为满二叉树；如果满二叉树的的层数为K，则节点总数为2^K-1

完全二叉树：完全二叉树的效率很高，是由满二叉树引出来的；对于深度为K，具有n个节点的二叉树，当且仅当其每个节点都与深度为K的满二叉树中从编号1到n的节点一一对应时，则称之为完全二叉树。满二叉树是一种特殊的完全二叉树

前k-1层都是满的，最后一层满或者不满都可以，从左到右要求连续，节点数量范围 [2^(k-1) , 2^k-1]

2.3二叉树的性质

若根节点的层数为1，则一颗非空二叉树的第i层上最多有2^(i-1)个节点

若根节点的层数为1，则深度为h的二叉树的最大节点数为2^h-1（等比数列求和）

对任意一颗二叉树，如果度为0的叶节点个数为n0，度为2的分支节点个数为n2，则存在公式 n0 = n2 + 1

若根节点的层数为1，具有n个节点的满二叉树的深度为 h=log(n+1)

对于具有n个节点的完全二叉树，若按照从上到下从左至右的数组顺序给所有节点从0开始编号，则对于编号为i的节点有

1.若 i>0，i节点的双亲编号：（i-1)/2 ; i=0,i为根节点，无双亲节点

2.若 2i+1<n , 左孩子；2i+1，2i+1>=n 无左孩子

3.若 2i+2<n，右孩子；2i+2，2i+2>=n 无右孩子

2.4二叉树的存储结构

二叉树一般使用两种结构进行存储：顺序结构,链式结构

顺序结构

顺序结构存储就是使用数组进行存储，一般数组只适合表示完全二叉树，否则会有空间的浪费。二叉树顺序结构的存储在物理上是一个数组，在逻辑上是一颗二叉树。

数组下标计算父子关系公式

leftchild = parent*2+1  奇数
rightchild = parent*2+2  偶数

链式存储

二叉树的链式存储结构：用链表来表示一颗二叉树，即用链表来指示元素的逻辑关系。一般的方法是链表中每个结点都由三部分组成：数据和左右指针，左右指针分别用来给出该节点左孩子和右孩子所在链表的节点的存储地址。

3.二叉树的顺序结构及实现

3.1二叉树的顺序结构

一般的二叉树不适合用数组来存储，可能会存在大量的空间浪费。完全二叉树比较适合使用顺序结构存储。

3.2堆的概念及结构

堆可以被看作一棵完全二叉树的数组对象

堆是一个一维数组，把它所有元素（a0,a1,a2…an-1)按完全二叉树的顺序存储方式存储在堆中，并满足：ai<=a2i+1 且 ai<=a2i+2 (或 ai>=a2i+1 且 ai>=a2i+2) i=0,i=1…,则称为小堆（或大堆）。

将根节点最大的堆称作大根堆，根节点最小的堆称作小根堆。

根的性质

堆中某个节点的值总是大于或小于其父节点

堆总是一颗完全二叉树

3.3堆的实现

3.3.1堆向下调整算法

给定某个数组，逻辑上看作一个完全二叉树。通过从根节点开始的向下调整算法可以把它调整为大堆。

左右子树必须是同样的堆（大根堆或者小根堆），才能调整

int a = {9,3,2,6,5,10};

向下调整

3.3.2堆的创建

给定一个数组，在逻辑结构上可以看作一颗完全二叉树（还不是堆），通过算法，将其构建成堆。

思路：从倒数的第一个非叶子节点的子树开始调整，一直调整到根节点，直到符合堆的特点

3.3.3建堆时间复杂度

因为堆是完全二叉树，满二叉树也是完全二叉树，为了方便，使用满二叉树进行计算时间复杂度

向下调整算法

需要移动节点的总次数

T(n)=2^0*(h-1) + 2^1*(h-2) + 2^2*(h-3) +…+ 2^(h-2)*1

计算可得

T(n) = 2^h -1 - h

n = 2^h - 1 h = log(n+1)

T(n) = n - log(n+1) = n

所以：建堆的时间复杂度为O(N)

3.3.4堆的插入

假设插入一个2到数组的末尾，再进行向上调整算法，直到构建成堆

将元素插入到堆的末尾，成为最后一个孩子

插入之后如果不满足堆的定义，将新插入的元素，顺着其双亲向上调整即可

3.3.5堆的删除

删除堆是删除堆顶的数据，将堆顶的数据和最后一个数据进行交换，然后删除数组最后一个数据，再进行向下调整。

思路

1. 堆顶元素与堆最后一个元素进行交换
2. 删除堆最后一个元素
3. 将堆顶元素向下调整到适当位置，构建出新的堆