数据结构第六章树和二叉树

数据结构第六章树和二叉树内容摘要：

er)遍历：若树为空，执行空操作；否则依次执行：  中序遍历左子树 L；  访问根结点 D；  中序遍历右子树 R。 2. 先序 (PreOrder)遍历：若树为空，执行空操作；否则依次执行：  访问根结点 D；  先序遍历左子树 L；  先序遍历右子树 R。 3. 后序 (PostOrder)遍历：若树为空，执行空操作；否则依次执行：  后序遍历左子树 L；  后序遍历右子树 R；  访问根结点 D。 中国科大 《 数据结构 》 622 遍历二叉树  二叉树遍历的实现 template class T void PreOrder(BiTreeNodeT *t, void Visit(T item)) //使用 Visit(item)函数前序遍历二叉树 t { if(t != NULL) { Visit(tdata)。 PreOrder(tLeft(), Visit)。 PreOrder(tRight(), Visit)。 } }  为了通用性，把访问操作设计成前序遍历二叉树函数的一个函数虚参 Visit()。 A D B F C G E 输出结果： ABDEGCF (第一个输出节点必为根节点 ) 中国科大 《 数据结构 》 623 遍历二叉树 template class T void InOrder(BiTreeNodeT *t, void Visit(T item)) //使用 Visit(item)函数中序遍历二叉树 t { if(t != NULL) { InOrder(tLeft(), Visit)。 Visit(tdata)。 InOrder(tRight(), Visit)。 } } 输出结果： DBGEAFC （先于根节点 A输出的节点为左子树的节点 后于根节点 A输出的节点为右子树的节点） A D B F C G E 中国科大 《 数据结构 》 624 遍历二叉树 template class T void PostOrder(BiTreeNodeT *t, void Visit(T item)) //使用 Visit(item)函数后序遍历二叉树 t { if(t != NULL) { PostOrder(tLeft(), Visit)。 PostOrder(tRight(), Visit)。 Visit(tdata)。 } } 输出结果： DGEBFCA (最后一个输出节点必为根节点 ) A D B F C G E 中国科大 《 数据结构 》 625 遍历二叉树  遍历二叉树应用 1. 利用后序求结点个数或树的高度 2. 利用前序实现二叉树复制 3. 判断两棵树是否相等 1. Return 1+Size (tlchild) + Size (trchild)。 2. tempdata=progmpde data。 temp lchile =copy(orignodelchild)。 temp rchile =copy(orignoderchild)。 3. If (a!=NULL amp。 amp。 b!=NULL amp。 amp。 adata=bdata amp。 amp。 equal(alchild=b lchild) amp。 amp。 equal(archild=b rchild)) 中国科大 《 数据结构 》 626 遍历二叉树  根据先、中序遍历求序列二叉树 ：如果已知一棵二叉树的先序遍历和中序遍历序列，则可以惟一确定这棵二叉树  算法： ，第一个节点为根节点 D ，根节点 D左边的节点归为左子树，根节点 D右边的节点归为右子树 1,2两步，直到确定二叉树 中国科大 《 数据结构 》 627 遍历二叉树  示例：已知一棵二叉树的  先序遍历序列为： ABDEGCF，  中序遍历序列为： DBGEAFC， 请画出这棵二叉树  解：根据先序遍历序列，可知根节点为 A；再根据中序遍历序列可知，左子树由 DBGE组成，右子树由 FC组成。 重复上述步骤，分别求出左子树和 右子树的细节。 27 A D B F C G E 左子树 右子树 中国科大 《 数据结构 》 628 遍历二叉树  根据后、中序遍历求序列二叉树 ：如果已知一棵二叉树的后序遍历和中序遍历序列，则可以惟一确定这棵二叉树  算法： ，最后一个节点为根节点 D ，根节点 D左边的节点归为左子树，根节点 D右边的节点归为右子树 1,2两步，直到确定二叉树 中国科大 《 数据结构 》 629 遍历二叉树  示例：已知。