离散数学课件第七章树.doc
21页
第7章 树trees分类根树有序树定位树无向树标号{a,b}无有无有无有无有N=1N=2N=3§7.1 树定义1：T是集合A上一个二元关系，T称为树tree，如果存在v0∈A，任意v∈A，v≠v0，到v0都有唯一一条路径，（v0, v0）ÏT. T叫做根树，记做（T，v0）A中元素称为T的顶点vertex，T中元素称为边，v0称为根root定理1. 设（T，v0）是树，则(a)T中没有回路b)只有一个根v0c)任意v∈A，v≠v0，v有入度1，v0入度是0证明：定义2层次levelv0的层次为0，v0的子女offspring层次为1，v0是子女的父母parent vi的层次为k，vi的子女offspring层次为k＋1，vi是子女的父母parent，T的最大层次称为高度height无子女的顶点叫叶leafvi的子女叫同胞sibling，同胞如有长幼，从左到右，老大，老二，老三等，组成线性序，T称为有序树，ordered tree定理2. 设（T，v0）是根树，则(a)T反自反b)T反对称c)(a,b)∈T，(b，c)∈T Þ (a，c)ÏT定义3：n－树：每个顶点至多n个子女二叉树：2－树。
完全n－树：每个非叶顶点恰有n个子女定义4A rooted binary tree is a rooted tree in which every node has at most two children. A full binary tree (sometimes proper binary tree or 2-tree) is a tree in which every node other than the leaves has two children. A perfect binary tree is a full binary tree in which all leaves are at the same depth or same level.[1] (This is ambiguously also called a complete binary tree.) A complete binary tree is a binary tree in which every level, except possibly the last, is completely filled, and all nodes are as far left as possible.[2] An infinite complete binary tree is a tree with levels, where for each level d the number of existing nodes at level d is equal to 2d. The cardinal number of the set of all nodes is . The cardinal number of the set of all paths is . A balanced binary tree is a tree where the depth of all the sub-trees differs by at most 1. 定理3. 设（T，v0）是根树，v∈T，则T(v)是T的子树，T(v)的根是v。
Homework P248－24918，19，20，21，26，28§7.2标识树labeled trees中缀表达式central operator expression（3－2×x）＋（（x－2））＋（3＋x）） 定位树positional tree定义Positional n-tree is a n-tree whose vertex potentially has exactly n offspring ordered by1,2,…,n, but some of the offsprings may be missing.定位3－树每个顶点的子女都有一定位置定位2－树 左右子树 普通二叉树问题7.2.1 1） n个节点的定位二叉树有多少个？2） 如何枚举？定位二叉树的计算机表示Computer Representation of Binary Positional TreesIndexLeftDataRight12start026＋337+4483550x0610-12711-098030902010030110x01214×13130x014020Homework PP253－25410，11，12，16，18，§7.3 树的遍历tree searching（自学）二叉树的遍历中序遍历的递归算法定义(1)遍历左子树；(2)访问根结点；(3)遍历右子树。
先序遍历的递归算法定义(1) 访问根结点；(2) 遍历左子树；(3) 遍历右子树后序遍历得递归算法定义(1)遍历左子树；(2)遍历右子树；(3)访问根结点树的搜索深度优先搜索广度优先搜索启发式搜索博弈树搜索§7.4无向树undirected trees无向图连通不含回路的图叫无向树例bfgdcea无向树：有向树的对称闭包定义：有向树的对称闭包定理1. R是对称关系则下列命题等价the following statement are equivalent：（TFAE）a) R是无向树b) R连通connected，无回路acycle证明：a) Þb)R显然连通若R有回路b) Þa)若R连通无回路，我们可以在R上构造一棵树定理2. R是对称关系TFAER是无向树R无回路，每增加一条边，都产生一个新的回路证明：Þ R连通，所以没加一边都有新的回路 Ü 若R不连通则 有两个以上连通分支，所以可以加一边不产生回路R连通，去掉任意一条边都不连通证明：Þ 若去掉一边还连通，则原图一定有回路 Ü 若原图有回路，则可以去掉一边后仍连通R无回路，且有n-1条边Þ 对定点做归纳即可得 边数为n-1 Ü 若原图不连通，则有k个连通分支，每支都是树，总边数为n-k。
R连通，且有n-1条边ÞÜ若原图有回路，则删掉k条边后为树，则总边数为n-1+k连通图的生成树spanning tree: 定义 含有所有顶点的极小连通图.存在性n个顶点连通图至少有n-1条边m条边的连通图去掉m－n＋1条边可以得到生成树从连通图中如有回路，去掉回路中的一条边，继续直至没有回路，就得到生成树唯一性最小生成树：权重最小的生成树带权的边：带边长的边带权的图：每边都带权Prim算法：设 G=
2） 将所得到的图为G，其对应的无向图为H3） 若H连通，则已经找到4） 否则H的每个连通分支，要么是从点1出发的一个树，要么去一条边后是树(假设只有一个C)5） 原图的最小树形图必然是连通分支C取一条从外部指向内部圈的边，并去掉圈内的指向该点的边如果不知道从那个顶点开始，则可以添加定点0，和n条权值为M的边HomeworkP270－271 14，18P275－276 4，8。
