文章目录
- 前言
- 一、树的定义
- 二、专业术语
- 三、树的分类
- 四、二叉树的存储
- 1.连续存储(完全二叉树)
- 2.连续存储的优缺点
- 3.链式存储
- 五、森林的存储
- 六、二叉树的遍历
- 七、树应用的简单介绍
- 八、链式二叉树三种遍历顺序详解(代码实现)
- 1.目标树结构
- 2.主函数
- 3.代码构建树
- 3.先序中序后序函数
前言
一、树的定义
1.专业定义:
<1> 有且只有一个根节点。
<2> 由若干个互不相干的子树&#xff0c;这些子树本身也是一棵树通俗的定义。
1.通俗的定义&#xff1a;
<1> 树是由节点和边组成的。
<2> 每个节点只有一个父亲节点但可以有多个子节点。
<3> 有一个节点例外&#xff0c;该节点没有父亲节点&#xff0c;此节点称为根节点。
二、专业术语
1.深度
从根节点到最底层节点的层数称为深度&#xff0c;根节点是第一层。
2.叶子结点
没有子节点的节点
3.非终端节点
实际就是非叶子节点
4.度
最大子节点的个数称为度
三、树的分类
1.一般树
任意一个节点的子节点的个数不受限制。
2.二叉树
任意一个子节点的个数最多是二&#xff0c;且子节点的位置不可更改。
<1> 满二叉树&#xff1a;在不增加树的层数的情况下无法在多添加一个节点的二叉树就是满二叉树
<2> 完全二叉树&#xff1a;如果只是删除了满二叉树最底层最右边的连续若干个节点&#xff0c;这样形成的二叉树就是完全二叉树。
3.森林
n个互不相交的树的集合
四、二叉树的存储
1.连续存储&#xff08;完全二叉树&#xff09;
改造后的存储结果&#xff1a;
2.连续存储的优缺点
优点&#xff1a;查找某个父节点和子节点&#xff08;包括判断有无子节点&#xff09;速度很快。
缺点&#xff1a;太耗内存空间。
3.链式存储
每个节点包含三个域&#xff0c;两个指针域和一个数值域。其中两个指针域用来指向两个孩子节点&#xff0c;数值域保存节点信息。
五、森林的存储
1.存储思路
将森林转化为二叉树在进行存储
设法保证任意一个节点的&#xff1a;
<1> 左指针指向他的第一个孩子。
<2> 右指针指向他的下一个兄弟节点。
<3> 将各个树的根节点互相看做兄弟节点。
2.例图如下
转换为二叉树之后的存储结构&#xff1a;
六、二叉树的遍历
1.先序遍历&#xff08;先访问根节点&#xff09;
先访问根节点。
再访问左子树。
最后访问右子树。
原理图&#xff1a;
例图&#xff1a;
2.中序遍历&#xff08;中间访问根节点&#xff09;
先访问左子树。
中间访问根节点。
最后访问右子树。
原理图&#xff1a;
例图&#xff1a;
3.后序遍历&#xff08;最后访问根节点&#xff09;
先访问左子树。
再访问右子树。
最后访问根节点。
原理图&#xff1a;
例图&#xff1a;
七、树应用的简单介绍
<1> 树是数据库中数据组织的一种重要形式。
<2> 操作系统父子进程本身就是一棵树。
<3> 面向对象语言类的继承关系本身就是一棵树。
八、链式二叉树三种遍历顺序详解&#xff08;代码实现&#xff09;
1.目标树结构
2.主函数
#include
#include
struct TreeNode {
char data;
struct TreeNode * pLchild;
struct TreeNode * pRchild;
};
struct TreeNode * CreatBTree();
void FirstOrderBTree(struct TreeNode *pT);
void InFixOrderBTree(struct TreeNode *pT);
void PostOrderBTree (struct TreeNode *pT);
int main()
{
struct TreeNode *pT&#61;CreatBTree();
printf("先序遍历结果为&#xff1a;");
FirstOrderBTree(pT);
printf("\\n");
printf("中序遍历结果为&#xff1a;");
InFixOrderBTree(pT);
printf("\\n");
printf("后序遍历结果为&#xff1a;");
PostOrderBTree(pT);
return 0;
}
3.代码构建树
struct TreeNode * CreatBTree(void)
{
struct TreeNode* pA &#61;(struct TreeNode *) malloc(sizeof(struct TreeNode));
struct TreeNode* pB &#61;(struct TreeNode *) malloc(sizeof(struct TreeNode));
struct TreeNode* pC &#61;(struct TreeNode *) malloc(sizeof(struct TreeNode));
struct TreeNode* pD &#61;(struct TreeNode *) malloc(sizeof(struct TreeNode));
struct TreeNode* pE &#61;(struct TreeNode *) malloc(sizeof(struct TreeNode));
pA->data&#61;&#39;A&#39;;
pB->data&#61;&#39;B&#39;;
pC->data&#61;&#39;C&#39;;
pD->data&#61;&#39;D&#39;;
pE->data&#61;&#39;E&#39;;
pA->pLchild&#61;pB;
pA->pRchild&#61;pC;
pB->pLchild&#61;pB->pRchild&#61;NULL;
pC->pLchild&#61;pD;
pC->pRchild&#61;NULL;
pD->pLchild&#61;NULL;
pD->pRchild&#61;pE;
pE->pLchild&#61;pE->pRchild&#61;NULL;
return pA;
}
3.先序中序后序函数
先序思路分析&#xff1a;pT->pLchild可以表示整个左子树&#xff0c;则在先序遍历的时候我可以先输出根节点&#xff0c;然后使用递归输出我的左子树&#xff0c;当左子树输出完递归结束。再用同样的方法递归出右子树。
void FirstOrderBTree(struct TreeNode *pT)
{
if(pT!&#61;NULL)
{
printf("%c ",pT->data);
FirstOrderBTree(pT->pLchild);
FirstOrderBTree(pT->pRchild);
}
}
中序思路分析&#xff1a;先递归输出左子树&#xff0c;然后输出根节点&#xff0c;最后递归输出右子树。
void InFixOrderBTree(struct TreeNode *pT)
{
if(pT!&#61;NULL)
{
InFixOrderBTree(pT->pLchild);
printf("%c ",pT->data);
InFixOrderBTree(pT->pRchild);
}
}
后序思路分析&#xff1a;先递归输出左子树&#xff0c;然后递归输出右子树&#xff0c;最后输出根节点。
void InFixOrderBTree(struct TreeNode *pT)
{
if(pT!&#61;NULL)
{
InFixOrderBTree(pT->pLchild);
printf("%c ",pT->data);
InFixOrderBTree(pT->pRchild);
}
}
void PostOrderBTree (struct TreeNode *pT)
{
if(pT!&#61;NULL)
{
PostOrderBTree(pT->pLchild);
PostOrderBTree(pT->pRchild);
printf("%c ",pT->data);
}
}
运行结果&#xff1a;