一顾鸭
2019-12-27 15:05
采纳率: 100%
浏览 549
已采纳

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

问题:改了很多次,左边的树不匹配,但是右边的树匹配,怎么回到左节点看接下来的树是否匹配啊!问题应该在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的序列


    }

}

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

2条回答 默认 最新

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

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

    评论
    解决 无用
    打赏 举报

相关推荐 更多相似问题