2019-12-27 15:05

# JAVA数据结构 用栈替换所有与pattern匹配的子树为bitree

``````//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()//输出带空子树先跟序列
{
}
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
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的序列

}

}

``````
• 写回答
• 好问题 提建议
• 关注问题
• 收藏
• 邀请回答

#### 2条回答默认 最新

• zqbnqsdsmd 2019-12-28 01:07
已采纳
已采纳该答案
评论
解决 无用
打赏 举报
• asita666 2020-09-08 15:00

楼主问题解决了吗能否分享一下源码
这个感觉有错误 栈里面本来没有结点 如果第一个结点右子树匹配了 p=stack.pop(); 这个就不对了

评论
解决 无用
打赏 举报