二叉树的详细实现(含递归展开图)
一、二叉树
1. 概念
一颗二叉树是结点的有限集合，该集合或者为空，或者由一个根节点加上两棵别称为左子树和右子树的二叉树的组成
2.特点
每个结点最多有两棵子树，即二叉树不存在大于2的结点 二叉树的子树有左右之分其子树次序不能颠倒
3.特殊二叉树
1.满二叉树
一个二叉树，如果每一个层的结点都达到最大值，则这个二叉树就是满二叉树，也就是说如果一个二叉树的层数为k,结点总数为(2^k)-1，则就为满二叉树
在这里插入图片描述
2.完全二叉树
对于深度为k的，有n个结点的二叉树，且仅当其每一个结点与深度为k的满二叉树中编号从1到n的结点，称为完全二叉树
在这里插入图片描述
4.性质
性质1.
若规定根节点的层数为1，则一颗非空二叉树的第i层上最多有2^(i-1)个结点
在这里插入图片描述
性质2.
若规定根节点的层数为1，则深度为h的二叉树的最大结点数是(2^h)-1
在这里插入图片描述
性质3.
对于任何一颗二叉树，如果度为0其叶结点个数为n0,度为2的分支节点个数为n2,则n0=n2+1 (有几个子树 ，度就为多少)
在这里插入图片描述
性质4.
若规定根节点的层数为1，具有n个结点的满二叉树的深度h=log N 2^h -1=N 2^h=N+1 h= log 2 N+1 但是由于大O渐进表示法的省略 ，时间复杂度化成 O(log N) 不太懂大O渐进表示法的 :时间复杂度与空间复杂度
二、二叉树整体实现
1.前序的实现
void prevorder(BTnode* root)//前序 根 左子树 右子树
{
if (root == NULL)
{
printf("NULL ");
return;
}
printf("%c ", root->data);
prevorder(root->left);
prevorder(root->right);
}递归展开图
在这里插入图片描述
2.中序的实现
void inorder(BTnode* root)//中序 左子树 根 右子树
{
if (root == NULL)
{
printf("NULL ");
return;
}
inorder(root->left);
printf("%c ", root->data);
inorder(root->right);
}递归展开图
在这里插入图片描述
3.后序的实现
void postorder(BTnode* root)//后序 左子树 右子树 根
{
if (root == NULL)
{
printf("NULL ");
return;
}
postorder(root->left);
postorder(root->right);
printf("%c ", root->data);
}递归展开图
在这里插入图片描述
4. 节点个数
int treesize(BTnode* root)//节点个数
{
if (root == NULL)
{
return 0;
}
return treesize(root->left) + treesize(root->right) + 1;
}递归展开图
在这里插入图片描述
5. 叶节点个数
int treeleafsize(BTnode* root)//叶子节点的个数
{
if (root == NULL)
{
return 0;
}
if (root->left == NULL && root->right == NULL)//只有当左右子树都为NULL时才会返回1
{
return 1;
}
return treeleafsize(root->left)+ treeleafsize(root->right);
}递归展开图
在这里插入图片描述
6.层序遍历
void levelorder(BTnode* root)//层序遍历 需要借助数据结构栈来实现
{
queue q;
queueinit(&q);//初始化栈
if (root)
{
queuepush(&q, root);//将根结点入栈
}
while (!queueempty(&q))
{
datatype 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);//销毁内存
}
在这里插入图片描述
本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2022-09-29，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录
腾讯云开发者
