问题：改了很多次，左边的树不匹配，但是右边的树匹配，怎么回到左节点看接下来的树是否匹配啊！问题应该在replaceALL方法里。
//10-24 以中根和后根遍历序列构造二叉树，替换所有与pattern匹配的子树为bitree。
public class BinaryTree<T>
{
public BinaryNode<T>root;
public BinaryTree()
{
this.root = null;
}
public boolean isEmpty() //判断是否是空
{
return this.root == null;
}
public String toString()//输出带空子树先跟序列
{
return toString(this.root);
}
public String toString(BinaryNode<T>p)
{
if(p==null)
return "^";
return p.data.toString()+""+toString(p.left)+toString(p.right);
}
public BinaryTree(T inlist[],T postlist[])
{
this.root=BinaryTreecreate(inlist,0,inlist.length-1,postlist,0,postlist.length-1);
}
//由后根遍历的次序可知，该二叉树的根是potlist[n-1]；改节点必定在中根次序中
//由中根遍历次序可知，Inlist[i]节点前段节点在根的左子树上，inlist[i]后的所有节点在根节点的右子树上
private BinaryNode<T> BinaryTreecreate(T[] inlist, int inbegin, int inend, T[] postlist, int postbegin, int postend)
{
if (postbegin < 0 || inbegin > inend) //递归结束条件
return null;
BinaryNode<T> p = new BinaryNode<T>(postlist[postend]);
int j = inbegin; //标记查找到的根结点的位置
while (j <= inend&&inlist[j] != postlist[postend]) { //遍历查找
j++;
}
p.left = BinaryTreecreate(inlist, inbegin, j - 1, postlist, postbegin, postbegin + j - inbegin - 1); //递归构造左子树
p.right = BinaryTreecreate(inlist, j + 1, inend, postlist, postbegin + j - inbegin, postend - 1); ////递归构造右子树
return p;
}
public BinaryTree(T[] prelist)//构造二叉树，prelist数组指定二叉树标明空子树的先根遍历序列
{
this.root=create(prelist);
}
//以从i开始的标明空子树的先根序列，创建一颗以prelist[i]为根的子树，返回根结点，递归方法
private int i=0;
private BinaryNode<T>create(T[] prelist)
{
BinaryNode<T>p=null;
if(i<prelist.length)
{
T elem=prelist[i];
i++;
if(elem!=null) //不能elem!="kong",因为T不一定是String
{
p=new BinaryNode<T>(elem); //创建叶子结点
p.left=create(prelist); //创建P的左子树，递归调用
p.right=create(prelist); //创建P的右子树，递归调用
}
}
return p;
}
//比较
public boolean equals(BinaryNode<T> p,BinaryNode<T> q)
{
return (p==null&&q==null)||(p!=null&&q!=null)&&(q.data.equals(p.data))&& equals(p.left,q.left)&&equals(p.right,q.right);
}
//对象复制
BinaryTree(BinaryTree<T> bitree) //实现BinaryTree<T>二叉树类声明的深拷贝构造方法
{
this.root = copy(bitree.root);
}
private BinaryNode<T> copy(BinaryNode<T> p) //方法实现
{
BinaryNode<T> q = null;
if (p != null) {
q = new BinaryNode<T>(p.data);
q.left = copy(p.left);
q.right = copy(p.right);
}
return q;
}
public void replaceAll(BinaryTree<T> pattern, BinaryTree<T> bitree)
{
if(equals(pattern))
this.root=this.copy(bitree.root);
else
** this.replaceall(this.root,pattern.root,bitree.root); ** //可不写
}
**_ public void replaceall(BinaryNode<T> p,BinaryNode<T> pattern,BinaryNode<T> bitree)
//parent指向this的结点；pattern指向pattern的结点；bitree指向bitree的结点；
{
//parent指向this的结点；p指向pattern的结点；m指向bitree的结点；
System.out.print("替换后："); //优先遍历的非递归算法 P154
LinkedStack<BinaryNode<T>>stack=new LinkedStack<BinaryNode<T>>();//创建的这个空栈为链式栈，使用单链表存储数据且实现栈接口 P91
while(p!=null||!stack.isEmpty())//P非空或栈非空时
{
if( p!= null&&pattern!=null)
{
if(this.equals(p.left, pattern))
{
// System.out.print(pattern);
p.left=this.copy(bitree);
// stack.push(p);
// p=p.left;
}
if(this.equals(p.right, pattern))
{
// System.out.print(pattern);
p.right=this.copy(bitree);
p=stack.pop();
// p=p.right;
}
else
{
// // System.out.print(p.data);
stack.push(p);
p=p.left;
}
}
//p==null&&!
if(stack.isEmpty()||p==null)
{
// // System.out.print("^");
// p=stack.pop(); // P指向出栈结点
if(stack.isEmpty())
** p=p.right; // 进入右子树**
else if (p==null) {
p = stack.pop();
p = p.right;
}
}
// System.out.print("");
//}
}
}**_
public static void main(String args[])
{
String[] parent={"A","B","D",null,"G",null,null,"D",null,"G",null,null,"C","E",null,null,"F","H",null,null,"D",null,"G"};
String[] inlist={"D","G","B","A","E","C","H","F"}; //中根次序
String[] postlist={"G","D","B","E","H","F","C","A"}; //后根次序
String[] pattern1={"D",null,"G"};
String[] bitree1={"M","D",null,"G"};
BinaryTree<String> values=new BinaryTree<String>(parent);
BinaryTree<String> pattern=new BinaryTree<String>(pattern1);
BinaryTree<String> bitree=new BinaryTree<String>(bitree1);
BinaryTree<String> tree=new BinaryTree<String>(inlist,postlist);
System.out.println("构造出来的二叉树以先根次序输出为："+tree);
System.out.println("替换前树values的序列： "+values); //输出替换前树values的序列
System.out.println("pattern序列： "+pattern);
System.out.println("bitree序列： "+bitree);
** values.replaceAll(pattern,bitree); //替换**
// System.out.print(values);
//System.out.println("替换后树values的序列： "+values); //输出替换后树values的序列
}
}
