Java实现二叉树的遍历

一、数据结构分类（一）按逻辑结构1.集合(无辑关系)2.线性结构(线性表)：数组、链表、栈、队列3.非线性结构：树、图、多维数组（二）按存储结构顺序（数组）储结构、链式储结构、索引储结构、散列储结构二、二叉树相关性质结点的度：一个结点的子树的个数记为该结点的度．树的度：所有节点中度数最大的结节的度数，叶子节点的度为零。树的高度：一棵树的最大层次数记为树的高度(或深度)。有序(无序)树：若将树中结点的各子树看成是从左到右具有次序的，即不能交换，则称该树为有序树。否则称为无序树。二叉树第i层（i≥1）上至多有2^(i-1)个节点。深度为k的二叉树至多有2^k-1个节点（k≥1）。对任何一棵二叉，若叶子节点数为n0，度为2的节点数为n2，则n0=n2+1。具有n个节点的完全二叉树的深度为(㏒2^n)(向下取整)+1。对一棵有n个节点的完全二叉树的节点按层次从上到下，自左至右进行编号，则对任一节点i(1≤i≤n)有：若i=1，则节点i是二叉树的根，无双亲；若i1，则其双亲为i/2(向下取整)。若2in，则节点i没有孩子节点，否则其左孩子为2i。若2i+1n，则节点i没有右孩子，否则其右孩子为2i+1。若深度为k的二叉树有2^k-1个节点，则称其为满二叉树。满二叉树是一棵完全二叉树。对于完全二叉树中，度为1的节点个数只可能为1个或0个。对于二叉树，如果叶子节点数为n0，度为1的节点数为n1，度为2的节点数为n2，则节点总数n=n0+n1+n2。对于任意树，总节点数=每个节点度数和+1二叉树的高度等于根与最远叶节点（具有最多祖先的节点）之间分支数目。空树的高度是-1。只有单个元素的二叉树，其高度为0。.三、二叉树的遍历遍历是按某种策略访问树中的每个节点，且仅访问一次。（一）二叉树结构实现Java代码1.packagetree.bintree;2./**3.*创建非完全二叉树、完全二叉树、满二叉树4.*5.*由于二叉树的节点增加没有什么规则，所以这里只是简单的使用了递一6.*次性把整棵树创建出来，而没有设计出一个一个添加节点的方法与删除7.*8.*@authorjzj9.*@date2009-12-2310.*/11.publicclassBinTree{//Bin=Binary(二进位的,二元的)12.13.protectedEntryroot;//根14.privateintsize;//树的节点数15.16./**17.*树的节点结构18.*@authorjzj19.*@date2009-12-2320.*/21.protectedstaticclassEntry{22.intelem;//数据域，这里我们作为编号23.Entryleft;//左子树24.Entryright;//右子树25.26.publicEntry(intelem){27.this.elem=elem;28.}29.30.publicStringtoString(){31.returnnumber=+elem;32.}33.}34.35./**36.*根据给定的节点数创建一个完全二叉树或是满二叉树37.*@paramnodeCount要创建节点总数38.*/39.publicvoidcreateFullBiTree(intnodeCount){40.root=recurCreateFullBiTree(1,nodeCount);41.}42.43./**44.*递归创建完全二叉树45.*@paramnum节点编号46.*@paramnodeCount节点总数47.*@returnTreeNode返回创建的节点48.*/49.privateEntryrecurCreateFullBiTree(intnum,intnodeCount){50.size++;51.EntryrootNode=newEntry(num);//根节点52.//如果有左子树则创建左子树53.if(num*2=nodeCount){54.rootNode.left=recurCreateFullBiTree(num*2,nodeCount);55.//如果还可以创建右子树，则创建56.if(num*2+1=nodeCount){57.rootNode.right=recurCreateFullBiTree(num*2+1,nodeCount);58.}59.}60.return(Entry)rootNode;61.}62.63./**64.*根据给定的数组创建一棵树，这个棵树可以是完全二叉树也可是普通二叉树65.*数组中为0的表示不创建该位置上的节点66.*@paramnums数组中指定了要创建的节点的编号，如果为0，表示不创建67.*/68.publicvoidcreateBinTree(int[]nums){69.root=recurCreateBinTree(nums,0);70.}71.72./**73.*递归创建二叉树74.*@paramnums数组中指定了要创建的节点的编号，如果为0，表示不创建75.*@paramindex需要使用数组中的哪个元素创建节点，如果为元素为0，则不创建76.*@returnTreeNode返回创建的节点，最终会返回树的根节点77.*/78.privateEntryrecurCreateBinTree(int[]nums,intindex){79.//指定索引上的编号不为零上才需创建节点80.if(nums[index]!=0){81.size++;82.EntryrootNode=newEntry(nums[index]);//根节点83.//如果有左子树则创建左子树84.if((index+1)*2=nums.length){85.rootNode.left=(Entry)recurCreateBinTree(nums,(index+1)*2-1);86.//如果还可以创建右子树，则创建87.if((index+1)*2+1=nums.length){88.rootNode.right=(Entry)recurCreateBinTree(nums,(index+1)*2);89.}90.}91.return(Entry)rootNode;92.}93.returnnull;94.95.}96.97.publicintsize(){98.returnsize;99.}100.101.//取树的最左边的节点102.publicintgetLast(){103.Entrye=root;104.while(e.right!=null){105.e=e.right;106.}107.returne.elem;108.}109.110.//测试111.publicstaticvoidmain(String[]args){112.113.//创建一个满二叉树114.BinTreebinTree=newBinTree();115.binTree.createFullBiTree(15);116.System.out.println(binTree.size());//15117.System.out.println(binTree.getLast());//15118.119.//创建一个完全二叉树120.binTree=newBinTree();121.binTree.createFullBiTree(14);122.System.out.println(binTree.size());//14123.System.out.println(binTree.getLast());//7124.125.//创建一棵非完全二叉树126.binTree=newBinTree();127.int[]nums=newint[]{1,2,3,4,0,0,5,0,6,0,0,0,0,7,8};128.binTree.createBinTree(nums);129.System.out.println(binTree.size());//8130.System.out.println(binTree.getLast());//8131.132.}133.}（二）利用二叉树本身特点进行递归遍历（属内部遍历）由于二叉树所具有的递归性质，一棵非空的二叉树可以看作是由根节点、左子树和右子树3部分构成，因为若能依次遍历这3部分的信息，也就遍历了整个二叉树。按照左子树的遍历在右子树的遍历之前进行的约定，根据访问根节点位置的不同，可以得到二叉的前序、中序、后序3种遍历方法。Java代码1.packagetree.bintree;2.3./**4.*二叉树的三种内部遍历：前序、中序、后序5.*但不管是哪种方式，左子树的遍历在右子树的遍历之前遍历是这有三种遍历方式都6.*必须遵循的约定7.*@authorjzj8.*@date2009-12-239.*/10.publicclassBinTreeInOrderextendsBinTree{11.12./**13.*节点访问者，可根据需要重写visit方法14.*/15.staticabstractclassVisitor{16.voidvisit(Objectele){17.System.out.print(ele+);18.}19.}20.21.publicvoidpreOrder(Visitorv){22.preOrder(v,root);23.}24.25./**26.*树的前序递归遍历pre=prefix(前缀)27.*@paramnode要遍历的节点28.*/29.privatevoidpreOrder(Visitorv,Entrynode){30.//如果传进来的节点不为空，则遍历，注，叶子节点的子节点为null31.if(node!=null){32.v.visit(node.elem);//先遍历父节点33.preOrder(v,node.left);//再遍历左节点34.preOrder(v,node.right);//最后遍历右节点35.}36.}37.38.publicvoidinOrder(Visitorv){39.inOrder(v,root);40.}41.42./**43.*树的中序递归遍历in=infix(中缀)44.*@paramnode要遍历的节点45.*/46.privatevoidinOrder(Visitorv,Entrynode){47.//如果传进来的节点不为空，则遍历，注，叶子节点的子节点为null48.if(node!=null){49.inOrder(v,node.left);//先遍历左节点50.v.visit(node.elem);//再遍历父节点51.inOrder(v,node.right);//最后遍历右节点52.}53.}54.55.publicvoidpostOrder(Visitorv){56.postOrder(v,root);57.}58.59./**60.*树的后序递归遍历post=postfix(后缀)61.*@paramnode要遍历的节点62.*/63.privatevoidpostOrder(Visitorv,Entrynode){64.//如果传进来的节点不为空，则遍历，注，叶子节点的子节点为null65.if(node!=null){66.postOrder(v,node.left);//先遍历左节点67.postOrder(v,node.right);//再遍历右节点68.v.visit(node.elem);//最后遍历父节点69.}70.}71.72.//测试73.publicstaticvoidmain(String[]args){74.75.//创建二叉树76.int[]nums=newint[]{1,2,3,4,0,0,5,0,6,0,0,0,0,7,8};77.BinTreeInOrdertr