图的遍历(搜索)算法
有根树与有向树
树是一个没有圈的连通图。如果指定树的一个顶点为根,则这棵树称为有
根树。在有根树中,邻接根的顶点称为根的儿子,而根称为这些儿子的父亲。
对于不是根的顶点,除了它的父亲之外其它与之邻接的顶点都称为该顶点的儿
子,该顶点也自然称为它的这些儿子的父亲。没有儿子的顶点称为叶顶点。
从根到每一个叶顶点都有一条唯一的路。这些路的最长者的长度称为该树
的高度;不是根的顶点 不通过其父顶点而能到达它所能到达的每个叶顶点只
有一条路,这些路的最长者的长度称为顶点 的高度。树的根到每个顶点都有
一条唯一的路,这条路的长度称为该顶点在树中的深度。如在图 2-2-1 的二叉
树中,树的高度为 4,顶点 D,E 的深度都是 2。每个顶点的高度与深度之和恰
好等于树的高度。在有根树 T 中,顶点 v 不通过其父顶点而能到达的所有顶点
同 v 一起生成的树称为以 v 为根的子树。
二叉树是这样一棵有根树,它的每个顶点至多有两个儿子。除了叶顶点以
外,每个顶点都恰有两个儿子的有根树称为完整的二叉树。高度为 的完整二
叉树恰有 个顶点,它的所有顶点按照从上到下、从左到右的顺序可以编
号为: 。从这样编号的完整二叉树中的某一位置开始,删掉后面
编号的所有顶点及与之关联的边所得到的二叉树称为一棵完全二叉树。
一个二叉树通常用两个数组 Lson 和 Rson 表示。假设二叉树的顶点标为
,则 Lson[i]=j 表示顶点 j 是顶点 i 的左儿子;同样,Rson[i]=j 表示顶
点 j 是顶点 i 的右儿子。一个完全的二叉树可以用一个数组来表示:设 T 是一棵
高度为 的完全二叉树,则数组的第一个元素是该树的根,第二个元素是根的
A
B
F
D
G
E
C
H I