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", "");yield:

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));
        }
    }

最后，一个简单的python计算base ^exp的例子（虽然是python，但应该很容易理解）：

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)