线索二叉树的介绍、创建和添加线索的方法，堆树的介绍、存储和创建以及实现方法

一、线索二叉树

1. 线索二叉树介绍：

​ 我们在遍历二叉树时会得到一个线性的序列结果，但遍历的过程是非线性的(函数递归)，该过程比较耗时，我们可以借助结点中的空的指针，增加一些线索，使用二叉树能够使用循环语句进行遍历，提高二叉树遍历的速度。

2. 添加线索的方法：

​ 在二叉树的结点中增加两个成员，使它的结点成为以下结构：

// 使用这种结点可以构建二叉双向链表，作为二叉树的存储结点，也叫作线索链表
typedef struct TreeNode
{
	int val;				// 数据域
	bool ltag;				// false == ltag left指针域指向是当前结点的左子树，否则指向的是它的前驱结点
	struct TreeNode* left;
	bool rtag;				// false == rtag right指针域指向是当前结点的右子树，否则指向的是它的后继结点
	struct TreeNode* right;
}

3. 线索二叉树的表示与实现：

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

#define Link false
#define Thread true

//线索二叉树结构体
typedef struct TreeNode
{
	int val;
	bool ltag;
	struct TreeNode *left;
	bool rtag;
	struct TreeNode *right;
} TreeNode;

//结点创建
TreeNode *create_node(int val)
{
	TreeNode *root = malloc(sizeof(TreeNode));
	root->val = val;
	root->ltag = false;
	root->left = NULL;
	root->rtag = false;
	root->right = NULL;
	return root;
}

//添加树的内部结构
void _add_tree(TreeNode **rpp, TreeNode *node)
{
	if (NULL == *rpp)
	{
		*rpp = node;
		return;
	}

	if (node->val < (*rpp)->val)
		_add_tree(&(*rpp)->left, node);
	else
		_add_tree(&(*rpp)->right, node);
}
//添加树函数
void add_tree(TreeNode **rpp, int val)
{
	_add_tree(rpp, create_node(val));
}

//初始化树函数
TreeNode *init_tree(int *arr, size_t len)
{
	TreeNode *root = NULL;
	for (int i = 0; i < len; i++)
	{
		_add_tree(&root, create_node(arr[i]));
	}
	return root;
}

//按中序遍历树的内部函数
void _in_order_tree(TreeNode *root)
{
	if (NULL == root)
		return;

	_in_order_tree(root->left);
	printf("%d ", root->val);
	_in_order_tree(root->right);
}

//按中序遍历树
void in_order_tree(TreeNode *root)
{
	_in_order_tree(root);
	printf("\n");
}


static TreeNode *pre;//定义全局的前驱结点

//给树的结点添加线索
void in_threading(TreeNode *root)
{
	if (NULL == root)
		return;

	in_threading(root->left);
	if (NULL == root->left)
	{
		root->ltag = Thread;
		root->left = pre;
	}
	if (NULL == pre->right)
	{
		pre->rtag = Thread;
		pre->right = root;
	}
	pre = root;
	in_threading(root->right);
}

//给树添加线索
TreeNode *in_order_threading(TreeNode *root)
{
	TreeNode *head = create_node(-1);
	head->ltag = Link;
	head->rtag = Thread;
	head->right = head;

	if (NULL == root)
		head->left = head;
	else
	{
		head->left = root;
		pre = head;
		in_threading(root);
		pre->right = head;
		pre->rtag = Thread;
	}
	return head;
}

//遍历树（搜索二叉树方式）
void in_order_thread_tree(TreeNode *head)
{
	TreeNode *node = head->left;
	while (node != head)
	{
		while (Link == node->ltag)
			node = node->left;
		printf("%d ", node->val);
		while (node->rtag == Thread && node->right != head)
		{
			node = node->right;
			printf("%d ", node->val);
		}
		node = node->right;
	}
}
主函数
int main(int argc, const char *argv[])
{
	int arr[10];
	for (int i = 0; i < 10; i++)
	{
		arr[i] = rand() % 100;
	}

	TreeNode *root = init_tree(arr, 10);
	in_order_tree(root);

	// 添加线索
	TreeNode *inhead = in_order_threading(root);
	// 遍历线索二叉树
	in_order_thread_tree(inhead);
	return 0;
}

二、堆树

1. 堆结构介绍：

​ 大根堆：根结点的值比它的左右子树都要大，同时它的左右子树也遵循这项规则，也就是说一棵树的根结点中存储的是这棵树中的最大值，这种完全二叉树叫大根堆。

​ 小根堆：根结点的值比它的左右子树都要小，同时它的左右子树也遵循这项规则，也就是说一棵树的根结点中存储的是这棵树中的最小值，这种完全二叉树叫小根堆。

​ 堆结构是是一种特殊的完全二叉树，它与堆栈完全不同且没有任何关系，我们可以从堆中顺序获取堆顶的数据，也可以使用大根堆、小根堆的规则可以对顺序表进行排序。

2. 堆结构的存储：

​ 堆结构是完全二叉树，所以特别适合顺序表存储，因此要熟练掌握二叉树性质5的分式：

​ 有一个n个结点的完全二叉树，结点按照从上到下从左到右的顺序排序为1~n。

​ 1、i > 1时，i/2就是它的双亲结点。

​ 2、i*2是i的左子树，当i*2>n时，则i没有左子树。

​ 3、2*i+1是i的右子树，2*i+1>n时，则i没有右子树。

3. 堆结构的表示与实现：

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

#define PARENT(index) ((index + 1) / 2 - 1)
#define LEFT_CHILD(index) ((index + 1) * 2 - 1)
#define RIGHT_CHILD(index) ((index + 1) * 2)

#define swap_mem(p1, p2, size)  \
	do                          \
	{                           \
		char temp[size];        \
		memcpy(temp, p1, size); \
		memcpy(p1, p2, size);   \
		memcpy(p2, temp, size); \
	} while (0)

#define swap(a, b) swap_mem(&a, &b, sizeof(a))

typedef struct MaxHeap
{
	int *base;
	size_t cnt;
	size_t cal;
} MaxHeap;

// 把base中的数据调整为堆结构
void adjust_max_heap(MaxHeap *heap, int index)
{
	// 从index下标处，向上调整堆结构
	while (index > 0)
	{
		// 计算出双亲下标
		int parent = PARENT(index);
		// 计算出双亲结点的左子树
		int left = LEFT_CHILD(parent);
		// 如果左子树下标合法并且值大于双亲，则与双亲交换
		if (left < heap->cnt && heap->base[left] > heap->base[parent])
			swap(heap->base[left], heap->base[parent]);

		int right = RIGHT_CHILD(parent);
		// 如果右子树下标合法并且值大于双亲，则与双亲交换
		if (right < heap->cnt && heap->base[right] > heap->base[parent])
			swap(heap->base[right], heap->base[parent]);

		// 向上一层
		index = parent;
	}
}

// 创建一个空堆
MaxHeap *create_max_heap(size_t cal)
{
	MaxHeap *heap = malloc(sizeof(MaxHeap));
	heap->base = malloc(sizeof(int) * cal);
	heap->cal = cal;
	heap->cnt = 0;
	return heap;
}

// 初始化堆
MaxHeap *init_max_heap(int *arr, size_t len)
{
	MaxHeap *heap = malloc(sizeof(MaxHeap));
	heap->base = malloc(sizeof(int) * len);
	memcpy(heap->base, arr, sizeof(int) * len);
	heap->cal = len;
	heap->cnt = len;

	// 从叶子结点出发向上调整,最后一个叶子结点的双亲结点就是最后一个非叶子结点
	for (int i = len - 1; i > len / 2; i--)
		adjust_max_heap(heap, i);

	return heap;
}

// 销毁堆
void destroy_max_heap(MaxHeap *heap)
{
	free(heap->base);
	free(heap);
}

// 堆是否为空
bool empty_max_heap(MaxHeap *heap)
{
	return 0 == heap->cnt;
}

// 堆是否为满
bool full_max_heap(MaxHeap *heap)
{
	return heap->cal == heap->cnt;
}

// 入堆
bool push_max_heap(MaxHeap *heap, int val)
{
	if (full_max_heap(heap))
		return false;

	// 在末尾添加一个新结点
	heap->base[heap->cnt++] = val;
	// 从最后一个结点出发向上调整
	adjust_max_heap(heap, heap->cnt - 1);
}

// 出堆
bool pop_max_heap(MaxHeap *heap)
{
	if (empty_max_heap(heap))
		return false;

	// 使用最后一个结点覆盖根结点,并且结点的数量减1
	heap->base[0] = heap->base[--heap->cnt];

	// 从根结点出发向下调整
	int parent = 0;
	while (parent < heap->cnt)
	{
		// 假定根结点是根、左右中的最大结点,并计算出它的左右子树的下标
		int max = parent, left = LEFT_CHILD(parent), right = RIGHT_CHILD(parent);

		// 如果左子树下标合法，且左子树的值大于最大结点，则把左子记作最大结点
		if (left < heap->cnt && heap->base[max] < heap->base[left])
			max = left;
		// 如果右子树下标合法，且右子树的值大于最大结点，则把右子记作最大结点
		if (right < heap->cnt && heap->base[max] < heap->base[right])
			max = right;

		// 如果最大结点就是根结点，则不需要再向下调整，
		if (max == parent)
			break;

		// 把最大结点与根结点交换，从从大结点处继续向下调整
		swap(heap->base[max], heap->base[parent]);
		parent = max;
	}
	return true;
}

// 堆顶
int top_max_heap(MaxHeap *heap)
{
	if (empty_max_heap(heap))
		return -1;
	return heap->base[0];
}

// 元素数量
size_t size_max_heap(MaxHeap *heap)
{
	return heap->cnt;
}

int main(int argc, const char *argv[])
{
	MaxHeap *heap = create_max_heap(10);
	int arr[10];
	for (int i = 0; i < 10; i++)
	{
		arr[i] = rand() % 100;
		printf("%d ", arr[i]);
		push_max_heap(heap, arr[i]);
	}
	printf("\n");
	while (!empty_max_heap(heap))
	{
		printf("%d ", top_max_heap(heap));
		pop_max_heap(heap);
	}
	return 0;
}

​

​

​