数据结构 第六章 树和二叉树6.2.pptVIP

* * 6.3 遍历二叉树和线索二叉树 一、遍历二叉树 二、线索二叉树(穿线树) 所谓遍历就是按某指定规则访问数据结构中的所有结点，且每个结点只访问一次。 各种数据结构包括线性表也有遍历运算。这里“访问”的含义很广，可以对结点作各种处理，如输出结点信息、求结点个数等。 对于线性结构，遍历的运算比较简单。而对二叉树这种非线性结构，每个结点都可能有两棵子树，需要寻找一种规律，以便使二叉树上的结点能排列在一个线性队列上，从而便于遍历。 一、遍历二叉树 6.3 遍历二叉树和线索二叉树 1、遍历规则 二叉树是由三个基本单元组成：根结点、左子树和右子树。所谓遍历规则是指在遍历时是先访问根结点还是先访问子树，是先访问左子树还是先访问右子树。不同的遍历规则会产生不同的遍历结果。 以D、L、R表示访问根结点、左子树、右子树,有6种遍历方式：DLR、LDR、LRD、DRL、RDL、RLD 一般规定，在二叉树遍历中，按先访问左子树，后访问右子树的顺序进行遍历。 一、遍历二叉树 6.3 遍历二叉树和线索二叉树 A D B C D L R A D L R D L R B D C D L R 先序遍历序列：A B D C 2、（1）先序遍历: 若二叉树为空，遍历结束。否则 （1）访问根结点； （2）先序遍历左子树； （3）先序遍历右子树。 一、遍历二叉树 6.3 遍历二叉树和线索二叉树 void preorder(BiTree T,status(*visit)()) { if(T==NULL) return; else visit(T-data); if(T-lchild!=NULL) preorder(T-lchild,visit); if(T-rchild!=NULL) preorder(T-rchild,visit); } 主程序 Pre( T ) 返回 返回 pre(T R); 返回 返回 pre(T R); A C B D T B printf(B); pre(T L); B T A printf(A); pre(T L); A T D printf(D); pre(T L); D T C printf(C); pre(T L); C 返回 T 左是空返回 pre(T R); T 左是空返回 T 右是空返回 T 左是空返回 T 右是空返回 pre(T R); 先序序列：A B D C 先序遍历递归算法 一、遍历二叉树 6.3 遍历二叉树和线索二叉树 A D B C L D R B L D R L D R A D C L D R 中序遍历序列：B D A C （2）中序遍历: 若二叉树为空，遍历结束。否则 （1）中序遍历左子树； （2）访问根结点； （3）中序遍历右子树。 一、遍历二叉树 6.3 遍历二叉树和线索二叉树 （2）中序遍历 void Inorder(BiTree T,status(*visit)()) { if(T==NULL) return; if(T-lchild!=NULL) Inorder(T-lchild,visit); visit(T-data); if(T-rchild!=NULL) Inorder(T-rchild,visit); } 递归算法: 一、遍历二叉树 6.3 遍历二叉树和线索二叉树 A D B C L R D L R D L R D A D C L R D 后序遍历序列： D B C A （3）后序遍历: B 若二叉树为空，遍历结束。否则 （1）后序遍历左子树； （2）后序遍历右子树； （3）访问根结点。 先序遍历序列： -+a*b-cd/ef 中序遍历序列： a+b*(c-d)-e/f 后序遍历序列： abcd-*+ef/- (前缀表示) (中缀表示) (后缀表示) 一、遍历二叉树 6.3 遍历二叉树和线索二叉树 3.遍历举例 例1：右图所示的二叉树表示下述表达式： a+b*(c-d)-e/f 一、遍历二叉树 6.3 遍历二叉树和线索二叉树 4.二叉树的遍历与存储结构之间的转化 (1)问题：给定一个遍历序列，能否唯一确定一棵二 叉树？如：