数据结构课件-树和二叉树教学幻灯片讲义.ppt

第六章 树和二叉树; 第六章 树和二叉树; 教学重点; 教学难点;张源; 6.1.1 树的定义 树(Tree)是n （n≥0）个结点的有限集合T，在一棵非空树中（n0）有且仅有一个称作根的结点；其余结点可分为m个（m≥0）互不相交的集合T1，T2……Tm，其中，每一个集合本身又是一棵树,并称为根的子树。 当n=0时，称为空树。; 有限集合T1，T2……Tm应该“互不相交”，即任意两个集合不能有相重的结点。 树的各个结点有不同层次关系，这种关系通常用图形表示，但与自然界的树木相反，习惯上将整 棵树的根画在最上层。树的结构参见下图6.1 ;A;6.1.2 基本术语;2、孩子(child)和双亲(parents) ：一个结点 的子树的根称为该结点的孩子，相应的该节点称为孩子的双亲(parents) 。 兄弟(sibling)：同一双亲的孩子之间互称兄弟。 祖先：从根到该结点所经分支上的所有结点都叫该结点的祖先 子孙：以某结点为根的子树中的任一结点都称为该结点的子孙 ;树形结构的逻辑特征;6.2 二叉树;6.2.1 二叉树的定义;; ? 二叉树结点的子树要区分左子树和右子树，即使只有一棵子树也要进行区分,说明它是左子树，还是右子树。这是二叉树与树的最主要的差别。 ;图 6.4;性质1 若二叉树的层数从1开始，则二叉树的第i层结点数，最多为2i-1个（i≥1）。; 深度（高度）为k的二叉树最大结点数为2k-1（k≥1）。 证明:最大结点个数=20+21+22+……+2k-1 =2k-1; 对任意一棵二叉树，如果叶子结点个数为n0，度为2的结点个数为n2，则有n0=n2+1。 证明：设n0,n1和n2分别为二叉树中度为0,度为1和度为2的结点个数，则二叉树中总的结点个数n满足： n=n0+n1+n2 ① 再有除了根结点之外，每个结点都由一个分支射入，则分支数B与总的结点数之间的关系为： n=B+1　② 另外，由于这些分支是由度为1或2的结点射出的，则有 B=n1+2n2　　③ 则由上三式得： n0=n2+1;满二叉树;图6.5 满二叉树;完全二叉树;1;对于完全二叉树，对其结点采用“按层编号”比较方便，即从根结点开始由上而下逐层给结点编号，同一层的结点由左向右编号。 ?对于??全二叉树中任一个编号为i的结点(1≤i≤n)，它的父结点和左、右儿子结点的编号与i值有如下的关系： 1) 如果i=1，则它是整个树的根结点，无父结点；若i1，则其父结点编号为 i/2 。 2) 如果2i≤n，则其左儿子结点编号为2i；若2in，则无左儿子结点。 3) 如果（2i+1）≤n，则其右儿子结点编号为（2i+1）；反之，则无右儿子结点。 ; ; 6.2.3 二叉树的存储结构1.顺序存储结构;分析: 显然，二叉树的结点必须按某种次序分别存入数组的各个单元，这种次序应能反映结点间的逻辑关系，否则二叉树上的各种基本运算在顺序存储结构上很难实现。 对于完全二叉树来说，可以采用“以编号为地址”的方法，将编号为i的结点存入一维数组的第i个单元(下标为i-1)。 ;1; 对应的顺序存储结构: 一维数组的21单元中只用上了7个.最坏情况下,一个深度为k且只有k个结点的单支树,却需要长度为2k-1的一维数组.;总结:★; ;存储表示;二叉链表; ;6.3 遍历二叉树和线索二叉树; 6.3 遍历二叉树和线索二叉树6.3.1 遍历二叉树;假如以L、D、R分别表示遍历左子树,访问根结点和遍历右子树，遍历整个二叉树则有DLR、LDR、LRD、DRL、RDL、RLD六种遍历方案。若规定先左后右，则只有前三种情况，分别规定为： DLR——先序（根）遍历,LDR——中序（根）遍历，LRD——后序（根）遍历。 ;(1) 中序（InOrder）遍历 若遍历的二叉树为空，执行空操作；否则依次执行下列操作： 中序遍历左子树； 访问根结点； 中序遍历右子树。 (2) 先序（PreOrder）遍历 若遍历的二叉树为空，执行空操作；否则依次执行下列操作： 访问根结点； 先序遍历左子树； 先序遍历右子树。;(3) 后序（PostOrder）遍历 若遍历的二叉树为空，执行空操作；否则依次执行下列操作： 后序遍历左子树； 后序遍历右子树； 访问根结点。;Void preorder(Bintree T){ if(T) {printf(“%d”,p–data);