1. 二叉树
- 空树
- 非空:根节点,根节点的左子树、根节点的右子树组成的。
1.1 二叉树的遍历
从二叉树的定义来看,二叉树是递归定义的,因此我们可以用递归的形式来遍历二叉树。
1.1.1二叉树前中后序遍历(递归版)
访问根结点的顺序不同。文章来源:https://www.toymoban.com/news/detail-460270.html
//先序遍历
void PreOrder(BTNode* root)
{
if (root == NULL)
{
printf("* ");
return;
}
printf("%d ", root->data);
PreOrder(root->left);
PreOrder(root->right);
}
//中序遍历
void InOrder(BTNode* root)
{
if (root == NULL)
{
printf("* ");
return;
}
PreOrder(root->left);
printf("%d ", root->data);
PreOrder(root->right);
}
//后序遍历
void PostOrder(BTNode* root)
{
if (root == NULL)
{
printf("* ");
return;
}
PreOrder(root->left);
PreOrder(root->right);
printf("%d ", root->data);
}
1.1.2 层序遍历
层序遍历是按照二叉树的高度,一层一层遍历,需要借助队列来完成。但是C语言没有这样的数据结构,需要我们自己来提前写一个。(本例子不提供队列的实现)文章来源地址https://www.toymoban.com/news/detail-460270.html
//层序遍历
void LevelOrder(BTNode* root)
{
Queue q;
QueueInit(&q);
//根节点入队
if (root)
{
QueuePush(&q, root);
}
while (!QueueEmpty(&q))
{
//先获取队首元素,再出队,左右孩子不为空,入队
BTNode* front = QueueFront(&q);
QueuePop(&q);
if (front->left)
{
QueuePush(&q, front->left);
}
if (front->right)
{
QueuePush(&q, front->right);
}
printf("%d ", front->data);
}
QueueDestroy(&q);
}
1.2 二叉树的其他相关接口
1.2.1 求二叉树的结点数量
//求二叉树的结点数量
int NodeSize(BTNode* root)
{
if (root == NULL)
return 0;
return 1+NodeSize(root->left)+NodeSize(root->right);
}
1.2.2 求叶子结点个数
//求叶子结点个数
int LeafSize(BTNode* root)
{
//防止空树
if (root == NULL)
return 0;
//是叶子
if (root->left == NULL && root->right == NULL)
return 1;
//不是叶子
return LeafSize(root->left)+LeafSize(root->right);
}
1.2.3 求树高
//求树高
int TreeDepth(BTNode* root)
{
//避免空树
if (root == NULL)
return 0;
int depth_left = 1 + TreeDepth(root->left);
int depth_right = 1 + TreeDepth(root->right);
return depth_left > depth_right ? depth_left : depth_right;
}
1.2.4 求第k层结点个数
//求第k层结点个数
int BinaryTreeLevelKSize(BTNode* root,int k)
{
//空树
if (root == NULL)
return 0;
if (k == 1)
return 1;
int count = BinaryTreeLevelKSize(root->left, k - 1) + BinaryTreeLevelKSize(root->right, k - 1);
return count;
}
1.2.5 查找二叉树值为k的结点
//查找二叉树值为x的结点
BTNode* BinaryTreeFind(BTNode* root, int 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;
}
到了这里,关于数据结构---二叉树(C语言)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!