photo by Tim Gouw from pexels
树和树的算法(一)—— 树的的定义以及表示
树数据结构在计算机领域有广泛的应用,包括操作系统,图形、数据库和计算机网络等。树数据结构具有根、分支、叶子,和自然界中的树差别在树数据结构的根在顶部,叶在底部。
tree1
如图为树数据结构的一个例子——文件系统。
一、定义
相关词汇:
节点:树的基本部分,包含附加信息
边:连接两个节点以显示他们之间的关系
根
路径:由边连接节点的有序列表
子节点
父节点
兄弟节点:拥有相同父节点的节点
子树
叶节点:没有子节点的节点
层数:节点n的层数为根节点到该节点所经过的分支(边)数目
高度:树的高度为该数中任何节点的最大层数
两种定义:
树由一组节点和一组连接节点节点的边组成。具有以下属性:
树的一个节点被指定为根节点。
除了根节点之外,每个节点 n 通过一个其他节点 p 的边连接,其中 p 是 n 的父节点。
从根路径遍历到每个节点路径唯一。
如果树中的每个节点最多有两个子节点,我们说该树是一个二叉树。
树是空的,或者由一个根节点和零个或多个子树组成,每个子树也是一棵树。
二、表示
列表表示
可以用python中的嵌套列表表示。具体实现不在此贴出。
类节点表示
用类表示一个节点,每个节点为该类的一个实例。类数据成员包括了自身的附件信息以及对其他节点的引用。
代码实现
领取专属 10元无门槛券
私享最新 技术干货