基于java數(shù)據(jù)結(jié)構(gòu)實驗 二叉樹實驗報告

實驗報告系部計算機系班級學(xué)號姓名課程名稱數(shù)據(jù)結(jié)構(gòu)實驗日期2019-11-14實驗名稱二叉樹的操作成績實驗?zāi)康模?理解二叉樹的類型定義與性質(zhì)；2、掌握二叉樹的二叉鏈表存儲結(jié)構(gòu)的表示和實現(xiàn)方法；3掌握二叉樹遍歷操作的算法實現(xiàn)。實驗條件：eclipse實驗內(nèi)容與步驟：內(nèi)容：建立二叉樹的二叉鏈表存儲結(jié)構(gòu)；實現(xiàn)二叉樹的先根，中根和后根三種遍歷操作。實現(xiàn)二叉搜索樹及相關(guān)操作。步驟：建立節(jié)點類publicclassBinaryTreeNode<T>{ privateTdata; privateBinaryTreeNode<T>lchild,rchild; publicBinaryTreeNode(Tdata,BinaryTreeNode<T>lchild,BinaryTreeNode<T>rchild){ super(); this.data=data; this.lchild=lchild; this.rchild=rchild; } publicBinaryTreeNode(Tdata){ this.data=data; this.lchild=null; this.rchild=null; } publicBinaryTreeNode(){ this(null); }先序，中序，后序遍歷privatevoidpreorder(BinaryTreeNodep){ if(p!=null){ System.out.print(p.getData()+"\t"); preorder(p.getLchild()); preorder(p.getRchild()); } }privatevoidinorder(BinaryTreeNodep){ if(p!=null){ inorder(p.getLchild()); System.out.print(p.getData()+"\t"); inorder(p.getRchild()); } } publicvoidinorder(){ System.out.println("中序遍歷："); inorder(root); }privatevoidpostorder(BinaryTreeNodep){ if(p!=null){ postorder(p.getLchild()); postorder(p.getRchild()); System.out.print(p.getData()+"\t"); } } publicvoidpostorder(){ System.out.println("后序遍歷："); postorder(root); }二叉搜索樹publicvoidinsearch(intx){ if(root==null){ root=newNode(x); return; } Nodep=root; while(p!=null){ if(x>p.getData()){ if(p.getRight()==null){ p.setRight(newNode(x)); return; } p=p.getRight(); } else{ if(p.getLeft()==null){ p.setLeft(newNode(x)); return; } p=p.getLeft(); } } }運行結(jié)果：二叉搜索樹：實驗總結(jié)：通過這次實驗，我掌握了二叉樹的結(jié)構(gòu)原理以及它的先序，中序，后序遍歷，運用遞歸的方法實現(xiàn)和不用遞歸的方法實現(xiàn)。二叉搜索樹的原理和算法實現(xiàn)，根據(jù)二叉搜索樹的特點，運用二分法進行二叉搜索樹的一系列操作。附：源程序：二叉樹：packagetree;importjava.util.Deque;importjava.util.LinkedList;publicclassBinaryTree<T>{ privateBinaryTreeNoderoot; publicBinaryTree(BinaryTreeNoderoot){ super(); this.root=root; } publicBinaryTree(){ this.root=null; } publicBinaryTreeNodegetRoot(){ returnroot; } publicvoidsetRoot(BinaryTreeNoderoot){ this.root=root; } @Override publicStringtoString(){ return"BinaryTree[root="+root+"]"; } privatevoidpreorder(BinaryTreeNodep){ if(p!=null){ System.out.print(p.getData()+"\t"); preorder(p.getLchild()); preorder(p.getRchild()); } } publicvoidpreorder(){ System.out.println("先序遍歷："); preorder(root); } privatevoidinorder(BinaryTreeNodep){ if(p!=null){ inorder(p.getLchild()); System.out.print(p.getData()+"\t"); inorder(p.getRchild()); } } publicvoidinorder(){ System.out.println("中序遍歷："); inorder(root); } privatevoidpostorder(BinaryTreeNodep){ if(p!=null){ postorder(p.getLchild()); postorder(p.getRchild()); System.out.print(p.getData()+"\t"); } } publicvoidpostorder(){ System.out.println("后序遍歷："); postorder(root); } privateintsize(BinaryTreeNodep){ if(p==null){ return0; } intlchildsize=size(p.getLchild()); intrchildsize=size(p.getRchild()); returnlchildsize+rchildsize+1; } publicintsize(){ System.out.println("節(jié)點數(shù)為："); returnsize(root); } privateintheight(BinaryTreeNodep){ if(p==null){ return0； } inthl=height(p.getLchild()); inthr=height(p.getRchild()); return(hl>hr)?hl+1:hr+1; } publicintheight(){ System.out.println("高度為："); returnheight(root); } publicvoidshowleaves(BinaryTreeNodep){ if(p!=null){ if(p.getLchild()==null&&p.getRchild()==null){ System.out.print(p.getData()+"\t"); } showleaves(p.getLchild()); showleaves(p.getRchild()); } } publicvoidpretravel(){ BinaryTreeNodep=root; Deque<BinaryTreeNode>mystack=newLinkedList<BinaryTreeNode>(); if(p!=null){ mystack.push(p); while(!mystack.isEmpty()){ p=mystack.pop(); System.out.print(p.getData()+""); if(p.getRchild()!=null){ mystack.push(p.getRchild()); } if(p.getLchild()!=null){ mystack.push(p.getLchild()); } } } }}二叉搜索樹packagetree;publicclassBinartSearchtree{ privateNoderoot; publicBinartSearchtree(Noderoot){ super(); this.root=root; } publicBinartSearchtree(){ root=null; } publicvoidinsearch(intx){ if(root==null){ root=newNode(x); return; } Nodep=root; while(p!=null){ if(x>p.getData()){ if(p.getRight()==null){ p.setRight(newNode(x)); return; } p=p.getRight(); } else{ if(p.getLeft()==null){ p.setLeft(newNode(x)); return; } p=p.getLeft(); } } } publicNodefind(intx){ Nodep=root; while(p!=null){ if(x>p.getData()){ p=p.getRight(); } elseif(x<p.getData()){ p=p.getLeft(); } else{ returnp; } } returnnull; } publicvoidpreorder(){ System.out.println("先序遍歷："); preorder(root); } privatevoidpreorder(Nodep){ if(p!=null){ System.out.print(p.getData()+""); preorder(p.getLeft()); preorder(p.getRight()); } } publicNodeminNode(Nodep){ // Nodep=root; while(p.getLeft()!=null){ p=p.getLeft(); } returnp; } publicNodemaxNode(Nodep){ // Nodep=root; while(p.getRight()!=null){ p=p.getRight(); } returnp; } publicNodedelete(intx,Nodep){ Nodetemp; if(p==null){ System.out.println("error"); returnnull; } elseif(x<p.getData()){ p.setLeft(delete(x,p.getLeft())); } elseif(x>p.getData()){ p.setRight(delete(x,p.getRight())); } else{if(p.getLeft