Algorithms and Datastrucstures:Trees 第五章树及二叉树 5.1树的定义和术语 5.2二叉树 5.3二叉树的遍历 5.4二叉树遍历的迭代器类 5.5中序穿线树(×) 5.6最优二叉树及其应用 5.7树和森林 1 ALDS
1 物料管理 ALDS 1 Algorithms and DataStrucstures:Trees 5.1 树的定义和术语 5.2 二叉树 5.3 二叉树的遍历 5.4 二叉树遍历的迭代器类 5.5 中序穿线树（×） 5.6 最优二叉树及其应用 5.7 树和森林 第五章 树及二叉树
Algorithms and Datastrucstures:Trees 5.1树的定义和术语 树是n(n≥1)个结点的有限集合T,并且满足： (1)有一个被称之为根(root)的结点； (2)其余的结点可分为m(m≥0)个互不相交的集合T1,T2,,Tm, 这些集合本身也是一棵树，并称它们为根结点的子树(Subree)。 每棵子树同样有自己的根结点。 D E M 2 ALDS
2 物料管理 ALDS 2 Algorithms and DataStrucstures:Trees 5.1 树的定义和术语 树是n (n≥1) 个结点的有限集合T，并且满足： (1)有一个被称之为根(root)的结点； (2)其余的结点可分为m(m≥0)个互不相交的集合Tl，T2，…，Tm， 这些集合本身也是一棵树，并称它们为根结点的子树(Subree)。 每棵子树同样有自己的根结点
D A K M 结点 兄弟结点 ·有序树 结点的度 祖先结点 ·无序树 ·叶子结点 ·子孙结点 森林 内部结点 ·结点所处层次 ·儿子结点 ·树的高度 ·父亲结点
•结点 •结点的度 •叶子结点 •内部结点 •儿子结点 •父亲结点 •兄弟结点 •祖先结点 •子孙结点 •结点所处层次 •树的高度 •有序树 •无序树 •森林
Algorithms and Datastrucstures:Trees 树的定义的形式化描述 树的定义还可形式化的描述为二元组的形式： T=(D,R) 其中D为树T中结点的集合，R为树中结点之间关系的集合。 D={Root}UDp 其中，Root为树T的根结点，D为树T的根Root的子树集合。D可由下式表示： Dp=D1UD2U.UDm且D:nD;=Φ(i≠j,1≤i≤m,1≤j≤m) 当树T中结点个数n=1时，R=Φ；当树T中结点个数n>1时有： R={<Root,r;>,i=1,2,...m} 其中，Root为树T的根结点，r:是树T的根结点Root的子树T:的根结点。 4 ALDS
4 物料管理 ALDS 4 Algorithms and DataStrucstures:Trees 树的定义的形式化描述 树的定义还可形式化的描述为二元组的形式： T＝（D，R） 其中D为树T中结点的集合，R为树中结点之间关系的集合。 D＝{Root}∪DF 其中，Root为树T的根结点，DF为树T的根Root的子树集合。DF可由下式表示： DF ＝D1∪D2∪…∪Dm且Di∩Dj ＝Φ（i≠j，1≤i≤m，1≤j≤m） 当树T中结点个数n=1时，R＝Φ；当树T中结点个数n > 1时有： R＝{<Root，ri>，i＝1，2，…，m} 其中，Root为树T的根结点，ri是树T的根结点Root的子树Ti的根结点
Algorithms and Datastrucstures:Trees 树的数学定义 树：连通无回路的无向图 不是树 有回路 a 不是树 不连通 5 ALDS
5 物料管理 ALDS 5 Algorithms and DataStrucstures:Trees a b 不是树 有回路 a b 不是树 不连通 a b 树的数学定义 树：连通无回路的无向图