树结构
为什么需要树这种数据结构
1,数组存储方式的分析
优点:通过索引访问元素,速度块,对于有序数组还可以用二分查找提高检索速度
缺点:如果要检索具体的某个值,或者需要增删(需要创建新数组)会比较麻烦
2,链式存储方式的分析
优点:增删效率优秀
缺点:检索效率低
3,树存储方式
能提高数据的存取效率,比如利用二叉排序树(Binary Sort Tree),既可以保证数据的检索速度,同时也能保证数据的插入删除和修改的速度.
以二叉排序树为例
[7,3,10,1,5,9,12]
比父节点小的子节点放在左边,大的放在右边
当检索时,每次比较可以排除一半的元素,有较高的检索效率
当添加时,只需要按规则添加在对应的节点下即可
删除叶节点时,只需将其父节点的指针移除即可
树的常用术语
1,节点
2,根节点:最顶端的节点
3,父节点
4,子节点
5,叶节点:没有子节点的节点
6,节点的权(节点值):节点内存放的数据
7,路径:从根节点到节点的路线
8,层:处于同一个级别的节点为一层
9,子树:节点的所有后代节点构成该节点的子树
10,树的高度:即树的最大层
11,森林:多颗子树构成森林
二叉树
每个节点最多只能存在两个子节点的一种形式称为二叉树
二叉树的子节点分为左节点和右节点
二叉树概念
如果所有叶子节点都在最后一层,且节点总数为2^n-1(n为层数),则称为满二叉树
如果二叉树的所有叶子节点都在最后一层或者倒数第二层,且最后一层的叶子节点在左侧连续,倒数第二层的叶子节点在右边连续,则称之为完全二叉树
二叉树的遍历
二叉树的前序遍历
先输出父节点,再遍历左子树和右子树
二叉树的中序遍历
先遍历左子树,再输出父节点,再遍历右子树
二叉树的后序遍历
先遍历左子树,再遍历右子树,最后输出父节点文章来源：https://www.toymoban.com/news/detail-848006.html
代码实现放在下一节文章来源地址https://www.toymoban.com/news/detail-848006.html
到了这里，关于数据结构6.1:树的基本概念的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
