树
对于大量的输入数据,链表的线性访问就时间太长了。
所以有必要学习更快的数据结构,二叉查找树就是一个很好的数据结构,它的每一个基本操作运行时间基本上是 O(logN)
预备知识
树是由根(root) 的结点以及零或多个非空的(子)树组成,这些子树中的每一颗根都被来自根root的一条有向的边(edge)所连接。
每一个子树的根叫做根root的儿子(child),而root是每一颗子树的根的父亲(parent),你可以将树的每个节点之间的关系想象成 父子,祖孙,兄弟
但是不能想象成 叔侄(因为不相连的结点就没有关系)
没有儿子的结点称为叶结点(leaf,树叶)
路径(path),一棵树从根到每一个节点恰好存在一条路径。路径的长指边的数目,结点到本身的长是0
深度,指从根到一个结点的唯一路径长。所以,根的深度为0。高度,指从一个结点到一个树叶的最长距离。所以,所以树叶高度都是0,树的高度就是根的高,从根到树叶的最长距离等于这棵树的高
实现
树的实现是基于链表而完成的,我们可以将所以的树结点放在一个链表中,但并不是像往常的链表那样连贯连接。
我们可以设计一个结构,拥有两个指针
1 | struct TreeNode{ |
遍历时就可以先考虑有无兄弟结点,在考虑有无子结点。但是这种思考策略并不通用,下面我将介绍通用的遍历方法。
树的遍历及应用
讲遍历方法之前,我们先了解一个特殊的树——二叉树。
二叉树
二叉树是指每一个结点不能多于俩个儿子的树。
具体结构体定义如下
1 | struct TreeNode{ |
我们之后会了解很多关于二叉树的操作
前序遍历
如果在一张普通树中,前序遍历基本与深度优先算法差不多,不如说前序是深度优先算法的特殊情况,只是因为在二叉树中有特殊说法(才有的区分)
简化来说 遍历的顺序是 当前结点,左子结点,右子结点
前序遍历的策略是
从根开始遍历,遍历时会直接遍历至叶结点,返回至叶结点上一结点 x,遍历叶结点的兄弟结点,如果 x 所有子结点全部遍历完成,会返回 x 的上一结点 y,遍历x的所有兄弟结点。重复该操作直整个树遍历完为止
后序遍历
简化来说 遍历的顺序是 左子结点,右子结点,当前结点
后序遍历策略(非递归)
创建两个栈,一个储存结点,一个储存标记,两个栈的元素数应当是相同的。
我们首先可以遍历左结点,并将结点入栈,并将标记0入栈
遍历至叶结点时,不入栈,查看标记栈顶,若为0,代表着右结点并未遍历,弹出0,将1入栈。获取存储栈的栈顶,遍历右结点,右结点入栈。
重复操作,直至叶结点,标记栈为1,就可出栈。我们很容易就能靠这种标记的方式将左右结点遍历完整表示出来
中序遍历
简化来说 遍历的顺序是 左子结点,当前结点,右子结点
从根开始遍历,遇到一个结点,保存他
遍历它左子节点
输出当前结点
遍历它右结点
中序思路跟前序的代码构造基本都差不多。
二叉查找树
二叉树的重要应用在于查找
二叉树成为二叉查找树的性质是对于每一个树的每个结点X,在左子树所有项
的值小于
结点X的值,在右子树所有项
的值大于
结点X。
具体代码单独放出
- 本文作者: TangZ
- 本文链接: http://wstzj.github.io/2020/07/25/学习笔记-树/
- 版权声明: 本博客所有文章除特别声明外,均采用 MIT 许可协议。转载请注明出处!