如何使用递归遍历此二叉树？

Question

我很卡。我懂递归，但是这个项目让我迷路了。

基本上，这棵树需要

(a(b()())(c(d()())()))

并输出

a b 
a c d

也就是说，每个节点都可以有 0、1 或 2 个子节点。因此，如果节点包含 0 个子节点，我知道这意味着是时候递归采取行动 & return 到树的根并转到树的右侧（因为它首先读取左侧） . 总的来说，我只是很困惑。

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Scanner;


public class BinaryTreeFinal {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        String tree = scan.nextLine();//correct format : (a()())
        String[] t = splitTree(tree);
        System.out.println(Arrays.toString(t));
        //System.out.println(tree2("a", "(a(b()())(c(d()())()))"));
    }

    public static String[] splitTree(String tree)
    {
        //expected format
        //(node tree tree)
        //0 1 2-x x-(length-2) length-1
        if(tree.length() <= 2)//tree not long enough to process
            return new String[]{tree};

        String[] temp = new String[3];
        temp[0] = "" + tree.charAt(1);//grab tree node
        tree = tree.substring(2, tree.length()-1);//remove node and outer paren
        int parenCount = 0;//count of open paren
        int endTreeOne = 0;//end of first tree
        for(int i = 0; i < tree.length(); i++)
        {
            if(tree.charAt(i) == '(')
                parenCount++;
            if(tree.charAt(i) == ')')
                parenCount--;
            if(parenCount == 0)
            {
                endTreeOne = i;
                break;//ends for loop early
            }
        }
        temp[1] = tree.substring(0, endTreeOne+1);//left tree
        temp[2] = tree.substring(endTreeOne+1);//right tree
        return temp;
    }

这是代码变得混乱的地方：

public static char tree2(String root, String path)
{

    int counter = 0;
    String[] trees = splitTree(path);

    if(trees[1].charAt(counter) == '(' && trees[1].charAt(counter++) == ')')
    {
        counter++;
        //return trees[1].charAt(counter);
        return tree2(String, String);
        //System.out.println(trees[1].charAt(counter));


    }
    else 
        //System.out.println(trees[1].charAt(counter));
        return trees[1].charAt(counter);
    //counter++;


}

非常感谢，很抱歉让您感到困惑。我不太会说这个。

Answer 1

我用 Stacks 写的一些东西。

Input: `(a(b()())(c(d()())()))`

Output: a b 
        a c d 

Input: `(a(b()())(c(d()())(e)))`

Output: a b 
        a c d 
        a c e

如您所知，我尚未对此进行彻底测试。请运行再进行一些测试，看看它是否按要求工作。

让我用几句话说说我的思考过程。我看到 character 前面有 (。 a 或 parent 部分仅在存在更多 children 时才会打印。所以，我想，只要找到 )，我就会检查我的堆栈，看看顶部的元素是否是 (。如果是的话，太好了。如果没有，我会一直弹出，直到找到匹配的 parenthesis。完成后，我知道我必须转到控制台的下一行。然后，我需要跟踪堆栈中已有的字母表，以防它们需要作为新 child 的 parent 重印。所以，我做到了。当遇到新的 child 时，会打印 parent 并且一切看起来都是金色的。让我知道是否不是（测试失败）。

Stack<Character> stack = new Stack<Character>();
String st = "(a(b()())(c(d()())(e)))";
String parent = null;
for (int i = 0; i < st.length(); i++) {
    char c = st.charAt(i);

    if (c != ')') {

        // if it is an alphabet
        if (c != '(') {
            // will require printing of parents
            // iff there are more characters to print
            if (parent != null) {
                System.out.print(parent);
                parent = null;
            }
            System.out.print(c + " ");
        }
        stack.push(c);
    } else {
        // is the character on top a matching opening bracket?
        // if it is, then nothing to do, if not 
        char curTop = stack.pop();
        if (curTop != '(')
            while (curTop != '(')
                curTop = stack.pop();
        else
            continue;

        // done working with a character; move to next line
        System.out.println();

        // now, need to reprint the `a` portion 
        // iff more children are present
        Stack<Character> temp = new Stack<Character> ();
        while (!stack.isEmpty())
            temp.push(stack.pop());

        while (!temp.isEmpty()) {
            Character ch = temp.pop();
            if (!(ch == '(' || ch == ')')) {
                // store content
                if (parent == null)
                    parent = "";
                parent += ch + " ";
            }

            stack.push(ch);
        }

    }
}

如何使用递归遍历此二叉树？

How do I transverse this binary tree using recursion?

java

tree

recursion

binary-tree

nodes