二叉树的创建和各个函数功能的实现

文章目录

• • 看看头文件
  • 通过前序遍历的数组"ABD##E#H##CF##G##"构建二叉树
  • 求树节点的个数
  • 叶子节点的个数
  • 求第K层节点的个数
  • 找节点
  • 前，中，后序遍历
  • 层序遍历
  • 判断一颗树是否是完全二叉树

看看头文件

这棵二叉树的形状应该是

#include
#include
#include

typedef char BTDataType;

typedef struct BTreeNode
{
	BTDataType data;
	struct BTreeNode* left;
	struct BTreeNode* right;
}BTNode;

// 通过前序遍历的数组"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 BinaryTreeLevelOrder(BTNode* root);

// 判断二叉树是否是完全二叉树
int BinaryTreeComplete(BTNode* root);

通过前序遍历的数组"ABD##E#H##CF##G##"构建二叉树

BTNode* BinaryTreeCreate(BTDataType* a, int n, int* pi)
{
	if (a[*pi] == '#')
	{
		(*pi)++;
		return NULL;
	}
	BTNode* root = (BTNode*)malloc(sizeof(BTNode));  //如果是根据中序和后序遍历呢？，只需要把这两行
	root->data = a[(*pi)++];                         // 放到root->left和root->right的中间和后面即可

	root->left = BinaryTreeCreate(a,n,pi);
	root->right = BinaryTreeCreate(a,n,pi);

	return root;
}

求树节点的个数

图解

int BinaryTreeSize(BTNode* root)
{
	if (root == NULL)
		return 0;

    //1是自己
	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层节点的个数

求第K层节点的个数，就是求第K-1层的左右孩子的个数

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

找节点

BTNode* BinaryTreeFind(BTNode* root, BTDataType x)
{
	if (root == NULL)
		return NULL;
	if (root->data == x)
		return root;
	//不为空就是找到了
	BTNode* left= BinaryTreeFind(root->left,x);
	if (left  != NULL)
		return left;
	BTNode* right= BinaryTreeFind(root->right,x);
	if (right != NULL)
		return right;

	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 != NULL)
	{
		QueuePush(&q, root);   //先入根
	}

	while (!QueueEmpty(&q))
	{
		BTNode* front = QueueFront(&q); //取出队头元素
		QueuePop(&q);                   //出队
		printf("%c ", front->data);

		if (front->left != NULL)    //不为空才入
		{
			QueuePush(&q, front->left);
		}
		if (front->right != NULL)
		{
			QueuePush(&q, front->right);
		}
	}
	QueueDestroy(&q);
}

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

核心思路：出一个节点，入它的左右孩子，这时候孩子是空也要入，当出到空的时候，
只需要判断后面有没有空就可以了，完全二叉树后面肯定是没有空的

int BinaryTreeComplete(BTNode* root)
{
	Queue q;
	QueueInit(&q);
	if (root != NULL)
	{
		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 != NULL)
			return false;
	}
	return true;

	QueueDestroy(&q);
}