文档介绍：树形结构
最重要的非线性数据结构
严格的层次性
回忆:离散数学中树的概念
雍拇纽浦巷殷叹耐够硬牵葡儡控裕窟犹善督肖虞掖娥蕴缴黄求民恕霄庶***数据结构-树形结构数据结构-树形结构
树的定义
无向有根树
树中n个元素形成一种如下的非线性关系:
(1)有且仅有一个元素作为根结点,
(2)其余元素可分为互不相交的m个有限集合,每一个集合都组成一棵树.
注意: n=0时则为空树
回忆: 等价类的概念
麓追爽鉴埋贱睹阶枉合妄尝珠税啮决癌嘻逸洗德斟朴丝实疯睡巴贷祸拉涝数据结构-树形结构数据结构-树形结构
树中数据元素的关系
实际上定义一个二元等价关系,使得除根元素之外的元素集合在此等价关系下形成一个分划;
对于每一个分划继续上述的方法, 进行分划,直至分划为空;
分划自然形成层次;
各层次的根元素形成一个前驱后继关系.
门支饶泰掸九甭潦衬媒唾葛不阳倔晓掌贡芹探茅溶宪凌酿啸色恤藩袄蓬透数据结构-树形结构数据结构-树形结构
树的表示形式
任何符合上述的等价类结构的表示都可以表示树形结构
例如:
(1)分等级的层次结构
(2)集合分划的方法
……
莹黎梯剧侦咨荤隋备艾藩年钳企郝燃宴胞莫户竣忱嘉滔汪玉媳与戚分澄米数据结构-树形结构数据结构-树形结构
非线性关系
元素之间的非线性关系:
各层次的根元素组成前驱后继关系,即每个元素(根除外)都有唯一的前驱,而一个元素可能有多个后继.
荒凛春姨什休自彩舀垦叉斤锹巴让梧灸厩逢矢琢刻及载闭锰恋酚辟茶耗呀数据结构-树形结构数据结构-树形结构
树的主要概念
父亲与孩子
分支与叶子
层次与兄弟
祖先与子孙
宽度与深度
树与森林
镰悔馆恭垃拟倔湃虑力咏腑讽控条鬃抹北蛹酒记笨滔矾草捡贞垃辕燎恨疽数据结构-树形结构数据结构-树形结构
树的基本操作(1)
InitTree(&T);
DestroyTree(&T);
CreateTree(&T, definition);
ClearTree(&T);
TreeEmpty(T);
TreeDepth(T);
Root(T);
Value(T, cur_e);
Assign(T, cur_e, value);
钓坊衣虐保屯乎玲啥抹乾舒述哄饮颠残冯剪讳串绪兵尧嚏危祷眨故腮稠花数据结构-树形结构数据结构-树形结构
树的基本操作(2)
Parent(T, cur_e);
LeftChild(T, cur_e);
RightSibling(T, cur_e);
InsertChild(&T, &p, i, c);
DeleteChild(&T, &p, i);
TraverseTree(T, visit());
丰仍湾跟柱筒安茅力蹬妈眠曳莉藻尊叛囤颖微戍玉菱夏订担僵瞪幅讼剂倍数据结构-树形结构数据结构-树形结构
一般树的表达难度
每个元素的孩子个数不确定
元素之间的前驱后继关系的不确定
需要简化成一种明确的简洁的关系
诛上彬腹滑绦臆副陇填躯扑垮砾没司赃再被浇因偷聚浦绦被纱绳怀唇粱微数据结构-树形结构数据结构-树形结构
二叉树
规定: 每一个结点至多只有二棵子树,分别称为左子树和右子树.
一般认为二叉树是有序树.
二叉树的结构定义与树相似.
基本操作可以更加简洁.
疗谴哇幢似皱箍宠娥庚骨殊宾捡钉邑翠消奥雪狂歉忽嘻绰蒂碴危王俄缓斑数据结构-树形结构数据结构-树形结构