[C/C++]数据结构: 链式二叉树的构建及遍历

一: 💬二叉树的概念

1.1:🚩?概念

? ? ? ?二叉树是指树中节点的度不大于2的有序树,它是一种最简单且重要的树,二叉树的递归定义为:二叉树是一颗空树,或者是一颗由一个根节点和两颗互不相交的,分别称为跟的左孩子和右孩子树组成的非空树,其中左子树和右子树都是二叉树.

1.2 : ?特殊的二叉树

1. 满二叉树：一个二叉树，如果每一个层的结点数都达到最大值，则这个二叉树就是满二叉树。也就是说，如果一个二叉树的层数为K，且结点总数是 ，则它就是满二叉树。
2. ?完全二叉树：完全二叉树是效率很高的数据结构，完全二叉树是由满二叉树而引出来的。对于深度为K的，有n个结点的二叉树，当且仅当其每一个结点都与深度为K的满二叉树中编号从1至n的结点一一对应时称之为完全二叉树。 要注意的是满二叉树是一种特殊的完全二叉树。

1.3: 🌟二叉树的性质

1. 若规定根节点的层数为1，则一棵非空二叉树的第i层上最多有 2^(i-1)个结点.
2. 若规定根节点的层数为1，则深度为h的二叉树的最大结点数是2^h-1?.
3. 对任何一棵二叉树, 如果度为0其叶结点个数为 , 度为2的分支结点个数为 ,则有 n0＝n2?＋1
4. 若规定根节点的层数为1，具有n个结点的满二叉树的深度，h=lg(n+1)?(ps：是log以2为底，n+1为对数)
5. 对于具有n个结点的完全二叉树，如果按照从上至下从左至右的数组顺序对所有节点从0开始编号，则对于序号为i的结点有：

1. 若i>0，i位置节点的双亲序号：(i-1)/2；i=0，i为根节点编号，无双亲节点
2. 若2i+1<n，左孩子序号：2i+1，2i+1>=n否则无左孩子
3. 若2i+2<n，右孩子序号：2i+2，2i+2>=n否则无右孩子

二:🥦链式二叉树的结构

????????二叉树的链式存储结构是指，用链表来表示一棵二叉树，即用链来指示元素的逻辑关系。 通常的方法是链表中每个结点由三个域组成，数据域和左右指针域，左右指针分别用来给出该结点左孩子和右孩子所在的链结点的存储地址 。由于二叉树可以分为根,左子树,右子树,而其左右子树又可以分为根左子树,右子树,所以链式二叉树非常适合使用递归.?

typedef char BTDataType;

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

三: ?链式二叉树的创建及遍历

1.前序遍历:先遍历树的根在遍历书的左子树和右子树

前序遍历递归图解:

代码:

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

	printf("%c ", root->data);//先访问根节点
	BinaryTreePrevOrder(root->left);//访问左子树
	BinaryTreePrevOrder(root->right);//访问右子树
}

2.中序遍历:和前序遍历思想一样,不过遍历顺序发生改变,先便利左子树,再遍历根,再遍历右子树

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

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

3.后序遍历:先遍历左子树再遍历右子树最后遍历根节点

void BinaryTreePostOrder(BTNode* root)
{
	if (root == NULL)
	{
		printf("NULL ");
		return;
	}
	BinaryTreePostOrder(root->left);
	BinaryTreePostOrder(root->right);
	printf("%c ", root->data);
}

4.层序遍历:

????????层序遍历就是从所在二叉树的根节点出发，首先访问第一层的树根节点，然后从左到右访问第2层上的节点，接着是第三层的节点，以此类推，自上而下，自左至右逐层访问树的结点的过程就是层序遍历.

实现方法: 层序遍历要使用到队列,忘记的帖子可以看[C/C++]数据结构 栈和队列

首先将节点1入队列

若1的左右节点不为空,再将左右节点依次入队,再把节点1出队(相当于遍历节点1)

重复上诉步骤,每次出队时先将这个节点不为空的子节点入队,当队列为空时就说明二叉树遍历完了

void BinaryTreeLevelOrder(BTNode* root)
{
	Queue q;
	QueueInit(&q);
	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);
	}
	QueueDestory(&q);
}

5.二叉树的构建

通过前序遍历的数组"ABD##E#H##CF##G##"构建二叉树,其中'#'代表NULL

还是采用递归的思想,首先函数的形参需要一个字符串数组,和一个整形指针,该指针是用来记录访问到数组的位置.遇到'#'就让改指针++,并返回NULL,否则就开辟一个节点,使该节点的数据域指向对应数组的元素,再递归遍历该节点的左子树和右子树

BTNode* BinaryTreeCreate(BTDataType* a, int* pi)
{
	if (a[*(pi)]=='#')
	{
		(*pi)++;
		return NULL;
	}

	BTNode* root = (BTNode*)malloc(sizeof(BTNode));
	if (root == NULL)
	{
		perror("malloc");
		exit(-1);
	}

	root->data = a[(*pi)++];
	root->left  = BinaryTreeCreate(a, pi);
	root->right = BinaryTreeCreate(a, pi);
	return root;
}

四:其他相关功能

像求二叉树的节点个数,高度等功能都是利用递归思想解决的,博主就不过多介绍了,需要的帖子可以看下方代码

//节点个数
int BinaryTreeSize(BTNode* root)
{
	if (root == NULL)
		return 0;
	else
		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)
{
	assert(k >0);
	if(root==NULL)
		return 0;
	else if (k == 1)
		return 1;
	else
	{
		return BinaryTreeLevelKSize(root->left, k - 1) + BinaryTreeLevelKSize(root->right, k - 1);
	}

}
//求二叉树的高度
int BinaryTreeHeight(BTNode* root)
{
	if (root == NULL)
		return 0;
	else
	{
		int left = BinaryTreeHeight(root->left);
		int right = BinaryTreeHeight(root->right);
		return left > right ? left+1 : right+1;
	}
}
//在二叉树中查找值为x的节点
BTNode* BinaryTreeFind(BTNode* root, BTDataType x)
{
	if (root == NULL)
		return NULL;

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

	BTNode* ret1 = BinaryTreeFind(root->left, x);
	if (ret1 != NULL)
		return ret1;

	BTNode* ret2 = BinaryTreeFind(root->right, x);
	if (ret2 != NULL)
		return ret2;

	return NULL;
}
//销毁二叉树
void BinaryTreeDestory(BTNode* root)
{
	if (root == NULL)
		return;
	BinaryTreeDestory(root->left);
	BinaryTreeDestory(root->right);
	free(root);
}