苏J9509 轻质隔墙、墙身、楼地面变形缝.pdf

树的定义和基本术语
二叉树
遍历二叉树和线索二叉树
树和森林
哈夫曼树及其应用
树的计数
本章小结
习题
定义:树(tree)是n(n≥0)个结点的有限集,在任一棵非空树中:1)有且仅有一个特定的称为树根(root)的结点;2)当n>1时,其余结点可分为m(m>0)个互不相交的有限集T1,T2,……Tm,其中每一个集合本身又是一棵树,称为根的子树(subtree)。例如:
特点:1)在非空树中至少有一个结点—根
2)树中各子树是互不相交的集合
树的定义和基本术语
例如:
A
(a)
A
B
C
D
E
F
G
H
I
J
M
K
L
(b)
只有根结点的树
根
子树
有子树的树
ADT Tree { 数据对象D:D是具有相同特性的数据元素的集合。 数据关系R:若 D 为空集,则称为空树;  若 D 中仅含一个数据元素,则关系R为空集; 否则 R={H},H是如下二元关系:
(1) 在D中存在唯一的称为根的数据元素 root,它在关系H下无前驱; (2) 若D-{root}≠⌽,则存在D-{root}的一个划分D1,D2,D3,…,Dm(m>0) ,即对于任意的j ≠k(1≤j,k≤m)有Dj∩Dk=⌽,且对任意的i=1,2,…,m。惟一存在数据元素xi∈Di, 有<root,xi> ∈ H;
抽象数据类型树的定义如下:
(3)对应于D-{root}的以上划分,H-{<root,x1> ,
<root,x2>,…, <root,xm> }有惟一的一个划分H1,H2,H3,…,Hm(m>0) ,即对于任意的j ≠k(1≤j,k≤m)有Hj∩Hk=⌽,且对任意的i(1≤i≤m),Hi是Di上的二元关系,( Di,Hi)是一棵符合本定义的树,称为根root的子树。
基本操作:15种基本操作,P119
}//tree
基本术语:
树:
无向树(无环的无向连通图)
有向树(要不考虑孤的方向时是一棵无向树)
根树(有且只有一个入度为0的结点(根),其余结点入度为1。我们书上讲的为根树
基本术语:
结点:
表示树中的元素,包括数据项及若干指向其子树的分支
结点的度:
分支个数(结点拥有的子树个数)。
树的度:
树中所有结点的度的最大值
叶子结点:
度为零的结点
分支结点:
度大于零的结点
从根到结点的路径:由从根到该结点所经分支和结点构成
孩子结点、双亲结点、兄弟结点、堂兄弟、祖先结点、子孙结点
A
B
E
F
K
L
C
G
D
H
I
J
M
树的深度:
树中叶子结点所在的最大层次
假设根结点的层次为1,根的孩子就在第2层,一个结点在第l 层,则其子树的根结点在l+1
结点的层次:
是 m(m≥0)棵互不相交的树的集合
森林:
任何一棵非空树是一个二元组
Tree = (root,F)
其中:root 被称为根结点,
F 被称为子树森林 P121。
有向树:……
有序树:
子树之间存在确定的次序关系。
无序树:
子树之间不存在确定的次序关系。
根树:……
InitTree(&T) // 初始化置空树
DestroyTree(&T) // 销毁树的结构
CreateTree(&T, definition) // 按定义构造树
ClearTree(&T) // 将树清空
Root(T) // 求树的根结点
Value(T, cur_e) // 求当前结点的元素值
LeftChild(T, cur_e) // 求当前结点的最左孩子
RightSibling(T, cur_e) // 求当前结点的右兄弟
TreeEmpty(T) // 判定树是否为空树
TreeDepth(T) // 求树的深度
Assign(T, cur_e, value) // 给当前结点赋值
InsertChild(&T, &p, i, c)
// 将以c为根的树插入为结点p的第i棵子树
Parent(T, cur_e) // 求当前结点的双亲结点
TraverseTree( T, Visit() ) // 遍历
DeleteChild(&T, &p, i) // 删除结点p的第i棵子树
树的表示形式:P120
1)树型表示
2)嵌套集合法
3)广义表法
4)凹入表示法
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
线性结构
树型结构
第一个数据元素(无前驱)
根结点(无前驱)
最后一个数据元素
(无后继)
多个叶子结点(无后继)
其它数据元素(一个前驱、一个后继)
其它数据元素(一个前驱、
多个后继)
对比