python数据结构递归树

树

在计算机科学中,树是分层结构的抽象模型 。本篇学习笔记记录树的内容如下： 树的基本功能：定义、术语、ADT 树的遍历方法：前序、中序、后序

树的定义

第一种：树由一组节点和一组连接节点的边组成。树具有以下属性： 树的一个节点被指定为根节点。 除了根节点之外，每个节点 n 通过一个其他节点 p 的边连接，其中 p 是 n 的父节点。 从根路径遍历到每个节点路径唯一。 如果树中的每个节点最多有两个子节点，我们说该树是一个二叉树。 第二种：树是空的，或者由一个根节点和零个或多个子树组成，每个子树也是一棵树。每个子树的根节点通过边连接到父树的根节点。 下图说明了树的这种递归定义。使用树的递归定义，我们知道图中的树至少有四个节点，因为表示一个子树的每个三角形必须有一个根节点。 它可能有比这更多的节点，但我们不知道，除非我们更深入树。

树的术语

根节点(Root)：无父节点 (A) 中间节点(Internal node)：具有至少一个子节点的节点 (A, B, C, F) 叶子(External node)：无子节点 (E, I, J, K, G, H, D) 祖先(Ancestors)：:父母,祖父母,祖父母,等等 后代(Descendant)：孩子,孙子,重孙子,等等. 深度(Depth of a node)：树的祖先高度数：任意节点的最大深度. Depth(E) = 2 高度(Height)：Height = 3 兄弟姐妹(Sibling)：C是B和D的兄弟姐妹. 子树(Subtree)：树由节点及其后代组成 边(Edge of tree)：边是树的另一个基本部分。边连接两个节点以显示它们之间存在关系。每个节点(除根之外)都恰好从另一个节点的传入连接。每个节点可以具有多个输出边。 通路(Path)：路径是由边连接节点的有序列表。如I到G的Path： I->F->B->A->C->G

树的ADT

二叉树可以通过存储一个节点的数据加两个子指针来实现. 具有两个以上孩子的树可以使用链接的节点列表来实现 通用方法: Int size() boolean isEmpty() Iterator elements() Iterator positions() 查询方法: boolean isInternal(p) boolean isExternal(p) boolean isRoot(p) 更新方法: object replace (p, o) 访问器方法: Node root() Node parent(p) List children(p)

树的遍历方法

有三种常用的模式来访问树中的所有节点。这些模式之间的差异是每个节点被访问的顺序。我们称这种访问节点方式为“遍历”。 先序： 在前序遍历中，我们首先访问根节点，然后递归地做左侧子树的前序遍历，随后是右侧子树的递归前序遍历。 中序(顺序遍历)：在一个中序遍历中，我们递归地对左子树进行一次遍历，访问根节点，最后递归遍历右子树。 后序：在后序遍历中，我们递归地对左子树和右子树进行后序遍历，然后访问根节点。