【数据结构】堆和二叉树详解(下)

<定义二叉树的结构>
typedef char BTDataType;
typedef struct BinaryTreeNode
{
	BTDataType Data;
	struct BinaryTreeNode* left;
	struct BinaryTreeNode* right;
}BTNode;

<创建一个申请结点的函数>
//开辟结点空间的函数
BTNode* BuyNode(char x)
{
	BTNode* node = (BTNode*)malloc(sizeof(BTNode));
	if (node == NULL)
	{
		perror("malloc fail!");
		exit(1);
	}
	//开辟成功 初始化、
	node->Data = x;
	node->left = node->right = NULL;//左孩子和右孩子都为空 为根结点

	//返回根结点
	return node;
}

<接下来就是创建多个结点将它们链接起来>
BTNode* CreatBinaryTree()
{
	BTNode* nodeA = BuyNode('A');
	BTNode* nodeB = BuyNode('B');
	BTNode* nodeC = BuyNode('C');
	BTNode* nodeD = BuyNode('D');
	BTNode* nodeE = BuyNode('E');
	BTNode* nodeF = BuyNode('F');

	nodeA->left = nodeB;
	nodeA->right = nodeC;
	nodeB->left = nodeD;
	nodeC->left = nodeE;
	nodeC->right = nodeF;

	return nodeA;

}

//前序遍历 根-左-右
void preOrder(BTNode* root)
{
	//判断根结点是否为空
	if (root == NULL)
	{
		printf("NULL ");
		return;
	}
	//不为空
	printf("%c ", root->Data);
	preOrder(root->left);
	preOrder(root->right);
}

//中序遍历 左-根-右
void inOrder(BTNode* root)
{
	//判断根结点是否为空
	if (root == NULL)
	{
		printf("NULL ");
		return;
	}
	//不为空
	preOrder(root->left);
	printf("%c ", root->Data);
	preOrder(root->right);
}

//后序遍历 左-右-根
void postOrder(BTNode* root)
{
	//判断根结点是否为空
	if (root == NULL)
	{
		printf("NULL ");
		return;
	}
	//不为空
	preOrder(root->left);
	preOrder(root->right);
	printf("%c ", root->Data);
}

// ⼆叉树结点个数 版本1                             存在问题 当多次调用的时候size会叠加
int size = 0;
int BinaryTreeSize(BTNode* root)
{
	//判断根结点是否为空
	if (root == NULL)
	{
		//printf("NULL ");
		return 0;
	}
	//不为空
	size++;
	BinaryTreeSize(root->left);
	BinaryTreeSize(root->right);
	return size;
}

//版本二  借助一个指针 通过形参的改变影响实参
int BinaryTreeSize2(BTNode* root, int* psize)
{
	if (root == NULL)
	{
		return 0;
	}
	//注意优先级
	(*psize)++;
	BinaryTreeSize2(root->left,psize);
	BinaryTreeSize2(root->right,psize);
	return *psize;
}

//版本三 大化小递归 找未知
int BinaryTreeSize3(BTNode* root)
{
	//递归结束条件
	if (root == 0)
	{
		return 0;
	}
	//结点个数=根节点+左子树结点总数+右子树结点总数
	return 1 + BinaryTreeSize3(root->left) +
		BinaryTreeSize3(root->right);
}

// ⼆叉树叶⼦结点个数
int BinaryTreeLeafSize(BTNode* root)
{
	if (root == 0)
	{
		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);
}

//⼆叉树的深度/⾼度
int BinaryTreeDepth(BTNode* root)
{
	if (root == NULL)
	{
		return 0;
	}
	//高度=根结点+max(左子树高度，右子树高度)
	int leftdepth = BinaryTreeDepth(root->left);
	int rightdepth = BinaryTreeDepth(root->right);
	//累加操作
	return 1 + 
		(leftdepth > rightdepth ? leftdepth : rightdepth);
}

// ⼆叉树查找值为x的结点
BTNode* BinaryTreeFind(BTNode* root, BTDataType x)
{
	if (root == NULL)
	{ 
		return 0;
	}
	//判断x是否等于结点值 这是一个重要的递归结束条件
	if (root->Data == x)
	{
		return root;//这个root是广义的根结点 不是二叉树的第一个结点 
	}
	//左子树查找
	BTNode* leftFind = BinaryTreeFind(root->left,x);
	if (leftFind)
	{
		return leftFind;
	}
	//右子树查找
	BTNode* rihgtFind = BinaryTreeFind(root->right,x);
	if (rihgtFind)
	{
		return rihgtFind;
	}
	//左右子树都遍历完后就说明找不到了
	return NULL;
}

// ⼆叉树销毁 使用后序遍历销毁 左-右-根
void BinaryTreeDestory(BTNode** root)
{
	if (root == NULL)
	{
		return;
	}
	//递归左子树  (*root)->left 拿到的是左子树这个成员
	BinaryTreeDestory(&(*root)->left);
	BinaryTreeDestory(&(*root)->right);
	//递归查找完后 将根节点的值释放掉
	free(*root);
	//释放后置空
	*root = NULL;
}

//层序遍历
void leverOrder(BTNode* root)
{
	//创建一个队列
	Queue q;
	//队列的初始化
	QueueInit(&q);
	//入队 插入根结点
	QueuePush(&q, root);
	while (!QueueEmpty(&q))
	{
		//取队头，打印队头 出对头
		BTNode* top = QueueFront(&q);//top拿到了
		printf("%c ", top->Data);
		QueuePop(&q);
		//出完队判断top(根结点)的左右孩子是否为空 不为空则入队
		//判断左孩子
		if (top->left)
			QueuePush(&q,top->left);
		//判断右孩子
		if (top->left)
			QueuePush(&q,top->left);
	}
	QueueDestroy(&q);
}

//判断是否为完全二叉树
bool BinaryTreeComplete(BTNode* root)
{
	Queue q;
	QueueInit(&q);
	//将根节点root入队列保证队列不为空
	QueuePush(&q, root);
	//第一次循环
	while (!QueueEmpty(&q))
	{
		//取队头，出队头
		BTNode* top = QueueFront(&q);
		QueuePop(&q);

		//判断出出来的队头是否为空 为空则跳出循环 不为空则继续讲根的左右孩子入队列 无论左右孩子是否存在
		if (top == NULL)
		{
			break;
		}
		QueuePush(&q, root->left);
		QueuePush(&q, root->right);
	}
	//跳出第一层循环 此时队列不一定为空 再判断一次
	while (!QueueEmpty(&q))
	{
		//取队头，出队头
		BTNode* top = QueueFront(&q);
		QueuePop(&q);

		//如果第二次循环还能出倒不为空的结点就不是完全二叉树 返回false
		if (top != NULL)
		{
			QueueDestroy(&q);
			return false;
		}
	}
	QueueDestroy(&q);
	//到这里第二次循环都已经结束了 队列彻底为空了 就说明没有出到非空结点 那么就是完全二叉树返回true
	return true;
}