树
树的遍历:都是依据根节点遍历的顺序来的,分为先序,中序,后序,然后先左节点,后右节点。
1:中序遍历:左根右(从左节点开始遍历,然后是根节点,然后是右节点,下同)
2:先序遍历:根左右
3:后序遍历:左右根
1:普通二叉树:每个节点最多有2颗子树。
a.满二叉树:除最后一层无任何子节点外,每一层上的所有结点都有两个子结点。
b.完全二叉树:只有最下面的两层结点度能够小于2,并且最下面一层的结点都集中在该层最左边的若干位置的二叉树。
2:二叉查找树:对于树中的每个节点X,它的左子树中所有项的值小于X中的值,而它的右子树中所有项的值大于X中的值。(左值<根值<右值)。
时间复杂度:插入和查找的时间复杂度均为O(logn),但是在最坏的情况下仍然会有O(n)的时间复杂度(原因在于插入和删除元素的时候,树没有保持平衡)。
3:平衡二叉树之AVL树:它是一棵空树或它的左右两个子树的高度差的绝对值不超过1(层级差<=1),并且左右两个子树都是一棵平衡二叉树,同时,平衡二叉树必定是二叉搜索树,反之则不一定。
时间复杂度:插入,查找,删除的时间复杂度最好情况和最坏情况都维持在O(logN)。
注:平衡二叉树进行插入和删除操作时,为了维持平衡,会进行自平衡操作---旋转(左旋和右旋)。
4:平衡二叉树之红黑树:每个节点都带有颜色属性的二叉查找树,颜色为红色或黑色。
特点:
性质1:节点是红色或黑色。
性质2:根是黑色。
性质3:所有叶子都是黑色(叶子是NIL节点)。
性质4:每个红色节点必须有两个黑色的子节点。(从每个叶子到根的所有路径上不能有两个连续的红色节点。)
性质5:从任一节点到其每个叶子的所有简单路径都包含相同数目的黑色节点。
时间复杂度:可以在O(logn)时间内做查找,插入和删除,这里的n是树中元素的数目。
注:红黑树存在左旋,右旋和着色问题。
5:B树(B-tree):是一种用于查找的平衡树,但是它不是二叉树。
B树和平衡二叉树稍有不同的是B树属于多叉树又名平衡多路查找树(查找路径不止两个),即一个节点下不止有2个字节。
时间复杂度:O(log n)的时间复杂度运行进行查找、顺序读取、插入和删除。
注:数据库索引技术里大量使用者B树和B+树的数据结构,文件系统也多是这个数据结构。
6:B+树和B*树的时间复杂度亦是如此。
详情见:
http://blog.jobbole.com/111680/
强子博客:
https://blog.51cloud.win/2017/12/16/%E6%A0%91%E4%B8%8E%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84/
分享到:
相关推荐
本文将深入探讨“数据结构之树”以及如何在MFC(Microsoft Foundation Classes)环境下实现树的可视化。 首先,我们来理解什么是树数据结构。树是一种非线性的数据结构,它由节点(或称为顶点)和边组成,每个节点...
【数据结构之树和二叉树】是计算机科学中重要的基础知识,主要研究树形数据结构的定义、特性和操作。本部分重点讲解了树和二叉树的基本概念、术语、性质以及相关的操作。 首先,**树的定义**是数据结构中的核心概念...
本资源“数据结构之树的C++源代码”提供了基于类实现的树结构的C++实现,这对于学习和理解数据结构以及提升编程能力非常有帮助。 首先,让我们深入了解一下树的基本概念。在树结构中,每个节点包含一个值以及指向其...
数据结构之树和二叉树.pptx
Java数据结构之树与二叉树.pptx
在众多数据结构中,树结构由于其独特的层次性和高效的操作性能,被广泛应用于排序、搜索、索引和空间数据划分等领域。本文将对树结构中的几种特定类型——包括平衡树、斐波那契堆、哈希树以及空间数据划分树(R树)...
数据结构是计算机科学中至关重要的一个领域,而树形结构是数据结构的一种基本类型,它在计算机算法设计、数据库管理、编译原理等多个方面都有广泛的应用。本篇内容主要介绍了树的基本概念、树的遍历、树的线性表示...
树的定义 基本术语 森林 二叉树 哈弗曼树定义、特性、遍历算法
2. 实现哈夫曼树数据结构,使用哈夫曼树完成如下文档的编码与译码,假设该文档由5种符号字符(A、B、C、D、E)构成 ABACDEABBCEABAACCCDEACCBAABCCCA 3. 选做:实现二叉树的中序遍历线索化数据结构 4. 选做:使用...
在“数据结构之二叉排序树的生成”这个程序中,我们可以深入理解二叉排序树的构建过程和相关操作。首先,我们需要初始化一个空的二叉树。这通常通过创建一个空的根节点来实现,根节点没有左右子节点。初始化操作是...
"数据结构——树结构.ppt"这份文件很显然是一个关于树结构的讲座或教程材料,它可能涵盖了树的基本概念、算法实现以及实际应用。 首先,我们要理解树的基本概念。树是一种非线性的数据结构,由若干个节点(或称为...
【数据结构:树和二叉树】 树是一种非线性的数据结构,它的基本概念和术语在计算机科学中至关重要,尤其在算法设计和数据组织中扮演着核心角色。树的定义基于递归,一棵非空树包含一个根节点,以及一组互不相交的...
java版数据结构-树结构;java版数据结构-树结构;java版数据结构-树结构;java版数据结构-树结构;java版数据结构-树结构;java版数据结构-树结构;