二叉树与堆

目录

• 树
  • 树的定义
  • 树的相关概念
  • 树的表示
  • 树的应用
• 二叉树
  • 二叉树的定义
  • 二叉树特点
  • 二叉树性质
  • 二叉树的存储结构
• 堆

树

树的定义

树是一种数据结构，树结构只有一个根节点，除根节点外，其余节点被分成M(M>0) 个互不相交的集合T1,T2,T3,......,Tm. 其中每一个集合Ti(1 < i < m)又是一颗与树结构类似的子树。每个子树的根节点有且只有一个前驱，可以有0个或多个后继。因此，树是递归定义的。
如图是一颗树结构：

由于树结构只有一个前驱，所以树结构不能出现交叉，如下不是一棵树结构

这种结构称为树结构是因为它像生活中倒着的树：

树的相关概念

节点的度：一个节点含有子树的个数成为节点的度；(上图，B节点的度为3)
叶节点或终端节点：度为0的节点称为叶节点或终端节点；(一般称叶节点，上图H节点是叶节点)
非终端节点或分支节点：度不为零的节点；（上图的非叶节点都是)
双亲结点或父节点：若一个节点含有一个子节点，则这个节点称为其子节点的父节点；(树中父节点只有一个，子节点可以有很多个;上图A节点是B节点的父节点)
孩子节点或子节点：一个节点的子树的根节点称为该点的子节点；(上图K节点是F节点的子节点)
兄弟节点：具有相同父节点的子节点互称兄弟节点；(上图H,I,J互称兄弟节点)
树的度：一棵树中度最大的节点的度称为树的度；(上图树的度为6)
节点的层次：从根节点开始，根节点为第一层，其子树一层为第二层，以此类推；(有些地方根节点从第0层开始计数)
树的高度或深度：树中节点的最大层数；(根节点从1开始计数，上图树的高度为4)
堂兄弟节点：双亲在同一层的节点互称堂兄弟；(上图J和K互称堂兄弟)
节点的祖先：从根到该节点所经分支上的所有节点；(父节点也是祖先节点)
子孙节点：以某节点为根的子树中任一节点都称该节点的子孙节点；
森林：由m(m > 0)棵互不相交的树的集合称为森林；(一棵树也可以构成森林)

树的节点个数 m(m ≥ 0)，当节点数=0时，树为空树

树的表示

树的表示由很多种方法，如双亲表示法，孩子表示法，双亲孩子表示法和孩子兄弟表示法等，这里介绍比较优秀的孩子兄弟表示法。

typedef int DateType;
struct Node
{
    struct Node* first_child;//指向第一个孩子节点
    struct Node* next_brother;//指向下一个兄弟节点
    DateType date;
}

孩子兄弟表示法是一种简洁的表示法，表示方法为：

如左边那棵树，它的孩子兄弟表示法如右边表示。

树的应用

树在实际中的应用有作为计算机系统的文件系统的目录：

如上图为Linux系统的文件目录，它也是树结构。

二叉树

二叉树的定义

二叉树也是一种树，它的每个节点的度m(0≤m≤2)，二叉树的度不能超过2。二叉树可以为空。

二叉树特点

二叉树有左右之分，不能颠倒，因此二叉树是有序树。
满二叉树：一个二叉树每一层节点都到达最大值，那么这棵树就是满二叉树。(若一颗二叉树高度为h，节点数为 2^h - 1 则这棵二叉树是满二叉树)

完全二叉树:若二叉树有n个节点，给每个节点按行从根节点依次连续编号，完全二叉树编号与满二叉树1到n个节点编号完全对应，则称此树为完全二叉树。(满二叉树是特殊的完全二叉树)

二叉树性质

1.若规定根节点层数为1，则一颗非空二叉树第h层最多有2^(h-1)个节点。
2.若规定根节点层数为1，则深度为h的二叉树的最大节点数是2^h - 1。
3.对任何一颗二叉树，如果度为0的节点个数为n₀,度为2的节点个数为n₂,则有n₀ = n₂ + 1.
4.若规定根节点的层数为1，具有n个节点的满二叉树的深度，h = log₂(n + 1)。
5.对于具有n个节点的完全二叉树，如果按照从上至下从左至右的数组顺序对所有节点从0开始编号，则对于序号为i的节点有：

1.若i > 0,i位置节点的双亲序号：(i - 1) / 2; i = 0,i为根节点编号，无双亲节点
2.若2i+1<n,2i+1为编号i节点的左孩子序号；2i+1≥n,则i节点无左孩子
3.若2i+2<n,2i+2为编号i节点的右孩子序号；2i+2≥n,则i节点无右孩子

二叉树的存储结构

二叉树一般有两种存储结构，一种顺序结构，一种链式结构

1. 顺序存储
   顺序结构存储就是使用数组存储，一般使用数组只适合表示完全二叉树，因为不是完全二叉树会有空间浪费。一般只有堆用数组来存储。二叉树顺序存储在物理上是一个数组，在逻辑上是一棵二叉树。
   

2. 链式存储
   二叉树的链式存储结构是指用链表来表示一棵二叉树，用链来指示元素的逻辑关系。通常方法是链表中每个节点由三个域组成，数据域和左右指针域，左右指针用来给出该节点左孩子和右孩子所在的链节点的存储地址。链式结构分为二叉链和三叉链。
   

   typedef int BTDataType;
   //二叉链
   struct BinaryTreeNode
   {
       struct BinaryTreeNode *lChild;
       struct BinaryTreeNode *rChild;
       BTDataType Data;
   }
    
   //三叉链
   struct BinaryTreeNode
   {
       struct BinaryTreeNode *parent;
       struct BinaryTreeNode *lChild;
       struct BinaryTreeNode *rChild;
       BTDataType Data;
   }

堆

这里所说的堆是一种数据结构，它不同于堆栈区所谓的堆，上面说了，堆是一种二叉树形式，它存储形式是顺序存储，逻辑上又是二叉树形式。堆有大堆和小堆。大堆就是任何节点它的父节点数据都大于孩子节点。小堆反之。
堆在存储结构上看与数组没有区别，但它在逻辑上是一棵所有节点的数据都大于(大堆)或小于(小堆)孩子节点的特殊二叉树。将一个堆从零建起来需要用到之前提到的一些二叉树的父节点与孩子节点之间的关系，建起一个小堆，每向堆尾插入数据，都需要向上调整一次；若父节点数据大于孩子节点，则需要交换父节点与子节点的数据，若不大于则停止调整，这个过程就是向上调整。

将上面的数组建为一个小堆，如：

将数据一个一个插入堆中，向上调整，最终建好的堆为：

建堆需要实现的函数有：

//Heap.h:
typedef int DataType;
typedef struct Heap
{
	size_t size;
	DataType* a;
	size_t capacity;
}heap;
 
void HeapInit(heap* hp);//初始化堆
void HeapPush(heap* hp, DataType x);//入堆
void AdjustUp(heap* hp, size_t child);//向上调整
void BuySpace(heap* hp);//申请空间
void Swap(DataType* x, DataType* y);//交换值
void HeapPrint(heap* hp);//打印堆
void AdjustDown(heap* hp, size_t parent);//向上调整
void HeapInsert(heap* hp, DataType x, size_t pos);//向堆任意位置插入值

上述函数有些不是必须，如AdjustDown()，若只是建堆，没有其他作用则此函数用处不大，该函数主要用在堆排序中。
建堆的主要函数实现：

void AdjustUp(heap* hp,size_t child)
{
	assert(hp);
	size_t parent = (child - 1) / 2;
	while (child != 0)
	{
		if (hp->a[child] < hp->a[parent])
			Swap(hp->a + child, hp->a + parent);
		child = parent;
		parent = (child - 1) / 2;
	}
}