国家级精品课程—《数据结构与算法》 第6章树 张铭、赵海燕、王腾蛟、宋国杰、高军 http:/www.ipk.pku.edu.cn/pkuipk/courselsig 北京大学信息科学与技术学院 “数据结构与算法”教学小组 本章主笔:王腾蛟 版权所有,转载或翻印必究
国家级精品课程—《数据结构与算法》 张铭、赵海燕、王腾蛟、宋国杰、高军 http://www.jpk.pku.edu.cn/pkujpk/course/sjjg/ 北京大学信息科学与技术学院 “数据结构与算法”教学小组 本章主笔：王腾蛟 ©版权所有，转载或翻印必究 第6章 树
主要内容 61树的定义和基本术语 62树的链式存储结构 6.3树的顺序存储结构 64K叉树 65树知识点总结 “十一五”国家缀规划教材。张铭,王腾蛟,赵海￡,《飙据结构与算法》,高教社,B0.6
“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008. 6。 主要内容 ◼ 6.1 树的定义和基本术语 ◼ 6.2 树的链式存储结构 ◼ 6.3 树的顺序存储结构 ◼ 6.4 K叉树 ◼ 6.5 树知识点总结
6.1树的定义和基本术语 611树和森林 612森林与二叉树的等价转换 613树的抽象数据类型 614树的周游 “十一五”国家缀规划教材。张铭,王腾蛟,赵海￡,《飙据结构与算法》,高教社,B0.6
“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008. 6。 ◼ 6.1.1 树和森林 ◼ 6.1.2 森林与二叉树的等价转换 ◼ 6.1.3 树的抽象数据类型 ◼ 6.1.4 树的周游 6.1 树的定义和基本术语
611树和森林 树(tre是包括n个结点的有限集合 T(n≥1),使得: 口有且仅有一个特定的称为根(ot)的结点。 口除根以外的其它结点被分成m个(m≥0)不 相交的有限集合T1,T2,…,Tm,而每一 个集合又都是树。其中树T,T2,…,Tm 称作这个根的子树( subtree “十一五”国家缀规划教材。张铭,王腾蛟,赵海￡,《飙据结构与算法》,高教社,B0.6
“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008. 6。 6.1.1 树和森林 ◼ 树(tree)是包括n个结点的有限集合 T（n ≥ 1），使得： ❑ 有且仅有一个特定的称为根(root)的结点。 ❑ 除根以外的其它结点被分成m个(m ≥ 0)不 相交的有限集合T1，T2，…，Tm，而每一 个集合又都是树。其中树T1，T2，…，Tm 称作这个根的子树(subtree)
611树和森林 B 图61树形表示法 “十一五”国家缀规划教材。张铭,王腾蛟,赵海￡,《飙据结构与算法》,高教社,B0.6
“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008. 6。 6.1.1 树和森林 图6.1 树形表示法 A B C D E F G H I J K L