1、树 /Trees11.1 树的概念 /Introduction of Trees11.2 树的应用 /Applications of Trees11.3 树的遍历 /Tree Traversal11.4 生成树 Spanning Trees 11.5 最小生成树 minimum Spanning Trees11.1: Introduction to Trees A tree is a connected undirected graph with no simple circuits. Theorem: There is a unique simple path between any two
2、 of its nodes. An undirected graph without simple circuits is called a forest.You can think of it as a set of trees having disjoint sets of nodes.G1 G2 G3 G4Examples of Trees and Graphs that are not Trees3) 连通且4) 无回路 ,但增加一条新边 ,得一个且仅一个回路 ;5) 连通但删去后便不连通 ;6) 每一对结点间有一条且仅有一条路 .给定图 T,以下关于树的定义是等价的 :1) 无回路的
3、连通图 ;2) 无回路且 树的概念定义 树： 一个无简单回路的连通无向图称为一棵 树 /Tree。记为。定义 林： 无简单回路的无向图是 林 /Forests。定理 1树的基本性质：(1）树是平面图。(2）树中任二顶点间都有唯一道路。(3) 去掉树的任一边，成了林。(4)在树上任添一条边，产生唯一回路。(5)设（，），则。 树是平面图，且无回路，区域数 ，满足欧拉公式 ，即。也可用强归纳法证：（对归纳）(1） ，显然成立(2）假设时成立，时，先移去一条边，成了两棵树 1和 2，有 1 1， 2 2，且 1 2，故 1 2 1 2（ 1 2）。Rooted Trees A rooted tree
4、 is a tree in which one node has been designated the root.Every edge is (implicitly or explicitly) directed away from the root. You should know the following terms about rooted trees:Parent, child, siblings, ancestors, descendents, leaf, internal node, subtree.定义 有向树：如果有向图（，）对应的无向图是树，称为 有向树 /directed tree。定义 有根树：如果有向树存在唯一一个入次为的顶点，其余顶点入次均为，称此有向树为 有根树 /rooted tree。定义 根：有根树中入次为的顶点称为 根 /root。定义 叶：有根树中出次为的顶点称为 叶 /leaf。定义 枝点：有根树中除叶以外的顶点均为 枝点/internal vertices。树根 root树叶 leave孩子 offspring双亲 ParentLevel 0 Level 2 Level 1 Level 3 Level 4 兄弟 siblingnHeight（高度） :the largest level number of the tree
