• [C语言数据结构]树

    提示：文章写完后，目录可以自动生成，如何生成可参考右边的帮助文档

    文章目录

    1.树

    1.1树的概念：

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

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

    1.2树与非树

    ①子树是不相交的

    ②除了根节点以外，每个节点有且仅有一个父节点

    ③一颗N个节点的树有N-1条边

    例如：一些非树：

    img

    1.3一些关于树的概念：

    img

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

    (2)叶节点或者终端节点：度为零的节点称为叶节点；如上图：B、C、H、I…等节点为叶节点

    (3)非终端节点或分支节点：度不为零的节点；如上图：D、E、F、G…等节点为分支节点

    (4)双亲节点或父节点若一个节点含有子节点，则称这个节点为双亲节点或者父节点；

    如上图：A是B的父节点

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

    (6)兄弟节点：具有相同父节点的节点互称为兄弟节点；如上图：B、C是兄弟节点
    **(7)树的度：**一棵树中，最大的节点的度称为树的度； 如上图：树的度为6

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

    (9)树的高度或深度：树中节点的最大层次； 如上图：树的高度为4
    (10)堂兄弟节点：双亲在同一层的节点互为堂兄弟；如上图：H、I互为兄弟节点

    **(11)节点的祖先：**从根到该节点所经分支上的所有节点；如上图：A是所有节点的祖先
    (12)子孙：以某节点为根的子树中任一节点都称为该节点的子孙。如上图：所有节点都是A的子孙

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

    1.4树的一些表示方法：

    首先我们要思考对于树来说他的分支可以只有一个，很多个，也可以没有。所以我们得余姚一种结构可以高效的表示这种结构；大佬想出了一种方法来高效的表示树这种结构：叫孩子兄弟表示法；

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

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7

    如图：

    img

    2.二叉树

    2.1概念：

    个人认为可以理解为是度为2的树；

    2.2二叉树的特点

    1. 每个结点最多有两棵子树，即二叉树**不存在度大于2的结点。**

    2. 二叉树的子树有左右之分，其子树的次序不能颠倒。

    img

    2.3满二叉树和完全二叉树：

    1. 满二叉树：一个二叉树，如果每一个层的结点数都达到最大值，则这个二叉树就是满二叉树。也就是说，如果一个二叉树的层数为K，且结点总数是(2^k) -1 ，则它就是满二叉树。
    2. 完全二叉树：对于深度为K的，有n个结点的二叉树，当且仅当其每一个结点都与深度为K的满二叉树中编号从1至n的结点一一对应时称之为完全二叉树。 要注意的是满二叉树是一种特殊的完全二叉树。（前n-1层都是满的，第n层是连续的）

    img

    2.4二叉树的性质：

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

    2.5堆：

    是将一个**完全二叉树**按顺序存储的方式存储在一个一维数组当中

    2.5.1大堆和小堆的概念：

    大堆：满足每个父节点大于自己的孩子节点的堆；

    小堆：满足每个父节点小于自己的孩子节点的堆；

    2.5.2堆的性质：

    ①堆中的某个节点的值总是不大于或不小于其父节点的值；

    ②堆总是一个完全二叉树；

    ③孩子和父节点的关系：

    ​ parent = (child - 1) / 2;

    ​ child(left) = parent * 2 + 1;

    ​ child(right) = parent * 2 + 2;

    2.5.3堆的实现：

    (1)结构的声明：

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

}HP;

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8

    (2)堆的初始化：

    //堆的初始化
void HeapInit(HP* php)
{
	assert(php);
	php->a = NULL;
	php->capacity = 0;
	php->size = 0;
}


    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9

    (3)堆的销毁：

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

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8

    (4)堆的插入：

    先判断空间是否够用，如果不够用就进行扩容。将x放到堆的最后一个位置，然后进行向上调整；

    //堆的插入
void HeapPush(HP* php, HPDataType x)
{
	assert(php);
	if (php->size == php->capacity)
	{
		int newcapacity = (php->capacity == 0 ? 4 : php->capacity * 2);
		HPDataType* newa = (HPDataType*)realloc(php->a, newcapacity * sizeof(HPDataType));
		if (newa == NULL)
		{
			perror("realloc of HeapPush failed ");
			exit(-1);
		}
		php->a = newa;
		php->capacity = newcapacity;
	}
	php->a[php->size] = x;
	php->size++;
	AdjustUp(php->a, php->size - 1);
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20

    (5)向上调整：

    ①向上调整的方法就是，孩子节点和自己的父节点来比较，符合条件就交换(大堆或小堆)，直到不能交换或者交换到根节点;

    ②向上调整的条件：除了最后一个之前所有的数据已经构成一个堆

    //向上调整  O(N* log N)
//这个例子是小堆的例子
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;
		}
	}
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19

    (6)向下调整：

    ①向下调整的方法(以小堆为例)：

    就是父节点和自己的孩子节点来比较，如果孩子节点中存在比父节点小的节点，那么就将父节点和孩子节点中最小的那个进行交换；

    ②向下调整的条件是(小堆为例)：根节点的左子树和右子树都是小堆；

    //向下调整   O(N)
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;
		}
	}

}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24

    (7)堆的打印：

    //堆的打印
void  HeapPrint(HP* php)
{
	for (int i = 0; i < php->size; i++)
	{
		printf("%d ", php->a[i]);
	}
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8

    (8)堆的删除：

    堆的删除是从根节点开始删除，但是不能破坏树的结构，所以删除的时候也是要遵循一定的逻辑；

    方法就是：先交换根节点和最后一个节点的位置(注意这里交换完之后是满足向下调整的条件的)，然后将最后一个节点进行向下调整即可；

    //堆的删除
void HeapDown(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);
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10

    (9)取堆顶的数据：

    //取堆顶的数据
HPDataType HeapTop(HP* php)
{
	assert(php);
	assert(php->size > 0);
	return php->a[0];
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7

    (10)堆的打印：

    //堆的打印
void  HeapPrint(HP* php)
{
	for (int i = 0; i < php->size; i++)
	{
		printf("%d ", php->a[i]);
	}
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8

    (11)交换函数：

    //交换函数
void Swap(HPDataType* a, HPDataType* b)
{
	HPDataType temp = *a;
	*a = *b;
	*b = temp;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7

    (12)堆是否为空：

    //堆是否为空
bool HeapEmpty(HP* php)
{
	return php->size == 0;
}

    • 1
    • 2
    • 3
    • 4
    • 5

    (13)创建堆的接口：

    ①根据需要申请所需要的空间；

    ②然后根据从数组最尾部的位置开始进行向下调整算法即可构建一个堆

    //创建堆的函数
void HeapCreate(HP* php, HPDataType* a, int n)
{
	assert(php);
	php->a = (HPDataType*)realloc(php->a ,sizeof(HPDataType) * n);
	if (php->a == NULL)
	{
		perror("realloc fail");
		exit(-1);
	}
	memcpy(php->a, a, sizeof(HPDataType) * n);
	php->size = php->capacity = n;
	//建堆算法
	for (int i = (n - 1 - 1) / 2; i >= 0; i--)
	{
			AdjustDown(a, n, i);
	}
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18

    (14)堆排序：

    这里以排升序为例子：

    ①如果是升序就需要建立大堆每次将好的大堆的根节点和尾部的节点进行交换；

    ②交换之后再进行一次向下调整，就产生了一个新的大堆(除去刚才交换到尾部的函数进行调整)；

    重复上述两步，直到将所有的待调整的元素为0时就停止，就可以得到一个升序的数组了，但是这个数组不一定是一个堆；

    //堆排序
void HeapSort(HPDataType* a, size_t n)
{
	//升序：大堆
	for (int i = (n - 1 - 1) / 2; i >= 0; i--)
	{
		AdjustDown(a, n, i);
	}
	int end = n - 1;
	while (end > 0)
	{
		Swap(&a[end], &a[0]);
		AdjustDown(a, end, 0);
		--end;
	}
	for (int i = 0; i < n; i++)
	{
		printf("%d ", a[i]);
	}
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20

    2.5.4 top k问题：

    如下这个例子就是生成大量的随机数然后用堆来获取其中的最大的k个数据：

    具体方法就是：

    ①先利用大量数据中的前k个数据来建立一个小堆；

    ②然后再依次遍历剩下的数据，如果有数据大于根节点位置的数据那么就交换；

    ③然后在进行依次向下调整；

    如此循环②③两步直到遍历结束，那么产生的最后一个小堆里面就是top k；

    复杂度的分析：

    ①时间复杂度：O(K + (N - k) * log k) = O(N * log K);

    首先建立一个k个节点的小堆，复杂度为k, 然后剩下的每个数据都需要向下调整时间复杂度为(N-K)*logK;

    ②空间复杂度：O(K)

    只需要占用一个大小为k的数组；

    void test2()
{
	//造数据
	int n = 1000;
	int k = 5;
	srand((unsigned int)time(NULL));
	FILE* fin = fopen("data.txt", "w");
	if (fin == NULL)
	{
		perror("fopen failed");
		exit(-1);
	}
	for (int i = 0; i < n; i++)
	{
		int val = rand();
		fprintf(fin, "%d\n", val);
	}
	fclose(fin);


    //开始运算topk
	HPDataType  minheap[5];
	FILE* fout = fopen("data.txt", "r");
	if (fout == NULL)
	{
		perror("fopen failed");
		exit(-1);
	}
	for (int i = 0; i < k; i++)
	{
		fscanf(fout, "%d", &minheap[i]);
	}

	//建立一个小堆
	for (int i = (k - 1 - 1) / 2; i >= 0; i--)
	{
		AdjustDown(minheap, k, i);
	}
	int val = 0;
	while (fscanf(fout, "%d", &val) != EOF)
	{
		if (val > minheap[0])
		{
			minheap[0] = val;
			AdjustDown(minheap, k, 0);
		}
	}
	for (int i = 0; i < k; i++)
	{
		printf("%d ", minheap[i]);
	}
	fclose(fout);
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53

    2.5.5向下调整和向上调整的时间复杂度的分析：

    ①向上调整：

    在这里插入图片描述

    可得：向上调整的时间复杂度为O(N);

    ②向上调整：

    [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-DsYKvmmp-1670250197250)(C:\Users\jason\AppData\Roaming\Typora\typora-user-images\image-20221125215123008.png)]

    带入之后O(N*log N);

    2.6链式二叉树：

    2.6.1链式二叉树的定义：

    和上面那种孩子兄弟表示表示法相比这种表示方法时才有左子树和右子树的方式；

    也就是说每个节点内部都有一个数据域和两个指针域，两个指针域分别指向该节点的左子树和右子树；

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

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7

    2.6.2创建一个树：

    这里是利用了前序顺序来创建一个树；

    可以对应牛客网的一个题目：

    二叉树遍历_牛客题霸_牛客网 (nowcoder.com)

    //创建树
BTNode* Creat(BTNode* root)
{
		char ch;
		ch = getchar();
		if (ch == '#') {
			return NULL;
		}
		else {
			root = (BTNode*)malloc(sizeof(BTNode));
			root->data = ch;
			root->left = Creat(root->left);
			root->right = Creat(root->right);
		}
		return root;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16

    2.6.3链式二叉树中的其他接口：

    (1)申请节点的函数:

    //申请节点
BTNode* BuyNode(BTDataType x)
{
	BTNode* node = (BTNode*)malloc(sizeof(BTNode));
	if (node == NULL)
	{
		perror("malloc failed");
		exit(-1);
	}
	node->data = x;
	node->left = node->right = NULL;
	return node;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13

    (2)计算节点的个数：

    这里是用了一个递归的方式来计算：

    ①首先判断这个树是不是一个空树：

    如果是空树就返回0；

    如果不是空树那么我们就返回左子树的节点个数 + 右子树的节点个数 + 1(根节点)；

    //计算结点的个数
int TreeSize(BTNode* root)
{
	return root == NULL ? 0 :
		TreeSize(root->left) + TreeSize(root->right) + 1;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6

    (3)计算叶子节点的个数：

    这里还是调用了一个递归的方法;

    ①如果根节点为空就直接返回0;

    ②如果根节点不为空，但是没有左子树和右子树，那么就返回1;

    ③如果不符合①②的条件那么就返回左子树加右子树的叶子节点(即调用递归);

    //计算叶子节点
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);
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14

    (4)求树的高度：

    这里的话也是利用了递归，但是为了进一步优化减少重复的计算，所以定义了两个整型变量。

    ①如果根节点为空就返回0；

    ②不为空的话就返回左子树和右子树中较大的那个值然后再加上1(也就是根节点)；

    //求树的高度
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;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11

    (5)计算树的第k层有几个节点：

    这里还是利用了递归的方法：

    ①假设根节点为空：直接返回0；

    ②若根节点不为空，而且k == 1的话就返回1(表示第k层中其中的一个节点)；

    ③若根节点不为空且k != 1那么我们就返回左子树的k-1层的节点数和右子树的k-1层的节点树；

    //计算树的第k层有几个节点
int TreeKLeveSize(BTNode* root, int k)
{
	if (root == NULL)
	{
		return 0;
	}
	if (k == 1)
	{
		return 1;
	}
	return TreeKLeveSize(root->left, k - 1) +
		TreeKLeveSize(root->right, k - 1);
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14

    (6)在树中查找

    这里还是利用了递归的思路：

    ①如果根节点为空的话就直接返回NULL；

    ②如果根节点的data刚好和要查找的值相等的话就返回当前节点的地址；

    ③如果①②都不符合的话那么我们就取左子树和右子树寻找：

    这里有一点需要注意的就是我们需要建立一个指针来保存左子树和右子树返回的地址要不然就是无效的递归；

    //在树中查找
BTNode* TreeFind(BTNode* root, BTDataType x)
{
	if (!root)
	{
		return NULL;
	}
	if (root->data == x)
	{
		return root;
	}
	BTNode* ret1 = TreeFind(root->left, x);
	if (ret1)
	{
		return ret1;
	}
	BTNode* ret2 = TreeFind(root->left, x);
	if (ret2)
	{
		return ret2;
	}
    return NULL;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23

    2.6.4四种遍历：

    [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-DF9pFc3I-1670250197251)(C:\Users\jason\AppData\Roaming\Typora\typora-user-images\image-20221126110439058.png)]

    以上图为例，展示下面几种遍历的结果；

    ①前序遍历/先根遍历：(根 左子树 右子树)

    遍历的结果1 2 3 NULL NULL 4 NULL NULL 5 6 NULL NULL NULL

    递归写法：

    //前序递归
void PrevOrder(BTNode* root)
{
	if (root == NULL)
	{
		printf("NULL ");
		return;
	}
	printf("%c ", root->data);
	PrevOrder(root->left);
	PrevOrder(root->right);
}


    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13

    非递归写法：

    对应leetcode题目：

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

    这个方法相对于递归的写法，代码的效率提高了，不需要递归减少了系统的内存开销；

    首先这个方法我们需要创建一个栈，这个栈适用于存储二叉树的**各个节点的指针的数组**；

    （1）入栈的时候是将目前temp所指向的节点存入到栈中；

    （2）出栈的时候是将栈顶的数据给到temp；

    后面两种的非递归入栈和出栈的方式都是和上面相同的，就不过多赘述，只讲不同的地方；

    因为我们是将节点的值存储在数组中返回然后再打印出来的：

    ①所以我们先将根节点入栈；

    ②然后进入循环首先出栈，出栈之后将temp->val放到数组中；

    ③然后先将右节点入栈，在入栈左节点(依据先进后出)；

    ④循环②③两步直到栈中的元素为空为止即：top = -1时；

    typedef struct stack
{
    struct TreeNode** a;
    int top;
}s;
void InitStack(s* stack)
{
    stack->a = (struct TreeNode**)calloc(100, sizeof(struct TreeNode*));
    stack->top = -1;
}
void StackPush(s* stack, struct TreeNode* x)
{
    stack->a[++stack->top] = x;
}
void StackPop(s* stack, struct TreeNode** temp)
{
    if (stack->top < 0) return;
    *temp = stack->a[stack->top--];
}
int* preorderTraversal(struct TreeNode* root, int* returnSize)
{
    if(!root)
    {
        *returnSize = 0;
        return NULL;
    }
    int cnt = 0;
    struct TreeNode* temp;
    s stack;
    int* ret = (int*)malloc(100*sizeof(int));
    InitStack(&stack);
    StackPush(&stack, root);
    while(stack.top > -1)
    {
        StackPop(&stack, &temp);
		ret[cnt++] = temp->val;
        if (temp->right) {
			StackPush(&stack, temp->right);
		}
		if (temp->left) {
			StackPush(&stack, temp->left);
		}
    }
    free(stack.a);
    *returnSize = cnt;
    return ret;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    ②中序遍历/中根遍历：(左子树 根 右子树)

    NULL 3 NULL 2 NULL 4 NULL 1 NULL 6 NULL 5 NULL;

    递归写法：

    //中序递归
void InOrder(BTNode* root)
{
	if (root == NULL)
	{
		printf("NULL ");
		return;
	}
	InOrder(root->left);
	printf("%c ", root->data);
	InOrder(root->right);
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12

    非递归：

    对应leetcode题目：

    94. 二叉树的中序遍历 - 力扣（LeetCode）

    栈的构建和前序都是相同的；

    不同的时循环体内的这里要嵌套while循环，因为要不断的寻找节点的左节点；具体步骤如下：

    ①从根节点开始已知寻找左节点，直到为空，每次都将当前节点入栈；

    ②然后将栈顶的节点出栈，将该节点的数据存入数组，进入该节点的右节点；

    循环上面的①②两步直到栈中为空，且当前节点为空的情况就算是将树遍历结束了；

     typedef struct stack
{
    struct TreeNode** a;
    int top;
}s;
void InitStack(s* stack)
{
    stack->a = (struct TreeNode**)calloc(100, sizeof(struct TreeNode*));
    stack->top = -1;
}
void StackPush(s* stack, struct TreeNode* x)
{
    stack->a[++stack->top] = x;
}
void StackPop(s* stack, struct TreeNode** temp)
{
    if (stack->top < 0) return;
    *temp = stack->a[stack->top--];
}
int* inorderTraversal(struct TreeNode* root, int* returnSize)
{
    if(!root)
    {
        * returnSize = 0;
        return NULL;
    }
    int cnt = 0;
    struct TreeNode* temp = root;
    s stack;
    int* ret = (int*)malloc(100*sizeof(int));
    InitStack(&stack);
    while(temp || stack.top > -1)
    {
        while(temp)
        {
            //不断的去找左子树
            StackPush(&stack, temp);
            temp = temp->left;
        }
        //到尽头之后，将最后一个左子树出栈，然后存入数组；
        StackPop(&stack, &temp);
        ret[cnt++] = temp->val;
        temp = temp->right;
    }
    * returnSize = cnt;
    return ret;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    ③后序遍历/后根遍历：(左子树 右子树 根)

    NULL NULL 3 NULL NULL 4 2 NULL NULL 6 NULL 5 1;

    //后序递归
void PostOrder(BTNode* root)
{
	if (root == NULL)
	{
		printf("NULL ");
		return;
	}
	PostOrder(root->left);
	PostOrder(root->right);
	printf("%c ", root->data);
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12

    非递归方式：

    对应leetcode：

    145. 二叉树的后序遍历 - 力扣（LeetCode）

    后序的非递归方式有点复杂，这里介绍一种从前序非递归方式改造过来的一种方法：

    和前序遍历方法唯一的区别就是这里优先寻找左节点，然后再寻找右节点；

    ①因为根节点在一开始入栈之后就直接出栈了所以最后在栈中的顺序就是 (左节点 右节点)

    ②所以全部遍历完之后(所有节点出栈后)数组中的顺序就是(根 右节点 左节点)；

    ③因此我们这时候只需要将这个数组reverse一下就可以，就产生了后序遍历序列；

    typedef struct stack
{
    struct TreeNode** a;
    int top;
}s;
void InitStack(s* stack)
{
    stack->a = (struct TreeNode**)calloc(100, sizeof(struct TreeNode*));
    stack->top = -1;
}
void StackPush(s* stack, struct TreeNode* x)
{
    stack->a[++stack->top] = x;
}
void StackPop(s* stack, struct TreeNode** temp)
{
    if (stack->top < 0) return;
    *temp = stack->a[stack->top--];
}
void swap(int* a, int *b)
{
    *a = *a ^ *b;
    *b = *b ^ *a;
    *a = *a ^ *b;
}
void reverse(int* a, int cnt)
{
    int left = 0;
    int right = cnt - 1;
    while(left < right)
    {
        swap(&a[left++], &a[right--]);
    }
}
int* postorderTraversal(struct TreeNode* root, int* returnSize)
{
    if(!root)
    {
        *returnSize = 0;
        return NULL;
    }
    int cnt = 0;
    struct TreeNode* temp;
    s stack;
    int* ret = (int*)malloc(100*sizeof(int));
    InitStack(&stack);
    StackPush(&stack, root);
    while(stack.top > -1)
    {
        StackPop(&stack, &temp);
		ret[cnt++] = temp->val;
        if (temp->left) {
			StackPush(&stack, temp->left);
		}
        if (temp->right) {
			StackPush(&stack, temp->right);
		}
    }
    free(stack.a);
    *returnSize = cnt;
    reverse(ret, cnt);
    return ret;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    ④层序遍历

    层序遍历：指的是从二叉树的第一层(根节点)开始，自上而下逐层遍历，同层内按从左到右的顺序逐个节点进行访问。

    由二叉树的层次遍历的要求可以知道，当一层访问完之后，按该层节点访问的次序，再对各节点的左，右孩子节点进行访问。这一个访问过程的特点就是，先访问的节点其子节点也将先访问，这一特点符合队列的特点所以说我们采用队列的方式。在这里实现层序遍历；

    算法如下：

    首先根节点入队，当队列非空时，重复如下操作；

    ①队头节点出队，并访问出队节点；

    ②出队节点的非空左右孩子节点入队；

    typedef BTNode* QdataType;

typedef struct QueueNode
{
	QdataType data;
	struct QueueNode* next;

}QueueNode;

typedef struct Queue
{
	QueueNode* head;
	QueueNode* tail;
	size_t size;
}Queue;
//队列的初始化
void InitQueue(Queue* pq)
{
	pq->head = NULL;
	pq->head = NULL;
	pq->size = 0;
}
//队列的销毁
void QueueDestroy(Queue* pq)
{
	assert(pq);
	QueueNode* cur = pq->head;
	while (cur != NULL)
	{
		QueueNode* next = cur->next;
		free(cur);
		cur = next;
	}
	pq->head = pq->tail = NULL;
}

//入队列
void QueuePush(Queue* pq, QdataType x)
{
	assert(pq);
	QueueNode* NewNode = (QueueNode*)malloc(sizeof(QueueNode));
	NewNode->next = NULL;
	NewNode->data = x;
	if (pq->head == NULL)
	{
		pq->head = NewNode;
		pq->tail = NewNode;
	}
	else
	{
		pq->tail->next = NewNode;
		pq->tail = NewNode;
	}
	pq->size++;
}

//出队列
void QueuePop(Queue* pq, BTNode** temp)
{
	assert(pq);
	assert(!QueueEmpty(pq));
	//剩余一个节点的情况
	if (pq->head->next == NULL)
	{
		*temp = pq->head->data;
		free(pq->head);
		pq->head = pq->tail = NULL;
	}
	else
	{
		QueueNode* del = pq->head;
		pq->head = pq->head->next;
		*temp = del->data;
		free(del);
	}
	pq->size--;
}

//判断队列是否为空
bool QueueEmpty(Queue* pq)
{
	assert(pq);
	return pq->head == NULL && pq->tail == NULL;
}
//二叉树的层序遍历
void LevelOrder(BTNode* root)
{
	Queue q;
	BTNode* temp;
	InitQueue(&q);
	if(root)
	QueuePush(&q, root);
	while (!QueueEmpty(&q))
	{
		QueuePop(&q, &temp);
		printf("%c ", temp->data);
		if (temp->left)
			QueuePush(&q, temp->left);
		if (temp->right)
			QueuePush(&q, temp->right);
	}
	QueueDestroy(&q);
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70
    • 71
    • 72
    • 73
    • 74
    • 75
    • 76
    • 77
    • 78
    • 79
    • 80
    • 81
    • 82
    • 83
    • 84
    • 85
    • 86
    • 87
    • 88
    • 89
    • 90
    • 91
    • 92
    • 93
    • 94
    • 95
    • 96
    • 97
    • 98
    • 99
    • 100
    • 101
    • 102
    • 103

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

    算法原理：利用层序遍历的为框架来构建；

    ①首先进行层序遍历，假设遇到空节点就退出遍历(不一行需要遍历结束)；

    ②这时候有两种情况就是：

    Ⅰ队列中剩下的节点都是空节点（完全二叉树）；

    Ⅱ队列中剩下的节点不都是空节点（存在不为空的节点，即不为完全二叉树）；

    //判断二叉树是否是完全二叉树
bool TreeComplete(BTNode* root)
{
	Queue q;
	BTNode* temp;
	InitQueue(&q);
	if (root)
		QueuePush(&q, root);
	while (!QueueEmpty(&q))
	{
		QueuePop(&q, &temp);
		if (!temp)
		{
			break;
		}
		else
		{
			QueuePush(&q,temp->left);
			QueuePush(&q, temp->right);
		}
	}
	while (!QueueEmpty(&q))
	{
		QueuePop(&q, &temp);
		if (temp)
		{
			return false;
		}
	}
	return true;
	QueueDestroy(&q);
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32

    2.6.6由二叉树的前序和中序确定出二叉树

    Ⅰ由前序和中序确定二叉树：

    ①由先序序列中的第一个节点确定根节点D；

    ②由根节点D分割中序序列:D之前的是左子树L的**中序序列，D之后的是右子树R的中序序列**，同时获得L和R的节点个数；

    ③根据左子树的L的节点个数，分割先序序列:第一节点根D，之后是左子树L的线序序列，最后是右子树R的线序序列。

    至此对上面获得的L和R进行上面①~③以此类推对每棵子树进行上述处理，便可确定整棵二叉树；

    例如：已知：

    先序序列：1 2 3 4 5 6

    中序序列：3 2 1 5 4 6

    首先由先序序列可知：根节点为：1 ，然后用1将中序序列分隔开为左子树L: 3 2 右子树R: 5 4 6

    然后先对L分析对照先序序列可知2为左子树L的根节点，然后用2把L序列分割成新的左右子树(因为L是中序序列)

    可知左子树L只有一个左子树3，没有右子树；至此左子树L分析完毕；

    在分析右子树R，对照先序序列可知4为右子树R的根节点，再分割中序序列R可得R的左子树为5右子树为6；至此右子树R也分析完毕 ；

    可得二叉树如下图所示；
    在这里插入图片描述

  • 相关阅读:
    Postgres-on conflict do 引起的core宕问题
    TCP的粘包拆包问题+解决方案
    2021年全国研究生数学建模竞赛华为杯A题相关矩阵组的低复杂度计算和存储建模求解全过程文档及程序
    BGP协议下的路由聚合、路由反射器、联邦的具体配置与运用（详解）
    UE4 Niagara Module Script 初次使用笔记
    单调栈总结
    k8s强制删除pod、svc、namespace（Terminating）
    刨析 代码中常用的 基础 String 对象类(源码解析)
    Python(八)——列表的详细使用
    【python】基础语法
  • 原文地址：https://blog.csdn.net/weixin_61766635/article/details/128194492