数据结构初阶——树和二叉树-易微帮

数据结构初阶——树和二叉树

1. 树的概念和结构
- 1.1 树的概念
- 1.2 树的表示
2. 二叉树
3. 二叉树的顺序结构及实现——堆
4. 二叉树链式结构的实现
5. 练习

1. 树的概念和结构

1.1 树的概念

1. 什么是树？

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

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

2. 树与非树：

在这里插入图片描述

子树是互不相交的；
除了根节点外，每个节点都有且仅有一个父节点；
一颗N个节点的数，有N-1条边。

像下面这些，就不是树，这是图：

在这里插入图片描述

3. 树的一些重要概念：

在这里插入图片描述

节点的度：一个节点含有的子树的个数称为该节点的度；如上图：A的为6；
叶节点或终端节点：度为0的节点称为叶节点；如上图：B、C、H、I…等节点为叶节点；
非终端节点或分支节点：度不为0的节点；如上图：D、E、F、G…等节点为分支节点；
双亲节点或父节点：若一个节点含有子节点，则这个节点称为其子节点的父节点；如上图：A是B的父节点；
孩子节点或子节点：一个节点含有的子树的根节点称为该节点的子节点；如上图：B是A的孩子节点；
兄弟节点：具有相同父节点的节点互称为兄弟节点；如上图：B、C是兄弟节点；
树的度：一棵树中，最大的节点的度称为树的度；如上图：树的度为6；
节点的层次：从根开始定义起，根为第1层，根的子节点为第2层，以此类推；
树的高度或深度：树中节点的最大层次；如上图：树的高度为4；
节点的祖先：从根到该节点所经分支上的所有节点；如上图：A是所有节点的祖先；
子孙：以某节点为根的子树中任一节点都称为该节点的子孙。如上图：所有节点都是A的子孙；
森林：由m（m>0）棵互不相交的多颗树的集合称为森林；（数据结构中的学习并查集本质就是一个森林）。

1.2 树的表示

1. 孩子兄弟表示法：

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

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

在这里插入图片描述

2. 双亲表示法：

在这里插入图片描述

使用一个结构体数组来存储树，一个结构体中包含该节点本身的信息，和自己父节点的下标。根节点没有父节点，父节点的下标设为-1。

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

在这里插入图片描述

树不是本章的重点，本章的重点是二叉树，关于树的内容会在数据结构进阶中讲到。

2. 二叉树

2.1 二叉树的概念和结构

1. 二叉树概念和特点：

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

二叉树的特点：

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

在这里插入图片描述

2. 特殊二叉树：

满二叉树：一个二叉树，如果每一个层的结点数都达到最大值，则这个二叉树就是满二叉树。也就是说，如果一个二叉树的层数为K，且结点总数是(2^k) -1 ，则它就是满二叉树。
完全二叉树：完全二叉树是效率很高的数据结构，完全二叉树是由满二叉树而引出来的。对于深度为K的，有n个结点的二叉树，当且仅当其每一个结点都与深度为K的满二叉树中编号从1至n的结点一一对应时称之为完全二叉树。要注意的是满二叉树是一种特殊的完全二叉树。节点范围：[2^(k-1), 2^k-1]

上面的概念很复杂，大家简单理解，最后一层全满的树，就是满二叉树；最后一层从左到右依次存在节点的树，就是完全二叉树。

3. 二叉树的性质：

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

2.2 二叉树的存储结构

2.2.1 顺序存储

顺序结构存储就是使用数组来存储，一般使用数组只适合表示完全二叉树，因为不是完全二叉树会有空间的浪费。

在这里插入图片描述

二叉树顺序存储中有一个规则：

leftchild下标 = parents下标 * 2 + 1
rightchild下标 = parent下标 * 2 + 2
parent下标 = (任一个child下标 - 1) / 2

基于这个规则，存储非完全二叉树就会极大的浪费数组空间。

现实使用中只有堆才会使用数组来存储。二叉树顺序存储在物理上是一个数组，在逻辑上是一颗二叉树。

2.2.2 链式存储

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

在这里插入图片描述

typedef int BTDataType;
// 二叉链
struct BinaryTreeNode_two
{
 struct BinTreeNode_two* _pLeft; // 指向当前节点左孩子
 struct BinTreeNode_two* _pRight; // 指向当前节点右孩子
 BTDataType _data; // 当前节点值域
}
 
// 三叉链
struct BinaryTreeNode_there
{
 struct BinTreeNode_there* _pParent; // 指向当前节点的双亲
 struct BinTreeNode_there* _pLeft; // 指向当前节点左孩子
 struct BinTreeNode_there* _pRight; // 指向当前节点右孩子
 BTDataType _data; // 当前节点值域
}；

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

3.1 堆的概念和结构

1. 堆的概念：

如果有一组数据，把它的所有元素按完全二叉树的顺序存储方式存储在一个一维数组中，并满足每一个父节点都小于两个子节点，则称为小堆(反之则是大堆)。将根节点最大的堆叫做最大堆或大根堆，根节点最小的堆叫做最小堆或小根堆。

2. 堆的性质：

是一颗顺序存储的完全二叉树。
大堆：树任何一个父亲都大于或等于孩子；
小堆：树任何一个父亲都小于或等于孩子。

本节会以主要以小堆做演示。

3.2 堆的实现

3.2.1 堆的定义

typedef int HPDataType;
typedef struct Heap
{
	HPDataType* a;
	int size;	  // 当前数据个数
	int capacity; // 容量
}HP;

数据类型是int，a记录一段连续的地址空间，就是数组。

3.2.2 堆的向上调整

任给一个数组，我们一定可以用这个数组建堆。

在这里插入图片描述

假设有一个堆是[15, 18, 19, 25, 28, 34, 65, 49, 27, 37]，现在我们要向这个堆中插入一个新的元素10，还要保证堆的结构不被破坏，如何做？

我们可以先将新元素插入到数组末尾，然后让这个新元素和自己的父亲比较，如果小于父亲就和父亲交换位置，如果大于等于父亲就不做处理；如果执行了交换操作，还要继续和交换后这个位置的父亲做比较，重复以上操作。

// 最小堆，向上调整
void AdjustUp(HPDataType* a, int child) // child在这里是下标
{
	int parent = (child - 1) / 2;
	while (child > 0) // child == 0 时，孩子走到根节点，循环停止
	{
		// 如果儿子比父亲小，就交换
		if (a[child] < a[parent]) // 这里改成 > 就变大堆
		{
			HPDataType tmp = a[child];
			a[child] = a[parent];
			a[parent] = tmp;

			// 继续向上走
			child = parent;				// 孩子站到原来父亲的位置上
			parent = (child - 1) / 2;	// 计算该位置的父亲
		}
		else
		{
			break;						// 如果出现儿子 >= 父亲的情况，就直接停止调整
		}
	}
}

可以通过向上调整的思路建堆，每push一个元素就向上调整。

3.2.3 堆的向下调整

1. 问题引入：

堆中有一个需求，删除堆顶的元素。这个操作要如何实现？
有同学可能想着直接挪动数组，将第一个元素覆盖。但是这样做带来的后果是，改变了堆中的各个元素之间的父子关系，堆可能不再是堆，不再满足堆的特性。
所以我们需要重新用向上调整的方式重新建堆，这样做的代价极大。
那么，有没有什么方法可以不影响个元素间的父子关系，让删除的代价小一点？

2. 向下调整：

可以先将根节点和数组尾部的那个节点互换一下，然后将数组尾部的结点删除。此时大概率堆已经不是堆了，但是里面的亲缘关系没有被破坏，再做调整即可。

假设上面这棵树已经完成交换头尾元素和删除的操作了，现在要对其进行调整，根节点是27。

先找到左右子节点中最小的一个，然后让27和它比较，如果子节点比27小，就交换；如果不小，就停止调整。如果进行了交换操作，还要继续和子节点进行比较，重复以上操作。

// 交换方法
void Swap(HPDataType* p1, HPDataType* p2)
{
	HPDataType tmp = *p1;
	*p1 = *p2;
	*p2 = tmp;
}

// 小堆，向下调整
void AdjustDown(HPDataType* a, int size, int parent)
{
	int child = parent * 2 + 1; // 默认是左孩子
	while (child < size) // 孩子不存在就结束循环
	{
		// 如果右孩子更小就选中右孩子
		if (child + 1 < size && a[child + 1] < a[child]) // 先判断一下child + 1有没有越界
		{
			child++;
		}

		// 如果孩子小于父亲，就交换
		if (a[child] < a[parent])
		{
			Swap(&a[child], &a[parent]);  
			parent = child;			
			child = parent * 2 + 1; // 默认找到左孩子
		}
		else
		{
			break;
		}
	}
}

3.3 堆模拟实现完整代码

#pragma once

#include<stdio.h>
#include<assert.h>
#include<stdlib.h>
#include<stdbool.h>


// 堆的定义（小堆）
typedef int HPDataType;
typedef struct Heap
{
	HPDataType* a;
	int size;	  // 当前数据个数
	int capacity; // 容量
}HP;

// 函数声明
void HeapInit(HP*);
void Swap(HPDataType* p1, HPDataType* p2);
void AdjustUp(HPDataType* a, int child);
void AdjustDown(HPDataType* a, int n, int parent);
void HeapDestory(HP* php);
void HeapPush(HP* php, HPDataType x);
void HeapPop(HP* php);
bool HeapEmpty(HP* php);
HPDataType HeapTop(HP* php);


// 函数实现

void HeapInit(HP* php)
{
	assert(php);
	php->a = NULL;
	php->capacity = 0;
	php->size = 0;
}

bool HeapEmpty(HP* php)
{
	assert(php);
	return php->size == 0;
}

void Swap(HPDataType* p1, HPDataType* p2)
{
	HPDataType tmp = *p1;
	*p1 = *p2;
	*p2 = tmp;
}

// 最小堆，向上调整
void AdjustUp(HPDataType* a, int child)
{
	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 AdjustDown(HPDataType* a, int size, int parent)
{
	int child = parent * 2 + 1; // 默认是左孩子
	while (child < size) // 孩子不存在就结束循环
	{
		// 如果右孩子更小就选中右孩子
		if (child + 1 < size && a[child + 1] < a[child]) // 先判断一下有没有越界
		{
			child++;
		}

		// 如果孩子小于父亲，就交换
		if (a[child] < a[parent])
		{
			Swap(&a[child], &a[parent]);
			parent = child;			
			child = parent * 2 + 1; // 默认找到左孩子
		}
		else
		{
			break;
		}
	}
}

void HeapDestory(HP* php)
{
	assert(php);
	free(php->a);
	php->a = NULL;
	php->capacity = 0;
	php->size = 0;
}

void HeapPush(HP* php, HPDataType x)
{
	assert(php);
	// 空间不够执行扩容
	if (php->size == php->capacity)
	{
		int newCapacity = php->capacity == 0 ? 4 : php->capacity * 2;
		HPDataType* tmp = (HPDataType*)realloc(php->a, newCapacity * sizeof(HPDataType));
		if (tmp == NULL)
		{
			perror("realloc fail");
			return;
		}

		php->a = tmp;
		php->capacity = newCapacity;
	}

	php->a[php->size] = x;
	php->size++;

	// 向上调整
	AdjustUp(php->a, php->size - 1); // size - 1 就是新插入元素的下标
}

// 获取堆顶数据
HPDataType HeapTop(HP* php)
{
	assert(php);
	assert(!HeapEmpty(php));

	return php->a[0];
}

// 删除堆顶数据
void HeapPop(HP* php)
{
	assert(php);
	assert(!HeapEmpty(php));

	// 交换加删除
	Swap(&php->a[0], &php->a[php->size - 1]);
	php->size--;

	// 向下调整
	AdjustDown(php->a, php->size, 0); // 传根节点下标 0
}

测试代码：

#include"Heap.h"

int main()
{
	HP hp;
	HeapInit(&hp);
	int a[] = { 65, 100, 70, 32, 50, 60 };
	for (int i = 0; i < sizeof(a) / sizeof(int); i++)
	{
		HeapPush(&hp, a[i]);
	}

	while (!HeapEmpty(&hp))
	{
		int top = HeapTop(&hp);
		printf("%d ", top);
		HeapPop(&hp);
	}
	
	HeapDestory(&hp);
	return 0;
}

输出：

32 50 60 65 70 100

可以实现升序排序，但这并不是堆排序算法！！！

3.4 堆的应用

3.4.1 堆排序

1. 不是堆排序的"堆排序"：

void HeapSort(HPDataType* a, int n)
{
	HP hp;
	HeapInit(&hp);
	// 先把数据放入堆中 -- O(N*logN)
	for (int i = 0; i < n; i++)
	{
		HeapPush(&hp, a[i]);
	}

	// 依次把堆顶数据存起来 -- O(N*logN)
	int i = 0;
	while (!HeapEmpty(&hp))
	{
		int top = HeapTop(&hp);
		a[i++] = top;
		HeapPop(&hp);
	}

	HeapDestory(&hp);
}

这样的写法有两个问题：

需要先建一个堆，太麻烦；
还要拷贝数据，造成空间复杂度的提升。

来稍微改进一下：

// 升序排序
void HeapSort(HPDataType* a, int n)
{
	// 升序 -- 建大堆
	// 降序 -- 建小堆

	// 建堆 -- 向上调整建大堆 O(N*logN)
	for (int i = 1; i < n; i++)
	{
		AdjustUp(a, i);
	}

	// O(N*logN)
	int end = n - 1;
	while (end > 0)
	{
		Swap(&a[0], &a[end]);

		// 再向下调整，选出次大的数，放在上一个大数的前面
		AdjustDown(a, end, 0);

		--end;
	}
}

首先我们可以在原有数组的基础上建堆，不用新开一个堆数组。思路就是在原有数组的基础上，模拟堆的插入。将a[0]设为根节点，然后插入a[1]，然后插入a[2]，依次将a中的所有数据入堆，此时的堆就是a本身。当然，每插入一个数据，需要进行向上调整，维护堆的结构。
这里涉及一个问题，就是我们是建大堆还是建小堆？这个问题取决于建好堆后，我们打算怎么排。
以升序排序为例，可以有两种思路：
- 建小堆，然后依次从a[0]开始，选出最小元素，然后将a[1]开始后面的数据看作一个新的数组，父子关系会被打乱，需要再次建堆，找到最小的，然后重复以上操作；
- 建大堆，第一次将a[0]取出，跟数组最后一个元素a[n-1]交换，将a[0]放在数组最后面，然后从堆中删除a[0]。堆中的父子关系没有被打乱，只需要进行向下调整即可维护堆的结构，每选出一个次大数，就将该数和堆末尾的数据互换，将这个次大数放在上一个大数的前面，然后将这个次大数从堆中删除，重复以上操作。
显然，第二种思路更优，时间复杂度更低，因此我们选择第二种，建大堆。这样我们就总结出一个结论，升序建大堆，降序建小堆。

2. 真正的堆排序：

如果没有现成的堆结构，需要写一个向上调整，一个向下调整才能实现堆排序。这样有点太麻烦了，我们可以直接用两个向下调整就搞定堆排序。

// O(N*logN)
void HeapSort(HPDataType* a, int n)
{
	// 升序 -- 建大堆
	// 降序 -- 建小堆


	// 建堆 -- 向下调整建大堆 O(N)
	for (int i = (n - 1 - 1) / 2; i >= 0; i--)
	{
		AdjustDown(a, n, i);
	}

	// O(N*logN)
	int end = n - 1;
	while (end > 0)
	{
		Swap(&a[0], &a[end]);

		// 再向下调整，选出次大的数，放在上一个大数的前面
		AdjustDown(a, end, 0);

		--end;
	}
}

向下调整也可以用来建堆，这里以建大堆为例，需要排升序的数据是{7, 8, 3, 5 ,1, 9, 5, 4}：

在这里插入图片描述

我们可以倒着调整，叶子结点不需要处理，通过倒数第一个非叶子结点n - 1（4的位置）找到最后一个父节点(n - 1 - 1) / 2（5的位置），从这个父节点开始调整，通过最后一个父节点下标--（先找到3），可以一层一层的找到所有父节点，把一个一个的子树整理成大堆。整理到根节点时，树就成了大堆。

3.4.2 TOP-K问题

1. 问题引入：

我们经常会遇到这样一类问题，找出N个数中前K大的数。正常的思路是将这N个数建大堆，然后依次popK次，就可以找到前K大的数。
但是如果N非常的，上面的思路就行不通。假设N为10亿，该数据是10亿个整型，足足有4G的大小。按照上面的思路，我们需要将这4个G的数据加载到内存，消耗大量CPU资源建堆。如果大家学过操作系统就会知道，操作系统是决不允许这样的事情发生的，本来CPU就没多少资源，CPU中宝贵的资源可不是主要用来存储数据的。所以怎么办？

2. TOP-K问题的终极思路：

先将文件中的前K个数读出来，建立一个小堆，注意一定是建小堆。然后再依次读取文件中剩余的数据，让其和堆顶元素比较，如果新数据比堆顶元素大，就将新数据放入堆顶，重复上面的操作。最后得到小堆中的数，就是前K大的数。
这样做的原理是：大数一定能入堆，并且大数不会被小数挤出去；小数遇到比自己大的数就会被挤出去。所以最后留下的就都是大数，他们是前K大的数据。

3. 代码实现，模拟文件环境：

#include"Heap.h" // 上面模拟实现的堆头文件
#include<time.h>

// 造数据，准备10万个数据，放入文件中
void CreatNDate()
{
	int n = 100000;
	srand(time(0));

	const char* file = "data.txt";
	FILE* fin = fopen(file, "w");
	if (fin == NULL)
	{
		perror("fopen error");
		return;
	}

	for (int i = 0; i < n; i++)
	{
		int x = rand() % 1000000; // 大小在100万以内的数据
		fprintf(fin, "%d\n", x);
	}

	fclose(fin);
}

// 打印前k大的数
void PrintTopK(int k)
{
	const char* file = "data.txt";
	FILE* fout = fopen(file, "r");
	if (fout == NULL)
	{
		perror("fopen error");
		return;
	}

	int* kminheap = (int*)malloc(sizeof(int) * k);
	if (kminheap == NULL)
	{
		perror("malloc error");
		return;
	}

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

	// 建小堆
	for (int i = (k - 1 - 1) / 2; i >= 0; i--)
	{
		AdjustDown(kminheap, k, i);
	}
	
	int val = 0;
	while (!feof(fout))
	{
		fscanf(fout, "%d", &val);
		if (val > kminheap[0])
		{
			kminheap[0] = val;
			AdjustDown(kminheap, k, 0);
		}
	}

	fclose(fout);

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

3.5 堆的时间复杂度

1. 建堆的时间复杂度：

因为堆是完全二叉树，而满二叉树也是完全二叉树，此处为了简化使用满二叉树来证明(时间复杂度本来看的就是近似值，多几个节点不影响最终结果)：
向下调整建堆：

因此：向下调整建堆的时间复杂度为O(N)。
向上调整建堆：

单看最后一层，向上调整就没有向下调整建堆优秀。最后一层一共有2^h-1个结点，每一个结点都向上调整，调整 h - 1 次，但最后一层的调整次数就有 (h - 1) * 2^h-1 次。向下调整是结点少的层，调整次数多；而向上调整是结点多的层，调整次数也多，从大方向上就比不过向下调整。
大家可以自行计算一下，向上调整建堆的时间复杂度是O(N*logN)。

2. pop和push的时间复杂度：

还是以满二叉树为例，满二叉树的高度为h = log(N+1)，1忽略不计为log(N)。所以pop和push的时间复杂度也是log(N)，最多移动h层，就是log(N)次。

4. 二叉树链式结构的实现

4.1 前言

普通二叉树的增删查改没有意义，真正有意义的是搜索树，平衡树，红黑树这些复杂的二叉树。但是学习控制普通二叉树的结构，是有意义的。

在学习二叉树的基本操作前，需先要创建一棵二叉树，然后才能学习其相关的基本操作。由于现在大家对二叉树结构掌握还不够深入，为了降低大家学习成本，此处手动快速创建一棵简单的二叉树，快速进入二叉树操作学习，等二叉树结构了解的差不多时，我们反过头再来研究二叉树真正的创建方式。

typedef int BTDataType;
typedef struct BinaryTreeNode
{
 	BTDataType _data;
 	struct BinaryTreeNode* _left;
 	struct BinaryTreeNode* _right;
}BTNode;

BTNode* BuyNode(BTDataType x)
{
	BTNode* node = (BTNode*)malloc(sizeof(BTNode));
	
	if (node == NULL)
	{
		perror("malloc fail");
		return NULL;
	}
	node->_data = x;
	node->_left = NULL;
	node->_right = NULL;
	
	return node;
}

// 手动构建
BTNode* CreatBinaryTree()
{
 	BTNode* node1 = BuyNode(1);
 	BTNode* node2 = BuyNode(2);
 	BTNode* node3 = BuyNode(3);
 	BTNode* node4 = BuyNode(4);
 	BTNode* node5 = BuyNode(5);
 	BTNode* node6 = BuyNode(6);
 
 	node1->_left = node2;
 	node1->_right = node4;
 	node2->_left = node3;
 	node4->_left = node5;
 	node4->_right = node6;
 	return node1;
}

在这里插入图片描述

从现在开始，大家看到一颗二叉树，一定要重点关注三个部分：

根节点；
左子树；
右子树；

注意不是关注左孩子和右孩子，而是左子树和右子树，这一点我们在后面慢慢感受。

4.2 二叉树的遍历

4.2.1 前序、中序、后序遍历

学习二叉树结构，最简单的方式就是遍历。所谓二叉树遍历(Traversal)是按照某种特定的规则，依次对二叉树中的节点进行相应的操作，并且每个节点只操作一次。访问结点所做的操作依赖于具体的应用问题。遍历是二叉树上最重要的运算之一，也是二叉树上进行其它运算的基础。

按照规则，二叉树的遍历有：前序/中序/后序的递归结构遍历：

前序遍历(Preorder Traversal 亦称先序遍历)——遍历顺序为根、左子树、右子树。
中序遍历(Inorder Traversal)——遍历顺序为左子树、根、右子树。
后序遍历(Postorder Traversal)——遍历顺序为左子树、右子树、根。

1. 理论分析：

在这里插入图片描述

上面这棵二叉树对应的前中后序遍历结果为：

前序：1 2 3 NULL NULL NULL 4 5 NULL NULL 6 NULL NULL；
中序：NULL 3 NULL 2 NULL 1 NULL 5 NULL 4 NULL 6 NULL；
后序：NULL NULL 3 NULL 2 NULL NULL 5 NULL NULL 6 4 1；

一定要把空节点也写出来，加深理解。

2. 代码实现：

#include<stdio.h>
#include<stdlib.h>

typedef int BTDataType;
typedef struct BinaryTreeNode
{
    ...
}BTNode;

BTNode* BuyNode(BTDataType x)
{
    ...
}

// 手动构建
BTNode* CreatBinaryTree()
{
    ...
}

// 先序
void PrevOrder(BTNode* node)
{
    if (node == NULL)
    {
        printf("NULL ");
        return;
    }

    printf("%d ", node->_data);
    PrevOrder(node->_left);
    PrevOrder(node->_right);
}

// 中序
void InOrder(BTNode* node)
{
    if (node == NULL)
    {
        printf("NULL ");
        return;
    }

    InOrder(node->_left);
    printf("%d ", node->_data);
    InOrder(node->_right);
}

// 后序
void PostOrder(BTNode* node)
{
    if (node == NULL)
    {
        printf("NULL ");
        return;
    }

    PostOrder(node->_left);
    PostOrder(node->_right);
    printf("%d ", node->_data);
}

测试代码：

int main()
{
    BTNode* tree = CreatBinaryTree();
    PrevOrder(tree);
    printf("\n");
    InOrder(tree);
    printf("\n");
    PostOrder(tree);
    printf("\n");
  	return 0;
}

递归遍历二叉树的时间复杂度为O(N)，空间复杂度为O(h)，h的范围是[logN, N]，最坏的情况就是结点全在一边，高度为N；好的情况就是完全二叉树的情况。

注意空间复杂度不是O(N)，因为每递归访问一个节点都要建立函数栈帧，但是一但访问到叶子结点开始回溯，为这个叶子结点开辟的栈帧就被销毁了。所以二叉树的高度是多少，递归遍历就最多开辟多少栈帧，空间复杂度为O(h)。

4.2.2 二叉树的层序遍历

1. 何为层序遍历？

设二叉树的根节点所在层数为1，层序遍历就是从所在二叉树的根节点出发，首先访问第一层的树根节点，然后从左到右访问第2层上的节点，接着是第三层的节点，以此类推，自上而下，自左至右逐层访问树的结点的过程就是层序遍历。

2. 实现原理：

二叉树的层序遍历符合先进先出的特性，一个节点在出队列时，顺带着要把自己的左右节点入队列，直到队列为空为止。

#inlcude"Queue.h" // 需要自己实现一个队列

//层序遍历
void LevelOrder(BTNode* node)
{
	//创建一个队列
	Queue Q;
	QueueInit(&Q); // 初始化队列
	
	if (node)
		QueuePush(&Q, node);					//将根节点入队
		
	while (!QueueEmpty(&Q))				//若队列不为空就进行循环
	{
		BTNode* pNode = QueueFront(&Q);		//队头元素出队
		QueuePop(&Q);
		printf("%c ", pNode->_data);			//访问操作

		// 左右节点不为空，就进队列
		if (pNode->_left)
		{
			QueuePush(&Q, pNode->_left);
		}
		if (pNode->_right)
		{
			QueuePush(&Q, pNode->_right);
		}
	}

	printf("\n");
	QueueDestroy(&Q); // 摧毁队列
}

如果是用C语言实现，需要我们手动创建一个队列，比较麻烦，这里就不再写了。用C++实现会方便很多，感兴趣的同学可以尝试一波。

4.3 求二叉树的各种属性

4.3.1 求二叉树中各种节点的个数

学习这一块，需要大家具有一定的抽象思维（分治递归），将左子树右子树抽象出来。实在不理解就尝试画递归展开图。

1. 求二叉树中的节点总数：

// 二叉树节点个数
int BinaryTreeSize(BTNode* node)
{
    if (node == NULL)
    {
        return 0;
    }

    // 递归计算左子树和右子树的节点个数
    return BinaryTreeSize(node->_left) + BinaryTreeSize(node->_right) + 1; 
}

一棵树的节点个数，就等于它的左子树和右子树个数之和，再加上自己的根节点。

2. 求二叉树中叶子结点的个数：

// 二叉树叶子节点个数(度为0节点的个数)
int BinaryTreeLeafSize(BTNode* node)
{
    if (node == NULL)
    {
        return 0;
    }

    // 满足条件就是叶子结点
    if (node->_left == NULL && node->_right == NULL)
    {
        return 1;
    }
    else
        return BinaryTreeLeafSize(node->_left) + BinaryTreeLeafSize(node->_right);
}

满足左子树和右子树都为空的节点就是叶子结点，递归到这个节点我们就返回1，没有递归到叶子结点就分别到左子树和右子树中去找。

3. 求度为1，和度为2节点的个数：

//统计二叉树中，度为1结点的个数
int NodeCount_One(BTNode* node)
{
    if (node == NULL)
    {
        return 0;
    }
    
    // 满足条件就是度为1的节点，要+1，然后往左子树或右子树继续遍历
    if ((node->_left != NULL && node->_right == NULL) || (node->_left == NULL && node->_right != NULL))
        return NodeCount_One(node->_left) + NodeCount_One(node->_right) + 1;
    else
        return NodeCount_One(node->_left) + NodeCount_One(node->_right);
}

//统计二叉树中，度为2结点的个数
int NodeCount_Two(BTNode* node)
{
    if (node == NULL)
        return 0;
    if (node->_left != NULL && node->_right != NULL)
        return NodeCount_Two(node->_left) + NodeCount_Two(node->_right) + 1;
    else
        return NodeCount_Two(node->_left) + NodeCount_Two(node->_right);
}

满足左子树和右子树有一个为空的节点，就是度为1的节点，我们记录它，加1，然后再到左子树或右子树中去找度为1的节点。

满足左子树和右子树都不为空的节点，就是度为2的节点，我们记录它，加1，然后遍历再左右子树。

4.3.2 求二叉树的高度

1. 思路：

求一颗二叉树的高度，先求左子树和右子树的高度，然后比较那个更高，就拿这个子树的高度加1得到该树的高度。

2. 先看一种不好的写法：

int BinaryTreeHeight(BTNode* node)
{
    if (node == NULL)
        return 0;

    if (BinaryTreeHeight(node->_left) < BinaryTreeHeight(node->_right))
        return BinaryTreeHeight(node->_right) + 1;
    else
        return BinaryTreeHeight(node->_left) + 1;
}

这样写从思路上来讲完全可行，但是效率极低，导致在有些做题网站上直接被判错，说超出时间限制。

现在把二叉树比作我们学校的一个管理结构，最上层是校长，第二层是各院长，第三层是各辅导员，最后一层是学生。想象一下，现在校长想统计学生成绩，比较哪个学院的成绩最好，下层就开始工作，但是每一层都不记数据。学生把成绩报给辅导员，各辅导员之间先比较了各班的成绩，然后把比较结果报给院长，（对应：BinaryTreeHeight(node->_left) < BinaryTreeHeight(node->_right)），院长说很好，但是各班具体的成绩是多少呢？辅导员没记住，又要重新跑回去问一下各个同学，然后告诉了院长。院长们通过比较各自各班学生成绩的总和，知道了哪个院的成绩更好，但是也不记数据。校长问院长要具体成绩单时，院长又跑去找辅导员要，辅导员还不记，再找同学们要。可想而知，这样的效率是多么低下，所以这种方案不可取。

3. 正确写法：

int BinaryTreeHeight(BTNode* node)
{
    if (node == NULL)
        return 0;

    // 先把值记录下来
    int heightLeft = BinaryTreeHeight(node->_left);
    int heightRight = BinaryTreeHeight(node->_right);

    if (heightLeft < heightRight)
        return heightRight + 1;
    else
        return heightLeft + 1;
}

一定要提前把每一层的高度都记录下来，不要比的时候算一回高度，记录高度的时候又算一次高度。

4.3.3 求二叉树第K层节点个数

1. 思路：

该问题的递归子问题是，求左子树k-1层的节点个数加上右子树k-1层的节点个数；
递归的终止条件是k==1。

2. 代码实现：

// 二叉树第k层节点个数
int BinaryTreeLevelKSize(BTNode* node, int k)
{
    if (node == NULL)
        return 0;

    if (k == 1)
        return 1;
    else
        return BinaryTreeLevelKSize(node->_left, k - 1) + BinaryTreeLevelKSize(node->_right, k - 1);
}

4.4 二叉树的一些操作

1. 查找值为x的节点：

// 二叉树查找值为x的节点
BTNode* BinaryTreeFind(BTNode* node, BTDataType x)
{
    if (node == NULL)
        return NULL;

    if (node->_data == x)
        return node;

    // 记录左子树查找结果
    BTNode* retLeft = BinaryTreeFind(node->_left, x);
    if (retLeft != NULL)
        return retLeft;

    // 记录右子树查找结果
    BTNode* retRight = BinaryTreeFind(node->_right, x);
    if (retRight != NULL)
        return retRight;

    return NULL; // 最后没有找到，返回空
}

2. 二叉树的复制：

//复制二叉树
void Copy(BTNode* node, BTNode** pNewNode)
{
	if (T == NULL)
	{
		*pNewNode = NULL;
		return;
	}
	if (!(*pNewNode = (BTNode*)malloc(sizeof(BTNode))))
	{
		perror("malloc");
		exit(-1);
	}
	(*pNewNode)->_data = node->_data;
	Copy(node->_left, &((*pNewNode)->_left));		// 递归复制左子树
	Copy(node->_right, &((*pNewNode)->_right));	// 递归复制右子树
}

3. 二叉树的创建：

牛客网链接：https://www.nowcoder.com/practice/4b91205483694f449f94c179883c1fef?tpId=60&&tqId=29483&rp=1&ru=/activity/oj&qru=/ta/tsing-kaoyan/question-ranking

#include<stdio.h>
#include<stdlib.h>
#include<string.h>

typedef char BTDataType;
typedef struct BTNode
{
    struct BTNode* _left;
    struct BTNode* _right;
    char _data;
}BTNode;

BTNode* BuyNode(BTDataType x)
{
    BTNode* node = (BTNode*)malloc(sizeof(BTNode));

    if (node == NULL)
    {
        perror("malloc fail");
        return NULL;
    }
    node->_data = x;
    node->_left = NULL;
    node->_right = NULL;

    return node;
}

// 前序创建二叉树
BTNode* creatBTree(const char array[], int* pi)
{
    if(array[*pi] == '#')
    {
        (*pi)++;
        return NULL;
    }
    BTNode* tree = BuyNode(array[*pi]);
    (*pi)++;
    tree->_left = creatBTree(array, pi);
    tree->_right = creatBTree(array, pi);
    return tree;
}

// 中序遍历
void InOrder(BTNode* tree)
{
    if(tree == NULL)
        return;
    
    InOrder(tree->_left);
    printf("%c ", tree->_data);
    InOrder(tree->_right);
}

int main() 
{
    char array[100];
    scanf("%s", array);

    int i = 0;
    BTNode* tree = creatBTree(array, &i);

    InOrder(tree);
    printf("\n");
    return 0;
}

4. 二叉树的销毁：

// 二叉树的销毁(后序遍历)
void BTreeDestory(BTNode* node)
{
    if (node == NULL)
        return;

    BTreeDestory(node->_left);
    BTreeDestory(node->_right);
    free(node);
}

也可以使用其他遍历方法，但是这里后序遍历更加合适。

如果使用前序遍历，是先访问根节点，就是先free根，但是如果先把根free了，左右子树就找不到了，所以需要先保存一下左右子树，再free根，比较麻烦；如果使用中序遍历，其实就是先free左子树，再free根，再free右子树，但是free根在free右子树的前面，所以还是需要先保存右子树。

5. 练习

1. 相同的树：

leedcode链接：https://leetcode.cn/problems/same-tree/

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
 
bool isSameTree(struct TreeNode* p, struct TreeNode* q) 
{
	// p和q同时为空时，就是相同，否则就是不相同
    if(p == NULL && q == NULL)
        return true;
    if((p == NULL && q != NULL) ||
       (p != NULL && q == NULL))
        return false;

    if(p->val != q->val)
    {
        return false;
    }
    
    // 记录左子树的比较结果
    bool resultOfLeft = isSameTree(p->left, q->left);
    if(resultOfLeft != false)
    {
    	// 左子树相同，继续比较右子树，并且右子树的比较结果就是整棵树的比较结果，直接返回即可
        return isSameTree(p->right, q->right); 
    }
    else
        return false;
}

2. 对称二叉树：

leedcode链接：https://leetcode.cn/problems/symmetric-tree/submissions/526478746/

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */

bool check(struct TreeNode* p, struct TreeNode* q)
{
    if(p == NULL && q == NULL)
        return true;
    // 这个判断是在上一个if的基础上进行的，可以判断p和q是否存在一个空，是就返回false
    if(p == NULL || q == NULL) 
        return false;
    if(p->val != q->val)
        return false;
    
    // 记录第一趟，p走左树，q走右树的比较结果
    bool result = check(p->left, q->right);
    if (result)
        return check(p->right, q->left);
    else
        return false;
}

bool isSymmetric(struct TreeNode* root) 
{
    return check(root, root);
}

3. 单值二叉树：

leedcode链接：https://leetcode.cn/problems/univalued-binary-tree/

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
 
bool isUnivalTree(struct TreeNode* root) 
{
    if(root == NULL)
        return true;

    if((root->left != NULL)&&(root->val != root->left->val))
        return false;
    if((root->right != NULL)&&(root->val != root->right->val))
        return false;

    bool resultLeft = isUnivalTree(root->left);
    if(resultLeft)
        return isUnivalTree(root->right);
    else
        return false;
}

4. 二叉树的前序遍历（不简单哦）：

leedcode链接：https://leetcode.cn/problems/binary-tree-preorder-traversal/submissions/526609878/

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
/**
 * Note: The returned array must be malloced, assume caller calls free().
 */

int TreeSize(struct TreeNode* root)
{
    return root == NULL? 0 : TreeSize(root->left) + TreeSize(root->right) + 1;
}

void _preorder(struct TreeNode* root, int* array, int* pi)
{
    if(root == NULL)
    {
        return;
    }
    array[(*pi)++] = root->val;
    _preorder(root->left, array, pi);
    _preorder(root->right, array, pi);
}

int* preorderTraversal(struct TreeNode* root, int* returnSize) 
{
    *returnSize = TreeSize(root);
    int* array = (int*)malloc(sizeof(int) * *returnSize);

    int i = 0;
    _preorder(root, array, &i);
    return array;
}

题中要求我们必须自己malloc一个数组来存储遍历序列，最后返回的也是这个数组。

5. 一棵树的子树：

leedcode链接：https://leetcode.cn/problems/subtree-of-another-tree/submissions/526620078/

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */

bool isSameTree(struct TreeNode* p, struct TreeNode* q) 
{
	// p和q同时为空时，就是相同，否则就是不相同
    if(p == NULL && q == NULL)
        return true;
    if((p == NULL && q != NULL) ||
       (p != NULL && q == NULL))
        return false;

    if(p->val != q->val)
    {
        return false;
    }
    
    // 记录左子树的比较结果
    bool resultOfLeft = isSameTree(p->left, q->left);
    if(resultOfLeft != false)
    {
    	// 左子树相同，继续比较右子树，并且右子树的比较结果就是整棵树的比较结果，直接返回即可
        return isSameTree(p->right, q->right); 
    }
    else
        return false;
}

bool isSubtree(struct TreeNode* root, struct TreeNode* subRoot)
{
    if(root == NULL)
        return false;

    if(isSameTree(root, subRoot))
        return true;

    /*
    bool resultLeft = isSubtree(root->left, subRoot);
    if(!resultLeft)
        return isSubtree(root->right, subRoot);
    else
        return true;
    */

    return isSubtree(root->left, subRoot) || isSubtree(root->right, subRoot);
}

复用之前比较树是否相同的代码。最后返回，是左子树的子树，或是右子树的子树。

6. 是否是完全二叉树：

bool BinaryTreeComplete(BTNode* node)
{
	//创建一个队列
	Queue Q;
	QueueInit(&Q); // 初始化队列

	if (node)
		QueuePush(&Q, node);					//将根节点入队
	else
		return false;

	while (!QueueEmpty(&Q))				
	{
		BTNode* front = QueueFront(&Q);
		QueuePop(&Q);

		// 遇到空就跳出
		if (front == NULL)
			break;

		QueuePush(&Q, front->_left);
		QueuePush(&Q, front->_right);
	}

	// 后面应该全是空，出现非空就返回false
	while (!QueueEmpty(&Q))
	{
		BTNode* front = QueueFront(&Q);
		QueuePop(&Q);

		if (front != NULL)
		{
			QueueDestroy(&Q);
			return false;
		}
	}

	QueueDestroy(&Q); 
	return true;
}

该题适合层序遍历，同样需要我们手撕一个队列。在一颗完全二叉树中，层序遍历访问到空节点时，说明该层的右侧全是空节点。所以我们可以从这个特性下手，如果在遍历过程中遇到了空节点，就跳出循环，判断这个队列往后的节点是否全为空，全为空就返回真，出现一个非空节点就返回假。

数据结构初阶——树和二叉树

数据结构初阶——树和二叉树

1. 树的概念和结构

1.1 树的概念

1.2 树的表示

2. 二叉树

2.1 二叉树的概念和结构

2.2 二叉树的存储结构

2.2.1 顺序存储

2.2.2 链式存储

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

3.1 堆的概念和结构

3.2 堆的实现

3.2.1 堆的定义

3.2.2 堆的向上调整

3.2.3 堆的向下调整

3.3 堆模拟实现完整代码

3.4 堆的应用

3.4.1 堆排序

3.4.2 TOP-K问题

3.5 堆的时间复杂度

4. 二叉树链式结构的实现

4.1 前言

4.2 二叉树的遍历

4.2.1 前序、中序、后序遍历

4.2.2 二叉树的层序遍历

4.3 求二叉树的各种属性

4.3.1 求二叉树中各种节点的个数

4.3.2 求二叉树的高度

4.3.3 求二叉树第K层节点个数

4.4 二叉树的一些操作

5. 练习

网站公告

今日签到

热门文章

最新发布