java - 木とグラフの再帰に関するアドバイス

Question

高度なデータ構造で再帰を使用する例を教えてください。今日は試験があります。フィボナッチや階乗の例よりも難しいが、ハノイの塔の問題よりも簡単な例を希望します。再帰を使用してデータ構造を操作する方法についてのアドバイスをいただければ幸いです。

Answer 1

ツリーの再帰的な例:

void action(Node root){
    if(root.left!=null)action(root.left);
    if(root.right!=null)action(root.right);
    //current node action code here
}

より多くのコードを持ちますが、システムにとってよりスタックフレンドリーな反復関数があります。システムのサイズに応じて、それらのいくつかを選択してください。大規模な構造で動作するものを作成し、速度に依存する場合は、反復がはるかに優れています。

これらをチェックしてください：link1と反復アプローチ

より多くの出力ブランチがあることを除いて、グラフと同じです。これにより、反復アプローチが改善されます。

Answer 2

これらはBinaryTrees、リンクされた構造で実装された訪問の例です。

public static <E> void printInorder(LinkedBTree<E> t) throws EmptyTreeException{
    if(t != null && !t.isEmpty())
        printInorder((BTPosition<E>)(t.root()));
    System.out.print("\n");
}

private static <E> void printInorder(BTPosition<E> v){
    if(v.getLeft() != null) printInorder(v.getLeft());
    System.out.print(v.element()+" ");
    if(v.getRight() != null) printInorder(v.getRight());
}

public static <E> void printPreorder(LinkedBTree<E> t) throws EmptyTreeException{
    if(t != null && !t.isEmpty())
        printPreorder((BTPosition<E>)(t.root()));
    System.out.print("\n");
}

private static <E> void printPreorder(BTPosition<E> v){
    System.out.print(v.element()+" ");
    if(v.getLeft() != null) printPreorder(v.getLeft());
    if(v.getRight() != null) printPreorder(v.getRight());
}

public static <E> void printPostorder(LinkedBTree<E> t) throws EmptyTreeException{
    if(t != null && !t.isEmpty())
        printPostorder((BTPosition<E>)(t.root()));
    System.out.print("\n");
}

private static <E> void printPostorder(BTPosition<E> v){
    if(v.getLeft() != null) printPostorder(v.getLeft());
    if(v.getRight() != null) printPostorder(v.getRight());
    System.out.print(v.element()+" ");
}

Answer 3

深さ優先トラバーサル:

public void preOrder(Node<T> root)
{
     if (root != null)
     {
         System.out.println(root);
         preOrder(root.leftChild);
         preOrder(root.rightChild);
     }
}


public void inOrder(Node<T> root)
{
     if (root != null)
     {
         inOrder(root.leftChild);
         System.out.println(root);
         inOrder(root.rightChild);
     }
}


public void postOrder(Node<T> root)
{
     if (root != null)
     {
         postOrder(root.leftChild);
         postOrder(root.rightChild);
         System.out.println(root);
     }
}

バランスの取れた式を確認する簡単な方法を次に示します。

private String open  = "([<{";
private String close = ")]>}";

private boolean isOpen(char ch)
{
    return open.indexOf(ch) == -1 ? false : true;
}

private boolean isClosed(char ch)
{
    return close.indexOf(ch) == -1 ? false : true;
}

private boolean balanced(String sequence)
{
    if (sequence != null && sequence.length() > 0)
        return isBalanced(sequence, "");
    else 
        return true;
}

private boolean matches(char fromSeq, char fromStack)
{
    return open.indexOf(fromStack) == close.indexOf(fromSeq);
}


private boolean isBalanced(String seq, String stack)
{
    if (seq.length() == 0 )
    {
        return stack.length() == 0;
    }
    else
    {
        char first = seq.charAt(0);

        if (isOpen(first))
        {
            return isBalanced(seq.substring(1), first + stack);
        }
        else if (isClosed(first))
        {
            return stack.length() != 0 && matches(first, stack.charAt(0)) && isBalanced(seq.substring(1), stack.substring(1));
        }
        else
        {
            return isBalanced(seq.substring(1), stack);
        }
    }

以下は、あるドメインのすべての順列を取得する簡単な方法です。つまり、次のように呼び出し
permute(3,"01", "");ます。

000 001 010 011 100 101 110 111

public void permute(int length, String domain, String result)
    {
        if (length == 0)
        {
            System.out.println(result);
        }
        else
        {
            for (int i = 0; i < domain.length(); i++)
                permute(length-1, domain, result + domain.charAt(i));
        }
    }

Finally, a simple python example for computing base^exp (while it's in python, it should be easy to understand):

def powrec(base, exp):
    if exp < 0 and base != 0:
        return powrec(1.0/base, -exp)

    if exp == 0:
        return 1

    if exp == 1:
        return base

    if exp % 2 == 0:
        return powrec(base*base, exp/2)

    else:
        return base*powrec(base*base, exp/2)