第十四讲 树(1)

概述

1. 树：数据成员、操作
2. 二叉树
3. 二进制搜索树

基本思想

在计算机科学中，树是分层结构的抽象模型。
一棵树由具有父子关系的节点组成。经常为时间牺牲空间，所有“洞”都浪费空间。依赖于元素的排序，这意味着内存块的排序。
应用：组织结构图、文件系统、编程环境

树术语

1. Root：无父节点
2. Internal node：具有至少一个子节点的节点
3. External node（leaf）：无子节点
4. Ancestors of a node：父母、祖父母等等
5. Descendant of a node：孩子、孙子、重孙子等等
6. Depth of a node：某节点的深度
7. Height：任何节点的最大深度
8. Sibling：兄弟姐妹
9. Subtree：某节点及其后代
10. Edge of tree：是一对节点（u，v），其中u是v的父节点
11. Path：节点S.T.的一个序列，来自边缘的任意两个连续的节点

树的ADT

1. 通用方法：
   （1）size() → Int
   （2）isEmpty() → boolean
   （3）elements() → Iterator
   （4）positions() → Iterator
2. 访问器方法：
   （1）root() → Node
   （2）parent(p) → Node
   （3）children(p) → list<Node>
3. 查询方法：
   （1）isInternal(p) → boolean
   （2）isExternal(p) → boolean
   （3）isRoot(p) → boolean
4. 更新方法：
   （1）replace(p,o) → object
   （2）其他
5. 二叉树可以通过存储一个节点的数据加两个子指针来实现
6. 具有两个以上孩子的树可以使用链接的节点列表来实现