【数据结构】二叉树

2024-10-23 08:45:47

1、树的概念及结构

1.1 树的概念

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

注意：

树形结构中，子树之间不能有交集，否则就不是树形结构

1.2 树的相关概念

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

叶节点或终端节点：度为0的节点称为叶节点；如上图：B、C、H、I...等节点为叶节点

分支节点：度不为0的节点；如上图：D、E、F、G...等节点为分支节点

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

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

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

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

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

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

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

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

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

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

1.3 树的表示

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

2、二叉树的概念及结构

2.1 二叉树的概念

一棵二叉树是结点的一个有限集合，该集合:

或者为空
由一个根节点加上两棵别称为左子树和右子树的二叉树组成

注意：

对于任意的二叉树都是由以下几种情况复合而成的：

2.2 特殊的二叉树

满二叉树：一个二叉树，如果每一个层的结点数都达到最大值，则这个二叉树就是满二叉树。也就是说，如果一个二叉树的层数为k，且结点总数是 (2 ^ k) - 1，则它就是满二叉树。
完全二叉树：前k - 1层都是满的，最后一层可以不满，但是从左到右是连续的。（节点范围是 [2 ^ (k - 1) , (2 ^ k) - 1] ）。

2.3 二叉树的性质

若规定根节点的层数为1，则一棵非空二叉树的第 i 层上最多有2 ^ (i - 1)个结点。
若规定根节点的层数为1，则深度为 h 的二叉树的最大结点数是(2 ^ h) - 1。
对任何一棵二叉树，如果度为0的叶结点个数为 n0, 度为2的分支结点个数为 n2, 则有 n0 = n2 + 1。
若规定根节点的层数为1，具有 n 个结点的满二叉树的深度，h = $\log_{2}(n + 1)$ 。对数函数_百度百科 (baidu.com)
若度为1的结点个数为 n1, 度为2的结点个数为 n2，一共有 n 个结点，则总边数与度之间的关系为：n - 1 = 0 * n0 + 1 * n1 + 2 * n2。（对于任何树都成立）
在完全二叉树中，如果节点总个数为奇数，则没有度为1的节点；如果节点总个数为偶数，只有一个度为1的节点。
对于具有 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否则无右孩子

2.4 二叉树的存储结构

二叉树一般可以使用两种结构存储，一种顺序结构，一种链式结构。

顺序存储：

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

完全二叉树父子间下标关系：

父亲下标找孩子：

leftchild = parent * 2 + 1

rightchild = parent * 2 + 2

孩子找父亲：

parent = (child - 1) / 2

链式存储：

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

3、二叉树顺序结构及实现

3.1 堆的概念及结构

如果有一个关键码的集合K = { $k_{0}, k_{1}, k_{2}, ..., k_{n-1}$ }，把它的所有元素按完全二叉树的顺序存储方式存储在一个一维数组中，并满足： $K_{i} <= K_{2*i+1}$ 且 $K_{i} <= K_{2*i+2}$ ，i = 0，1，2...，则称为小堆，反之为大堆。将根节点最大的堆叫做大根堆，根节点最小的堆叫做小堆或小根堆。

堆的性质：

堆中某个节点的值总是不大于或不小于其父节点的值
堆总是一棵完全二叉树

3.2 堆的实现

3.2.1 堆向下调整算法

现在我们给出一个数组，逻辑上看做一颗完全二叉树。我们通过从根节点开始的向下调整算法可以把它调整成一个小堆。向下调整算法有一个前提：左右子树必须是一个堆，才能调整。

int array[] = {27,15,19,18,28,34,65,49,25,37};

3.2.2 堆的创建

下面我们给出一个数组，这个数组逻辑上可以看做一颗完全二叉树，但是还不是一个堆，现在我们通过算法，把它构建成一个堆。根节点左右子树不是堆，我们怎么调整呢？这里我们从倒数的第一个非叶子节点的子树开始调整，一直调整到根节点的树，就可以调整成堆。

int a[] = {1,5,3,8,7,6};

3.2.3 建堆时间复杂度

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

等比数列求和公式_百度百科 (baidu.com)

因此：（向下）建堆的时间复杂度为O(N)

3.2.4 堆的插入

先插入一个10到数组的尾上，再进行向上调整算法，直到满足堆

3.2.5 堆的删除

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

3.2.6 堆的代码实现

Heap.h

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

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

void HeapInit(HP* php);
void HeapDestroy(HP* php);
void Swap(HPDataType* p1, HPDataType* p2);
void AdjustUp(HPDataType* a, int child);
void AdjustDown(int* a, int n, int parent);
void HeapPush(HP* php, HPDataType x);
void HeapPop(HP* php);
HPDataType HeapTop(HP* php);
bool HeapEmpty(HP* php);
int HeapSize(HP* php);

Heap.c

#include "Heap.h"

void HeapInit(HP* php)
{
	assert(php);

	php->a = NULL;
	php->size = 0;
	php->capacity = 0;
}

void HeapDestroy(HP* php)
{
	assert(php);

	free(php->a);
	php->a = NULL;
	php->size = 0;
	php->capacity = 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)
	{
		if (a[child] < a[parent])
		{
			swap(&a[child], &a[parent]);
			child = parent;
			parent = (child - 1) / 2;
		}
		else
		{
			break;
		}
	}
}

//堆向下调整算法（默认为小堆）
void AdjustDown(int* a, int n, int parent)
{
	//先默认找左孩子
	int child = (parent * 2) + 1;

	while (child < n)
	{
		//先把child更新为左右孩子比较小的那一个
		//如果child + 1 = n，表示parent没有右孩子，不需要再判断谁大谁小了
		if (child + 1 < n && a[child] > a[child + 1])
		{
			child = child + 1;
		}

		//然后再拿小的和双亲结点的值比较
		if (a[child] < a[parent])
		{
			swap(&a[child], &a[parent]);
			parent = child;
			child = (parent * 2) + 1;
		}
		else
		{
			break;
		}
	}
}

void HeapPush(HP* php, HPDataType x)
{
	assert(php);

	if (php->capacity == php->size)
	{
		int newcapacity = php->capacity == 0 ? 4 : php->capacity * 2;
		HPDataType* tmp = (HPDataType*)realloc(php->a, sizeof(HPDataType) * newcapacity);
		if (NULL == tmp)
		{
			perror("realloc fail");
			return;
		}

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

	php->a[php->size] = x;
	php->size++;
	AdjustUp(php->a, php->size - 1);
}

//删除堆顶数据
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);
}

HPDataType HeapTop(HP* php)
{
	assert(php);
	assert(!HeapEmpty(php));

	return php->a[0];
}

bool HeapEmpty(HP* php)
{
	assert(php);

	return php->size == 0;
}

int HeapSize(HP* php)
{
	assert(php);

	return php->size;
}

test.c

#include "Heap.h"

int main()
{
	HP hp;
	HeapInit(&hp);
	int a[] = { 65,100,70,32,50,60 };
	int sz = sizeof(a) / sizeof(int);
	for (int i = 0; i < sz; i++)
	{
		HeapPush(&hp, a[i]);
	}
	while (!HeapEmpty(&hp))
	{
		int top = HeapTop(&hp);
		printf("%d ", top);
		HeapPop(&hp);
	}
    HeapDestroy(&hp);
	return 0;
}

3.3 堆的应用

3.3.1 堆排序

第一种方法：新建了一个堆

在我们刚才 Heap.c（小堆）的基础上：

void HeapSort(int* a, int n)
{
	HP hp;
	HeapInit(&hp);

	for (int i = 0; i < n; i++)
	{
		HeapPush(&hp, a[i]);
	}//此时能保证根节点是堆的最小值，但是不能保证是有序的

	int i = 0;
	while (!HeapEmpty(&hp))
	{
		int top = HeapTop(&hp);
		a[i++] = top;
		HeapPop(&hp);//此时重新调整之后根节点又是新的最小值
	}
}

int main()
{
	int a[] = { 7,8,3,5,1,9,5,4 };
	HeapSort(a, sizeof(a) / sizeof(int));
	return 0;
}

第二种方法：在原数组的基础上排序（推荐这种方法）

void HeapSort(int* a, int n)
{
	//降序，建小堆
	//第0个位置上的值直接看做堆，从第一个位置开始向上调整
	for (int i = 1; i < n; i++)
	{
		AdjustUp(a, i);
	}//此时就变成了小堆：1 3 5 4 5 9 7 8，但不是有序的
	//end是下标，n-1就是最后一个数据的下标
	int end = n - 1;
	while (end > 0)
	{
		Swap(&a[0], &a[end]);//数组中最后一个元素是最小的数
		AdjustDown(a, end, 0);//这里end是数据个数，第一次最后一个数据不看做堆中的数据
		//选出了次小的数据
		end--;
	}
}

int main()
{
	int a[] = { 7,8,3,5,1,9,5,4 };
	HeapSort(a, sizeof(a) / sizeof(int));
	for (int i = 0; i < 8; i++)
	{
		printf("%d ", a[i]);
	}
	return 0;
}

void HeapSort(int* a, int n)
{
	//升序，建大堆
	//求最后一个元素的双亲节点的下标
	for (int i = (n - 1 - 1) / 2; i >= 0; i--)
	{
		AdjustDown(a, n, i);
	}//此时就变成了大堆：9 8 7 5 1 3 5 4，但不是有序的

	int end = n - 1;
	while (end > 0)
	{
		Swap(&a[0], &a[end]);//数组中最后一个元素是最大的数
		//为什么要这样做呢？
		//因为每次交换第一个和最后一个数据不会改变中间节点的母女关系
		//再向下调整就可以找到次大的数据
		AdjustDown(a, end, 0);
		end--;
	}
}

int main()
{
	int a[] = { 7,8,3,5,1,9,5,4 };
	HeapSort(a, sizeof(a) / sizeof(int));
	for (int i = 0; i < 8; i++)
	{
		printf("%d ", a[i]);
	}
	return 0;
}

练习：

一组记录排序码为(5 11 7 2 3 17),则利用堆排序方法建立的初始堆为

A(11 5 7 2 3 17)

B(11 5 7 2 17 3)

C(17 11 7 2 3 5)

D(17 11 7 5 3 2)

选C，可以自己测试一下

3.3.2 TOP-K问题

TOP- K问题：即求数据结合中前K个最大的元素或者最小的元素，一般情况下数据量都比较大。

对于 Top-K 问题，能想到的最简单直接的方式就是排序，但是：如果数据量非常大，排序就不太可取了。最佳的方式就是用堆来解决，基本思路如下：

用数据集合中前 K 个元素来建堆

前 K 个最大的元素，则建小堆
前 K 个最小的元素，则建大堆

用剩余的 N-K 个元素依次与堆顶元素来比较，不满足则替换堆顶元素，将剩余 N-K 个元素依次与堆顶元素比完之后，堆中剩余的 K 个元素就是所求的前 K 个最小或者最大的元素。

void CreateNData()
{
	int n = 10000;
	srand(time(0));
	const char* file = "data.txt";
	FILE* fin = fopen(file, "w");
	if (NULL == fin)
	{
		perror("fopen fail");
		return;
	}

	for (int i = 0; i < n; i++)
	{
		int x = rand() % 100000;
		fprintf(fin, "%d ", x);
	}
	fclose(fin);
}

void PrintTopK(int k)
{
	const char* file = "data.txt";
	FILE* fout = fopen(file, "r");
	if (NULL == fout)
	{
		perror("fopen fail");
		return;
	}

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

	//将文件中的数据写入堆
	for (int i = 0; i < k; i++)
	{
		fscanf(fout, "%d", &kminheap[i]);
	}

	//建小堆
	for (int i = 1; i < k; i++)
	{
		AdjustUp(kminheap, i);
	}

	int val = 0;
	while (!feof(fout))
	{
		fscanf(fout, "%d", &val);
		if (val > kminheap[0])
		{
			kminheap[0] = val;
			AdjustDown(kminheap, k, 0);
		}
	}

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

int main()
{
	CreateNData();
	PrintTopK(5);//找到前5个最大元素
	return 0;
}

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

4.1 二叉树的遍历

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

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

由于被访问的结点必是某子树的根，所以N(Node）、L(Left subtree）和R(Right subtree）又可解释为根、根的左子树和根的右子树。NLR、LNR和LRN分别又称为先根遍历、中根遍历和后根遍历。

前序遍历

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 (NULL == node)
	{
		perror("malloc fail");
		return;
	}

	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;
}

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

int main()
{
	BTNode* root = CreatBinaryTree();
	PrevOrder(root);
	return 0;
}

中序遍历

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

后序遍历

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

4.1.2 层序遍历

修改一下之前队列的代码：

void LevelOrder(BTNode* root)
{
	Queue q;
	QueueInit(&q);

	if (root)
		QueuePush(&q, root);
	while (!QueueEmpty(&q))
	{
		BTNode* front = QueueFront(&q);
		QueuePop(&q);
		printf("%d ", front->data);
		if (front->left)
			QueuePush(&q, front->left);
		if (front->right)
			QueuePush(&q, front->right);
	}
	printf("\n");
	QueueDestroy(&q);
}

4.2 节点个数以及高度

// 二叉树节点个数
int BTreeSize(BTNode* root)
{
	if (root == NULL)
		return 0;
	return BTreeSize(root->left)
		+ BTreeSize(root->right)
		+ 1;
}

// 二叉树叶子节点个数
int BTreeLeafSize(BTNode* root)
{
	if (root == NULL)
		return 0;
	if (root->left == NULL
		&& root->right == NULL)
		return 1;

	return BTreeLeafSize(root->left)
		+ BTreeLeafSize(root->right);
}

// 二叉树的高度
int BTreeHeight(BTNode* root)
{
	if (root == NULL)
		return 0;

	int leftHigh = BTreeHeight(root->left);
	int rightHigh = BTreeHeight(root->right);

	return leftHigh > rightHigh ? leftHigh + 1 : rightHigh + 1;
}

// 二叉树第k层节点个数
int BTreeLevelKSize(BTNode* root, int k)
{
	assert(k > 0);

	if (root == NULL)
		return 0;

	if (k == 1)
		return 1;

	return BTreeLevelKSize(root->left, k - 1)
		+ BTreeLevelKSize(root->right, k - 1);
}

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

	if (root->data == x)
		return root;

	BTNode* ret1 = BTreeFind(root->left, x);
	if (ret1)
		return ret1;

	BTNode* ret2 = BTreeFind(root->right, x);
	if (ret2)
		return ret2;

	return NULL;
}

4.3 练习题

4.3.1 单值二叉树

965. 单值二叉树 - 力扣（LeetCode）

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;

	return isUnivalTree(root->left)
		&& isUnivalTree(root->right);
}

4.3.2 检查两棵树是否相同*

100. 相同的树 - 力扣（LeetCode）

bool isSameTree(struct TreeNode* p, struct TreeNode* q) {
    if (p == NULL && q == NULL)
        return true;
    if (p == NULL || q == NULL)
        return false;
    if (p->val != q->val)
        return false;

    return isSameTree(p->left, q->left) 
        && isSameTree(p->right, q->right);
}

4.3.3 对称二叉树*

101. 对称二叉树 - 力扣（LeetCode）

bool is_Symmetric(struct TreeNode* LeftRoot, struct TreeNode* RightRoot) 
{
    //都为空
    if (LeftRoot == NULL && RightRoot == NULL)
        return true;
    //其中一个为空
    if (LeftRoot == NULL || RightRoot == NULL)
        return false;
    //都不为空
    if (LeftRoot->val != RightRoot->val)
        return false;

    return is_Symmetric(LeftRoot->left, RightRoot->right)
        && is_Symmetric(LeftRoot->right, RightRoot->left);
}

bool isSymmetric(struct TreeNode* root) {
    return is_Symmetric(root->left,root->right);
}

4.3.4 二叉树的前序遍历

144. 二叉树的前序遍历 - 力扣（LeetCode）

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

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

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

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

4.3.5 另一棵树的子树

572. 另一棵树的子树 - 力扣（LeetCode）

bool isSubtree(struct TreeNode* root, struct TreeNode* subRoot)
{
    if (root == NULL)
        return false;
    if (isSameTree(root, subRoot) == true)
        return true;
    return isSubtree(root->left, subRoot)
        || isSubtree(root->right, subRoot);
}

4.4 二叉树的创建和销毁

二叉树遍历_牛客题霸_牛客网

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

typedef char 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 = node->right = NULL;

	return node;
}

// 通过前序遍历的数组"ABC##DE#G##F###"构建二叉树
BTNode* CreateTree(BTDataType* a, int* pi)
{
	if (a[*pi] == '#')
	{
		(*pi)++;
		return NULL;
	}

	BTNode* root = BuyNode(a[*pi]);
	(*pi)++;

	root->left = CreateTree(a, pi);
	root->right = CreateTree(a, pi);

	return root;
}

void InOrder(BTNode* root)
{
	if (root == NULL)
		return;

	InOrder(root->left);
	printf("%c ", root->data);
	InOrder(root->right);
}

int main()
{
	char a[100];
	scanf("%s", a);
	int i = 0;
	BTNode* root = CreateTree(a, &i);
	InOrder(root);
	printf("\n");
	return 0;
}

判断二叉树是否为完全二叉树

bool BTreeComplete(BTNode* root)
{
	Queue q;
	QueueInit(&q);

	if (root)
		QueuePush(&q, root);

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

		if (front == NULL)
			break;

		QueuePush(&q, root->left);
		QueuePush(&q, root->right);
	}

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

		if (front)
		{
			QueueDestroy(&q);
			return false;
		}
	}
	QueueDestroy(&q);

	return true;
}

二叉树的销毁

void BinaryTreeDestroy(BTNode** root)
{
	if (root == NULL || *root == NULL)
	{
		return;
	}

	BinaryTreeDestroy(&(*root)->left);
	BinaryTreeDestroy(&(*root)->right);
	free(*root);
	*root = NULL;
}

码农公寓