1、数据结构java实验四数据结构（JAVA）综合性、设计性实验成绩单 开设时间：2012学年第一学期 班级 11信管4班 学号 1.201130560415 姓名 1.刘梓明 2.201130560418 2.王悦 3.201130560419 3.薛泽展 4.201130560420 4.杨海龙 5.201130560424 5.余柏烨 实实验四 树和二叉树的基本操作 验题目 成绩 教师签名 数据结构（JAVA） 实 验 报 告 实验题目： 树和二叉树的基本操作 指导教师： 实验组长（姓名+学号）： 组员（姓名+学号）： 实验时间： 组长签名： 1 一、实验报告撰写提纲 1、实验目的 1 理解
2、二叉树的定义、性质、存储结构等基本概念，掌握二叉树类的设计方法，以及遍历、插入、删除等二叉树操作的算法实现；掌握采用链式存储结构表达非线性结构的设计方法；掌握采用递归算法实现递归数据结构基本操作的设计方法。 2 熟悉树的定义、表示、存储结构和遍历，具备使用树各种操作的能力。 2、实验内容 （1）在一棵二叉链表表示的二叉树中，实现以下操作，并说明采用哪种遍历算法，其他遍历算法是否可行。 输入叶子结点。 求二叉树中叶子结点个数。 将每个结点的左子树与右子树交换。 验证二叉树的性质3：n0=n2+1。 输出值大于k的结点。 已知先根和中根次序遍历序列构造二叉树。 以广义表表示构造二叉树。 判断两颗二
3、叉树是否相等。 求结点所在的层次。 求一颗二叉树在后根次序遍历下第一个访问的结点。 复制一颗二叉树。 判断一颗二叉树是否为完全二叉树。 实现二叉树后根次序遍历的非递归算法。 （2）声明三叉链表表示的二叉树类，实现二叉树的基本操作以及以下操作。 构造一颗三叉链表表示的二叉树。 返回指定结点的父母结点。 返回指定结点的所有祖先结点。 返回两结点最近的共同祖先结点。 （3）在一颗中序线索二叉树中，实现以下操作。 调用求结点的前驱结点算法，按中根次序遍历一颗中序线索二叉树 。 按后根次序遍历中序线索二叉树。 在构造二叉树时进行线索化。 插入、删除操作。 3、实验步骤与结果 （1）审题：在一棵二叉链表表
4、示的二叉树中，实现以下操作，并说明采用哪种遍历算法，其他遍历算法是否可行。 输入叶子结点。 求二叉树中叶子结点个数。 将每个结点的左子树与右子树交换。 验证二叉树的性质3：n0=n2+1。 输出值大于k的结点。 已知先根和中根次序遍历序列构造二叉树。 2 以广义表表示构造二叉树。 判断两颗二叉树是否相等。 求结点所在的层次。 求一颗二叉树在后根次序遍历下第一个访问的结点。 复制一颗二叉树。 判断一颗二叉树是否为完全二叉树。 实现二叉树后根次序遍历的非递归算法。 编程：这道小题需要用到几个类，分别是结点类Node,树结点类BinaryNode，顺序栈LinkedStack,顺序队列LinkedQ
5、ueue，然后编写BinaryTree类，逐一实现以上功能。验证类为yanzheng。 验证结果： 图 1 图 2 图 3 图 4 图 5 图 6 图 7 图 8 图 9 图 10 图 11 图 12 图 13 3 （2）审题：（2）声明三叉链表表示的二叉树类，实现二叉树的基本操作以及以下操作。 构造一颗三叉链表表示的二叉树。 返回指定结点的父母结点。 返回指定结点的所有祖先结点。 返回两结点最近的共同祖先结点。 编程：编写结点类TriNode，然后编写TriBinaryNode类实现二叉树的各个功能和方法。验证类为yanzheng2. 验证结果： 图 14 （3）审题：（3）在一颗中序线索二
6、叉树中，实现以下操作。 调用求结点的前驱结点算法，按中根次序遍历一颗中序线索二叉树 。 按后根次序遍历中序线索二叉树。 在构造二叉树时进行线索化。 插入、删除操作。 编程：编写结点类ThreadNode，然后编写中性线索二叉树ThreadTreee逐一实现各个功能。验证类为yanzheng3. 验证结果： 图 15 图 16 图 17 4、源码 （1）BinaryTree类 package 实验4； public class BinaryTree public BinaryNode root; public BinaryTree() this.root=null; 4 public void
7、preOrder() System.out.print(先根次序遍历二叉树：); preOrder(root); System.out.println(); public void preOrder(BinaryNode p) if(p!=null) System.out.print(p.data.toString()+ ); preOrder(p.left); preOrder(p.right); public BinaryTree(T prelist) this.root=create(prelist); private int i=0; public BinaryNode create(
8、T prelist) BinaryNode p=null; if(iprelist.length) T elem=prelisti; i+; if(elem!=null) p=new BinaryNode(elem); p.left=create(prelist); p.right=create(prelist); return p; public BinaryNode search(T key)/ 输入叶子结点。 return search(root,key); public BinaryNode search(BinaryNode p,T key) if(p=null|key=null)
9、return null; if(p.data.equals(key) return p; BinaryNode find=search(p.left,key); if(find=null) find=search(p.right,key); return find; public BinaryNode insertChild(BinaryNode p,T x) 5 if(p=null|x=null) return null; if(p.left=null) p.left=new BinaryNode(x,null,null); return p.left; else p.right=new B
10、inaryNode(x,null,null); return p; public int yecount()/ 求二叉树中叶子结点个数。 return yecount(root); public int yecount(BinaryNode p) if(p=null) return 0; if(p!=null&p.left=null&p.right=null) return 1; return yecount(p.left)+yecount(p.right); public BinaryNode JHjiedian()/ 将每个结点的左子树与右子树交换。 return JHjiedian(ro
11、ot); public BinaryNode JHjiedian(BinaryNode p) BinaryNode q=null; q=p.left; p.left=p.right; p.right=q; if(p.left!=null) JHjiedian(p.left); if(p.right!=null) JHjiedian(p.right); return p; public int twoyezi() / 验证二叉树的性质3：n0=n2+1。 return twoyezi(root); public int twoyezi(BinaryNode p) int i,j; if(p=nu
12、ll) return 0; else i=twoyezi(p.left); 6 j=twoyezi(p.right); if(p.left!=null&p.right!=null) return i+j+1; else return (i+j); public void DaJieDina(T value)/ 输出值大于k的结点。 System.out.print(大于+value+的结点有：); BinaryNode p = this.root; DaJieDina(p, value); System.out.println(); public void DaJieDina(BinaryNo
13、de p, T value) if (p != null) if (String) p.data).compareTo(String)value) 0) System.out.print(p.data.toString() + ); DaJieDina(p.left, value); DaJieDina(p.right, value); public BinaryTree(T prelist,T inlist)/ 已知先根和中根次序遍历序列构造二叉树。 this.root=create(prelist,inlist,0,0,prelist.length); private BinaryNode
14、 create(T prelist,T inlist,int preStart,int inStart,int n) if(n=0) return null; T elem=prelistpreStart; BinaryNode p=new BinaryNode(elem); int i=0; while(in&!elem.equals(inlistinStart+i) i+; p.left=create(prelist,inlist,preStart+1,inStart,i); p.right=create(prelist,inlist,preStart+i+1,inStart+i+1,n-
15、1-i); return p; public String toGenListString()/ 以广义表表示构造二叉树。 return 广义表表示为：+toGenListString(root)+n; public String toGenListString(BinaryNode p) if(p=null) 7 return null; String str=p.data.toString(); if(p.left!=null|p.right!=null) str+= (+toGenListString(p.left)+,+toGenListString(p.right)+); retur
16、n str; public boolean compareTree(BinaryNode root2)/ 判断两颗二叉树是否相等。 return compareNode(root,root2); public boolean compareNode(BinaryNode p,BinaryNode q) if(p=null&q=null) return true; else if(p=null|q=null) return false; else if(p.data!=q.data) return false; boolean cleft=compareNode(p.left,q.left);
17、boolean cright=compareNode(p.right,q.right); if(cleft&cright) return true; else return false; public int getLevel(T x)/ 求结点所在的层次。 return getLevel(root, 1, x); /令根结点的层次为1 private int getLevel(BinaryNode p, int i, T x)/在以p结点（层次为i）为根的子树中，求x结点所在的层次 if (p=null) /空树或查找不成功 return -1; if (p.data.equals(x) r
18、eturn i; /查找成功 int level = getLevel(p.left, i+1, x); /在左子树查找 if (level=-1) level = getLevel(p.right, i+1, x); /继续在右子树中查找 return level; 8 public BinaryNode FirstpostOrder()/ 求一颗二叉树在后根次序遍历下第一个访问的结点. BinaryNode p = this.root; while (true) while (p.left != null) p = p.left; if (p.right != null) p = p.ri
19、ght; continue; break; return p; public BinaryTree(BinaryTree bitree)/11 复制一颗二叉树。 this.root = copy(bitree.root); private BinaryNode copy(BinaryNode p) /复制以p根的子二叉树，返回新建子二叉树的根结点 if (p=null) return null; BinaryNode q = new BinaryNode(p.data); q.left = copy(p.left); /复制左子树，递归调用 q.right = copy(p.right); /
20、复制右子树，递归调用 return q; /返回建立子树的根结点 boolean isCompleteBinaryTree() / 12判断一颗二叉树是否为完全二叉树。 if (this.root=null) return true; LinkedQueueBinaryNode que = new LinkedQueueBinaryNode(); que.enqueue(root); /根结点入队 BinaryNode p=null; while (!que.isEmpty() p = que.dequeue(); /p指向出队结点 if (p.left!=null ) /p的非空孩子结点入队
21、 que.enqueue(p.left); if (p.right!=null) que.enqueue(p.right); else break; /发现空子树，须检测队列9 中是否都是叶子结点 else if (p.right!=null) return false; /p的左子树空而右子树不空，确定不是 else break; /p是叶子，须检测队列中是否都是叶子结点 while (!que.isEmpty() /检测队列中是否都是叶子结点 p = que.dequeue(); if (p.left!=null | p.right!=null) /发现非叶子，确定不是 return fa
22、lse; return true; public void postOrderTraverse() / 13实现二叉树后根次序遍历的非递归算法。 System.out.print(后根次序遍历（非递归）： ); LinkedStackBinaryNode stack = new LinkedStackBinaryNode(); BinaryNode p=this.root, front=null; while (p!=null | !stack.isEmpty() /p非空或栈非空时 if (p!=null) stack.push(p); /p结点入栈 p=p.left; /进入左子树 els
23、e /p为空且栈非空时 p=stack.get(); /从左子树返回p结点，p结点不出栈 if (p.right!=null & p.right!=front) /p有右孩子，且右孩子没被访问过 p = p.right; /进入右子树 stack.push(p); p=p.left; /向左走 else 10 p=stack.pop(); /从右子树返回p结点，p结点出栈 System.out.print(p.data+ ); front = p; /front是p在后根遍历次序下的前驱结点 p=null; System.out.println(); BinaryNode类 package 实
24、验4; public class BinaryNode public T data; public BinaryNode left,right; public BinaryNode(T data,BinaryNode left,BinaryNode right) this.data=data; this.left=left; this.right=right; public BinaryNode(T data) this(data,null,null); public BinaryNode() this(null,null,null); LinkedStack类 package 实验4; pu
25、blic class LinkedStack private Node top; public LinkedStack() this.top=null; public boolean isEmpty() return this.top=null; public void push(T x) if(x!=null) this.top=new Node(x,this.top); public T pop() 11 if(this.top=null) return null; T temp=this.top.data; this.top=this.top.next; return temp; pub
26、lic T get() return this.top=null? null:this.top.data; LinkedQueue类 package 实验4; public class LinkedQueue private Node front,rear; public LinkedQueue() this.front=this.rear=null; public boolean isEmpty() return this.front=null&this.rear=null; public void enqueue(T x) if(x=null) return; Node q=new Nod
27、e(x,null); if(this.front=null) this.front=q; else this.rear.next=q; this.rear=q; public T dequeue() if(isEmpty() return null; T temp=this.front.data; this.front=this.front.next; if(this.front=null) this.rear=null; return temp; Node类 package 实验4; public class Node public T data; 12 public Node next; public Node(T data,Node next) this.data=data; this.next=next; public Node(T Data) this(Data,null); public Node() this(null,null); 验证代码 package 实验4; public class yanZheng public static void main(String args) String prelist=A,B,D,M,E,C,F,Z,H,I; String inlist=M,D,B,E,A,Z,F,C,H,I; B
