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）;
returnp;
}
publicStringtoGenListString（）{//⑦以广义表表示构造二叉树。
return"广义表表示为：
"+toGenListString（root）+"\n";
}
publicStringtoGenListString（BinaryNodep）{
if（p==null）
returnnull;
Stringstr=p.data.toString（）;
if（p.left!
=null||p.right!
=null）
str+="（"+toGenListString（p.left）+","+toGenListString（p.right）+"）";
returnstr;
}
publicbooleancompareTree（BinaryNoderoot2）{//⑧判断两颗二叉树是否相等。
returncompareNode（root,root2）;
}
publicbooleancompareNode（BinaryNodep,BinaryNodeq）{
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;
}
else
returnfalse;
}
}
publicintgetLevel（Tx）{//⑨求结点所在的层次。
returngetLevel（root,1,x）;//令根结点的层次为1
}
privateintgetLevel（BinaryNodep,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;
}
publicBinaryNodeFirstpostOrder（）{//⑩求一颗二叉树在后根次序遍历下第一个访问的结点.
BinaryNodep=this.root;
while（true）{
while（p.left!
=null）
p=p.left;
if（p.right!
=null）
{
p=p.right;
continue;
}
break;
}
returnp;
}
publicBinaryTree（BinaryTreebitree）{//11复制一颗二叉树。
this.root=copy（bitree.root）;
}
privateBinaryNodecopy（BinaryNodep）{//复制以p根的子二叉树，返回新建子二叉树的根结点
if（p==null）
returnnull;
BinaryNodeq=newBinaryNode（p.data）;
q.left=copy（p.left）;//复制左子树，递归调用
q.right=copy（p.right）;//复制右子树，递归调用
returnq;//返回建立子树的根结点
}
booleanisCompleteBinaryTree（）{//12判断一颗二叉树是否为完全二叉树。
if（this.root==null）
returntrue;
LinkedQueue>que=newLinkedQueue>（）;
que.enqueue（root）;//根结点入队
BinaryNodep=null;
while（!
que.isEmpty（））
{
p=que.dequeue（）;//p指向出队结点
if（p.left!
=null）//p的非空孩子结点入队
{
que.enqueue（p.left）;
if（p.right!
=null）
que.enqueue（p.right）;
elsebreak;//发现空子树，须检测队列中是否都是叶子结点
}
else
if（p.right!
=null）
returnfalse;//p的左子树空而右子树不空，确定不是
elsebreak;//p是叶子，须检测队列中是否都是叶子结点
}
while（!
que.isEmpty（））//检测队列中是否都是叶子结点
{
p=que.dequeue（）;
if（p.left!
=null||p.right!
=null）//发现非叶子，确定不是
returnfalse;
}
returntrue;
}
publicvoidpostOrderTraverse（）{//13实现二叉树后根次序遍历的非递归算法。
System.out.print（"后根次序遍历（非递归）：
"）;
LinkedStack>stack=newLinkedStack>（）;
BinaryNodep=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结点不出栈
if（p.right!
=null&&p.right!
=front）//p有右孩子，且右孩子没被访问过
{
p=p.right;//进入右子树
stack.push（p）;
p=p.left;//向左走
}
else
{
p=stack.pop（）;//从右子树返回p结点，p结点出栈
System.out.print（p.data+""）;
front=p;//front是p在后根遍历次序下的前驱结点
p=null;
}
}
System.out.println（）;
}
}
BinaryNode类
package实验4;
publicclassBinaryNode{
publicTdata;
publicBinaryNodeleft,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）;
}
}
LinkedStack类
package实验4;
publicclassLinkedStack{
privateNodetop;
publicLinkedStack（）{
this.top=null;
}
publicbooleanisEmpty（）{
returnthis.top==null;
}
publicvoidpush（Tx）{
if（x!
=null）
this.top=newNode（x,this.top）;
}
publicTpop（）{
if（this.top==null）
returnnull;
Ttemp=this.top.data;
this.top=this.top.next;
returntemp;
}
publicTget（）{
returnthis.top==null?
null:
this.top.data;
}
}
LinkedQueue类
package实验4;
publicclassLinkedQueue{
privateNodefront,rear;
publicLinkedQueue（）{
this.front=this.rear=null;
}
publicbooleanisEmpty（）{
returnthis.front==null&&this.rear==null;
}
publicvoidenqueue（Tx）{
if（x==null）
return;
Nodeq=newNode（x,null）;
if（this.front==null）
this.front=q;
else
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;
returntemp;
}
}
Node类
package实验4;
publicclassNode{
publicTdata;
publicNodenext;
publicNode（Tdata,Nodenext）{
this.data=data;
this.next=next;
}
publicNode（TData）{
this（Data,null）;
}
publicNode（）{
this（null,null）;
}
}
验证代码
package实验4;
public
升级会员 