数据结构（数据结构（DataStructureDataStructure））主讲：严冬梅第6章树和二叉树（Tree&Binarytree）第6章树和二叉树6.1二叉树6.1.1树的定义和基本术语6.2.2二叉树的定义和基本术语6.2.3二叉树的几个基本性质6.2.4二叉树的存储结构6.2二叉树遍历6.2.1问题的提出6.2.2遍历算法描述6.2.3二叉树遍历应用举例6.2.4线索二叉树6.3树和森林6.3.1树和森林的定义6.3.2树和森林的存储结构6.3.3树、森林与二叉树的转换6.3.4树和森林的遍历6.4树的应用6.4.1堆排序的实现6.4.2二叉排序树6.4.3赫夫曼树及其应用6.1二叉树6.1.1树的定义和基本术语6.1.2二叉树的定义和基本术语6.1.3二叉树的几个基本性质6.1.4二叉树的存储结构第6章树和二叉树树型结构是一类重要的非线性数据结构，其中以树和二叉树最为常用。直观角度看，树是以分支关系定义的层次结构。树在计算机领域中得到广泛应用，如文件管理中的目录结构、数据库系统中的信息组织形式等。树结构在客观世界中也广泛存在，如人类社会的族谱和各种社会组织机构都可用树来形象表示。本章重点讨论二叉树的存储结构及各种操作，并研究树和森林与二叉树的转换关系。第6章树和二叉树到目前为止，我们已经介绍了线性数据结构和表数据结构。这些数据结构一般不适合于描述具有层次结构的数据。在层次化的数据之间可能有祖先-后代、上级-下属、整体-部分以及其他类似的关系。例1[Joe的后代]：上图给出了Joe的后代，并按层次方式组织，其中Joe在最顶层。Joe的孩子（Ann，Mary和John）列在下一层，在父母和孩子间有一条边。在层次表示中，非常容易地找到Ann的兄弟姐妹，Joe的后代，Chris的祖先等。第6章树和二叉树例2[软件工程]：考察另一种层次数据——软件工程中的模块化技术。通过模块化，可以把大的复杂的任务分成一组小的不太复杂的任务。模块化的目标是把软件系统分成许多功能不相关的部分或模块以便于进行相对独立的开发。由于解决几个小问题比解决大问题更容易一些，因此模块化方法可以缩短整个软件的开发时间。另外，不同的程序员可以同时开发不同的模块。如果有必要，每个模块可以再细分，从而得到如图所示的用树形表示的模块层次结构。该树给出了某文字处理器的一种可行的模块分解图。第6章树和二叉树例3：学校的组织结构学院教务科院办基础部科学系技术系计算中心软件系研究所后勤处应用室人工智能室可计算性室学生科师资科教学科教材科何谓树状结构树是n(n0≧)个结点的有限集。在任意一棵非空树中：(1)有且仅有一个特定的称为根的结点；(2)当n>1时，其余结点可分为m(m>0)个互不相交的有限集T1,T2,…,Tm，其中每一个集合本身又是一棵树，并且称为根的子树。若一棵树中的结点可以有n个子结点，则称这样的树为n元树，例如二叉树中的结点，最多只能有两个结点。AMDCBRQPA为根结点B、C、D、M为A的子结点6.1树的定义和基本术语树的相关名称及意义根结点（rootnode）一棵树中没有父结点的结点，称为根结点叶（子）结点leafnode或终端结点terminalnode一棵树中没有子结点的结点，称为叶（子）结点或终端结点分支结点或非终端结点（nonterminalnode）除了叶（子）结点以外的其他结点，称为分支结点或非终端结点ADCBEFGHI叶子结点根结点6.1树的定义和基本术语非终端结点父结点（parent）和子结点（child）若结点x有一个以结点y为树根的子树,则x为y的父结点（父亲），而y为x的子结点（孩子）。兄弟（sibling）同一个父结点之子结点，称为兄弟如图B、C、D的父结点均为A，故B、C、D互为兄弟结点的度（degree）结点的子树个数，称为结点的度。如图，A的度为3，B的度为3，C的度为1，最大的度值为3，故树为3元树。层次（level）层次为结点之特性值，将根结点之层次设为1，其子结点为2，依此类推。如图，层次为1的有结点A,为2的有结点B、C、D，为3的有结点E、F、G、H、I。6.1树的定义和基本术语ADCBEFGHI深度（depth）或高度（height）叶子结点的最大层次数称为树的深度。如图，叶子最大层次值为3，故树T的深度为3祖先（ancestor）由某结点X到根结点之路径上的所有结点，...
