计算机软件技术基础(邮电)1-6.ppt

《计算机软件技术基础(邮电)1-6.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、计算机软件技术基础课件第一章数据结构第二章操作系统第三章软件工程第四章数据库1第一章数据结构第一单元第二单元第三单元第四单元第五单元第六单元第七单元第八单元2树、森林与二叉树的转换第六单元第一章数据结构31.3.3二叉树的遍历所谓遍历(Traversal)是指沿着某条搜索路线，依次对树中每个结点均做一次且仅做一次访问。访问结点所做的操作依赖于具体的应用问题。遍历是二叉树上最重要的运算之一，是二叉树上进行其它运算之基础。“访问”的意思对结点施行某些操作。例：输入结点的信息、修改结点的数据值等。（但要求这种访问不破坏它原来的数据结构）遍历的规则从二叉树

2、的递归定义可知，一棵非空的二叉树由根结点及左、右子树这三个基本部分组成。因此，对于任一给定结点，可以按某种次序执行三个操作：（1）访问结点本身(N)，（2）遍历该结点的左子树(L)，（3）遍历该结点的右子树(R)。以上三种操作有六种执行次序：NLR、LNR、LRN、NRL、RNL、RLN。设访问根结点记作N遍历根的左子树记作L遍历根的右子树记作R则可能的遍历次序有前序NLR镜像NRL中序LNR镜像RNL后序LRN镜像RLN4一．遍历算法(InorderTraversal)1．中序遍历的递归算法定义：若二叉树非空，则依次执行如下操作：(1)遍历左子树

3、；(2)访问根结点；(3)遍历右子树。例：表达式语法树遍历结果:a+b*c-d-e/f表达式a+b*(c–d)–e/f对应的语法树5采用二叉链表作为存储结构，则中序遍历算法可描述为：voidInOrder(BinTreeT){if(T){//如果二叉树非空InOrder(T->lchild)；printf("％c"，T->data)//访问结点InOrder(T->rchild);}}//InOrder6例：表达式语法树遍历结果-+a*b-cd/ef表达式a+b*(c–d)–e/f对应的语法树2．先序遍历的递归算法定义：若二叉树非空，则依次执行如下操作

4、：前序遍历二叉树算法的框架是若二叉树为空，则空操作；否则(1)访问根结点；(2)遍历左子树；(3)遍历右子树。7例：表达式语法树遍历结果abcd-*+ef/-表达式a+b*(c–d)–e/f对应的语法树3．后序遍历的递归算法定义：若二叉树非空，则依次执行如下操作：后序遍历二叉树算法的框架是若二叉树为空，则空操作；否则(1)遍历左子树；(2)遍历右子树；(3)访问根结点。8二．遍历序列1．遍历二叉树的执行踪迹ABCDEFØØØØØØØ图1-50遍历二叉树的搜索路线9例:右图,得到的中序序列为：DBAECF2.遍历序列(1)中序序列中序遍历二叉

5、树时，对结点的访问次序为中序序列。ABCDEF(2)先序序列先序遍历二叉树时，对结点的访问次序为先序序列。例:上图，得到的先序序列为：ABDCEF10三二叉链表的构造1.基本思想基于先序遍历的构造，即以二叉树的先序序列为输入构造。(3)后序序列后序遍历二叉树时，对结点的访问次序为后序序列。ABCDEF例:右图,得到的后序序列为：DBEFCAABCDEFØØØØØØØ例:建立上图所示二叉树，其输入的先序序列是：ABDØØØCEØØFØØ。112．构造算法假设虚结点输入时以空格字符表示，相应的构造算法为:voidCreateBinTree(BinTree*

6、T){//构造二叉链表。T是指向根指针的指针,//故修改*T就修改了实参(根指针)本身charch；if((ch=getchar())=='')*T=NULL；//读入空格，将相应指针置空else12{//读入非空格*T=(BinTNode*)malloc(sizeof(BinTNode))；//生成结点(*T)->data=ch；CreateBinTree(&(*T)->lchild)；//构造左子树CreateBinTree(&(*T)->rchild)；//构造右子树}}131.3.4树、森林与二叉树的转换一．树、森林到二叉树的转换1．将树转换为

7、二叉树左子女-右兄弟表示法①在所有兄弟结点之间加一连线；②对每个结点,除了保留与其长子的连线外,去掉该结点与其它孩子的连线。例:图1－51(a)所示的树可转换为图1－51(c)所示的二叉树。14ＡＢＣＤＥＦＧＨＩＪ(a)图1-51树转换为二叉树ＡＢＣＤＥＦＧＨＩＪ(b)ＡＢＣＤＥＦＧＨＩＪ(c)152．将一个森林转换为二叉树具体方法是：①将森林中的每棵树变为二叉树；②因为转换所得的二叉树的根结点的右子树均为空，故可将各二叉树的根结点视为兄弟从左至右连在一起,就形成了一棵二叉树。例如图1－52中,(a)中包含三棵树的森林可转换为(c)的二叉树。16森林与

8、二叉树的转换森林与二叉树的对应关系图1-52森林转换为二叉树17二．二叉树到树、森林的转换(a