数据结构 第六章 节 树和二叉树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 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)问题：给定一个遍历序列，能否唯一确定一棵二 叉树？如：先序序列为abcd,其二叉树的结构是什么？ 答案是不惟一。 给定中序和后序 给定先序和中序 给定前序和后序不能唯一确定一棵二叉树 唯一确定一棵二叉树 (2) 给定某两种序列能否唯一确定一棵二叉树 一、遍历二叉树 6.3 遍历二叉树和线索二叉树 例：设某二叉树前序和中序遍历序列分别为： 前序：1 2 4 6 3 5 7 8 中序：2 6 4 1 3 7 5 8 1 前 246 中264 前 3578 中3758 1 前 46 中64 前 3578 中3758 2 1 前 3578 中3758 2 4 6 二、线索二叉树(穿线树) 遍历二叉树就是按一定的规则将二叉树中的结点排列成一个线性序列。实际上就是对一个非线性结构进行线性化操作，使每个节点（除第一个和最后一个）在这些线性序列中有且仅有一个直接前驱和直接后继。 有n个结点的二叉链链表中必定存在n+1个空链域，考虑利用这些空