目录树概念及结构相关概念树的表示树在实际中的运用(表示文件系统的目录树结构)二叉树概念及结构概念需要注意的特殊二叉树二叉树的性质二叉树的存储结构顺序存储链式存储总结树概念及结构 树是
树是一种 非线性 的数据结构,它是由 n ( n>=0 )个有限结点组成一个具有层次关系的集合
把它叫做树是因 为它看起来像一棵倒挂的树,也就是说它是根朝上,而叶朝下的
注意:
如图:
注意:
如图:
树结构相对线性表就比较复杂了,要存储表示起来就比较麻烦了,既然保存值域,也要保存结点和结点之间
的关系,实际中树有很多种表示方式如:双亲表示法,孩子表示法、孩子双亲表示法以及孩子兄弟表示法
等。我们这里就简单的了解其中最常用的 孩子兄弟表示法。
typedef int DataType;
struct node
{
struct Node* _firstChild1; // 第一个孩子结点
struct Node* _pNextBrother; // 指向其下一个兄弟结点
DataType _data; // 结点中的数据域
};
如图:
满二叉树:
一个二叉树,如果每一个层的结点数都达到最大值,则这个二叉树就是满二叉树
也就是说,如果一个二叉树的层数为K,且结点总数是2^k-1,则它就是满二叉树
完全二叉树:
完全二叉树是效率很高的数据结构,完全二叉树是由满二叉树而引出来的(特殊的完全二叉树)
对于深度为K的,有n个结点的二叉树,当且仅当其每一个结点都与深度为K的满二叉树中编号从1至n的结点一一对应时称之为完全二叉树
存储结构类型:
顺序结构存储就是使用 数组来存储 ,一般使用数组只适合表示完全二叉树(不完全二叉树有空间的浪费)而现实中使用中只有堆才会使用数组来存储
注:二叉树顺序存储在物理上是一个数组,在逻辑上是一颗二叉树
如图:
二叉树的链式存储结构是指,用链表来表示一棵二叉树,即用链来指示元素的逻辑关系。 通常的方法是
链表中每个结点由三个域组成,数据域和左右指针域,左右指针分别用来给出该结点左孩子和右孩子所
在的链结点的存储地址 。
例:
typedef int BTDataType;
// 二叉链
struct BinaryTreeNode
{
struct BinTreeNode* _pLeft; // 指向当前节点左孩子
struct BinTreeNode* _pRight; // 指向当前节点右孩子
BTDataType _data; // 当前节点值域
}
// 三叉链
struct BinaryTreeNode
{
struct BinTreeNode* _pParent; // 指向当前节点的双亲
struct BinTreeNode* _pLeft; // 指向当前节点左孩子
struct BinTreeNode* _pRight; // 指向当前节点右孩子
BTDataType _data; // 当前节点值域
};
这只是二叉树的基本知识,之后我们还会详细解析二叉数的递归实现和有关题目。
到此这篇关于C语言深入浅出解析二叉树的文章就介绍到这了,更多相关C语言 二叉树内容请搜索编程网以前的文章或继续浏览下面的相关文章希望大家以后多多支持编程网!
--结束END--
本文标题: C语言深入浅出解析二叉树
本文链接: https://www.lsjlt.com/news/144507.html(转载时请注明来源链接)
有问题或投稿请发送至: 邮箱/279061341@qq.com QQ/279061341
下载Word文档到电脑,方便收藏和打印~
2024-03-01
2024-03-01
2024-02-29
2024-02-29
2024-02-29
2024-02-29
2024-02-29
2024-02-29
2024-02-29
2024-02-29
回答
回答
回答
回答
回答
回答
回答
回答
回答
回答
0