递归不导航所有子节点

Question

我需要浏览我的 23Tree 并打印所有级别和相应的元素。但是，我的递归在任何一个方向上进行，并且不会 return 并执行其他调用。任何帮助将非常感激。

这是我的节点class:

class Node<T extends Comparable<T>> {
    List<T> vals = new ArrayList<T>();
    List<Node<T>> children = new ArrayList<Node<T>>();

    boolean isLeaf() { return children.size() == 0; }
    boolean is4Node() { return vals.size() == 3; }

    // new Nodes always are 2-nodes (1 value).  The node may be
    // a leaf, or has 2 children.
    Node(T x) {
        vals.add(x);
    }

    Node(T x, Node<T> left, Node<T> right) {
        vals.add(x);
        children.add(left);
        children.add(right);
        children.add(null); // hack
    }

这是我打印节点的递归函数：

private boolean iterateChildrenAndPrintPerLevelAndLevelType(int level, String levelType,  Node root){
    System.out.println("present element: " + root);
    if(root.vals.size() == 1 ){
        System.out.println("Level = " + level + " [" + levelType + "] value = " + root.vals.get(0));
    }else if(root.vals.size() == 2 ){
        System.out.println("Level = " + level + " [" + levelType + "] value = " + root.vals.get(0) + "/" + root.vals.get(1));
    }

    if(root.children.get(0) != null){
        iterateChildrenAndPrintPerLevelAndLevelType(level+1, "left", (Node) root.children.get(0));
    }
    if(root.children.get(1) != null){
        iterateChildrenAndPrintPerLevelAndLevelType(level+1, "middle", (Node) root.children.get(1));
    }
    if(root.children.get(2) != null){
        iterateChildrenAndPrintPerLevelAndLevelType(level+1, "right", (Node) root.children.get(2));
    }
    return true;
}

这是输出：

present element: [[[a]b[c]]d, [[e]f[g]]h[[i]j, [k]y[z]]]
Level = 0 [root] value = d/h
present element: [[a]b[c]]
Level = 1 [left] value = b
present element: [a]
Level = 2 [left] value = a

（编辑）这是我的主要方法：

public static void main(String[] args) {
    StringTwoThreeTree set = new StringTwoThreeTree();
    try{
        String line = null;
        FileReader fileReader =
                new FileReader("C:\Users\Redoubt\IdeaProjects\23Tree\src\resources\test.dat");
                // new FileReader("C:\Users\Redoubt\IdeaProjects\23Tree\src\resources\a4q1search.txt");

        // Always wrap FileReader in BufferedReader.
        BufferedReader bufferedReader =
                new BufferedReader(fileReader);

        while((line = bufferedReader.readLine()) != null) {
            set.insert(line);
        }
        // System.out.println("\n\n\n");
        String str = set.toString();
        // System.out.println(str);
        set.print();
    }catch (Exception e){

    }
}

和文件内容 test.dat :

a
a
b
c
d
e
f
g
h
i
j
k
y
z

为清楚起见，我还添加了 2 个大 classes：
StringTwoThree class:

import java.util.List;

public class StringTwoThreeTree extends TwoThreeTree<String> {

@Override
public String toString() {
    return super.toString();
}

public void insert(String str){
    super.add(str);
}

public void print(){
    Node root = super.root;
    // System.out.println(root.vals);
    // dumpList("",root);
    iterateChildrenAndPrintPerLevelAndLevelType(0, "root", root);


    super.displayLevelWise();
}

private void dumpList(String string, Node list) {
    int i = 0;
    for (Object item : list.children) {
        if (item instanceof List) {
            dumpList(string + i, (Node) item);
        } else {
            System.out.println(String.format("%s%d %s", string, i, item));
        }
        ++i;
    }
}

private boolean iterateChildrenAndPrintPerLevelAndLevelType(int level, String levelType,  Node root){
    System.out.println("present element: " + root);
    if(root.vals.size() == 1 ){
        System.out.println("Level = " + level + " [" + levelType + "] value = " + root.vals.get(0));
    }else if(root.vals.size() == 2 ){
        System.out.println("Level = " + level + " [" + levelType + "] value = " + root.vals.get(0) + "/" + root.vals.get(1));
    }

    if(root.children.get(0) != null){
        iterateChildrenAndPrintPerLevelAndLevelType(level+1, "left", (Node) root.children.get(0));
    }
    if(root.children.get(1) != null){
        iterateChildrenAndPrintPerLevelAndLevelType(level+1, "middle", (Node) root.children.get(1));
    }
    if(root.children.get(2) != null){
        iterateChildrenAndPrintPerLevelAndLevelType(level+1, "right", (Node) root.children.get(2));
    }
    return true;
}

}

TwoThreeTree class:

import java.util.List;
import java.util.ArrayList;
import java.util.Iterator;
import java.util.Queue;

public class TwoThreeTree<T extends Comparable<T>> implements Iterable<T> {

// a Node has 1 (2-Node) or 2 (3-Node) values
// and 2 or 3 children.  Values and children are stored
// in ArrayLists.  If there are children, that ArrayList
// has a null element at the end, so as to make easier the
// method which adds a new child.
class Node<T extends Comparable<T>> {
    List<T> vals = new ArrayList<T>();
    List<Node<T>> children = new ArrayList<Node<T>>();

    boolean isLeaf() { return children.size() == 0; }
    boolean is4Node() { return vals.size() == 3; }

    // new Nodes always are 2-nodes (1 value).  The node may be
    // a leaf, or has 2 children.
    Node(T x) {
        vals.add(x);
    }

    Node(T x, Node<T> left, Node<T> right) {
        vals.add(x);
        children.add(left);
        children.add(right);
        children.add(null); // hack
    }

    public String toString() {
        String answer = "[";
        for (int i=0; i<vals.size(); i++) {
            if (i != 0) answer += ", ";
            if (children.size() != 0)
                answer += children.get(i).toString();
            answer += vals.get(i);
        }
        if (children.size() != 0)
            answer += children.get(children.size()-2).toString();
        return answer + "]";
    }

    // used in Iterator
    void getVals(List<T> iteratorList) {
        for (int i=0; i<vals.size(); i++) {
            if (children.size() != 0)
                children.get(i).getVals(iteratorList);
            iteratorList.add(vals.get(i));
        }
        if (children.size() != 0)
            children.get(children.size()-2).getVals(iteratorList);
    }

    // recursively adds a new value to a subtree
    boolean add(T val) {
        if (isLeaf())
            return addToLeaf(val);
        else return addToInterior(val);
    }

    // new values are always added to a leaf.  The result may be a 4-node leaf.
    boolean addToLeaf(T x) {
        int cmp;
        // size is 1 for a 2-node, or 2 for a 3-node
        for (int i = 0; i < vals.size(); i++) {
            cmp = x.compareTo(vals.get(i));
            if (cmp == 0) return false;
            else if (cmp < 0) {
                vals.add(i,x);
                return true;
            }
        }
        vals.add(x);
        return true;
    }

    // adds a value to a subtree rooted by an interior node.  If
    // the addition results in one of the children being a 4-node,
    // then adjustments are made.
    boolean addToInterior(T x) {
        int cmp;
        // size is 1 for a 2-node, or 2 for a 3-node
        for (int i = 0; i <= vals.size(); i++) {
            if (i == vals.size()) cmp = -1; // hack because there is no vals[2]
            else cmp = x.compareTo(vals.get(i));
            if (cmp == 0) return false;
            else if (cmp < 0) {
                boolean retVal = children.get(i).add(x);
                if (children.get(i).is4Node())
                    childIs4Node(i);
                return retVal;
            }
        }
        return false;  // unreachable  -- just for compiler
    }

    // the ith child is a 4-node
    void childIs4Node(int i) {
        Node<T> the4Node = children.get(i);
        // move the middle value from the 4-node child up
        // to its parent
        if (i == 2)
            vals.add(children.get(i).vals.get(1));
        else vals.add(i, children.get(i).vals.get(1));
        Node<T> newChild1, newChild2;
        if (children.get(i).isLeaf()) {
            newChild1 = new Node<T>(children.get(i).vals.get(0));
            newChild2 = new Node<T>(children.get(i).vals.get(2));
        }
        else {
            newChild1 = new Node<T>(children.get(i).vals.get(0),
                    children.get(i).children.get(0),
                    children.get(i).children.get(1));
            newChild2 = new Node<T>(children.get(i).vals.get(2),
                    children.get(i).children.get(2),
                    children.get(i).children.get(3));
        }
        children.remove(the4Node);
        children.add(i, newChild2);
        children.add(i, newChild1);
    }
}

Node<T> root;

public TwoThreeTree() {
    root = null;
}

// TwoThreeTree add
public boolean add(T val) {
    if (root == null) {
        root = new Node<T>(val);
        return true;
    }
    else {
        boolean isNew = root.add(val);
        // if root is a 4-node, split it
        if (root.vals.size() == 3) {
            Node<T> left, right;
            if (root.isLeaf()) {
                left = new Node<T>(root.vals.get(0));
                right = new Node<T>(root.vals.get(2));
            }
            else {
                left = new Node<T>(root.vals.get(0),
                        root.children.get(0),
                        root.children.get(1));
                right = new Node<T>(root.vals.get(2),
                        root.children.get(2),
                        root.children.get(3));
            }
            root = new Node<T>(root.vals.get(1), left, right);
        }
        return isNew;
    }
}

// this method creates a list containing all of the values in
// the tree and returns that list's iterator
public Iterator<T> iterator() {
    List<T> vals = new ArrayList<T>();
    if (root != null) root.getVals(vals);
    return vals.iterator();
}

public String toString(){
    String result = "[";
    for (T item : this
         ) {
        result += item.toString() + ",";
    }
    result = result.substring(0,result.length()-1);
    result += "]";
    return result;
}

public void displayLevelWise(){

}

}

Answer 1

您的 private boolean iterateChildrenAndPrintPerLevelAndLevelType(int level, String levelType, Node root) 方法中的索引超出范围。

递归不导航所有子节点

recursion not navigating all child nodes

java

recursion

2-3-tree