[数据结构与算法]二叉树的相关操作

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));
	node->data = x;
	node->left = NULL;
	node->right = NULL;

	return node;
}

BTNode* CreatBinaryTree()
{
	BTNode* node1 = BuyNode('A');
	BTNode* node2 = BuyNode('B');
	BTNode* node3 = BuyNode('C');
	BTNode* node4 = BuyNode('D');
	BTNode* node5 = BuyNode('E');
	BTNode* node6 = BuyNode('F');

	node1->left = node2;
	node1->right = node3;
	node2->left = node4;
	node3->left = node5;
	node3->right = node6;
	return node1;
}

计算结点个数

思路

1. 该结点为空，总结点个数+0
2. 该结点不为空，结点个数为1+左结点个数+右结点个数

代码实现

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

运行结果

计算叶子结点个数

思路

1. 结点不为叶结点，计算该结点左右两边的叶子结点个数
2. 结点为空，返回0
3. 结点为叶结点，返回1

代码实现

int BinaryTreeLeafSize(BTNode* root)
{
	if (root == NULL)
	{
		return 0;
	}
	else if (root->left == NULL&&root->right == NULL)
	{
		return 1;
	}
	else
	{
		return BinaryTreeLeafSize(root->left) + BinaryTreeLeafSize(root->right);
	}
}

运行结果

二叉树第k层节点个数

思路

向下遍历，结点为第K层时，返回1，结点为空结点时，返回0

代码实现

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

	int leftDepth = BinaryTreeDepth(root->left);
	int rightDepth = BinaryTreeDepth(root->right);

	return leftDepth > rightDepth ? 1 + leftDepth : 1 + rightDepth;
}

运行结果

二叉树查找值为x的节点

思路

遍历向下找即可

代码实现

BTNode* BinaryTreeFind(BTNode* root, BTDataType x)
{
	if (root == NULL)
		return NULL;

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

	struct BinaryTreeNode* retleft = BinaryTreeFind(root->left, x);
	if (retleft)
	{
		return retleft;
	}

	struct BinaryTreeNode* retright = BinaryTreeFind(root->right, x);
	if (retleft)
	{
		return retright;
	}

	return NULL;
}

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

思路

1. 利用队列，访问结点时将其左右结点入队列
2. 访问队列，如果在访问完所有结点前遇到空结点则该树不为完全二叉树，否则该树是完全二叉树

注意：队列结构中存放的数据为二叉树结点

typedef struct BinaryTreeNode* QDataType;

typedef struct QueueNode
{
	struct QueueNode* next;
	QDataType data;
}QueueNode;

代码实现

bool 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;
		}
		QueuePush(&q, front->left);
		QueuePush(&q, front->right);
	}

	while (!QueueEmpty(&q))
	{
		BTNode* front = QueueFront(&q);
		QueuePop(&q);
		if (front)
		{
			QueueDestroy(&q);
			return false;
		}
	}

	QueueDestroy(&q);
	return true;
}

二叉树销毁

从下往上，从左往右挨个释放

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

	BinaryTreeDestory(root->left);
	BinaryTreeDestory(root->right);
	free(root);
}