数据结构应用(树――基础知识二)

树基础知识二叉树的遍历•顺着某一条搜索路径巡访二叉树中的结点，使得每个结点均被访问一次，而且仅被访问一次。•“访问”的含义可以很广如：输出结点的信息等。问题的提出对“二叉树”而言，可以有四条遍历路径：先上后下的按层次遍历前序（先根）的遍历算法中序（中根）的遍历算法后序（后根）的遍历算法•二叉树的基本结构是由根结点(D)、左子树(L)和右子树(R)三个基本单元组成。DLRDLRLDR、LRD、DLRRDL、RLD、DRLLChilddataRChild二叉链表结点的基本组成ABC^^^^ADBC遍历序列：ABCD层次遍历:①从上到下②从左到右二叉树的遍历ADBCDLRADLRDLRBDCDLR前序遍历序列：ABDC前序遍历:①访问根结点②按前序遍历左子树③按前序遍历右子树二叉树的遍历中序遍历:①按中序遍历左子树②访问根结点③按中序遍历右子树ADBCLDRBLDRLDRADCLDR中序遍历序列：BDAC二叉树的遍历后序遍历:①按后序遍历左子树②按后序遍历右子树③访问根结点ADBCLRDLRDLRDADCLRD后序遍历序列：DBCAB二叉树的遍历例子1ABCFDEGH•前序遍历：•中序遍历：•后序遍历：ABDFCEGHBFDAGEHCFDBGHECA•层次遍历：ABCDEFGH前序遍历:①访问根结点②按前序遍历左子树③按前序遍历右子树二叉树的遍历例子2--表达式求值例(a+b*c)-d/e-+/a*bcde•前序遍历(前缀)：-+a*bc/de•中序遍历(中缀)：a+b*c-d/c•后序遍历(后缀)：abc*+de/-前缀表达式也称波兰表达式,后缀表达式也称逆波兰表达式，在计算机内使用后缀表达式易于求值二叉树的遍历voidPreOrder(BiTreeroot){/*前序遍历二叉树，root为指向二叉树(或某一子树)根结点的指针*/if(root!=NULL){Visit(root-data);/*访问根结点*/PreOrder(root-LChild);/*前序遍历左子树*/PreOrder(root-RChild);/*前序遍历右子树*/}}二叉树的遍历算法前序遍历:①访问根结点②按前序遍历左子树③按前序遍历右子树voidInOrder(BiTreeroot){/*中序遍历二叉树，root为指向二叉树(或某一子树)根结点的指针*/if(root!=NULL){InOrder(root-LChild);/*中序遍历左子树*/Visit(root-data);/*访问根结点*/InOrder(root-RChild);/*中序遍历右子树*/}}二叉树的遍历算法中序遍历:①按中序遍历左子树②访问根结点③按中序遍历右子树voidPostOrder(BiTreeroot){/*后序遍历二叉树，root为指向二叉树(或某一子树)根结点的指针*/if(root!=NULL){PostOrder(root-LChild);/*后序遍历左子树*/PostOrder(root-RChild);/*后序遍历右子树*/Visit(root-data);/*访问根结点*/}}二叉树的遍历算法后序遍历:①按后序遍历左子树②按后序遍历右子树③访问根结点二叉树遍历的非递归算法所有的递归的遍历算法都可以用非递归算法来替代，下面给出层次遍历和前序遍历的非递归算法的伪代码层次遍历定义队列QNode*p=root;Q.EnQueue(p){while(!Q.IsEmpty(){Q.DeQueue(p);visit(p);If(p-pLeft!=NULL)Q.EnQueue(p-pLeft);if(p-pRight!=NULL)Q.EnQueue(p-pRight);}前序遍历定义栈sNode*p=root;While(p!=NULL){visit（p);if(p-pRight！=NULL)s.push(p-pRight);if(p-pLeft!=NULL)p=p-pLeft;elsep=s.pop();}遍历算法的应用输出二叉树中的结点输出二叉树中的叶子结点求二叉树的高度建立二叉树1、先序遍历输出二叉树的结点:voidPreOrder(BiTreeroot){/*先序遍历输出二叉树结点，root为指向二叉树根结点的指针*/if(root!=NULL){coutroot-data;/*输出根结点*/PreOrder(root-LChild);/*前序遍历左子树*/PreOrder(root-RChild;/*前序遍历右子树*/}}返回2、输出二叉树的叶子结点:voidPreOrder(BiTreeroot){/*前序遍历输出二叉树的叶子结点，root为指向二叉树根结点的指针*/if(root!=NULL){if(root-LChild==NULL&&root-RChild==NULL)coutroot-data;/*输出叶子结点*/PreOrder(root-LChild);/*先序遍历左子树*/PreOrder(root-RChild;/*先序遍历右子树*/}}D^^假设用LeafCount表示叶子结点数目的变量，则如何实现统计叶子结点数目呢？LeafCount++;返回3、求二叉树的高度：f(bt)=0;若bt==NULLf(bt)=max(f(bt-LChild),f(bt-RChild))+1;若bt!=NULLADBC空二叉树3、求二叉树的高度：intTreeDepth(BiTreebt){inthl,hr,max;if(bt!=NULL){hl=TreeDepth(bt-LChild);/*求左子树的深度*/hr=TreeDepth(bt-RChild);/*求右子树的深度*/max=hlhr?hl:hr;/*求深度最大者*/return(max+1);/*返回树的深度*/}elsereturn(0);}返回4、建立二叉链表方式存储的二叉树voidCreateBiTree(BiTree*bt){charch;ch=getchar();if(ch==‘.’)*bt=NULL;else{*bt=newBiTNode;(*bt)-data=ch;CreateBiTree(&((*bt)-LChild));CreateBiTree(&((*bt)-RChild));}}类似前序遍历的递归算法:①建立当前根结点②建当前根结点左子域③建当前根结点右子域按前序遍历序列建立二叉树的二叉链表，前序序列为：ABCDEGFABCDEFGA^B^C^D^E^F^^G^Play由遍历序列确定二叉树–任意一棵二叉树结点的前序遍历和中序遍历是唯一的。•给定一棵二叉树的前序序列和中序序列，可用递归的方法得到一棵确定的二叉树；•给定结点的中序序列和后序序列也可以唯一确定一棵二叉树。由遍历序列确定二叉树例1--已知结点的前序序列和中序序列分别为：前序序列：18147311223527中序序列：37111418222735371114○18222735（1）371114○18222735（1）左子树由遍历序列确定二叉树右子树例1--已知结点的前序序列和中序序列分别为：前序序列：18147311223527中序序列：37111418222735○143711○182735○22○143711○182735○22例1--已知结点的前序序列和中序序列分别为：前序序列：18147311223527中序序列：37111418222735○14○1827○22○7○35311例2--已知结点的中序序列和后序序列分别为：中序序列：debac后序序列：dabecdeba○c左子树deba○c由遍历序列确定二叉树由遍历序列确定二叉树–2、已知结点的中序序列和后序序列分别为：中序序列：debac后序序列：dabecd○c○ebad○c○eba例2--已知结点的中序序列和后序序列分别为：中序序列：debac后序序列：dabec○c○e○d○b○a小结二叉树采用顺序存储与二叉链表存储，其孩子个数最大为2，故采用二叉树的二叉链表表示法实现存储。二叉树根据对根的访问先后顺序不同，有三种基本遍历方式：先序遍历，中序遍历和后序遍历。任意一棵二叉树结点的前序遍历和中序遍历是唯一的，根据中序遍历是先遍历左子树L，然后访问根D，最后遍历右子树R，则根结点D将中序序列分割成两部分：–在D之前是左子树结点的中序序列–在D之后是右子树结点的中序序列•用递归的方法由前序序列和中序序列可唯一确定一棵二叉树；由后序序列和中序序列可唯一确定一棵二叉树。