以先序和中序构造二叉树，替换所有与pattern匹配的子树为bitree
使用栈的非递归算法，深拷贝
类和对象！
类和对象！
类和对象！
以中根和后根遍历序列构造二叉树，替换所有与pattern匹配的子树为bitree。
public class BinaryTree
{
public BinaryNoderoot;
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]后的所有节点在根节点的右子树上
public 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)
//p指向this的结点；pattern指向pattern的结点；bitree指向bitree的结点；q指向
{
//优先遍历的非递归算法 P154
LinkedStack<BinaryNode<T>>stack=new LinkedStack<BinaryNode<T>>();//创建的这个空栈为链式栈，使用单链表存储数据且实现栈接口 P91
BinaryNode<T> q=null; //q标记P的根结点
while(p!=null||!stack.isEmpty())//P非空或栈非空时
{
if( p!= null)
{
if(this.equals(p, pattern)) //以p为根结点的子树，以pattern为根结点的子树
{
if(p==q.left ) //如果p与p的根结点的左子树相等
{ q.left=this.copy(bitree);
p=null;} //p置空
else
{ q.right=this.copy(bitree);
p=null;}
}
else
{
stack.push(p);
q=p;
p=p.left;
}
}
else
{
p = stack.pop();
q=p;
p = p.right;
}
}
}
public static void main(String args[])
{
String[] parent={"A","D","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("构造出来的二叉树以先根次序输出为："+values.toString());
System.out.println("中根后根构造： "+tree.toString());
System.out.println("pattern序列： "+pattern.toString());
System.out.println("bitree序列： "+bitree.toString());
values.replaceAll(pattern,bitree); //替换
System.out.println("替换后树values的序列： "+values.toString()); //输出替换后树values的序列
}
可以参考下文
https://blog.csdn.net/Wannna/article/details/103199662