实验五二叉树

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

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

2、yNode{publicTdata;publicBinaryNodeleft,right;publicBinaryNode(TdataBinaryNodeleft^BinaryNoderight){thiSedata=data;this.left=left;this.right=right;}publicBinaryNode(Tdata){this(data，null，null);}publicBinaryNode(){this(null^null^null);}}packageQl;publiccl

3、assBinaryTree{publicNodehead_pre;publicNodehead_in;publicBinaryNoderoot;publicBinaryTree(){this.root=null;}publicbooleanisEmpty(){returnthis.root==null;privateBinaryTreeinit_make(){BinaryTreebitree=newBinaryTree();Binar

4、yNodechild_f,child一d,child_b,chiId一c;child_d=newBinaryNode(nDn,null,newBinaryNode("G"));child_b=newBinaryNode(MB",child_dJnull);child_f=newBinaryNode(nF",newBinaryNode(nC’’，new

5、BinaryNode("E")?child_f);bitree.root=newBinaryNode(,,AMchild^^child_c);returnbitree;}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(Bina

6、ryNodep){if(p==null)return0;if(p.left==null&&p.right==null)return1;elsereturnleaf_count(p>left)+leaf_count(p.right);}privatevoidexchange(BinaryNodep){BinaryNodetemp=newBinaryNodeQ;if(p!=null){temp=p>left;p.left=p>right;p,right=tempjexchange(p.left);

7、exchange(p.right);}}publicBinaryTree(T[]prelist^T[]inlist){this.root=preOrder_inOrder_make(prelist>inlist,0,0,prelist.length);}privateBinaryNodepreOrder_inOrder_make(T[]preList,T[]inList,intpreStart^intinStartintn){if(n<=0)returnnull;Telem=preList[preStart];Bina

8、ryNodep=newBinaryNode(elem);inti=0;while(i