数据结构与算法c++，使用类和对象采用成员函数完成算法

Question

以先序和中序构造二叉树，替换所有与pattern匹配的子树为bitree
使用栈的非递归算法，深拷贝
类和对象！
类和对象！
类和对象！

Answer 1

以中根和后根遍历序列构造二叉树，替换所有与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的序列

}