精仪学院06级测控技术与仪器3班.ppt

树,精仪学院06级测控技术与仪器3班邱侠斐dosxpTOJqiuxiafei,什么是树,数据结构中的树,树是无回路的有向连通图树是nn0个结点的有限集。在任意一棵非空树中1有且仅有一个特定的称为根的结点；2当n1时,其余结点可分为mm0个互不相交的有限集T1,T2,...Tm,其中每一个集合本身又是一棵树,并且称为根的子树.,相关名词,结点拥有的子树数目称为结点的度。度为0的结点称为叶子结点。树的度是树内各结点的度最大值。结点的子树的根称为该结点的儿子，相应地，该结点称为儿子的父亲。同一个父亲的孩子之间互称兄弟。结点的祖先是从根到该结点所经分支上的所有结点。以某结点为根的子树中的任一结点都称为该结点的子孙。树中结点的最大层次称为树的深度或高度。,,二叉树,,,,,五种基本形态,,,,,二叉树,每个结点至多只有二棵子树。且子树有左右之分。,满二叉树,完全二叉树,二叉树的性质,二叉树的性质,nn0n1n2n-1n1*1n2*2,,二叉树的性质,性质5如果对一棵有n个结点的完全二叉树的结点按层序编号，则对任一结点i1n,则结点i无左儿子结点i为叶子结点;否则其左儿子是结点2i;如果2i1n,则结点i无右儿子;否则其右儿子是结点2i1;,二叉树顺序储存结构,优点编程简单，安全缺点对非完全二叉树而言，浪费存储空间,二叉树链式储存结构,structnode{intkey;node*ls,*rs;};node*rootnewnode;root-key-1;root-lsroot-rsNULL;,二叉树的遍历,遍历按照一定顺序访问且仅访问一次树中每一个结点。,前序遍历VLR次序访问当前结点，前序遍历左子树，前序遍历右子树。中序遍历LVR次序中序遍历左子树，访问当前结点，中序遍历右子树。后续遍历LRV次序后序遍历左子树，后序遍历右子树，访问当前结点。,V当前访问到的结点L当前结点的左子树R当前结点的右子树,V,L,R,PreOderTraversal,ABDGECF,voidpreodernode*p{ifpNULLreturn;coutkey;preoderp-ls;preoderp-rs;return;},InOderTraversal,voidinodernode*p{ifpNULLreturn;inoderp-ls;coutkey;inoderp-rs;return;},DGBEAFC,PostOderTraversal,voidpostodernode*p{ifpNULLreturn;postoderp-ls;postoderp-rs;coutkey;return;},GDEBFCA,Haveanrciseorabreak,入门篇TOJ3009.MonkeyVines,题目大意一群猴子爬树，猴子挂在树枝上，要使整个树平衡，至少需要多少只猴子树在每个中间节点都有两个分支。,Sample3[][[][[]]],SampleOutput122138,charbuf[MAX];redep0;cinbuf;fort0;buf[t]\0;t{ifbuf[t][dep;elseifbuf[t]]dep--;ifredepredep;}coutreiendreturn;intt;fortist;tiend;tifin[t]pre[pst]break;solvpst1,pstt-ist,ist,t-1;solvpstt-ist1,pend,t1,iend;couta},二叉树性质3n0n21,ExpandedTask,建立一颗深度为10的完全二叉树建立一棵区间为[0,100]的线段树,堆Heap,堆是一棵完全二叉树，它的任意一个结点的值都大于小于它的子结点。,保持堆的性质Heapfy,16,10,7,9,8,3,2,1,4,14,14,4,4,8,保持堆的性质Heapfy,16,14,10,7,9,3,2,1,8,4,Done,16,14,10,8,7,9,4,3,2,1,堆的插入Insert,15,16,14,10,8,15,9,4,3,2,1,堆的插入Insert,7,16,15,10,8,14,9,4,3,2,1,堆的插入Insert,7,Done,7,出堆Pop,16,15,10,8,14,9,4,3,2,1,7,Heapfy....,15,14,10,8,7,9,4,3,2,1,Done,出堆Pop,TOJ2196.NuanransIdolII,题目大意Nuanran同学喜欢搜集凯蒂猫的图片，他会给每张图片一个分数表示其受喜爱的程度，分数越高表示越喜欢。他会经常自己买一些新图片，也会给别人一些，但每次都是给自己最不喜爱的给别人。,Sample8B20B10GB9GB100B25G0,SampleOutput10920,想一想,1.每次买进后就排序，nlogn；2.扫描一遍现有的图片，n；3.堆，logn;,Butwhylogn,So,comeon,准备工作,用数组实现，why,inlineintparentintt{returnt/2;}//返回父结点的下标inlineintleftintt{returnt*2;}//返回左孩子的下标inlineintrightintt{returnt*21;}//返回右孩子的下标inlinevoidswapint//指向堆的尾部，从1开始,初始化Initialize,voidinit{memsetheap,-1,sizeofheap;len1;return;},inlineintgettop{returnheap[1];},取最优值GetBest,保持堆的性质Heapfy,voidheapfyintt{intlleftt;intrrightt;intmt;iflheap[b]},出堆Pop,voidpop{iflen1return;len--;heap[1]heap[len];heap[len]0;heapfy1;return;},Anyquestion,ThatsallThx,