实验五二叉树.doc

《实验五二叉树.doc》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、实验五二叉树一、实验目的：1、掌握二叉树的创建算法、掌握二叉树的遍历算法2、掌握哈夫曼树的构造和应用，利用哈夫曼方法及其编/译码技术实现对传输信息编码/译码系统。二、实验内容：1、在一棵二叉链表表示的二叉树中，实现以下操作。1）输出叶子结点。2）求二叉树中叶子结点个数。3）将每个结点的左子树与右子树交换。4）已知先根和中根次序遍历序列构造二叉树。5）判断两棵二叉树是否相等。6）求结点所在的层次。7）复制一棵二叉树。8）判断一棵二叉树是否为完全二叉树。算法及测试结果粘贴如下：packageQ1;publicclassBinaryNode{publicTdata;pub

2、licBinaryNodeleft,right;publicBinaryNode(Tdata,BinaryNodeleft,BinaryNoderight){this.data=data;this.left=left;this.right=right;}publicBinaryNode(Tdata){this(data,null,null);}publicBinaryNode(){this(null,null,null);}}packageQ1;publicclassBinaryTree{publicNodehead_pre;pub

3、licNodehead_in;publicBinaryNoderoot;publicBinaryTree(){this.root=null;}publicbooleanisEmpty(){returnthis.root==null;}privateBinaryTreeinit_make(){BinaryTreebitree=newBinaryTree();BinaryNodechild_f,child_d,child_b,child_c;child_d=newBinaryNode

4、ing>("D",null,newBinaryNode("G"));child_b=newBinaryNode("B",child_d,null);child_f=newBinaryNode("F",newBinaryNode("H"),null);child_c=newBinaryNode("C",newBinaryNode("E"),child_f);bitree.root=newBinaryNode("A",child_b,child_c);returnb

5、itree;}privatevoidleaf(BinaryNodep){if(p!=null){if(p.left==null&&p.right==null){System.out.print(p.data+"");}leaf(p.left);leaf(p.right);}}privateintleaf_count(BinaryNodep){if(p==null)return0;if(p.left==null&&p.right==null)return1;elsereturnleaf_count(p.left)+leaf_count(p.r

6、ight);}privatevoidexchange(BinaryNodep){BinaryNodetemp=newBinaryNode();if(p!=null){temp=p.left;p.left=p.right;p.right=temp;exchange(p.left);exchange(p.right);}}publicBinaryTree(T[]prelist,T[]inlist){this.root=preOrder_inOrder_make(prelist,inlist,0,0,prelist.length);}privateBinaryN

7、odepreOrder_inOrder_make(T[]preList,T[]inList,intpreStart,intinStart,intn){if(n<=0)returnnull;Telem=preList[preStart];BinaryNodep=newBinaryNode(elem);inti=0;while(i