【数据结构（C语言版）】二叉树_c 语言二叉树

目录

1. 树

1.1 树的概念

1.2 树的基本术语

1.3 树的表示

2. 二叉树

2.1 二叉树的概念

2.2 特殊的二叉树

2.2.1 满二叉树

2.2.2 完全二叉树

2.3 二叉树的性质

2.4 二叉树的存储结构

2.4.1 顺序存储

2.4.1 链式存储

3. 二叉树的顺序存储结构——堆

3.1 堆的存储

3.2 堆的调整

3.2.1 向上调整算法

3.2.2 向下调整算法

3.3 堆的接口实现

3.3.1 初始化

3.3.2 构建

3.3.3 插入

3.3.4 删除

3.3.5 读堆顶元素

3.3.6 判空

3.3.7 堆中元素个数

3.3.7 打印

3.3.8 销毁

3.4 堆的应用

3.4.1 堆排序

3.4.2 TOP-K问题

4. 二叉树的链式存储结构

4.1 二叉树的结点

4.1 二叉树的遍历

4.1.1 前序遍历

4.1.2 中序遍历

4.1.3 后序遍历

4.1.3 层序遍历

4.2 二叉树的接口实现

4.2.1 创建

4.2.2 结点个数

4.2.3 叶子结点个数

4.2.4 第k层结点个数

4.2.5 高度

4.2.6 查找

4.2.7 判断完全二叉树

4.2.8 销毁

---

1. 树

1.1 树的概念

树是n （n≥0）个结点的有限集。当n=0时，称为空树。在任意一棵非空树中应满足：

1. 有且仅有一个特定的称为根的结点。
2. 当n>1时，其余结点可分为m（m>0）个互不相交的有限集T1，T2，…，Tm，其中每个集合本身又是一棵树，并且称为根的子树。

显然，树的定义是递归的，即在树的定义中又用到了其自身，树是一种递归的数据结构。树作为一种逻辑结构，同时也是一种分层结构，具有以下两个特点：

1. 树的根结点没有前驱，除根结点外的所有结点有且只有一个前驱。
2. 树中所有结点可以有零个或多个后继。 

除根结点外，每个结点和其双亲结点都有且仅有一条边，因此n个结点的树有n-1条边。

1.2 树的基本术语

1. 考虑结点K。根A到结点K的唯一路径上的任意结点，称为结点K的祖先。如结点B是结点K的祖先，而结点K是结点B的子孙。路径上最接近结点K的结点E称为K的双亲，而K为结点E的孩子。根A是树中唯一没有双亲的结点。有相同双亲的结点称为兄弟，如结点K和结点L有相同的双亲E，即K和L为兄弟。

2. 树中一个结点的孩子个数称为该结点的度，树中结点的最大度数称为树的度。如结点B的度为2，结点D的度为3，树的度为3。

3. 度大于0的结点称为分支结点（又称非终端结点）；度为0（没有子女结点）的结点称为叶子结点（又称终端结点）。在分支结点中，每个结点的分支数就是该结点的度。

4. 结点的层次从树根开始定义，根结点为第1层，它的子结点为第2层，以此类推。双亲在同一层的结点互为堂兄弟，图中结点G与E，F，H，I，J互为堂兄弟。结点的深度是从根结点开始自顶向下逐层累加的。结点的高度是从叶结点开始自底向上逐层累加的。树的高度（或深度）是树中结点的最大层数。图中树的高度为4。

5. 树中结点的各子树从左到右是有次序的，不能互换，称该树为有序树，否则称为无序树。假设图为有序树，若将子结点位置互换，则变成一棵不同的树。

6. 树中两个结点之间的路径是由这两个结点之间所经过的结点序列构成的，而路径长度是路径上所经过的边的个数。

7. 森林是m（m≥0）棵互不相交的树的集合。森林的概念与树的概念十分相近，因为只要把树的根结点删去就成了森林。反之，只要给m棵独立的树加上一个结点，并把这m棵树作为该结点的子树，则森林就变成了树。

1.3 树的表示

树有很多表示方法，如，双亲表示法、孩子表示法、孩子双亲表示法、孩子兄弟表示法。

孩子兄弟表示法：

typedef int TreeDataType;
struct TreeNode
{
    TreeDataType data;        // 数据域
    struct Node* firstChild;  // 指向第一个孩子
    struct Node* nextBrother; // 指向下一个兄弟
};

2. 二叉树

2.1 二叉树的概念

二叉树是另一种树形结构，其特点是每个结点至多只有两棵子树（即二叉树中不存在度大于2的结点），并且二叉树的子树有左右之分，其次序不能任意颠倒。

与树相似，二叉树也以递归的形式定义。二叉树是n（n≥0）个结点的有限集合：

1. 或者为空二叉树，即n=0。
2. 或者由一个根结点和两个互不相交的被称为根的左子树和右子树组成。左子树和右子树又分别是一棵二叉树。

二叉树是有序树，若将其左、右子树颠倒，则成为另一棵不同的二叉树。即使树中结点只有一棵子树，也要区分它是左子树还是右子树。

二叉树有5种基本形态：

1. 空二叉树
2. 只有根结点
3. 只有左子树
4. 只有右子树
5. 左右子树都有

二叉树与度为2的有序树的区别：

1. 度为2的树至少有3个结点，而二叉树可以为空。
2. 度为2的有序树的孩子的左右次序是相对于另一孩子而言的，若某个结点只有一个孩子，则这个孩子就无须区分其左右次序，而二叉树无论其孩子数是否为2，均需确定其左右次序，即二叉树的结点次序不是相对于另一结点而言，而是确定的。

2.2 特殊的二叉树

2.2.1 满二叉树

树的每层都含有最多的结点。

2.2.2 完全二叉树

高度为h、有n个结点的二叉树，当且仅当其每个结点都与高度为h的满二叉树中编号为1~n的结点一一对应时，称为完全二叉树。

2.3 二叉树的性质

1. 若规定根结点的层数为1，则一棵非空二叉树的第i层上最多有个结点。

2. 若规定根结点的层数为1，则深度为h的二叉树的最大结点数是。

3. 对于任何一棵二叉树， 如果度为0的叶结点个数为n0， 度为2的分支结点个数为n2，则有n0=n2＋1。

设度为0,1和2的结点个数分别为n0，n1，n2，结点总数n=n0+n1+n2。

设二叉树边的个数为E，E=n-1，E=n1+2*n2。

可得n0=n2＋1。

4. 若规定根结点的层数为1，具有n个结点的完全二叉树的高度为 或 。

假设第n个结点在第h层。

① 深度为h-1的二叉树的最大结点数< n ≤ 深度为h的二叉树的最大结点数：

所以，

② 深度为h-1的二叉树的最大结点数+1 ≤ n < 深度为h的二叉树的最大结点数+1：

 

所以，

5. 对于具有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 二叉树的存储结构

2.4.1 顺序存储

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

2.4.1 链式存储

二叉树的链式存储结构是指，用链表来表示一棵二叉树，即用链来指示元素的逻辑关系。 通常的方法是链表中每个结点由三个域组成，数据域和左右指针域，左右指针分别用来给出该结点左孩子和右孩子所在的链结点的存储地址 ，这样的存储结构称为二叉链表。增加指向双亲结点的指针后，变为三叉链表。

3. 二叉树的顺序存储结构——堆

如果有一个关键码的集合K = {k0,k1,k2,…,kn-1}，把它的所有元素按完全二叉树的顺序存储方式存储在一个一维数组中，并满足：Ki<=K2i+1 且Ki<=K2i+2（或Ki>=K2i+1 且Ki>=K2i+2）i = 0，1，2…，将根结点最大的堆叫做最大堆或大根堆，根结点最小的堆叫做最小堆或小根堆。

堆（heap）的性质：

1. 堆中某个结点的值总是不大于或不小于其双亲结点的值。
2. 堆总是一棵完全二叉树。

3.1 堆的存储

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

3.2 堆的调整

3.2.1 向上调整算法

在堆的末尾插入一个数据，再进行调整，使其仍然是一个堆。以建大根堆为例，向上调整算法的思想：将目标结点的关键字与其双亲结点的关键字比较。若目标结点的关键字>其双亲结点的关键字，则交换关键字，然后令双亲结点作为新的目标结点，一层层向上调整。

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)
	{
		if (a[child] > a[parent])
		{
			Swap(&a[child], &a[parent]);
			child = parent;
			parent = (child - 1) / 2;
		}
		else
		{
			break;
		}
	}
}

3.2.2 向下调整算法

左右子树必须已经是一个堆，才能从根结点开始向下调整。以建大根堆为例，向下调整算法的思想：将根结点的关键字与其左右孩子的关键字中较大的进行比较。若其孩子结点的关键字>根结点的关键字，则交换关键字，然后令孩子结点作为新的根结点，一层层向下调整。

void Swap(HPDataType* p1, HPDataType* p2)
{
	HPDataType tmp = *p1;
	*p1 = *p2;
	*p2 = tmp;
}
 
void AdjustDown(HPDataType* a, int n, int parent)
{
	int child = parent * 2 + 1; // 默认为左孩子
	while (child < n)
	{
		// 保证child指向左右孩子中最大的
		if (child + 1 < n && a[child + 1] > a[child])
		{
			++child; // 如果存在右孩子且右孩子>左孩子，变为右孩子
		}
		// 向下调整
		if (a[child] > a[parent])
		{
			Swap(&a[child], &a[parent]);
			parent = child;
			child = parent * 2 + 1; // 默认为左孩子
		}
		else
		{
			break;
		}
	}
}

3.3 堆的接口实现

3.3.1 初始化

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

3.3.2 构建

给定数组{1, 5, 3, 8, 7, 6}，建大根堆：

3.3.2.1 向上调整建堆

首先把第一个元素看成是一个堆，然后把第二个元素看成要插入的元素，进行向上调整算法，再把第三个元素看成要插入的元素……即从下标为1的元素开始，一个一个进行向上调整算法。

向上调整建堆的时间复杂度：（最坏情况）

总移动步数：

错位相减法：

所以向上调整建堆的时间复杂度为O(n*logn)。

3.3.2.2 向下调整建堆

首先从最后一个结点的双亲结点（即最后一个非叶子结点）开始，进行向下调整算法，再从倒数第二个非叶子结点开始，进行向下调整算法……即从下标为(n-1-1)/2的元素开始，一个一个进行向下调整算法。

向下调整建堆的时间复杂度：（最坏情况）

总移动步数：

错位相减法：

所以向下调整建堆的时间复杂度为O(n)。

void HeapCreate(HP* php, HPDataType* a, int n)
{
	assert(php);
	php->a = (HPDataType*)malloc(sizeof(HPDataType) * n);
	if (php->a == NULL)
	{
		perror("malloc failed");
		exit(-1);
	}
	memcpy(php->a, a, sizeof(HPDataType) * n);
	php->size = php->capacity = n;
 
	// 向上调整建堆 O(n*logn)
    /*
	for (int i = 1; i < n; ++i)
	{
		AdjustUp(php->a, i);
	}
    */
 
	// 向下调整建堆 O(n) 更优
	for (int i = (n - 1 - 1) / 2; i >= 0; --i)
	{
		AdjustDown(php->a, n, i);
	}
}

3.3.3 插入

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, sizeof(HPDataType) * newCapacity);
		if (tmp == NULL)
		{
			perror("realloc failed");
			exit(-1);
		}
		php->a = tmp;
		php->capacity = newCapacity;
	}
	// 堆的末尾插入
	php->a[php->size] = x;
	php->size++;
	// 向上调整
	AdjustUp(php->a, php->size - 1);
}

3.3.4 删除

void HeapPop(HP* php)
{
	assert(php);
	assert(php->size > 0);
	// 根结点和最后一个结点交换，然后删除根结点
	Swap(&php->a[0], &php->a[php->size - 1]);
	php->size--;
	// 向下调整
	AdjustDown(php->a, php->size, 0);
}

3.3.5 读堆顶元素

HPDataType HeapTop(HP* php)
{
	assert(php);
	assert(php->size > 0);
	return php->a[0];
}

3.3.6 判空

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

3.3.7 堆中元素个数

int HeapSize(HP* php)
{
	assert(php);
	return php->size;
}

3.3.7 打印

void HeapPrint(HP* php)
{
	assert(php);
	for (int i = 0; i < php->size; ++i)
	{
		printf("%d ", php->a[i]);
	}
	printf("\n");
}

3.3.8 销毁

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

3.4 堆的应用

3.4.1 堆排序

堆排序的基本思想：首先将存放在L[1...n]中的n个元素建成初始堆，由于堆本身的特点（以大根堆为例），堆顶元素就是最大值。将堆顶元素和堆底元素交换，然后堆底元素不再看作是堆里的内容。此时堆顶元素已不满足大根堆的性质，堆被破坏，将堆顶元素向下调整使其继续保持大根堆的性质，循环操作，直到所有元素都排完序。

大根堆：

交换：向下调整：

交换：向下调整：  

交换：向下调整：  

交换：向下调整： 

交换：此时堆排序完成

void AdjustDown(int* a, int n, int parent)
{
	int child = parent * 2 + 1; // 默认为左孩子
	while (child < n)
	{
		// 保证child指向左右孩子中最大的
		if (child + 1 < n && 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 HeapSort(int* a, int n)
{
	// 从最后一个非叶子结点开始，逐步向下调整建堆
	for (int i = (n - 1 - 1) / 2; i >= 0; --i)
	{
		AdjustDown(a, n, i);
	}
	// 排序
	int end = n - 1;
	while (end > 0)
	{
		swap(&a[0], &a[end]);  // 堆顶元素和堆底元素交换
		AdjustDown(a, end, 0); // 从堆顶元素进行向下调整
		--end;				   // 缩小堆的范围
	}
}

3.4.2 TOP-K问题

求前k个最大的元素的思路：取数据集合中前k个元素，建立k个元素的小根堆，依次遍历剩下的n-k个数据，比堆顶数据大，就替换堆顶，再向下调整，最后最大的k个就在这个小根堆里面。

void AdjustDown(int* a, int n, int parent)
{
	int child = parent * 2 + 1; // 默认为左孩子
	while (child < n)
	{
		// 保证child指向左右孩子中最大的
		if (child + 1 < n && 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 PrintTopK(int* a, int n, int k)
{
	// 动态开辟k个空间的数组minHeap
	int* minHeap = (int *)malloc(sizeof(int) * k);
	if (minHeap == NULL)
	{
		perror("malloc failed");
		exit(-1);
	}
	// 将数组a的前k个元素赋值给minHeap的k个元素
	int i = 0;
	for (i = 0; i < k; i++)
	{
		minHeap[i] = a[i];
	}
	// 创建小根堆
	for (i = (k - 1 - 1) / 2; i >= 0; --i)
	{
		AdjustDown(minHeap, k, i);
	}
	// 替换堆顶
	for (i = k; i < n; i++)
	{
		if (a[i] > minHeap[0])
		{
			minHeap[0] = a[i];
			AdjustDown(minHeap, k, 0);
		}
	}
	// 打印堆中元素
	for (i = 0; i < k; ++i)
	{
		printf("%d ", minHeap[i]);
	}
	// 释放空间
	free(minHeap);
}

LeetCode 692.前K个高频单词

使用哈希表记录每个单词出现的频率，key——单词，value——频率。

在哈希表中取单词和它的频率，按频率建立小根堆，但是当两个单词的频率相同的时候，我们需要的是字典序较小的，此时是一个大根堆的属性，在定义比较器的时候需要注意：

• 当两个字符串出现的频率不同的时候，需要的是基于频次比较的小根堆
• 当两个字符串出现的频率相同的时候，需要的是基于字典序比较的大根堆

维持堆中元素不超过k个，如果超过k个就把堆顶弹出。

遍历完哈希表后，堆中剩余元素就是前k大元素。

class Solution {
    typedef pair<string, int> PSI;
    struct cmp
    {
        bool operator()(const PSI& e1, const PSI& e2)
        {
            if (e1.second == e2.second) // 频率相同，按字典序创建大根堆
                return e1.first < e2.first;
            return e1.second > e2.second; // 频率不相同，按频率创建小根堆
        }
    };
 
public:
    vector<string> topKFrequent(vector<string>& words, int k) {
        unordered_map<string, int> hash; // key——单词，value——频率
        // 初始化哈希表
        for (auto& s : words)
        {
            hash[s]++;
        }
        // 创建堆
        priority_queue<PSI, vector<PSI>, cmp> heap;
        // TOP-K主逻辑
        for (auto& psi : hash)
        {
            heap.push(psi);
            if (heap.size() > k)
            {
                heap.pop();
            }
        }
        // 提取结果
        vector<string> ans(k);
        for (int i = k - 1; i >= 0; i--)
        {
            ans[i] = heap.top().first;
            heap.pop();
        }
        return ans;
    }
};

4. 二叉树的链式存储结构

4.1 二叉树的结点

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

4.1 二叉树的遍历

4.1.1 前序遍历

1. 访问根结点
2. 遍历左子树
3. 遍历右子树

void PreOrder(BTNode* root)
{
	if (root == NULL)
    {
		printf("NULL ");
		return;
	}
	printf("%d ", root->data);
	PreOrder(root->left);
	PreOrder(root->right);
}

4.1.2 中序遍历

1. 遍历左子树
2. 访问根结点
3. 遍历右子树

void InOrder(BTNode* root)
{
	if (root == NULL)
	{
		printf("NULL ");
		return;
	}
	InOrder(root->left);
	printf("%d ", root->data);
	InOrder(root->right);
}

4.1.3 后序遍历

1. 遍历左子树
2. 遍历右子树
3. 访问根结点

void PostOrder(BTNode* root)
{
	if (root == NULL)
	{
		printf("NULL ");
		return;
	}
	PostOrder(root->left);
	PostOrder(root->right);
	printf("%d ", root->data);
}

4.1.3 层序遍历

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

void LevelOrder(BTNode* root)
{
	Queue q;
	QueueInit(&q);
    // 根结点入队
	if (root)
		QueuePush(&q, root);
	// 一个结点出队，该结点的左右孩子入队，这一层都出完了，下一层都入队了
	while (!QueueEmpty(&q))
	{
        // 队头出队
		BTNode* front = QueueFront(&q);
		printf("%d ", front->data);
		QueuePop(&q);
        // 孩子入队
		if (front->left)
		{
			QueuePush(&q, front->left);
		}
		if (front->right)
		{
			QueuePush(&q, front->right);
		}
	}
	printf("\n");
	QueueDestroy(&q);
}

4.2 二叉树的接口实现

4.2.1 创建

通过前序遍历的数组"ABD##E#H##CF##G##"构建二叉树

BTNode* TreeCreate(BTDataType* a, int* pi)
{
	if (a[*pi] == '#')
	{
		(*pi)++;
		return NULL;
	}
	BTNode* root = (BTNode*)malloc(sizeof(BTNode));
	if (root == NULL)
	{
		perror("malloc failed");
		return NULL;
	}
	root->data = a[(*pi)++];
	root->left = TreeCreate(a, pi);
	root->right = TreeCreate(a, pi);
	return root;
}

4.2.2 结点个数

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

4.2.3 叶子结点个数

int TreeLeafSize(BTNode* root)
{
	if (root == NULL)
	{
		return 0;
	}
	if (root->left == NULL && root->right == NULL)
	{
		return 1;
	}
	return TreeLeafSize(root->left) + TreeLeafSize(root->right);
}

4.2.4 第k层结点个数

int TreeKLevelSize(BTNode* root, int k)
{
	if (root == NULL)
		return 0;
	if (k == 1)
		return 1;
	return TreeKLevelSize(root->left, k - 1) + TreeKLevelSize(root->right, k - 1);
}

4.2.5 高度

int TreeHeight(BTNode* root)
{
	if (root == NULL)
	{
		return 0;
	}
	int leftHeight = TreeHeight(root->left);
	int rightHeight = TreeHeight(root->right);
	return leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;
}

4.2.6 查找

BTNode* TreeFind(BTNode* root, BTDataType x)
{
	if (root == NULL)
		return NULL;
	if (root->data == x)
		return root;
	BTNode* ret1 = TreeFind(root->left, x);
	if (ret1)
		return ret1;
	BTNode* ret2 = TreeFind(root->right, x);
	if (ret2)
		return ret2;
	return NULL;
}

4.2.7 判断完全二叉树

bool TreeComplete(BTNode* root)
{
	Queue q;
	QueueInit(&q);
	if (root)
	{
		QueuePush(&q, root);
	}
	while (!QueueEmpty(&q))
	{
		BTNode* front = QueueFront(&q);
		QueuePop(&q);
		if (front == NULL)
		{
			break;
		}
		else
		{
			QueuePush(&q, front->left);
			QueuePush(&q, front->right);
		}
		// 出到空以后，如果后面全是空，则是完全二叉树
		while (!QueueEmpty(&q))
		{
			BTNode* front = QueueFront(&q);
			QueuePop(&q);
			if (front != NULL)
			{
				QueueDestroy(&q);
				return false;
			}
		}
		QueueDestroy(&q);
		return true;
	}
}

4.2.8 销毁

void TreeDestroy(BTNode* root)
{
	if (root == NULL)
	{
		return;
	}
	TreeDestroy(root->left);
	TreeDestroy(root->right);
	free(root);
}