基于java数据结构实验 二叉树实验报告

实验报告系部计算机系班级学号姓名课程名称数据结构实验日期2019-11-14实验名称二叉树的操作成绩实验目的：1理解二叉树的类型定义与性质；2、掌握二叉树的二叉链表存储结构的表示和实现方法；3掌握二叉树遍历操作的算法实现。实验条件：eclipse实验内容与步骤：内容：建立二叉树的二叉链表存储结构；实现二叉树的先根，中根和后根三种遍历操作。实现二叉搜索树及相关操作。步骤：建立节点类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(); } } }运行结果：二叉搜索树：实验总结：通过这次实验，我掌握了二叉树的结构原理以及它的先序，中序，后序遍历，运用递归的方法实现和不用递归的方法实现。二叉搜索树的原理和算法实现，根据二叉搜索树的特点，运用二分法进行二叉搜索树的一系列操作。附：源程序：二叉树：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("节点数为："); 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