树的递归定义 树是n(n≥0)个结点的有限集T。当T非空时,满足: 1.有且仅有一个特别标出的称为根的结点r 2.除根结点外,其余结点可分为m(m>=0)个互不 相交非空的有限集T1,T2,…m,其中每一个集 合本身又是一棵非空树,称为根r的子树( subtree) 空树:结点数为0的树。 树可以没有子树(m=0 下一顶
返回本章首页 下一页 上一页 树的递归定义： 树是n (n≥0) 个结点的有限集T。当T非空时，满足： 1. 有且仅有一个特别标出的称为根的结点r； 2. 除根结点外，其余结点可分为m（m >= 0）个互不 相交非空的有限集T1, T2, …, Tm，其中每一个集 合本身又是一棵非空树，称为根r 的子树(subtree)。 • 空树：结点数为0 的树。 • 树可以没有子树（m = 0）
8.1.2基本术语 Fd b F H (a)树t b)树t 有序树和无序树:树中的子树的顺序是否重要 下一顶
返回本章首页 下一页 上一页 8.1.2 基本术语 (a) 树t (b) 树t ' 有序树和无序树：树中的子树的顺序是否重要
父结点,子结点,边 兄弟结点 祖先,子孙 D 路径,路径长度 结点的层数(根的层为0) EA F6 bG 深度或高度(结点的最大层数)H 结点的度数、树的度数 树叶、分支结点 结点的次序(最左,…) 下一顶
返回本章首页 下一页 上一页 父结点，子结点，边 兄弟结点 祖先，子孙 路径，路径长度 结点的层数（根的层为0） 深度或高度（结点的最大层数） 结点的度数、树的度数 树叶、分支结点 结点的次序（最左，…）
8.1.3树林 树林:m(m≥0)棵互不相交的树的集合 棵非空树是二元组Tree=(ro,F),其中root是 树根 结点,F是m(m≥0)棵子树构成的树林 F=(T1, T2,…,TmTi称作根ro的第i棵子树。 注意树与树林的关系 树由根和子树树林组成 树林由一集树组成 下一顶
返回本章首页 下一页 上一页 8.1.3 树林 树林：m（m≥0）棵互不相交的树的集合 一棵非空树是二元组Tree = (root, F) , 其中root是 树根 结点，F 是m（m≥0）棵子树构成的树林。 F=(T1, T2,…, Tm)。Ti 称作根root 的第i 棵子树。 注意树与树林的关系： • 树由根和子树树林组成 • 树林由一集树组成
8.1.4树的基本运算 抽象运算(操作) 创建空树 ree create Tree(Node p, Tree tl, Tree t2,..., Tree ti) i=1,2,3,… 判断某棵树是否为空 int isNull( Tree t 求树中的根结点,若为空树,则返回特殊值 Node root( Tree t) 求指定结点的父结点,当结点是树根时返回特殊值 Node parent( Node p) 下一顶
返回本章首页 下一页 上一页 8.1.4 树的基本运算 抽象运算（操作） •创建空树 Tree createTree(Node p, Tree t1, Tree t2, …, Tree ti ) i = 1, 2, 3, … •判断某棵树是否为空 int isNull ( Tree t ) •求树中的根结点，若为空树，则返回特殊值 Node root ( Tree t ) •求指定结点的父结点，当结点是树根时返回特殊值 Node parent ( Node p )