一.树及其相关概念

(1).树的介绍

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

树的特点 :
(1).有一个特殊的结点，称为根结点，根节点没有前驱结点
(2).除根节点外，其余结点被分成M(M>0)个互不相交的集合T1、T2、……、Tm，其中每一个集合Ti(1<= i <= m)又是一棵结构与树类似的子树。每棵子树的根结点有且只有一个前驱，可以有0个或多个后继,因此，树是递归定义的。

树的相关概念

节点的度：一个节点含有的子树的个数称为该节点的度； 如上图：A的为2

叶节点或终端节点：度为0的节点称为叶节点； 如上图：F,G,H,I,J 节点为叶节点

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

双亲节点或父节点：若一个节点含有子节点，则这个节点称为其子节点的父节点； 如上图：A是B的父节点

孩子节点或子节点：一个节点含有的子树的根节点称为该节点的子节点； 如上图：B是A的孩子节点

兄弟节点：具有相同父节点的节点互称为兄弟节点； 如上图：B、C是兄弟节点

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

节点的层次：从根开始定义起，根为第1层，根的子节点为第2层，以此类推；

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

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

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

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

森林：由m（m>0）棵互不相交的树的集合称为森林；

(2).树的表示

我们可以通过左孩子右兄弟的表示法来表示整个树

data域用来存储树结点的数据
child域指向该结点从左往右数的第一个孩子结点
brother域指向该结点从左往右数的第一个兄弟结点

由此画出上图的左孩子右兄弟的示意图

定义的结构体如下

typedef int DataType;
struct Node
{
 struct Node* _firstChild1; // 第一个孩子结点
 struct Node* _pNextBrother; // 指向其下一个兄弟结点
 DataType _data; // 结点中的数据域
};

二.二叉树概念及结构

(1).二叉树概念及特点

概念:
一棵二叉树是结点的一个有限集合，该集合或者为空，或者是由一个根节点加上两棵别称为左子树和右子树的二叉树组成

二叉树的特点：
(1). 每个结点最多有两棵子树，即二叉树不存在度大于2的结点。
(2). 二叉树的子树有左右之分，其子树的次序不能颠倒。

(2).特殊的二叉树

(1).满二叉树
如果每一个层的结点数都达到最大值，则这个二叉树就是满二叉树。也就是说，如果一个二叉树的层数为K，且结点总数是(2^k) -1 ，则它就是满二叉树。

(2). 完全二叉树
若一个二叉树的层数为k,前 k - 1 层结点都是满的,第k层结点取值范围为[1,2^(k - 1)],结点从左到右是 连续 的,由定义可知满二叉树是第k层结点为 2^(k - 1)的完全二叉树

(3).二叉树的性质

1. 若规定根节点的层数为1，则一棵非空二叉树的第i层上最多有2^(i-1) 个结点.
2. 若规定根节点的层数为1，则深度为h的二叉树的最大结点数是2^h- 1.
3. 对任何一棵二叉树, 如果度为0其叶结点个数为 n0, 度为2的分支结点个数为 n2,则有n0＝n2＋1
4. 若规定根节点的层数为1，具有n个结点的满二叉树的深度，h=Log2(n+1). (ps：Log2(n+1)是log以2为底，n+1为对数)
5. 对于具有n个结点的完全二叉树，如果按照从上至下从左至右的数组顺序对所有节点从0开始编号，则对于序号为i的结点有：
   若i>0，i位置节点的双亲序号：(i-1)/2；i=0，i为根节点编号，无双亲节点
   若2i+1<n，左孩子序号：2i+1，2i+1>=n否则无左孩子
   若2i+2<n，右孩子序号：2i+2，2i+2>=n否则无右孩子

(4).二叉树相关练习

(1).某二叉树共有 399 个结点，其中有 199 个度为 2 的结点，则该二叉树中的叶子结点数为

由性质3可知 叶子结点有200个

(2).在具有 2n 个结点的完全二叉树中，叶子结点个数为

设叶子结点个数有n0个,由性质3可知,度为2的结点个数有 n0 - 1 个，由完全二叉树的定义可知,完全二叉树度为1的结点个数为 1 个或 0 个

n0 + n0 - 1 + n1 = 2n
由于2n为偶数,所以n1 = 1,n0 = n

(3).一棵完全二叉树的节点数为531个，那么这棵树的高度为

高度为9的满二叉树的结点个数为 2^9 - 1 = 511个
高度为10的满二叉树的结点个数为2^10 - 1 = 1023个

因此高度为10

(4).一个具有767个节点的完全二叉树，其叶子节点个数为

设叶子结点个数有n0个,由性质3可知,度为2的结点个数有 n0 - 1 个，由完全二叉树的定义可知,完全二叉树度为1的结点个数为 1 个或 0 个

n0 + n0 - 1 + n1 = 767
由于767为奇数,所以n1 = 0,n0 = 384个

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

(1).堆的概念

普通的二叉树是不适合用数组来存储的，因为可能会存在大量的空间浪费。而完全二叉树更适合使用顺序结构存储。现实中我们通常把堆(完全二叉树)使用顺序结构的数组来存储

我们将根节点最大的堆叫做最大堆或大根堆，根节点最小的堆叫做最小堆或小根堆

堆的特点
(1).堆中某个节点的值总是不大于或不小于其父节点的值；
(2).堆总是一棵完全二叉树

(2).堆的实现

typedef int HPDataType;
typedef struct Heap 
{
 	HPDataType* _a;
 	int _size;
 	int _capacity; 
}Heap;

当我们拿到一组数据以后,我们怎么把这组数据变成堆呢?首先我们先来了解一下向下调整算法

向下调整算法

注意 : 向下调整算法的前提是左右子树必须是堆(小堆/大堆)
我们在这里以int a[] = {27,15,19,18,28,34,65,49,25,37} 将其调整成小堆为例
向下调整算法实现(调整成小堆)

void AdjustDown(int* a,int parent,int n)
{
	int child = 2 * parent + 1;
	while(child < n)
	{
		// 注意判断 child + 1 下标是否合法
		if(child + 1 < n && a[child + 1] < a[child]) // a[child + 1] > a[child] 为调大堆
		{
			++child;
			// 选出左右孩子中最小的那个
		}
		if(a[parent] > a[child]) // a[parent] < a[child] 为调大堆
		{
			Swap(&a[parent],&a[child]);
			// 继续循环迭代
			parent = child;
			child = 2 * parent + 1;
		}
		else
		{
			break;
		}
	}
}

可我们拿到的数据不一定左右子树都是堆,那么我们可以从第一个非叶子结点开始,进行向下调整算法

建堆

以int a[] = {1,5,3,8,7,6} 建大堆为例

由上面二叉树的性质5可知第一个非叶子结点的下标为 (n - 1 - 1) / 2, n - 1为最后一个结点的下标
(n - 1 - 1) / 2为最后一个结点的父结点的下标,即第一个非叶子结点下标
建大堆实现

void HeapCreate(Heap* hp, HPDataType* a, int n)
{
	assert(hp);
	hp->_a = (HPDataType*)malloc(sizeof(HPDataType) * n);
	hp-_size = hp->_capacity = n;
	memcpy(hp->_a,a,sizeof(HPDataType) * n);
	int i = (n - 2) / 2;
	for(i = (n - 2) / 2;i >= 0;i--)
	{
		AdjustDown(hp->_a,i,n);
	}
}

建大堆时将向下调整算法写成调大堆即可
建小堆时将向下调整算法写成调小堆即可

堆的插入

堆的插入，我们可以将数据插入到堆数组末尾，再进行向上调整堆
以int a[] = {8,7,6,5,1,3} 插入9为例

堆的插入实现

void AdjustUp(int* a,int child)
{
	int parent = (child - 1) / 2;
	while(child > 0)
	{
		if(a[child] > a[parent])
		{
			Swap(&a[child],&a[parent]);
			child = parent;
			parent = (child - 1) / 2;
		}
		else
		{
			break;
		}
	}
}
void HeapPush(Heap* hp, HPDataType x)
{
	assert(hp);
	if(hp->_size == hp->_capacity)
	{
		hp->capacity *= 2;
		HPDataType* tmp = (HPDataType*)realloc(hp->_a,sizeof(HPDataType) * hp->capacity);
		if(tmp == NULL)
		{
			printf("realloc failed\n");
			exit(-1);
		}
		hp->_a = tmp;
	}
	hp->_a[hp->_size] = x;
	hp->size++;
	AdjustUp(hp->_a,hp->size - 1);
}

堆的删除

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

以int a[] = {8,7,6,5,1,3} 删除8为例
堆的删除实现

void HeapPop(Heap* hp)
{
	assert(hp);
	assert(hp->_size > 0);
	Swap(&hp->_a[0],&hp->_a[hp->_size - 1]);
	hp->size--;
	AdjustDown(hp->_a,0,hp->size)
}

堆的销毁

堆的销毁实现

void HeapDestroy(Heap* hp)
{
	assert(hp);
	free(hp->_a);
	free(hp);
}

取堆顶数据

HPDataType HeapTop(Heap* hp)
{
	assert(hp);
	assert(hp->_size > 0);
	return hp->_a[0];
}

堆的数据个数

int HeapSize(Heap* hp)
{
	assert(hp);
	return hp->_size;
}

堆的判空

bool HeapEmpty(Heap* hp)
{
	assert(hp);
	return hp->_size == 0;
}

完整代码

鉴于篇幅原因,完整代码放到gitee上，有需要的可以看一下

Heap

(3).堆排序

首先说明结论,排升序,建大堆,排降序,建小堆

可能有读者会想排升序的话，建小堆选出最小的一个，再对剩下的元素建小堆不就好了吗，这种方法虽然可行，但效率低下，每次都要重新建堆

排升序建大堆，每次选出最大的数据之后，和堆的最后一个数据交换，再对前 n - 1个数据进行向下调整算法即可

排降序建小堆，每次选出最小的数据之后，和堆的最后一个数据交换，再对前 n - 1个数据进行向下调整算法即可

// 排升序
void HeapSort(int* a,int n)
{
	int i = (n - 2) / 2;
	for(i = (n - 2) / 2;i >= 0;i--)
	{
		AdjustDown(a,i,n);
	}
	// 大堆已经建好
	int end = n - 1;
	while(end > 0)
	{
		Swap(&a[0],&a[end]);
		AdjustDown(a,0,end);
		end--;
	}
}

四.二叉树的链式结构及实现

(1).二叉树链式结构

typedef int BTDataType;
typedef struct BinaryTreeNode
{
 	struct BinTreeNode* left; // 指向当前节点左孩子
 	struct BinTreeNode* right; // 指向当前节点右孩子
 	BTDataType data; // 当前节点值域
}BTNode;

(2).二叉树的前中后序遍历

前序遍历的遍历顺序 : 根----左子树-----右子树
中序遍历的遍历顺序 : 左子树----根-----右子树
后序遍历的遍历顺序 : 左子树----右子树-----根

前序遍历的递归示意图如下图所示，中序和后序的结果类似，读者可以自己去画一下

// 前序遍历
void BinaryTreePrevOrder(BTNode* root)
{
	if(root == NULL)
		return;
	printf("%c ",root->val);
	BinaryTreePrevOrder(root->left);
	BinaryTreePrevOrder(root->right);
}

// 中序遍历
void BinaryTreePrevOrder(BTNode* root)
{
	if(root == NULL)
		return;
	BinaryTreePrevOrder(root->left);
	printf("%c ",root->val);
	BinaryTreePrevOrder(root->right);
}

// 后序遍历
void BinaryTreePrevOrder(BTNode* root)
{
	if(root == NULL)
		return;
	BinaryTreePrevOrder(root->left);
	BinaryTreePrevOrder(root->right);
	printf("%c ",root->val);
}