学习树这种数据结构,从普通树到工业级别使用的树,它是一个递进的过程。如果跳过前面的步骤,而直接取学习和查阅工业级别使用的树(红黑树)的相关资料,我想这样学习的效果和体验都是很差的。
学习红黑树之前。首先需要理解的是树的基本概念和相关术语。其次二叉树,二叉树的相关概念和术语,以及二叉树的存储方式和遍历方式。其次是弄明白什么样的树是二叉查找树,以及二叉查找树的性能分析和其不能成为工业级别使用的树的原因。再引出平衡二叉查找树以及构建平衡二叉查找树的初衷,分析AVL树(最先被发明的严格的平衡二叉树)的优越点,最后才是工业级别常用的树结构(红黑树)。红黑树是一颗不严格的平衡二叉树。
相关知识点
树的基本概念和相关术语
树(Tree):是若干节点组成的有限集合,其中必须有一个节点是根节点,其余节点划分为互不相交的集合,每一个集合还是一棵树,被称为根的子树。
树中的数据元素被称之为节点。有关节点的相关术语:根节点、父节点、子节点、兄弟节点、叶子节点。如下图:
A节点就是B节点、C节点、D节点的父节点。B、C、D节点是A节点的子节点。B、C、D的父节点为同一节点,所以它们之间又互相称之为兄弟节点。没有父节点的节点被称之为根节点,如图,节点E。我们把没有子节点的节点称之为叶子节点,或者叶节点,如图种的G、H、I、J、K、L节点。
树的其他相关概念:高度(height)、深度(Depth)、层(Level)
节点的高度=节点到叶子节点的最长路径(边数)
节点的深度=根节点到这个节点所经历的边的个数
节点的层数=节点的深度+1
树的高度 = 根节点的高度
概念的定义比较容易混淆,如下图:
二叉树
二叉树(Binary Tree):是一种每个节点最多拥有2个子树的树结构。其中左边的子树称为左子树,右边的子树称为右子树。
如下图所示:
其中编号2和编号3为特殊的二叉树。
编号2的二叉树中,叶子节点全都在最底层,除了叶子节点外,每一个节点都有左右两个子节点,这种二叉树称为满二叉树。
编号3中的二叉树,叶子节点都在最底下两层,最后一层的叶子节点都靠左排列,并且除了最后一层,其他层数的节点都要达到最大,这种二叉树称之为完全二叉树。
如何存储一颗二叉树呢?
1、基于指针或者引用的链式存储法
2、基于数组的顺序存储法
基于指针的链式存储法有多种,但主要详述的是二叉链表存储法,其他的就不做介绍了。如下图所示,每一个节点都有三个字段,其中一个字段存储数据,另外两个是指向左右节点的指针。大部分二叉树代码都是通过二叉链表存储法实现的
基于数组的顺序存储法,我们把根节点放在数组的第一个位置,从上至下,从左至右依次存储数组种的值。如下图所示,
上图是存储的是一颗完全二叉树。而对于非完全二叉树,使用基于数组的存储法,只有添加一些不存在的节点,使之称为一颗完全二叉树,在使用数组存储,需下图所示。这样就比较浪费内存空间了。
总结:最适合用数组来存储的无疑是完全二叉树。这也是为什么单独把完全二叉树拿出来介绍的原因。
二叉树的遍历?
遍历二叉树的三种经典方式:前序遍历、中序遍历、后序遍历
前序遍历(DLR)
前序遍历的递归过程为:若二叉树为空,遍历结束,否则
1、先访问根几点
2、递归遍历左子树
3、递归遍历右子树
代码实现:
public void preOrder(Node<T> node){
if(node==null) return; //递归的终止条件
visit(node.data); //先访问根节点
preOrder(node.leftChild); //递归遍历左子树
preOrder(node.rightChild); // 递归遍历右子树
}
中序遍历(LDR)
中序遍历的递归过程为:若二叉树为空,遍历结束,否则
1、先递归遍历左子树
2、再访问根几点
3、最后递归遍历右子树
代码实现:
public void inOrder(Node<T> node){
if(node==null) return; // 终止条件
inOrder(node.leftChild); //递归遍历左子树
visit(node.data); //访问根节点
inOrder(node.rightChild); // 递归遍历右子树
}
后序遍历(LRD)
后序遍历的递归过程为:若二叉树为空,遍历结束,否则
1、先递归遍历左子树
2、再递归遍历右子树
3、最后访问根几点
代码实现:
public void postOrder(Node<T> node){
if(node==null) return; // 终止条件
postOrder(node.leftChild); //递归遍历左子树
postOrder(node.rightChild); // 递归遍历右子树
visit(node.data); //访问根节点
}
如下图所示:
时间复杂度分析 ,对于一个节点,最多会被访问两次,所以时间复杂度跟n成正比,所以遍历的时间复杂度为O(n)
总结
本篇是学习了树的相关知识点和专业术语,以及二叉树的相关知识点,二叉树的概念,满二叉树,完全二叉树,二叉树的存储,二叉树的遍历。
参考:数据结构与算法之美-王争
《数据结构--java语言描述》
最后
以上就是无聊未来最近收集整理的关于数据结构--树以及二叉树的相关概念的全部内容,更多相关数据结构--树以及二叉树内容请搜索靠谱客的其他文章。
发表评论 取消回复