gpt4 book ai didi

java - 递归未导航所有子节点

转载 作者:太空宇宙 更新时间:2023-11-04 10:36:30 24 4
gpt4 key购买 nike

我需要导航我的 23Tree 并打印所有级别和相应的元素。但是,我的递归朝任何一个方向进行,并且不会返回并执行其他调用。任何帮助将非常感激。

这是我的节点类:

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 个大类:
StringTwoThree 类:

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 类:

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(){

}

}

最佳答案

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

关于java - 递归未导航所有子节点,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/49401238/

24 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com