第五章树与二叉树第五章树与二叉树退出退出主要内容主要内容5.15.1树的定义及基本术语树的定义及基本术语5.25.2二叉树二叉树5.35.3遍历二叉树遍历二叉树5.45.4线索二叉树线索二叉树5.55.5二叉排序树二叉排序树5.75.7哈夫曼树哈夫曼树55．．11树的定义及基本术语树的定义及基本术语55．．11．．11树的定义树的定义结点的度结点的度终端结点终端结点非终端结点非终端结点结点的层次结点的层次树的度树的度树的深度树的深度有序树、无序树有序树、无序树森林森林55．．11树的定义及基本术语树的定义及基本术语55．．11．．11树的定义树的定义孩子、双亲孩子、双亲子孙子孙祖先祖先兄弟兄弟堂兄弟堂兄弟55．．11．．11树的定义树的定义定义：定义：树是一种常用的非线性结构。树是一种常用的非线性结构。树树是是nn（（n≥0n≥0）个结点的有限集合。若）个结点的有限集合。若n=0n=0，则称为，则称为空树空树；否则，有且仅有一个特；否则，有且仅有一个特定的结点被称为定的结点被称为根根，当，当n>1n>1时，其余结点被时，其余结点被分成分成mm（（m>0m>0）个互不相交的子集）个互不相交的子集T1T1，，T2T2，，......，，TmTm，每个子集又是一棵，每个子集又是一棵树。树。由此可以看出，树的定义是递归。由此可以看出，树的定义是递归。55．．11．．11树的定义树的定义5.25.2二叉树二叉树定义：定义：二叉树二叉树是另一种树形结构。它与树形结构是另一种树形结构。它与树形结构的区别是：的区别是：（（11）每个结点最多有两棵子树；）每个结点最多有两棵子树；（（22）子树有左右之分。）子树有左右之分。二叉树也可以用递归的形式定义。即：二叉树也可以用递归的形式定义。即：二叉树是二叉树是nn（（nn≥≥00）个结点的有限集合。当）个结点的有限集合。当n=0n=0时，称为空二叉树；当时，称为空二叉树；当n>0n>0时，有且仅有时，有且仅有一个结点为二叉树的根，其余结点被分成两个互一个结点为二叉树的根，其余结点被分成两个互不相交的子集，一个作为左子集，另一个作为右不相交的子集，一个作为左子集，另一个作为右子集，每个子集又是一个二叉树。子集，每个子集又是一个二叉树。5.25.2二叉树二叉树二叉树的二叉树的55种形态：种形态：ø5.25.2二叉树二叉树完全二叉树完全二叉树：有一棵深度为：有一棵深度为hh，具，具有有nn个结点的二叉树，若将它与一棵同深度的满个结点的二叉树，若将它与一棵同深度的满二叉树中的所有结点按从上到下，从左到右的顺序二叉树中的所有结点按从上到下，从左到右的顺序分别进行编号，且该二叉树中的每个结点分别与满分别进行编号，且该二叉树中的每个结点分别与满二叉树中编号为二叉树中编号为1~n1~n的结点位置一一对应，则称的结点位置一一对应，则称这棵二叉树为这棵二叉树为完全二叉树完全二叉树。。55．．22．．11二叉树的性质二叉树的性质(1)(1)在二叉树的第在二叉树的第ii上至多有上至多有22i-1i-1个结点（个结点（i>=1i>=1））(2)(2)深度为深度为kk的二叉树至多有的二叉树至多有22kk-1-1个结点。个结点。(3)(3)设任何一棵二叉树中，叶结点数为设任何一棵二叉树中，叶结点数为n0n0，度为，度为11的的结点数为结点数为n1,n1,度为度为22的结点数为的结点数为n2n2，则有：，则有：n0=n2+1n0=n2+1(4)(4)具有具有nn个结点的完全二叉树其深度为：个结点的完全二叉树其深度为：k=k=[log[log22n]+1n]+155．．22．．22二叉树的存储结构二叉树的存储结构11、顺序存储、顺序存储这种存储结构适用于完全二叉树。其存储形式这种存储结构适用于完全二叉树。其存储形式为：用一组连续的存储单元按照完全二叉树的每个为：用一组连续的存储单元按照完全二叉树的每个结点编号的顺序存放结点内容。结点编号的顺序存放结点内容。顺序存储的二叉树的定义如下：顺序存储的二叉树的定义如下：#defineN50/*#defineN50/*树结点的最大个数树结点的最大个数**//typedefelemtypeSQTREE[N];typedefelemtypeSQTREE[N];55．．22．．22二叉树的存储结构二叉树的存储结构8456723155．．22．．22二叉树的存储结构...
