本书在选材与编排上贴近当前普通高等院校“数据结构”课程的现状和发展趋势，内容难度适中，突出实用性和应用性。本书的具体内容并未涉及各种数据结构，而是通过分类和讲解典型结构使读者形成对数据结构的宏观认识。根据内容的侧重，本书共分8章，分别为绪论、线性表、栈和队列、串和数组、树形结构、图、排序和查找。
本书可作为普通高校计算机相关专业“数据结构”课程的教材，也可供学习数据结构的读者自学使用（包括参加计算机等级考试或相关专业自学考试）、参考，还可供程序员、系统工程师等相关人员阅读参考。
本书是高等院校计算机科学、软件工程及相关专业“数据结构”课程的理想教材。
内容精炼、强化基础、合理安排内容结构，做到内容由浅入深，循序渐进。
应用实例丰富完整。代码有详细明了的注释，易于阅读。
章节后附有小结和习题，便于学习总结和提高。
采用Java的泛型方法来体现方法的通用性。
图文并茂，便于学生直观地理解数据结构与算法。
前言
随着近年来计算概念的快速发展，计算学科已经发展成为一个内涵繁杂的综合性学科，其至少可以划分为计算机工程(CE)、计算机科学(CS)、信息系统(IS)、信息技术(IT)和软件工程(SE)5个领域，而且不同领域的人才所应具备的知识结构与能力侧重也不尽相同。尽管如此，从目前已经完成的部分来看，数据结构在各领域的知识体系中仍然占据着重要的位置。“数据结构”是普通高等院校计算机和信息管理等专业的一门必修课程，主要讨论数据的逻辑结构、在计算机中的存储结构以及对其进行的各种处理运算的方法和算法。
N.Wirth早在20世纪70年代就指出“程序=数据结构+算法”。数据结构主要研究数据在计算机中存储、组织、传递和转换的过程及方法，这些也是构成与支撑算法的基础。近年来，随着面向对象技术的广泛应用，从数据结构的定义、分类、组成到设计、实现与分析的模式和方法都有了长足的发展，现代数据结构更加注重和强调数据结构的整体性、通用性、复用性、简洁性和安全性。
为遵循上述原则，本书选择Java作为描述语言，因为相对于其他语言，Java程序设计语言是应用最广泛、面向对象程度化最高的语言，利用Java语言中的类和接口能够准确地描述任何一种数据结构的逻辑定义和运算，利用一种存储结构定义的派生类能够高效地实现对数据的运算。
在内容的选取与结构上，本书并未涉及各种数据结构，而是通过分类和讲解典型结构使读者形成对数据结构的宏观认识。根据内容的侧重，本书共分8章，分别为绪论、线性表、栈和队列、串和数组、树形结构、图、排序和查找。
第1章介绍数据结构的基本概念，算法的描述和算法时间复杂度、空间复杂度等内容，是全书的基础。
第2章主要介绍线性表的基本概念和抽象数据类型定义、线性表顺序和链式两种存储方式的表示、基本操作的实现和相应的应用。
第3章简要介绍栈和队列的基本概念和抽象数据类型定义、栈和队列在顺序存储和链式存储结构下的基本操作和应用。
第4章主要介绍串的基本概念和数据类型定义、串的存储结构、基本操作实现和应用等内容。
第5章主要介绍树和二叉树的基本概念，详细介绍二叉树的性质和存储结构、遍历方法的实现及应用、哈夫曼树的概念和构造方法。
第6章主要介绍图的基本概念、抽象数据类型定义、存储结构和遍历方法，还介绍最小生成树的基本概念和算法、最短路径的相关算法、拓扑排序的概念和实现方法。
第7章介绍排序的基本概念，插入排序、交换排序、选择排序、归并排序等多种排序的原理、实现方法及性能分析。
第8章主要介绍查找的基本概念，顺序查找、二分查找等查找的原理、实现方法和性能分析，平衡二叉树、哈希表的概念、结构定义和实现方法。
本书的理论知识的教学安排建议如下：
章节内容学时数
第1章绪论2
第2章线性表4~6
第3章栈和队列6~8
第4章串和数组2~4
第5章树形结构6~8
第6章图4~8
第7章排序4~6
第8章查找4~6
建议先修课程：Java语言
建议理论教学时数：32~48学时
建议实验(实践)教学时数：16~32学时
本书中的所有算法都已经通过上机调试，尽量确保算法的正确性。在每章内容后都有小结，便于读者复习总结，并配有丰富的习题，包括选择题、填空题、算法设计题等，给读者更多思考的空间。
本书在以下几个方面具有突出特色：
（1）内容精练，强化基础，合理安排内容结构，做到由浅入深、循序渐进。
本书各章节都从基本概念入手，逐步介绍其特点和基本操作的实现，把重点放在基础知识的介绍上，缩减难度较大的内容，使理论叙述简洁明了、重点突出、详略得当。
（2）应用实例丰富、完整。
本书通过丰富的应用实例和源代码使理论和应用紧密结合，增强学生的理解能力，锻炼程序设计思维，并且代码有详细明了的注释，易于阅读。
（3）每章后面附有小结和习题，便于学习、总结和提高。
本书结合学生的学习实际选择难度适中、逻辑合理，适于初学者和进阶者开拓思路、深入了解数据结构使用方法和技巧的习题，并附有详细的解答过程和注意要点，达到通俗易懂、由浅入深的效果，培养读者迁移知识的能力。
（4）采用Java的泛型方法来体现方法的通用性。
本书采用面向对象的观点讨论数据结构技术，先将抽象数据类型定义成接口，再结合具体的存储结构加以实现，并以各实现类为线索对类中各种操作的实现方法加以说明。
（5）图文并茂，便于学生直观地理解数据结构与算法。
本书通过图表的方式对数据结构及相应操作进行简单直接的描述，使内容更加浅显易懂。
教师可以按照自己对数据结构的理解适当地跳过一些章节，也可以根据教学目标灵活地调整章节的顺序，增减各章的学时数。
由于数据结构本身还在探索之中，加上我们的水平和能力有限，本书难免有疏漏之处，恳请各位同仁和广大读者给予批评指正，也希望各位能将实践过程中的经验和心得与我们交流(yunxianglu@hotmail.com)。
作者
2017年6月
第5章
树形结构
5.1树
5.1.1树的基本概念
树是数据元素之间具有层次关系的非线性结构，是由n个结点构成的有限集合，结点数为0的树叫空树。树必须满足以下条件。
(1)有且仅有一个被称为根的结点。
(2)其余结点可分为m个互不相交的有限集合，每个集合又构成一棵树，叫根结点的子树。
与线性结构不同，树中的数据元素具有一对多的逻辑关系，除根结点以外，每个数据元素可以有多个后继但有且仅有一个前驱，反映了数据元素之间的层次关系。
树是递归定义的。结点是树的基本单位，若干个结点组成一棵子树，若干棵互不相交的子树组成一棵树。
图5.1树的逻辑结构示意图
人们在生活中所见的家谱、Windows的文件系统等，虽然表现形式各异，在本质上是树结构。图5.1给出了树的逻辑结构示意图。
树的表示方法有多种，如树形表示法、文氏图表示法、凹入图表示法和广义表表示法。图5.1所示为树形表示法，图5.2给出了用其他3种表示法对树的表示。
图5.2树的3种表示方法
5.1.2树的术语
1.结点
树的结点就是构成树的数据元素，就是其他数据结构中存储的数据项，在树形表示法中用圆圈表示。
2.结点的路径
结点的路径是指从根结点到该结点所经过结点的顺序排列。
3.路径的长度
路径的长度指的是路径中包含的分支数。
4.结点的度
结点的度指的是结点拥有的子树的数目。
5.树的度
树的度指的是树中所有结点的度的最大值。
6.叶结点
叶结点是树中度为0的结点，也叫终端结点。
7.分支结点
分支结点是树中度不为0的结点，也叫非终端结点。
8.子结点
子结点是指结点的子树的根结点，也叫孩子结点。
9.父结点
具有子结点的结点叫该子结点的父结点，也叫双亲结点。
10.子孙结点
子孙结点是指结点的子树中的任意结点。
11.祖先结点
祖先结点是指结点的路径中除自身之外的所有结点。
12.兄弟结点
兄弟结点是指和结点具有同一父结点的结点。
13.结点的层次
树中根结点的层次为0，其他结点的层次是父结点的层次加1。
14.树的深度
树的深度是指树中所有结点的层次数的最大值加1。
15.有序树
有序树是指树的各结点的所有子树具有次序关系，不可以改变位置。
16.无序树
无序树是指树的各结点的所有子树之间无次序关系，可以改变位置。
17.森林
森林是由多个互不相交的树构成的集合。给森林加上一个根结点就变成一棵树，将树的根结点删除就变成森林。
5.2二叉树
5.2.1二叉树的基本概念
1.普通二叉树
二叉树是特殊的有序树，它也是由n个结点构成的有限集合。当n=0时称为空二叉树。二叉树的每个结点最多只有两棵子树，子树也为二叉树，互不相交且有左右之分，分别称为左二叉树和右二叉树。
二叉树也是递归定义的，在树中定义的度、层次等术语同样也适用于二叉树。
2.满二叉树
满二叉树是特殊的二叉树，它要求除叶结点外的其他结点都具有两棵子树，并且所有的叶结点都在同一层上，如图5.3所示。
3.完全二叉树
完全二叉树是特殊的二叉树，若完全二叉树具有n个结点，它要求n个结点与满二叉树的前n个结点具有完全相同的逻辑结构，如图5.4所示。
新书资讯
