数据结构java实验四Word下载.docx
《数据结构java实验四Word下载.docx》由会员分享，可在线阅读，更多相关《数据结构java实验四Word下载.docx（27页珍藏版）》请在冰点文库上搜索。
⑪复制一颗二叉树。
⑫判断一颗二叉树是否为完全二叉树。
⑬实现二叉树后根次序遍历的非递归算法。
（2）声明三叉链表表示的二叉树类，实现二叉树的基本操作以及以下操作。
①构造一颗三叉链表表示的二叉树。
②返回指定结点的父母结点。
③返回指定结点的所有祖先结点。
④返回两结点最近的共同祖先结点。
（3）在一颗中序线索二叉树中，实现以下操作。
①调用求结点的前驱结点算法，按中根次序遍历一颗中序线索二叉树。
②按后根次序遍历中序线索二叉树。
③在构造二叉树时进行线索化。
④插入、删除操作。
3、实验步骤与结果
（1）①审题：
在一棵二叉链表表示的二叉树中，实现以下操作，并说明采用哪种遍历算法，其他遍历算法是否可行。
2
⑦以广义表表示构造二叉树。
②编程：
这道小题需要用到几个类，分别是结点类Node,树结点类BinaryNode，顺序栈LinkedStack,顺序队列LinkedQueue，然后编写BinaryTree类，逐一实现以上功能。
验证类为yanzheng。
③验证结果：
图1
图2
图3
图4
图5
图6
图7
图8
图9
图10
图11
图12
图133
（2）①审题：
编写结点类TriNode，然后编写TriBinaryNode类实现二叉树的各个功能和方法。
验证类为yanzheng2.
图14
（3）①审题：
编写结点类ThreadNode，然后编写中性线索二叉树ThreadTreee逐一实现各个功能。
验证类为yanzheng3.③验证结果：
图15
图16
图17
4、源码
（1）BinaryTree类
package实验4；
publicclassBinaryTree<
T>
{publicBinaryNode<
root;
publicBinaryTree（）{this.root=null;
4
}publicvoidpreOrder（）{System.out.print（"
先根次序遍历二叉树：
"
）;
preOrder（root）;
System.out.println（）;
}
publicvoidpreOrder（BinaryNode<
p）{
if（p!
=null）{
System.out.print（p.data.toString（）+"
"
preOrder（p.left）;
preOrder（p.right）;
}}
publicBinaryTree（Tprelist[]）{
this.root=create（prelist）;
privateinti=0;
publicBinaryNode<
create（Tprelist[]）{BinaryNode<
p=null;
if（i<
prelist.length）{Telem=prelist[i];
i++;
if（elem!
=null）{p=newBinaryNode<
（elem）;
p.left=create（prelist）;
p.right=create（prelist）;
returnp;
search（Tkey）{//①输入叶子结点。
returnsearch（root,key）;
search（BinaryNode<
p,Tkey）{if（p==null||key==null）returnnull;
if（p.data.equals（key））returnp;
BinaryNode<
find=search（p.left,key）;
if（find==null）
find=search（p.right,key）;
returnfind;
insertChild（BinaryNode<
p,Tx）{
5
if（p==null||x==null）returnnull;
if（p.left==null）{
p.left=newBinaryNode<
（x,null,null）;
returnp.left;
elsep.right=newBinaryNode<
publicintyecount（）{//②求二叉树中叶子结点个数。
returnyecount（root）;
publicintyecount（BinaryNode<
p）{if（p==null）return0;
=null&
&
p.left==null&
p.right==null）return1;
returnyecount（p.left）+yecount（p.right）;
JHjiedian（）{//③将每个结点的左子树与右子树交换。
returnJHjiedian（root）;
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）;
publicinttwoyezi（）{//④
验证二叉树的性质3：
returntwoyezi（root）;
publicinttwoyezi（BinaryNode<
p）{inti,j;
if（p==null）return0;
else{
i=twoyezi（p.left）;
6
j=twoyezi（p.right）;
p.right!
=null）returni+j+1;
else
return（i+j）;
}
publicvoidDaJieDina（Tvalue）{//⑤输出值大于k的结点。
System.out.print（"
大于"
+value+"
的结点有：
p=this.root;
DaJieDina（p,value）;
publicvoidDaJieDina（BinaryNode<
p,Tvalue）{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）;
publicBinaryTree（Tprelist[],Tinlist[]）{//⑥已知先根和中根次序遍
历序列构造二叉树。
this.root=create（prelist,inlist,0,0,prelist.length）;
private
BinaryNode<
create（Tprelist[],Tinlist[],int
preStart,int
inStart,intn）{
if（n<
=0）returnnull;
Telem=prelist[preStart];
p=newBinaryNode<
inti=0;
while（i<
n&
!
elem.equals（inlist[inStart+i]））i++;
p.left=create（prelist,inlist,preStart+1,inStart,i）;
p.right=create（prelist,inlist,preStart+i+1,inStart+i+1,n-1-i）;
publicStringtoGenListString（）{//⑦以广义表表示构造二叉树。
return"
广义表表示为：
+toGenListString（root）+"
\n"
;
publicStringtoGenListString（BinaryNode<
p）{if（p==null）7
returnnull;
Stringstr=p.data.toString（）;
=null||p.right!
=null）str+="
（"
+toGenListString（p.left）+"
"
+toGenListString（p.right）+"
）"
returnstr;
publicbooleancompareTree（BinaryNode<
root2）{//⑧判断两颗二叉树
是否相等。
returncompareNode（root,root2）;
publicbooleancompareNode（BinaryNode<
p,BinaryNode<
q）{if（p==null&
q==null）returntrue;
elseif（p==null||q==null）{returnfalse;
}else{
if（p.data!
=q.data）{returnfalse;
booleancleft=compareNode（p.left,q.left）;
booleancright=compareNode（p.right,q.right）;
if（cleft&
cright）{returntrue;
elsereturnfalse;
publicintgetLevel（Tx）{//⑨求结点所在的层次。
returngetLevel（root,1,x）;
//令根结点的层次为1}
privateintgetLevel（BinaryNode<
p,inti,Tx）{//在以p结点（层次为i）为根的子树中，求x结点所在的层次
if（p==null）//空树或查找不成功
return-1;
if（p.data.equals（x））
returni;
//查找成功
intlevel=getLevel（p.left,i+1,x）;
//在左子树查找
if（level==-1）
level=getLevel（p.right,i+1,x）;
//继续在右子树中查找
returnlevel;
}8
publicBinaryNode<
FirstpostOrder（）{//⑩求一颗二叉树在后根次序遍历下
第一个访问的结点.
while（true）{while（p.left!
=null）p=p.left;
if（p.right!
=null）
{p=p.right;
continue;
}break;
publicBinaryTree（BinaryTree<
bitree）{//11复制一颗二叉树。
this.root=copy（bitree.root）;
privateBinaryNode<
copy（BinaryNode<
p）{//复制以p根的子二叉树，
返回新建子二叉树的根结点
if（p==null）returnnull;
q=newBinaryNode<
（p.data）;
q.left=copy（p.left）;
//复制左子树，递归调用
q.right=copy（p.right）;
//复制右子树，递归调用
returnq;
//返回建立子树的根结点
booleanisCompleteBinaryTree（）{//12判断一颗二叉树是否为完全二叉
树。
if（this.root==null）returntrue;
LinkedQueue<
>
que=new
LinkedQueue<
（）;
que.enqueue（root）;
//根结点入队
while（!
que.isEmpty（））{
p=que.dequeue（）;
//p指向出队结点
if（p.left!
=null）//p的非空孩子结点入队
{
que.enqueue（p.left）;
if（p.right!
=null）que.enqueue（p.right）;
break;
//发现空子树，须检测队列
9
中是否都是叶子结点
}else
=null）
returnfalse;
//p的左子树空而右子树不空，确定不是
//p是叶子，须检测队列中
是否都是叶子结点
}while（!
que.isEmpty（））//检测队列中是否都是叶子结点
{p=que.dequeue（）;
=null||p.right!
=null）//发现非叶子，确定
不是
returntrue;
publicvoidpostOrderTraverse（）{//13实现二叉树后根次序遍历的非递归算法。
后根次序遍历（非递归）：
LinkedStack<
stack=newLinkedStack<
p=this.root,front=null;
while（p!
=null||!
stack.isEmpty（））//p非空或栈非
空时
if（p!
=null）{
stack.push（p）;
//p结点入栈
p=p.left;
//进入左子树
else//p为空且栈非空时
p=stack.get（）;
//从左子树返回p结点，p结点不出栈
=null&
p.right!
=front）//p有右孩子，
且右孩子没被访问过
//进入右子树
//向左走
}else10
{
p=stack.pop（）;
//从右子树返回p
结点，p结点出栈
System.out.print（p.data+"
front=p;
//front是p在后根遍历次序下的前驱结点
BinaryNode类
package实验4;
publicclassBinaryNode<
{publicTdata;
left,right;
publicBinaryNode（Tdata,BinaryNode<
left,BinaryNode<
right）{this.data=data;
this.left=left;
this.right=right;
publicBinaryNode（Tdata）{this（data,null,null）;
publicBinaryNode（）{this（null,null,null）;
LinkedStack类
publicclassLinkedStack<
{privateNode<
top;
publicLinkedStack（）{this.top=null;
publicbooleanisEmpty（）{returnthis.top==null;
publicvoidpush（Tx）{if（x!
=null）this.top=newNode（x,this.top）;
publicTpop（）{11
if（this.top==null）returnnull;
Ttemp=this.top.data;
this.top=this.top.next;
returntemp;
publicTget（）{returnthis.top==null?
null:
this.top.data;
LinkedQueue类
publicclassLinkedQueue<
front,rear;
publicLinkedQueue（）{this.front=this.rear=null;
publicbooleanisEmpty（）{returnthis.front==null&
this.rear==null;
publicvoidenqueue（Tx）{if（x==null）return;
Node<
q=newNode<
（x,null）;
if（this.front==null）this.front=q;
this.rear.next=q;
this.rear=q;
publicTdequeue（）{if（isEmpty（））returnnull;
Ttemp=this.front.data;
this.front=this.front.next;
if（this.front==null）this.rear=null;
Node类
publicclassNode<
{publicTdata;
12
publicNode<
next;
publicNode（Tdata,Node<
next）{this.data=data;
this.next=next;
publicNode（TData）{this（Data,null）;
publicNode（）{this（null,null）;
验证代码
publicclassyanZheng{publicstaticvoidmain（String[]args）{Stringprelist[]={"
A"
B"
D"
M"
E"
C"
F"
Z"
H"
I"
};
Stringinlist[]={"
B
升级会员 