二叉树遍历和应用.ppt

《二叉树遍历和应用.ppt》由会员上传分享，免费在线阅读，更多相关内容在PPT专区-天天文库。

1、二叉树的遍历和应用二叉树的遍历小结和作业问题的提出递归遍历算法非递归遍历算法复习融四岁，能让梨。弟于长，宜先知。二叉树遍历算法的应用复习在二叉树的第i层上至多有2i-1个结点。(i≥1)深度为k的二叉树上至多含2k-1个结点（k≥1）对任何一棵二叉树，若它含有n0个叶子结点、n2个度为2的结点，则必存在关系式：n0=n2+1具有n个结点的完全二叉树的深度为log2n+1复习若对含n个结点的完全二叉树从上到下且从左至右进行1至n的编号，则对完全二叉树中任意一个编号为i的结点：(1)若i=1，则该结点是二叉树的根，无双亲,否则，编号

2、为i/2的结点为其双亲结点;(2)若2i>n，则该结点无左孩子，否则，编号为2i的结点为其左孩子结点；(3)若2i+1>n，则该结点无右孩子结点，否则，编号为2i+1的结点为其右孩子结点。二叉树的顺序存储ACGBDEFHJI12345678910完全二叉树：从上到下，从左往右依次编号012345678910ABCEFDGHIJ二叉树的顺序存储ABDCEF一般的二叉树：想象成一个完全二叉树ABDCEF00000000二叉树的顺序存储ABDCEF000000001234567891011121314二叉树的顺序存储ABDCEF1

3、253714二叉树的顺序存储ABDCEF125371401234567891011121314ABCDEF0123456789101112131411110010000001如何知道有无数据？#defineMAX_TREE_SIZE100//二叉树的最大结点数typedefTElemTypeSqBiTree[MAX_TREE_SIZE];//1号单元存储根结点SqBiTreebt;二叉树的顺序存储适合完全二叉树（书上的定义0号单元？）#defineMAX_TREE_SIZE100//二叉树的最大结点数typedefstruct{TE

4、lemTypedata[MAX_TREE_SIZE];charflag[MAX_TREE_SIZE];}SqBiTree;二叉树的顺序存储适用于一般的二叉树链式存储—二叉链表lchilddatarchild二叉链表的结点结构:左指针域，指向当前结点的左子树数据域，存储当前结点的取值信息右指针域，指向当前结点的右子树前述二叉树的二叉链表如下所示：AF∧∧E∧C∧D∧∧B∧root链式存储—二叉链表ABDCEFtypedefstructBiTNode{//结点结构TElemTypedata;structBiTNode*lchild,*r

5、child;//左右孩子指针}BiTNode,*BiTree;lchilddatarchild结点结构:二叉链表的C语言类型描述如下:左指针域数据域右指针域链式存储—二叉链表parentlchilddatarchild三叉链表的结点结构:指向双亲结点的指针域左指针域数据域右指针域链式存储—三叉链表rootAEF∧∧∧D∧∧C∧B∧∧二叉树的三叉链表表示：链式存储—三叉链表typedefstructTriTNode{TElemTypedata;structTriTNode*lchild,*rchild;structTriTNode*p

6、arent;}TriTNode,*TriTree;三叉链表的C语言类型描述如下:parentlchilddatarchild结点结构://结点结构//左右孩子指针//双亲指针链式存储—三叉链表链式存储—双亲链表结点结构:dataparentLRTag数据域双亲域，存储当前结点双亲结点的存储位置左右孩子标志，如果是其双亲的左孩子，则填写“L”;如果是右孩子，则填写“R”根链式存储—双亲链表BDCEAF01234564401-13LRRRLABDCEF链式存储—双亲链表typedefstructBPTNode{//结点结构TElemTy

7、pedata;intparent;//指向双亲的指针charLRTag;//左、右孩子标志域}BPTNodetypedefstructBPTree{//树结构BPTNodenodes[MAX_TREE_SIZE];intnum_node;//结点数目introot;//根结点的位置}BPTree链式存储—双亲链表问题的提出在实际应用中，经常需要在二叉树中查找具有某些特征的结点，或者对树中的全部结点逐一进行某种处理，这就提出了二叉树的遍历的问题。问题的提出定义：顺着某一条搜索路径巡访二叉树中的结点，使得每个结点均被访问一次，而且仅被访

8、问一次。作用：遍历的目的是线性化，使二叉树中的结点能够按照某种次序排列在一个线性队列上，便于处理。问题的提出线性结构的遍历：因为每个结点均只有一个后继，所以只有一条搜索路径。二叉树的遍历：二叉树是非线性结构，每个结点有两个后继，则存在