ch树old.ppt

第4章 树和二叉树 第4章 树 （Tree） 4.1 树 4.2 二叉树 4.3 二叉树的遍历 4.4 线索二叉树 4.5 树和森林 4.6 哈夫曼树（Huffman Tree） 4.1 树的相关概念和术语 树是一类重要的非线性数据结构，以二叉树最为常用； 树反映元素之间的层次、分支结构关系，类似自然界的树； 树型结构的应用： 家族的族谱； 各种社会组织结构； 计算机磁盘文件的组织； Internet 的域名解析系统 DNS； … 4.1 树的相关概念和术语 家族关系图/单位机构组成 定义：树T是由n个结点组成的有限集合（n 0）。 其中有且仅有一个根结点（树根）， 其余结点可划分成m个（m=0）互不相交的子集T1, T2,...,Tm， 且这些子集也分别构成树——子树 说明：树的定义是递归的。即树由子树构成，子树又由更小的子树构成。 树结构示例： 非树结构示例 4.1 树的相关概念和术语 4.1.1 树的基本概念 1. 结点（节点） 包含数据域，存放数据元素； 指针域，存放若干指针，指向其上、下层结点。 2. 结点的度 结点拥有的子树数目。 节点关联的边数。（有向图中可分为：出度、入度） 3. 叶结点 度为 0 的结点。或没有子树的节点。 4. 分支结点 度不为 0 的结点。或有子树的节点。 4.1 树的相关概念和术语 5. 树的度 树内各结点的度的最大值。 (以下为描述节点关系的术语) 6. 孩子结点（子结点、直接后继结点） 与当前结点有边(edge)直接相连的下一层结点，叫做当前结点的孩子结点、子结点。 子树的根节点 叶子结点没有孩子结点。 4.1 树的相关概念和术语 7. 父结点（双亲结点、直接前驱节点） 与当前结点有边(edge)直接相连的上一层结点，叫做当前结点的双亲结点、父结点。 树中根结点没有双亲结点；其它结点有且仅有一个双亲结点。 8. 祖先（前驱）结点-- ancestor 从根结点有路径到达当前结点，路径经过的所有结点，都是当前结点的祖先结点、先驱结点。 9. 子孙（后裔）结点-- descendant 当前结点作为根结点，其子树上的所有结点，都是当前结点的后裔结点。 4.1 树的相关概念和术语 10. 兄弟结点( Sibling ) 双亲结点相同的所有结点互称为兄弟结点。 11. 堂兄弟结点 双亲结点在同一层次（深度相同）的结点，互为堂兄弟。 4.1 树的相关概念和术语 (以下为描述树的层次术语) 12. 结点的层次（深度）-- level 根结点的层次为 1；(也有设为 0 的) 其它结点层次等于父结点层次加 1。 13. 树的高度/深度--depth 整个树中结点的最大层次 14. 有序树 同一结点的所有子树，从左至右规定次序。 15. 无序树 结点的子树不分先后次序。 16. 森林 m (m≧0) 棵不相交树的集合 4.1 树的相关概念和术语 4.1.2 树的运算 初始化树：initialTree(T)； 查询根结点：rootOf(T)； 查询父结点：fatherOf(T)； 查询孩子结点：childOf(T)； 查询兄弟结点：siblingOf(T)； 插入子树：insertTree (T,S)； 插入兄弟结点：insertSibling(T,S)； 删除结点 树的遍历 … 4.2 二叉树(Binary Tree) 4.2.1 二叉树的基本概念 1. 二叉树定义 二叉树T：是n个结点组成的有限集合（n = 0），n=0为空二叉树，否则： 其中有一个根结点， 其余结点可以划分成两个互不相交的子集TL, TR， 且TL, TR也分别构成二叉树 —— 左、右子树。 2. 二叉树特点 一个结点最多只能有两个孩子结点； 二叉树是有序树，即其左、右子树不能交换位置；即使只有一棵子树也要区分是左子树还是右子树。 结点都相同，交换左、右子树后，即为另一棵二叉树。 (见下图) 4.2 二叉树的定义 4.2 二叉树的定义 4. 二叉树与树的区别： 是两种不同的结构； 二叉树最