树和树的算法（一）——树的的定义以及表示

photo by Tim Gouw from pexels

树和树的算法（一）—— 树的的定义以及表示

树数据结构在计算机领域有广泛的应用，包括操作系统，图形、数据库和计算机网络等。树数据结构具有根、分支、叶子，和自然界中的树差别在树数据结构的根在顶部，叶在底部。

tree1

如图为树数据结构的一个例子——文件系统。

一、定义

相关词汇：

节点：树的基本部分，包含附加信息

边：连接两个节点以显示他们之间的关系

根

路径：由边连接节点的有序列表

子节点

父节点

兄弟节点：拥有相同父节点的节点

子树

叶节点：没有子节点的节点

层数：节点n的层数为根节点到该节点所经过的分支（边）数目

高度：树的高度为该数中任何节点的最大层数

两种定义：

树由一组节点和一组连接节点节点的边组成。具有以下属性：

树的一个节点被指定为根节点。

除了根节点之外，每个节点 n 通过一个其他节点 p 的边连接，其中 p 是 n 的父节点。

从根路径遍历到每个节点路径唯一。

如果树中的每个节点最多有两个子节点，我们说该树是一个二叉树。

树是空的，或者由一个根节点和零个或多个子树组成，每个子树也是一棵树。

二、表示

列表表示

可以用python中的嵌套列表表示。具体实现不在此贴出。

类节点表示

用类表示一个节点，每个节点为该类的一个实例。类数据成员包括了自身的附件信息以及对其他节点的引用。

代码实现