第4章 树-36 - v2.ppt

第4章 树 张成文 北京邮电大学计算机学院 本章要点 熟练掌握二叉树的结构特性； 熟悉二叉树的各种存储结构的特点及适用范围； 熟练掌握二叉树各种遍历策略的算法； 利用遍历结果确定二叉树问题 树 二叉树 二叉树的遍历 中序遍历 先序遍历 后序遍历 三、算法的递归描述 1) 先序遍历 void PreOrder(BiTree bt) /*先序遍历,根指针为bt的二叉树*/ { if(bt!=NULL) { Visit(bt-data); //访问根结点 PreOrder(bt-LChild); //遍历左子树 PreOrder(bt-RChild); //遍历右子树 } } 2) 中序遍历 void InOrder(BiTree bt) /*中序遍历根指针为bt的二叉树*/ { if(bt!=NULL) { InOrder(bt-LChild); //遍历左子树 Visit(bt-data); //访问根结点 InOrder(bt-RChild); //遍历右子树 } } 3) 后序遍历 void PostOrder(BiTree bt) /* 后序遍历根指针为bt的二叉树 */ { if(bt!=NULL) { PostOrder(bt-LChild); //遍历左子树 PostOrder(bt-RChild); //遍历右子树 Visit(bt-data); //访问根结点 } } 仅知二叉树的先序序列abcdefg不能唯一确定一棵二叉树,如果同时已知二叉树的中序序列cbdaegf,则会如何？ 4)由先序和中序序列确定二叉树 二叉树的先序序列 二叉树的中序序列 左子树 左子树 右子树 右子树 根 根 a b c d e f g c b d a e g f 例如: a a b b c c d d e e f f g g a b c d e f g ^ ^ ^ ^ ^ ^ ^ ^ 先序序列中序序列 小结 * * 树的定义与基本术语 1.定义: 树是n(n≥0)个结点的有限集合T。当n=0时,称为空树;当n0时,该集合满足如下条件: (1) 其中必有一个称为根(root)的特定结点,它没有直接前驱,但有零个或多个直接后继。 (2) 其余n-1个结点可以划分成m(m≥0)个互不相交的有限集T1,T2,T3,…,Tm,其中Ti又是一棵树,称为根root的子树。每棵子树的根结点有且仅有一个直接前驱,但有零个或多个直接后继。 一、树(tree)的基本概念: A B C D E F G H I J M K L A( B(E, F(K, L)), C(G), D(H, I, J(M)) ) T1 T3 T2 树根 例如: 线性结构 树型结构 第一个数据元素 (无前驱) 根结点 (无前驱) 最后一个数据元素 (无后继) 多个叶子结点 (无后继) 其它数据元素 (一个前驱、 一个后继) 其它数据元素 (一个前驱、 多个后继) 对比树型结构和线性结构的结构特点 结点(node): 树的度: 叶子结点(leaf) : 分支结点: 数据元素+若干指向子树的分支 树各结点的度的最大值 度为零的结点 度大于零的结点 D H I J M 2.树的相关术语 结点的度(degree): 结点拥有的子树数 结点的层次: (level) 假设根结点的层次为1,第l 层的结点的子树根结点的层次为l+1 树的深度(depth): 叶子结点所在的最大层次 分支(branch): 表示数据元素与它的子树的关系 路径(path): 常用家族树的术语表示结点关系 孩子(child) 结点 双亲(parent)结点 兄弟结点 由根到该结点所经的分支和结点构成 A B C D E F G H I J M K L 树的结点数n和分支数b的关系是: b=n-1 二叉树 1 二叉树的定义与基本操作 定义： 满足以下两个条件的树称做二叉树(Binary Tree): （1）每个结点的度都不大于2； （2）每个结点的孩子结点次序不能任意颠倒。 二叉树或为空树, 或是由一个根结点加上两棵分别称为左子树和右子树的、互不交的二叉树组成。 注意:二叉树是有序树,它的子树有左右之分。二叉树的度数不超过二,但度数不超过二的树未必是二叉树。 A B C D E F G H K 根结点 左子树 右子树 二叉树的五种基本形态: N 空树 只含根结点 N N N L R R 右子树为空树 L 左子树为空树 左右子树均非空树 用