【C语言】二叉树

今天我们来讲解一下 与二叉树有关的操作。

二叉树的概念

一颗二叉树是节点的一个有限集合，该集合：

1. 或者为空
2. 由一个根节点加上两颗别称为左子树和右子树的二叉树组成

对于二叉树，都是由一下几种情况复合而成：

除此以外，还有两种特殊的二叉树：

二叉树的性质

二叉树的存储 顺序存储

顺序结构存储就是使用数组来存储，一般使用数组只适合表示完全二叉树，因为不是完全二叉树会有空间的浪费。而现实中使用中只有堆才会使用数组来存储，关于堆我们后面的章节会专门讲解。二叉树顺序存储在物理上是一个数组，在逻辑上是一颗二叉树。

这里附上 堆 的博客：
【C语言】堆

链式存储

二叉树的链式存储结构是指，用链表来表示一棵二叉树，即用链来指示元素的逻辑关系。 通常的方法是链表中每个结点由三个域组成，数据域和左右指针域，左右指针分别用来给出该结点左孩子和右孩子所在的链结点的存储地址 。

前中后遍历

• 前序遍历

void PreOrder(BTNode* root)
{
	if (root == NULL)
	{
		printf("NULL ");
		return;
	}

	printf("%c ", root->data);
	PreOrder(root->left);
	PreOrder(root->right);

}

• 中序遍历

void InOder(BTNode* root)
{
	if (root == NULL)
	{
		printf("NULL ");
		return;
	}

    InOder(root->left);
	printf("%c ", root->data);
	InOder(root->right);

}

• 后序遍历

void PostNode(BTNode* root)
{
	if (root == NULL)
	{
		printf("NULL ");
		return;
	}

	printf("%c ", root->data);
	PreOrder(root->left);
	PreOrder(root->right);

}

二叉树节点个数

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

叶子节点个数

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层节点个数

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

查找值为k的节点

BTNode* BinaryFind(BTNode* root, BTDataType x)
{
	if (root == NULL)
	{
		return NULL;
	}
	if (root->data == x)
	{
		return root;
	}
	BTNode* retLeft = BinaryFind(root, x);
	if (retLeft->data == x)
	{
		return retLeft;
	}
	BTNode* retRight = BinaryFind(root, x);
	if (retRight->data == x)
	{
		return retRight;
	}
	return NULL;
}

二叉树的深度

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

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

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

}

二叉树的销毁

void BinaryTreeDestory(BTNode* root)
{
	if (root == NULL)
	{
		return;
	}
	BinaryTreeDestory(root->left);
	BinaryTreeDestory(root->right);
	free(root);
}

判断二叉树是否为完全二叉树 二叉树基础oj练习 检查两棵树是否相同

bool isSameTree(BTNode* p, BTNode* q)
{
	if (p == NULL || q == NULL)
	{
		return false;
	}
	if (p == NULL && q == NULL)
	{
		return false;
	}
	if (p->data != q->data)
	{
		return false;
	}
	return isSameTree(p->left, q->right) && isSameTree(p->right, q->right);

}

对称二叉树

bool _isSymmetric(BTNode* root1, BTNode* root2)
{
	if (root1 == NULL || root2 == NULL)
	{
		return false;
	}
	if (root1 == NULL && root2 == NULL)
	{
		return false;
	}
	return _isSymmetric(root1->left, root2->right)&&_isSymmetric(root1->right,root2->left);

}

另一颗树的子树

bool issSubtree(BTNode* root, BTNode* subRoot)
{
	if (root == NULL)
	{
		return false;
	}
	if (isSameTree(root, subRoot))
	{
		return true;
	}
	return issSubtree(root->left, subRoot) || issSubtree(root->right, subRoot);
}

编一个程序，读入用户输入的一串先序遍历字符串，根据此字符串建立一个二叉树（以指针方式存储）例如如下的先序遍历字符串：ABC##DE#G##F###，建立起二叉树以后，再对二叉树进行中序遍历，输出遍历结果

BTNode* CreateTree(char* str, int* pi)
{
	if (str[*pi] == '#')
	{
		(*pi)++;
		return NULL;
	}

	BTNode* root = (BTNode*)malloc(sizeof(BTNode));
	root->data = str[(*pi)++];
	root->left = CreateTree(str, pi);
	root->right = CreateTree(str, pi);

	return root;
}