8 树与树林.pdf

面向21世纪课程教材 普通高等教育“十一五”国家级规划教材 北京市高等教育精品教材 教育部普通高等教育精品教材 算法与数据结构 第八讲：树与树林 1 张乃孝等编著 《算法与数据结构—C语言描述》 5 二叉树与树 • 5.5 树及其抽象数据类型 • 5.6 树的实现 • 5.7 树林 2 5.5 树及其抽象数据类型 • 树的几种不同表现形式 3 基本定义 • 树是n(n≥0)个结点的有限集T, T非空时满足: –有且仅有一个特殊的称为根(root)的结点r ； –除根结点外,其余结点可分为m(m≥0)个互不相交的 非空有限集T 1, T2 , …,Tm ,其中每个集合又是一棵 非空树,称为r 的子树(subtree)。 • 关于子树 –结点数为0的树称为空树； –一棵非空树也可以没有子树(m=0)，即这棵树只包 含一个根结点； –如有子树，则子树非空。 4 主要概念 • 空树 • 父结点、子结点、路径、路径长度 • 结点的度数 • 树的度数 • 无序树、有序树 • 结点的次序 • 最左子结点、长子、次子 • 右兄弟 5 抽象数据类型 ADT Tree is operations Tree createEmptyTree (void) 创建一棵空树。 Tree consTree(Node p ,Tree t , …Tree t ) 1 i 以P为根，t …t 为子树创建一棵树。 1 i int isNull ( Tree t ) 判断树t是否为空树。 6 Node root ( Tree t ) 返回树t 的根结点。若为空树，则返回一特殊值。 Node parent (Node p ) 返回结点p 的父结点。当指定的结点为根时，它 没有父结点，返回一个特殊值。 Tree leftChild (Tree t ) 返回树t 的长子树。当指定树没有子树时，返回 一特殊值。 Tree rightSibling (Tree t ) 返回树t 的右兄弟树。当指定树没有右兄弟子树 时，返回一特殊值。 end ADT Tree 7 树的周游 • 深度优先周游： 先根次序 ：A B D E I J F C G H 后根次序 ：D I J E F B G H C A  能否确定树结构？如何确定？  广度优先周游 : A B C D E F G H I J