C语言数据结构之二叉树详解

    typedef int DataType;
    struct Node
    {
         struct Node* firstChild1; 
         struct Node* pNextBrother; 
         DataType data; 
    };

   // 二叉链
   struct BinaryTreeNode
   {
    struct BinTreeNode* _pLeft; // 指向当前节点左孩子
    struct BinTreeNode* _pRight; // 指向当前节点右孩子
    BTDataType _data; // 当前节点值域
   }
   // 三叉链
   struct BinaryTreeNode
   {
    struct BinTreeNode* _pParent; // 指向当前节点的双亲
    struct BinTreeNode* _pLeft; // 指向当前节点左孩子
    struct BinTreeNode* _pRight; // 指向当前节点右孩子
    BTDataType _data; // 当前节点值域
   }；

typedef int HPDataType;
typedef struct Heap
{
	HPDataType* _a;
	int _size;
	int _capacity;
}Heap;

void swap(int *a, int *b);
void AdjustDown(int *a, int parent, int n);
void AdjustUp(int *a, int child, int n);

// 堆的构建
void HeapCreate(Heap* hp, HPDataType* a, int n);
// 堆的销毁
void HeapDestory(Heap* hp);
// 堆的插入
void HeapPush(Heap* hp, HPDataType x);
// 堆的删除
void HeapPop(Heap* hp);
// 取堆顶的数据
HPDataType HeapTop(Heap* hp);
// 堆的数据个数
int HeapSize(Heap* hp);
// 堆的判空
int HeapEmpty(Heap* hp);

// 对数组进行堆排序
void HeapSort(int* a, int n);

void swap(int *a, int *b)
{
	int tmp = *a;
	*a = *b;
	*b = tmp;
}

void AdjustUp(int *a, int child, int n)
{
	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 parent,int n)
{
	int child = parent * 2 + 1;
	while ( child < n)
	{
		if (child + 1 < n && a[child]<a[child + 1])
		{
			++child;
		}
		if(a[child]>a[parent])
		{
			swap(&a[child], &a[parent]);
			parent = child;
			child = (parent * 2) + 1;
		}
		else
		{
			break;
		}
	}
}
void HeapCreate(Heap* hp, HPDataType* a, int n)
{
	assert(hp);
	hp->_a = (HPDataType*)malloc(sizeof(HPDataType)*n);
	if (hp->_a == NULL)
	{
		printf("malloc fail");
		exit(-1);
	}
	for (int i = 0; i < n; ++i)
	{
		hp->_a[i] = a[i];
	}
	hp->_size = hp->_capacity = n;
	for (int i = (n - 2) / 2; i >= 0; --i)
	{
		AdjustDown(hp->_a,i, hp->_size);
	}
}

// 堆的销毁
void HeapDestory(Heap* hp)
{
	assert(hp);
	hp->_size = hp->_capacity = 0;
	free(hp);
}
// 堆的插入
void HeapPush(Heap* hp, HPDataType x)
{
	assert(hp);
	if (hp->_size == hp->_capacity)
	{
		HPDataType* tmp = (HPDataType*)realloc(hp->_a, sizeof(HPDataType)* 2 * hp->_capacity);
		if (tmp == NULL)
		{
			printf("realloc fail");
			exit(-1);
		}
		hp->_a = tmp;
		hp->_a[hp->_size] = x;
		++hp->_size;
		hp->_capacity *= 2;
	}
	else
	{
		hp->_a[hp->_size] = x;
		++hp->_size;
	}
	AdjustUp(hp->_a, hp->_size-1, hp->_size);

}
// 堆的删除
void HeapPop(Heap* hp)
{
	assert(hp);
	assert(hp->_size>0);
	swap(&hp->_a[hp->_size-1], &hp->_a[0]);
	--hp->_size;
	AdjustDown(hp->_a, 0, hp->_size);
}
// 取堆顶的数据
HPDataType HeapTop(Heap* hp)
{
	assert(hp);
	assert(hp->_size>0);
	return hp->_a[0];
}
// 堆的数据个数
int HeapSize(Heap* hp)
{
	assert(hp);
	return hp->_size;
}
// 堆的判空
int HeapEmpty(Heap* hp)
{
	assert(hp);
	return hp->_size == 0 ? 1 : 0;

	for (int i = 0; i < 3; ++i)}

// 对数组进行堆排序
void HeapSort(int* a, int n)
{
	assert(a);
	for (int i = (n - 2) / 2; i >= 0; --i)
	{
		AdjustDown(a, i, n);
	}
	int end = n - 1;
	while (end > 0)
	{
		swap(&a[0], &a[end]);
		AdjustDown(a, 0, end);
		--end;
	}
}

typedef char BTDataType;

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




typedef BTNode* QDataType;
// 链式结构：表示队列 
typedef struct QListNode
{
	struct QListNode* _next;
	QDataType _data;
}QNode;

// 队列的结构 
typedef struct Queue
{
	QNode* _front;
	QNode* _rear;
}Queue;




BTNode* CreateBTNode(BTDataType x);
// 通过前序遍历的数组"ABD##E#H##CF##G##"构建二叉树
BTNode* BinaryTreeCreate(BTDataType* a, int n, int* pi);
// 二叉树销毁
void BinaryTreeDestory(BTNode** root);
// 二叉树节点个数
int BinaryTreeSize(BTNode* root);
// 二叉树叶子节点个数
int BinaryTreeLeafSize(BTNode* root);
// 二叉树第k层节点个数
int BinaryTreeLevelKSize(BTNode* root, int k);
// 二叉树查找值为x的节点
BTNode* BinaryTreeFind(BTNode* root, BTDataType x);
// 二叉树前序遍历 
void BinaryTreePrevOrder(BTNode* root);
// 二叉树中序遍历
void BinaryTreeInOrder(BTNode* root);
// 二叉树后序遍历
void BinaryTreePostOrder(BTNode* root);



// 初始化队列 
void QueueInit(Queue* q);
// 队尾入队列 
void QueuePush(Queue* q, QDataType data);
// 队头出队列 
void QueuePop(Queue* q);
// 获取队列头部元素 
QDataType QueueFront(Queue* q);
// 获取队列队尾元素 
QDataType QueueBack(Queue* q);
// 获取队列中有效元素个数 
int QueueSize(Queue* q);
// 检测队列是否为空，如果为空返回非零结果，如果非空返回0 
int QueueEmpty(Queue* q);
// 销毁队列 
void QueueDestroy(Queue* q);



// 层序遍历
void BinaryTreeLevelOrder(BTNode* root);
// 判断二叉树是否是完全二叉树
int BinaryTreeComplete(BTNode* root);

// 初始化队列 
void QueueInit(Queue* q)
{
	assert(q);
	q->_front = q->_rear = NULL;
}
// 队尾入队列 
void QueuePush(Queue* q, QDataType data)
{
	assert(q);
	QNode *newnode = ((QNode*)malloc(sizeof(QNode)));
	newnode->_data = data;
	newnode->_next = NULL;
	if (q->_rear == NULL)
	{
		q->_front = q->_rear = newnode;
	}
	else
	{
		q->_rear->_next = newnode;
		//q->_rear = q->_rear->_next;
		q->_rear = newnode;
	}
}
// 队头出队列 
void QueuePop(Queue* q)
{
	assert(q);
	assert(!QueueEmpty(q));
	if (q->_front == q->_rear)
	{
		free(q->_front);
		//free(q->_rear);
		q->_front = q->_rear = NULL;
	}
	else
	{
		QNode *cur = q->_front->_next;
		free(q->_front);
		q->_front = cur;
	}
}
// 获取队列头部元素 
QDataType QueueFront(Queue* q)
{
	assert(q);
	assert(!QueueEmpty(q));
	return q->_front->_data;
}
// 获取队列队尾元素 
QDataType QueueBack(Queue* q)
{
	assert(q);
	assert(!QueueEmpty(q));
	return q->_rear->_data;
}
// 获取队列中有效元素个数 
int QueueSize(Queue* q)
{
	assert(q);
	int size = 0;
	QNode* cur = q->_front;
	while (cur)
	{
		++size;
		cur = cur->_next;
	}
	return size;
}
// 检测队列是否为空，如果为空返回非零结果，如果非空返回0 
int QueueEmpty(Queue* q)
{
	assert(q);
	return q->_front == NULL ? 1 : 0;
}
// 销毁队列 
void QueueDestroy(Queue* q)
{
	assert(q);
	QNode *cur = q->_front;
	while (cur)
	{
		QNode *next = cur->_next;
		free(cur);
		cur = next;
	}
	q->_front = q->_rear = NULL;
}






BTNode* CreateBTNode(BTDataType x)
{
	BTNode *node = (BTNode*)malloc(sizeof(BTNode));
	node->_data = x;
	node->_left = NULL;
	node->_right = NULL;
	return node;
}


// 通过前序遍历的数组"ABD##E#H##CF##G##"构建二叉树
BTNode* BinaryTreeCreate(BTDataType* a, int n, int* pi)
{
	if (a[*pi] == '#')
	{
		return NULL;
	}
	BTNode *node = (BTNode*)malloc(sizeof(BTNode));
	node->_data = a[*pi];
	++*pi;
	node->_left = BinaryTreeCreate(a, n, pi);
	++*pi;
	node->_right = BinaryTreeCreate(a, n, pi);
	return node;
}
// 二叉树销毁
void BinaryTreeDestory(BTNode** root)
{
	if (*root != NULL)
	{
		if ((*root)->_left) // 有左孩子
			BinaryTreeDestory(&(*root)->_left); // 销毁左孩子子树
		if ((*root)->_right) // 有右孩子
			BinaryTreeDestory(&(*root)->_right); // 销毁右孩子子树

		free(*root); // 释放根结点
		*root = NULL; // 空指针赋NULL
	}
}
// 二叉树节点个数
int BinaryTreeSize(BTNode* root)
{
	if (root == NULL)
	{
		return 0;
	}
	return BinaryTreeSize(root->_left) + BinaryTreeSize(root->_right) + 1;
}
// 二叉树叶子节点个数
int BinaryTreeLeafSize(BTNode* root)
{
	if (root == NULL)
	{
		return 0;
	}
	if (root->_left == NULL&&root->_right == NULL)
	{
		return 1;
	}
	return BinaryTreeLeafSize(root->_left) + BinaryTreeLeafSize(root->_right);
}
// 二叉树第k层节点个数
int BinaryTreeLevelKSize(BTNode* root, int k)
{
	if (root == NULL)
	{
		return 0;
	}
	if (k == 1)
	{
		return 1;
	}
	return BinaryTreeLevelKSize(root->_left, k - 1) + BinaryTreeLevelKSize(root->_right, k - 1);
}
// 二叉树查找值为x的节点
BTNode* BinaryTreeFind(BTNode* root, BTDataType x)
{
	if (root == NULL)
	{
		return NULL;
	}
	if (root->_data == x)
	{
		return root;
	}
	BTNode* ret=BinaryTreeFind(root->_left,x);
	if (ret != NULL)
	{
		return ret;
	}
	ret = BinaryTreeFind(root->_right, x);
	if (ret != NULL)
	{
		return ret;
	}
	return NULL;
}
// 二叉树前序遍历 
void BinaryTreePrevOrder(BTNode* root)
{
	if (root == NULL)
	{
		//printf("NULL  ");
		return;
	}
	printf("%c  ", root->_data);
	BinaryTreePrevOrder(root->_left);
	BinaryTreePrevOrder(root->_right);
}
// 二叉树中序遍历
void BinaryTreeInOrder(BTNode* root)
{
	if (root == NULL)
	{
		//printf("NULL  ");
		return;
	}
	BinaryTreeInOrder(root->_left);
	printf("%c  ", root->_data);
	BinaryTreeInOrder(root->_right);
}
// 二叉树后序遍历
void BinaryTreePostOrder(BTNode* root)
{
	if (root == NULL)
	{
		//printf("NULL  ");
		return;
	}
	BinaryTreePostOrder(root->_left);
	BinaryTreePostOrder(root->_right);
	printf("%c  ", root->_data);
}
// 层序遍历
void BinaryTreeLevelOrder(BTNode* root)
{
	Queue q;
	QueueInit(&q);
	if (root)
	{
		QueuePush(&q, root);
	}
	while (!QueueEmpty(&q))
	{
		BTNode *front = QueueFront(&q);
		QueuePop(&q);
		printf("%c  ", front->_data);
		if (front->_left)
		{
			QueuePush(&q, front->_left);
		}
		if (front->_right)
		{
			QueuePush(&q, front->_right);
		}
	}
}
// 判断二叉树是否是完全二叉树
int BinaryTreeComplete(BTNode* root)
{
	Queue q;
	QueueInit(&q);
	if (root)
	{
		QueuePush(&q, root);
	}
	while (!QueueEmpty(&q))
	{
		BTNode *front = QueueFront(&q);
		QueuePop(&q);
		if (front == NULL)
		{
			break;
		}
		printf("%s ", front->_data);
		if (front->_left)
		{
			QueuePush(&q, front->_left);
		}
		if (front->_right)
		{
			QueuePush(&q, front->_right);
		}
	}
	while (!QueueEmpty(&q))
	{
		BTNode *front = QueueFront(&q);
		QueuePop(&q);
		if (front != NULL)
		{
			return 0;
		}
	}
	return 1;

}