鞍山科技大学：《C语言程序设计与数据结构》第8章 树的存储结构及应用

第8章树的存储结构及应用 8,1树与树林 8.2树和树林的存储表示 8.3二叉树 8.4二叉树的存储表示 8.5哈夫曼算法及其应用 上章 道最

返回本章首页 下一页 上一页 第8章树的存储结构及应用 • 8.1 树与树林 • 8.2 树和树林的存储表示 • 8.3 二叉树 • 8.4 二叉树的存储表示 • 8.5 哈夫曼算法及其应用 上一章 下一章 返回目录

8.树与树林 8.1.1树的定义 8.12基本术语 8.,1.3树林 8.1.4树的基本运算 8.1.5树的周游 8.,1.6树林的周游 下一顶

返回本章首页 下一页 上一页 8.1 树与树林 • 8.1.1 树的定义 • 8.1.2 基本术语 • 8.1.3 树林 • 8.1.4 树的基本运算 • 8.1.5 树的周游 • 8.1.6 树林的周游

8.1.1树(Tree)的定义 树的例子:家族树 A有子女B,C;B和C分别有子女D,E,F和G,H E有子女I,J。 T=(N,R),其中 N=(A,B, C, D,E,F,G,H,I,J) °R={,,,, °,,,} 上一页 关系有层次性,总是高层与低层相关,同层之间无美 也没有低层到高层的关系。与不同元素相关的元素也 互不相交。 下一顶

返回本章首页 下一页 上一页 8.1.1 树(Tree) 的定义 树的例子：家族树 • A 有子女B, C；B 和C 分别有子女D, E, F 和G, H; • E有子女I , J。 • T = (N, R) ，其中 • N={A, B, C, D, E, F, G, H, I, J} • R={, , , , , • , , , } • 关系有层次性，总是高层与低层相关，同层之间无关， 也没有低层到高层的关系。与不同元素相关的元素也 互不相交

树的表示方法 Q B C DEFGH 基本图形表示 凹入表 下一顶

返回本章首页 下一页 上一页 树的表示方法：

文氏图 B IE CLH fA(B(D)E(1)()(C(G)11 嵌套括号表乖法

返回本章首页 下一页 上一页

树的递归定义 树是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 )