二叉树遍历和应用

二叉树的遍历和应用二叉树的遍历小结和作业问题的提出递归遍历算法非递归遍历算法复习二叉树遍历算法的应用复习在二叉树的第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，则该结点是二叉树的根，无双亲,否则，编号为i/2的结点为其双亲结点;(2)若2in，则该结点无左孩子，否则，编号为2i的结点为其左孩子结点；(3)若2i+1n，则该结点无右孩子结点，否则，编号为2i+1的结点为其右孩子结点。二叉树的顺序存储ACGBDEFHJI12345678910完全二叉树：从上到下，从左往右依次编号012345678910ABCEFDGHIJ二叉树的顺序存储ABDCEF一般的二叉树：想象成一个完全二叉树ABDCEF00000000二叉树的顺序存储ABDCEF000000001234567891011121314二叉树的顺序存储ABDCEF1253714二叉树的顺序存储ABDCEF125371401234567891011121314ABCDEF0123456789101112131411110010000001如何知道有无数据？#defineMAX_TREE_SIZE100//二叉树的最大结点数typedefTElemTypeSqBiTree[MAX_TREE_SIZE];//1号单元存储根结点SqBiTreebt;二叉树的顺序存储适合完全二叉树（书上的定义0号单元？）#defineMAX_TREE_SIZE100//二叉树的最大结点数typedefstruct{TElemTypedata[MAX_TREE_SIZE];charflag[MAX_TREE_SIZE];}SqBiTree;二叉树的顺序存储适用于一般的二叉树链式存储—二叉链表lchilddatarchild二叉链表的结点结构:左指针域，指向当前结点的左子树数据域，存储当前结点的取值信息右指针域，指向当前结点的右子树前述二叉树的二叉链表如下所示：AF∧∧E∧C∧D∧∧B∧root链式存储—二叉链表ABDCEFtypedefstructBiTNode{//结点结构TElemTypedata;structBiTNode*lchild,*rchild;//左右孩子指针}BiTNode,*BiTree;lchilddatarchild结点结构:二叉链表的C语言类型描述如下:左指针域数据域右指针域链式存储—二叉链表parentlchilddatarchild三叉链表的结点结构:指向双亲结点的指针域左指针域数据域右指针域链式存储—三叉链表rootAEF∧∧∧D∧∧C∧B∧∧二叉树的三叉链表表示：链式存储—三叉链表typedefstructTriTNode{TElemTypedata;structTriTNode*lchild,*rchild;structTriTNode*parent;}TriTNode,*TriTree;三叉链表的C语言类型描述如下:parentlchilddatarchild结点结构://结点结构//左右孩子指针//双亲指针链式存储—三叉链表链式存储—双亲链表结点结构:dataparentLRTag数据域双亲域，存储当前结点双亲结点的存储位置左右孩子标志，如果是其双亲的左孩子，则填写“L”;如果是右孩子，则填写“R”根链式存储—双亲链表BDCEAF01234564401-13LRRRLABDCEF链式存储—双亲链表typedefstructBPTNode{//结点结构TElemTypedata;intparent;//指向双亲的指针charLRTag;//左、右孩子标志域}BPTNodetypedefstructBPTree{//树结构BPTNodenodes[MAX_TREE_SIZE];intnum_node;//结点数目introot;//根结点的位置}BPTree链式存储—双亲链表问题的提出在实际应用中，经常需要在二叉树中查找具有某些特征的结点，或者对树中的全部结点逐一进行某种处理，这就提出了二叉树的遍历的问题。问题的提出定义：顺着某一条搜索路径巡访二叉树中的结点，使得每个结点均被访问一次，而且仅被访问一次。作用：遍历的目的是线性化，使二叉树中的结点能够按照某种次序排列在一个线性队列上，便于处理。问题的提出线性结构的遍历：因为每个结点均只有一个后继，所以只有一条搜索路径。二叉树的遍历：二叉树是非线性结构，每个结点有两个后继，则存在如何遍历即按什么样的搜索路径进行遍历的问题。问题的提出二叉树存在下述三条搜索路径：1．先上后下的按层次遍历；2．先左（子树）后右（子树）的遍历；DLR，LDR，LRD3．先右（子树）后左（子树）的遍历。DRL，RDL，RLD先左后右的遍历算法先（根）序的遍历算法中（根）序的遍历算法后（根）序的遍历算法根左子树右子树根根根根根先序（根）遍历左子树右子树根根左子树右子树若二叉树为空树，则空操作；否则，（1）访问根结点（2）先序遍历左子树（3）先序遍历右子树先序（根）遍历ABCDEFGHKABCDEFGHKABCDEFGHK先序遍历ABDCEFABC先序遍历voidPreorder(BiTreeT,void(*visit)(TElemType&e)){//先序遍历二叉树if(T){visit(T-data);//访问结点Preorder(T-lchild,visit);//遍历左子树Preorder(T-rchild,visit);//遍历右子树}}中序（根）遍历左子树右子树根根左子树右子树若二叉树为空树，则空操作；否则，（1）中序遍历左子树；（2）访问根结点；（3）中序遍历右子树中序（根）遍历ABCDEFGHKABCDEFGHKABDCEHGKF中序遍历voidInorder(BiTreeT,void(*visit)(TElemType&e)){//中序遍历二叉树1if(!T)return;2Inorder(T-lchild,visit);//遍历左子树3visit(T-data);//访问结点4Inorder(T-rchild,visit);//遍历右子树}后序（根）遍历左子树右子树根根左子树右子树若二叉树为空树，则空操作；否则，（1）后序遍历左子树；（2）后序遍历右子树；（3）访问根结点。后序（根）遍历ABCDEFGHKABCDEFGHKADCBHKGFEvoidPostorder(BiTreeT,void(*visit)(TElemType&e)){//后序遍历二叉树1if(!T)return;2Postorder(T-lchild,visit);//遍历左子树3Postorder(T-rchild,visit);//遍历右子树4visit(T-data);//访问结点}后序遍历ABCDEFGHK先序序列：中序序列：后序序列：ABCDEFGHKBDCAEHGKFDCBHKGFEA三种遍历的比较1、如果不考虑visit，三种遍历的算法在结构上是一样的，因此，压栈和出栈的过程相同。三种遍历的比较2、三种遍历的执行过程是不一样的（visit的位置不一样）。3、由前序序列和中序序列，或者后序和中序序列可以唯一确定一颗二叉树ABECD中序遍历-执行过程中序遍历-执行过程(A)1.if2.(B)3.vi4.(E)1.if2.(C)3.vi4.(D)1.if2.({})3.vi4.({})1.if1.if1.if2.({})3.vi4.({})1.if1.if1.if2.({})3.vi4.({})1.if1.ifA1A1B1A1B1C1A1B1C1NULLA1B1C2A1B1NULLA1B2A1D1ABECDNullNullNullNullNullNull算法6.2中序遍历-算法6.2StatusInOrder(BiTreeT,Status(*visit)(TElemTypee){InitStack(S);Push(S,T);while(!StackEmpty(S)){while(GetTop(S,p)&&p){//栈顶不是空指针push(S,p-lchild);Pop(S,p);if(!StackEmpty(S)){Pop(S,p);visit(p);Push(S,p-rchild;}}//while}中序遍历非递归，算法6.3StatusInOrderTraverse(BiTreeT,Status(*visit)(TElemType&e)){InitStack(S);p=T;While(p||!StackEmpty(S)){if(p){Push(S,p);p=p-lchild;}else{Pop(S,p);if(!visit(p-data))returnERROR;p=p-rchild;}//else}//whilereturnOK;}非递归算法ABCDEFGpiP-A(1)ABCDEFGpiP-AP-B(2)ABCDEFGpiP-AP-BP-C(3)p=NULLABCDEFGiP-AP-B访问：C(4)算法6.3pABCDEFGiP-A访问：CB(5)ABCDEFGiP-AP-D访问：CBp(6)ABCDEFGiP-AP-DP-E访问：CBp(7)ABCDEFGiP-AP-D访问：CBEp(8)ABCDEFGiP-AP-DP-G访问：CBEP=NULL(9)ABCDEFGiP-A访问：CBEGDp(11)ABCDEFGiP-AP-F访问：CBEGDp(12)ABCDEFGiP-AP-D访问：CBEGp(10)ABCDEFGiP-A访问：CBEGDFp=NULL(13)ABCDEFGi访问：CBEGDFAp(14)ABCDEFGi访问：CBEGDFAp=NULL(15)ABECD先序遍历-执行过程先序遍历-执行过程(A)1.if2.vi3.(B)4.(E)1.if2.vi3.(C)4.(D)1.if2.vi3.({})4.({})1.if2.vi3.({})4.({})1.if2.vi3.({})4.({})ABECD先序遍历-执行过程(A)1.if2.vi3.(B)4.(E)1.if2.vi3.(C)4.(D)1.if2.vi3.({})4.({})1.if2.vi3.({})4.({})1.if2.vi3.({})4.({})2、统计二叉树中叶子结点的个数3、求二叉树的深度(后序遍历)5、建立二叉树的存储结构1、查询二叉树中某个结点遍历算法的应用举例1）查询二叉树中的某个结点1.在二叉树不空的前提下,和根结点的元素进行比较,若相等,则找到返回指向根结点的指针;2.否则在左子树中进行查找,若找到,则返回指针3.否则继续在右子树中进行查找,若找到,则返回TRUE,否则返回空指针;1）查询二叉树中的某个结点BiTreePreorder(BiTreeT,ElemTypex){}if(!T)return(NULL);if(T-data==x)return(T)；if(p)//返回值不是空指针，则表示x在左子树中return(p);elsereturn(Preorder(T-rchild,x));p=Preorder(T-lchild,x);使用先序遍历:设置一个全局变量2）统计二叉树中叶子结点的个数将visit改为判断结点是否是叶子结点，是则累加2）统计二叉树中叶子结点的个数voidPreOrder(BiTreeT){}if(T){}//ifif((!T-lchild)&&(!T-rchild))count++;//对叶子结点计数Preorder(T-lchild);Preorder(T-rchild);2）统计二叉树中叶子