0

以前に尋ねられた場合は申し訳ありませんが、適切な答えが見つかりませんでした。再帰的な方法で書かれた二分探索木トラバーサルを非再帰的な方法に変換する際に大きな問題があります。親切に私を助けてください。これは、Java で再帰メソッドを使用するコードです。

//BinarySt クラス

public interface BinaryST {
public void insert(Integer nData);
public Integer remove(Integer nData);
public boolean isExist(Integer nData);

public String preOrder();
public String inOrder();
public String postOrder();

}

//BinaryTreeNode クラス

public class BinaryTreeNode {
Integer element;
BinaryTreeNode LChild;
BinaryTreeNode RChild;

BinaryTreeNode() {}
}

//BinarySearchTree は BinaryST クラスを実装します

public class BinarySearchTree implements BinaryST{
protected StringBuffer s;
protected BinaryTreeNode root;

public BinarySearchTree() {}        
public BinarySearchTree(Integer nData)
{
    root = new BinaryTreeNode();
    root.element = nData;
}

public void insert(Integer nData)
{
    if( root==null ) {
        root = new BinaryTreeNode();
        root.element = nData;
        return;
    }

    boolean flag=true;
    BinaryTreeNode c=root;

    while(flag) {
        if( nData>=c.element ) {
            if( c.RChild==null ) {
                c.RChild = new BinaryTreeNode();
                c.RChild.element = nData;
                flag = false;
            }
            c = c.RChild;
        } 
        else {
            if( c.LChild==null ) {
                c.LChild = new BinaryTreeNode();
                c.LChild.element = nData;
                flag = false;
            }
            c = c.LChild;
        }
    }
}

public Integer remove(Integer nData)
{
    return new Integer(5);
}

public boolean isExist(Integer nData)
{
    return true;
}

public String preOrder()
{
    if( root==null ) {
        return new String( "null" );
    }

    s = new StringBuffer("");
    prOrder( root );

    return new String(s);
}

public String inOrder()
{
    if( root==null ) {
        return new String( "null" );
    }

    s = new StringBuffer("");
    iOrder( root );

    return new String(s);
}

public String postOrder()
{
    if( root==null ) {
        return new String( "null" );
    }

    s = new StringBuffer("");
    poOrder( root );

    return new String(s);
}

private void prOrder(BinaryTreeNode t) {
    if( t!=null ) {
        s.append( t.element.toString() + " " );
        prOrder( t.LChild );
        prOrder( t.RChild );
    }
}

private void iOrder(BinaryTreeNode t) {
    if( t!=null ) {
        iOrder( t.LChild );
        s.append( t.element.toString() + " " );
        iOrder( t.RChild );
    }
}

private void poOrder(BinaryTreeNode t) {
    if( t!=null ) {
        poOrder( t.LChild );
        poOrder( t.RChild );
        s.append( t.element.toString() + " " );
    }
}
}

//ランナークラス

public class Runner {
public static void main(String[] args) {
    BinarySearchTree a = new BinarySearchTree();

    System.out.println( "Pre-Order : "+a.preOrder() );
    System.out.println( "In-Order  : "+a.inOrder() );
    System.out.println( "Post-Order: "+a.postOrder() );

    a.insert( (Integer) 100 );
    a.insert( (Integer) 50  );
    a.insert( (Integer) 150 );
    a.insert( (Integer) 25  );
    a.insert( (Integer) 75  );
    a.insert( (Integer) 125 );
    a.insert( (Integer) 175 );
    a.insert( (Integer) 60  );
    a.insert( (Integer) 160 );
    a.insert( (Integer) 200 );
    a.insert( (Integer) 155 );

    System.out.println( "Pre-Order : "+a.preOrder() );
    System.out.println( "In-Order  : "+a.inOrder() );
    System.out.println( "Post-Order: "+a.postOrder() );
}
}
4

2 に答える 2

0

これは予約注文用のコードです。これを使用して、postorder と inorder に変換します

private void prOrder(BinaryTreeNode t) {
        if( t!=null ) {
            Stack<BinaryTreeNode> rootStack=new Stack<BinaryTreeNode>();
            BinaryTreeNode current=t;

            do{     
                s.append( current.element.toString() + " " );
                if(current.RChild!=null)
                    rootStack.add(current.RChild);
                if(current.LChild!=null)
                    rootStack.add(current.LChild);

                if(rootStack.isEmpty())
                    current=null;
                else
                    current=rootStack.pop();

            }while(current!=null);  

        }
    }
于 2014-04-27T04:59:01.590 に答える