那么本篇文是初阶数据结构这个系列的最后一篇文章,那么闲话少叙,我们直接进入正题
在讲二叉树的一些之前知识点之前,我先给大家送个小礼物哈
手搓二叉树
手搓二叉树的思路
首先创建一个结构体,且结构体里的元素也是需要自己设置,就拿链表来举例,结构体内必须包含数据以及指向下一个节点的指针next,那么返回到二叉树这里,结构体需要包含的就是数据,以及左右指针,然后创建子节点以及子节点之间相互连接
前序遍历
那么我们可以先从这个图中得到一个结论
前序遍历:根 左子树 右子树
这里我也是给大家准备了一个小视频,大家可以参考一下
二叉树前序遍历思路讲解
源代码
void FrontOrder(TFT* node)
{
if (node == NULL)
{
printf("N ");
return;
}
printf("%d ", node->data);
FrontOrder(node->left);
FrontOrder(node->right);
}
中序遍历
我们先来说一下结论
中序遍历:左子树 根 右子树
这里的操作我也给大家准备了 一个小视频,大家可以参考一下
二叉树中序遍历思路讲解
源代码
void MiddleOrder(TFT* node)
{
if (node == NULL)
{
printf("N ");
return;
}
MiddleOrder(node->left);
printf("%d ", node->data);
MiddleOrder(node->right);
}
后序遍历
还是一样,我们先讲结论
后序遍历:左子树 右子树 根
这里的操作我也给大家准备了 一个小视频,大家可以参考一下
二叉树的后序遍历
源代码
void BehindOrder(TFT* node)
{
if (node == NULL)
{
printf("N ");
return;
}
BehindOrder(node->left);
BehindOrder(node->right);
printf("%d ", node->data);
}
前中后序的共同特点
通过递归的方法,进行遍历
节点计数
思路:当节点不为空时,计数器+1,节点为空时,计数器+0,然后用递归进行遍历
源代码
int TreeSize(TFT* root)
{
/*int size = 0;*/
if (root == NULL)
return 0;
else
++size;
TreeSize(root->left);
TreeSize(root->right);
return size;
}
计算树的高度
思路:进入函数后先判空,如果为空,则返回0,不为空时,先记录当前左右两科树的高点,然后进行左右判断,谁大谁加1
源代码
int TreeHighSize(TFT* node)
{
if (node == NULL)
return 0;
int left = TreeHighSize(node->left);
int right = TreeHighSize(node->right);
return left > right ? left + 1 : right + 1;
}
树的销毁
树的销毁其实不难,基本上就是还原变量指针等等
源代码
void DestroyTree(TFT* node)
{
if (node == NULL)
return;
DestroyTree(node->left);
DestroyTree(node->right);
free(node);
}
那么初阶数据结构系列的文章就先给大家更新到这里,如果喜欢我的文章,还请各位观众老爷们留个赞谢谢,我们下期再见