目录

前言

一、树的概念和结构

1、树的概念

2、树的表示

 3、树在实际中的应用（表示文件系统的目录树结构）

二、二叉树概念及结构

1.概念

 2、特殊的二叉树

3、二叉树的性质

4、二叉树的存储

4.1顺序存储

4.2链状存储

 三、二叉树的顺序结构和实现

1、二叉树的顺序结构

2、堆的概念及结构

3、堆的实现

3.1堆的代码框架

3.2堆的插入

3.3堆的删除

3.4堆的建立 

3.5建堆的时间复杂度 

4、堆的应用

4.1堆排序

 4.2TOP-K问题

四、二叉树链式结构的实现

 1、建二叉树

2、二叉树的遍历

2.1前序、中序以及后序遍历

2.2层序遍历

3、二叉树的销毁

总结

前言

哈喽，小伙伴们大家好，相信对数据结构有一定了解的小伙伴对树这个名字都不陌生。今天，我将为大家介绍以下什么是树，并主要介绍一种树中的特殊结构——二叉树。

---

一、树的概念和结构

1、树的概念

树是一种非线性的数据结构，它是由n（n>=0）个有限结点组成一个具有层次关系的集合。把它叫做树是因为它看起来像一棵倒挂的树，也就是说它是根朝上，而叶朝下的。

• 有一个特殊的结点，称为根结点，根节点没有前驱结点。
• 除根节点外，其余结点被分成几个互不相交的集合，每个集合又是一棵结构与树类似的子树。每棵子树的根结点有且只有一个前驱，可以有0个或多个后继。
• 因此，树是递归定义的。

如下图，A为整个树的根节点。而B，C，D可以看做子树的根节点，在下面分别长出三棵子树。

• 节点的度：一个节点含有的子树的个数，叫做该节点的度。
• 叶节点和终端节点：度为零的节点。
• 双亲结点或父节点：如图，C为G的父节点。
• 孩子节点或子节点：如图，G为C的子节点。
• 兄弟节点：拥有相同父节点的节点称为兄弟节点。
• 树的度：一棵树中最大的节点的度称为树的度。
• 节点的层次：从根开始定义起，根为第1层，根的子节点为第2层，以此类推。
• 树的高度或深度：树中节点的最大层次，如图，高度为4。
• 祖先：从跟到该节点所经分支上的所有节点。A是所有节点的祖先。
• 森林：由m（m>0）棵互不相交的树的集合称为森林。

2、树的表示

树结构相对线性表就比较复杂了，要存储表示起来就比较麻烦了，实际中树有很多种表示方式，如：双亲表示法，孩子表示法、孩子兄弟表示法等等。我们这里就简单的了解其中最常用的孩子兄弟表示法。

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

 3、树在实际中的应用（表示文件系统的目录树结构）

二、二叉树概念及结构

1.概念

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

二叉树的特点：

1、每个节点最多有两棵子树，即不存在超过度为2的节点。

2、二叉树的子树有左右之分，且左右不能颠倒。

现实中的二叉树：

 2、特殊的二叉树

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

2、完全二叉树：完全二叉树是由满二叉树引出的。满二叉树要求每一层的节点数都达到最大值，完全二叉树仅要求除最后一层外的节点数达到最大值，也就是说最后一层可以不满。我们可以把满二叉树看错特殊的完全二叉树。

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)
5. 对于具有n个结点的完全二叉树，如果按照从上至下从左至右的数组顺序对所有节点从0开始编号，则对于序号为i的结点有：

（1）. 若i>0，i位置节点的双亲序号：(i-1)/2；i=0，i为根节点编号，无双亲节点

（2）. 若2i+1=n否则无左孩子

（3）. 若2i+2=n否则无右孩子

4、二叉树的存储

4.1顺序存储

顺序结构存储就是使用数组来存储，一般使用数组只适合表示完全二叉树，因为不是完全二叉树会有空间的浪费。而现实中使用中只有堆才会使用数组来存储，关于堆我们后面会专门讲解。二叉树顺序存储在物理上是一个数组，在逻辑上是一颗二叉树。

 注意：空节点的地方在数组中要空出来，不然无法模拟出树的结构。

4.2链状存储

二叉树的链式存储结构是指，用链表来表示一棵二叉树，即用链来指示元素的逻辑关系。 通常的方法是链表中每个结点由三个域组成，数据域和左右指针域，左右指针分别用来给出该结点左孩子和右孩子所在的链结点的存储地址 。链式结构又分为二叉链和三叉链，当前我们学习中一般都是二叉链，高阶数据结构如红黑树等会用到三叉链。如图：左边为二叉链，右边为三叉链。

 三、二叉树的顺序结构和实现

1、二叉树的顺序结构

普通的二叉树是不适合用数组来存储的，因为可能会存在大量的空间浪费。而完全二叉树更适合使用顺序结构存储。现实中我们通常把堆(一种二叉树)使用顺序结构的数组来存储，需要注意的是这里的堆和操作系统虚拟进程地址空间中的堆是两回事，一个是数据结构，一个是操作系统中管理内存的一块区域分段。

2、堆的概念及结构

堆是一种特殊的二叉树，具有一些特殊的性质。

堆的性质：

• 堆中某个节点的值总是不大于或不小于其父节点的值。我们把子节点都不大于父节点的称为大堆，反之称为小堆。
• 堆总是一棵完全二叉树。

3、堆的实现

3.1堆的代码框架

typedef int HPDataType;
typedef struct Heap
{
	int size;
	int capacity;
	HPDataType* a;
	
}HP;

void heap_init(HP* heap);   //堆的初始化
void heap_destory(HP* heap);   //堆的销毁
void heap_push(HP* heap, HPDataType x);   //堆的插入
void heap_pop(HP* heap);    //堆的删除
HPDataType heap_top(HP* heap);   //取堆顶的数据
int heap_size(HP* heap);   //堆的数据个数

3.2堆的插入

堆的插入要求，原二叉树为一个堆，再插入新数据后依然为一个堆。这就要求对新数据的位置进行调整，对此我们要学习向上调整算法。

注意：插入时只能在堆的末尾进行操作，否则会破坏堆的整个结构。

向上调整算法：把新节点顺着其双亲调整到合适的位置，就能形成一个新的堆。

代码如下

//向上调整
void adjust_up(HPDataType* a,int child)
{
	assert(a);
	int parent = (child - 1) / 2; //找出父节点
	while (child > 0)  //child等于0说明已经到了根部
	{
		if (a[child] < a[parent])//建小堆用小于号，建大堆用大于号
		{
			swap(&a[child], &a[parent]);
			child = parent;
			parent = (child - 1) / 2;
		}
		//调整完毕即退出
		else
		{
			break;
		}
	}
}

有了向上调整算法，我们就可以进行堆的插入

void heap_push(HP* heap, HPDataType x)
{
	assert(heap);
	if (heap->size == heap->capacity)
	{
		int newcapacity = heap->capacity == 0 ? 4 :heap-> capacity * 2;
		HPDataType* temp = (HPDataType*)realloc(heap->a,sizeof(HPDataType) * newcapacity);
		if (temp == NULL)
		{
			exit(-1);
		}
		heap->a = temp;
		heap->capacity = newcapacity;
	}
	heap->a[heap->size] = x;
	heap->size++;
	adjust_up(heap->a,heap->size-1);
}

3.3堆的删除

堆的删除要求在原有堆的基础上，删掉第一个元素，通过调整，形成新的堆。

如果只是简单的直接删除，会使堆的整个结构发生错乱（例如兄弟节点变父子节点），想要调整形成新的堆要花很大力气。所以这里我们才用一种很巧妙的方法：把第一个元素和最后一个元素交换位置，然后把最后一个元素删掉，这样不会破坏堆的整体结构。最后把第一个元素进行简单的向下调整，就能形成新的堆。

向下调整算法：从根节点开始沿着合适的路线向下调整，形成新的堆。但向下调整算法有一个前提，那就是左右子树必须都是堆，才能进行调整。我们上面的一系列操作恰巧满足这个要求。

向下调整算法代码如下：

//向下调整
void adjust_down(HPDataType* a, int size, int parent)
{
	assert(a);
	int child = 2 * parent + 1;
	while (child < size)
	{
		//挑出两个子节点中更大或更小的那个
		if (child + 1 < size && a[child+1]

堆的删除代码如下：

void heap_pop(HP* heap)
{
	assert(heap);
	assert(heap->a);
	swap(&(heap->a[0]), &(heap->a[heap->size-1])); //交换首节点和尾节点的值
	heap->size--;
	adjust_down(heap->a, heap->size, 0);
}

3.4堆的建立 

上面我们说的无论是堆的插入还是堆的删除都是建立在有堆的基础上，那么如果我们眼前仅仅是一个普通的二叉树，怎么把它建成一个堆呢？

堆的建立方式有两种，分别是向上调整建堆和向下调整建堆。

	//数组a可以看成一棵普通二叉树
	int a[5] = { 5,4,3,2,1 };
	int n = sizeof(a) / sizeof(int);

	//向上调整建堆法
	for (int i = 0; i < n; i++)
	{
		adjust_up(a, i);
	}

	//向下调整建堆法，叶子节点不用调，从最后一个父节点调即可
	//n-1为最后一个叶子节点，再减1除2是它的父节点，即整棵树的最后一个父节点
	for (int i = (n - 1 - 1) / 2; i >= 0; i--) 
	{
		adjust_down(a, n, i);
	}

3.5建堆的时间复杂度 

向上调整建堆的时间复杂度为O（N*log N），向下调整的时间复杂度为O(N)，所以我们常用向下调整建堆。

下面我将重点演示向下调整建堆的时间复杂度计算，感兴趣的小伙伴也可以自己验证一下向上调整的时间复杂度，方法相同。

 从图中我们也可以看出，每一层节点越多，需要移动的次数就越少，故导致最后的时间复杂度为 O(N)。

4、堆的应用

4.1堆排序

堆排序即利用堆的思想来进行排序，总共分为两个步骤：

（1）建堆

升序建大堆，降序建小堆。

（2） 利用堆删除思想来进行排序

以排升序为例，先建好大堆，然后把最大的数也就是第一个数和最后一个数进行交换。把最后一个数看作从堆中取中，再把第一个数进行向下调整建立新堆，即能找到次大的数。反复重复上述步骤，便可以实现排序。

堆排序的代码如下：

heap_sort(int* a,int n)
{
	//建堆，O（N）
	for (int i = (n - 1 - 1) / 2; i >= 0; i--)
	{
		adjust_down(a, n, i);
	}

	//排序，O（N*logN）
	int end = n;
	while (end > 0)
	{
		swap(&a[0], &a[end-1]);
		end--;
		adjust_down(a, end, 0);
	}
}

 4.2TOP-K问题

所谓TOP-K问题，就是找到一堆数中前K个最大的数或最小的数。比如：专业前10名、世界500强、富豪榜、游戏中前100的活跃玩家等。

对于这个问题，我们最先想到的就是排序。但是如果数据过多的时候，是无法进行排序的，因为内存放不下这么多数据。例如100亿个整形数据，需要400亿个字节即40g的内存（1GB等于10亿字节），一般没有这么大的空间。所以一般利用堆来解决，具体方法如下：

1、用数据中前K个数来建堆

• 找前k个最大元素则建小堆
• 找前k个最小元素则建大堆

2、用剩余的N-K个元素分别与堆顶元素比较，不满足则替换堆顶元素

以找前k个最大元素举例。用剩下N-K个数分别与堆顶元素比较，如果比堆顶元素大，就替换堆顶元素，然后向下调整建之后再继续进行比较。将剩下的数都比完后，堆中的数即为要找的前k个数。

代码如下

void printtopk(int*a,int n,int k)
{
	//用前k个数据建堆
	int* kminheap = (int*)malloc(sizeof(int) * k);
	assert(kminheap);
	for (int i = 0; i < k; i++)
	{
		kminheap[i] = a[i];
	}
	for (int i = (k - 1 - 1) / 2; i >= 0; i--)
	{
		adjust_down(kminheap, k, i);
	}

	//用剩下N-K个数比较
	for (int i = k; i < n; i++)
	{
		if (a[i] > kminheap[0])
		{
			kminheap[0] = a[i];
			adjust_down(kminheap, k, 0);
		}
	}

	for (int i = 0; i < k; i++)
	{
		printf("%d", kminheap[i]);
	}
}

四、二叉树链式结构的实现

 1、建二叉树

想要创建一棵二叉树，我们首先要建一个二叉树节点。

typedef int BTDataType;
typedef struct BinaryTreeNode
{
	struct BinaryTreeNode* left;
	struct BinaryTreeNode* right;
	BTDataType data;
}BTNode;


//创建一个节点
BTNode* BuyNode(BTDataType x)
{
	BTNode* node = (BTNode*)malloc(sizeof(BTNode));
	assert(node);

	node->data = x;
	node->left = NULL;
	node->right = NULL;

	return node;
}

有了节点之后，我们就可以用n个节点来拼成一棵树。这里采用前序遍历的思想，往下递归时先把节点的值填充，等返回时节点和节点就会连到一起。

// 通过前序遍历的数组构建二叉树,0代表空指针
BTNode* CreatBinaryTree(BTDataType* arr,int* pi)
{
	if (arr[*pi] == 0)
	{
		(*pi)++;
		return NULL;
	}
	BTNode* root = BuyNode(arr[*pi]);
	(*pi)++;
	root->left = CreatBinaryTree(arr, pi);
	root->right = CreatBinaryTree(arr, pi);
	return root;
}

2、二叉树的遍历

2.1前序、中序以及后序遍历

这三种遍历都是深度优先。遵循的顺序如下：

• 前序遍历——访问根结点的操作发生在遍历其左右子树之前。
• 中序遍历——访问根结点的操作发生在遍历其左右子树之中。
• 后序遍历——访问根结点的操作发生在遍历其左右子树之后。

以前序遍历为例，代码如下：

//前序遍历
void pre_order(BTNode* root)
{
	if (root == NULL)
	{
		printf("%c ", '#');
		return;
	}
	printf("%d ", root->data);
	pre_order(root->left);
	pre_order(root->right);
}

2.2层序遍历

层序遍历，顾名思义，就是一层一层的遍历。这里我们要借助队列。

 以这棵树为例，我们想要层序遍历。先把1放入队列中。然后开始循环下列操作：取队头的节点并删除掉，在删除的同时把队头节点的左右子节点放到队列中。这样把第一层的节点取完后第二层就会放到队列中，第二层节点取完后第三层的节点就会被放到队列中，循环此操作，实现层序遍历。

代码如下：

//层序遍历
void level_order(BTNode* root)
{
	Queue q;
	QueueInit(&q);
	if (root)
	{
		QueuePush(&q, root);
	}
	BTNode* front;
	while (!QueueEmpty(&q))
	{
		front = QueueFront(&q);
		printf("%d", front->data);
		QueuePob(&q);
		if (front->left)
		{
			QueuePush(&q, front->left);
		}

		if (front->right)
		{
			QueuePush(&q, front->right);
		}
	}
	printf("n");
	QueueDestory(&q);
}

3、二叉树的销毁

二叉树的遍历要采用后续遍历，不然父节点销毁后会找不到子节点。

void tree_destory(BTNode* root)
{
	if (root == NULL)
	{
		return;
	}
	//要采用后序遍历，不然父节点销毁了就找不到子节点了
	tree_destory(root->left);
	tree_destory(root->right);
	free(root);

}

---

总结

本章主要介绍了二叉树的一些基础知识，至于一些更高级的二叉树，例如搜索二叉树，红黑树等，我会在学完c++后向大家介绍。感谢阅读，来日方长，期待和大家再次相遇。