I am having trouble implementing traversals in a tree.
The assignment explicitly states that the pre-order traversal must be done recursively.
In addition, the traversal method MUST also return a list without declaring any global variables.
The problem I am running into is that if I instantiate the list within my main method, I get a "cannot find symbol" error on my preorder_list variable. However, if I instantiate the list within the method, every time a recursive call is made the list will clear itself.
Are there any workarounds for this?
The code of Traversal and TreeNode classes.
Traverals:
import java.util.List;
import java.util.ArrayList;
import java.util.LinkedList;
/**
* Your implementation of the pre-order, in-order, and post-order
* traversals of a tree.
*/
public class Traversals<T extends Comparable<? super T>> {
/**
* DO NOT ADD ANY GLOBAL VARIABLES!
*/
/**
* Given the root of a binary search tree, generate a
* pre-order traversal of the tree. The original tree
* should not be modified in any way.
*
* This must be done recursively.
*
* Must be O(n).
*
* @param <T> Generic type.
* @param root The root of a BST.
* @return List containing the pre-order traversal of the tree.
*/
public List<T> preorder(TreeNode<T> root) {
if (root == null) {
return preorder_list;
}
else {
preorder_list.add(root);
preorder(root.getLeft());
preorder(root.getRight());
}
return preorder_list;
}
/**
* Given the root of a binary search tree, generate an
* in-order traversal of the tree. The original tree
* should not be modified in any way.
*
* This must be done recursively.
*
* Must be O(n).
*
* @param <T> Generic type.
* @param root The root of a BST.
* @return List containing the in-order traversal of the tree.
*/
//public List<T> inorder(TreeNode<T> root) {
// WRITE YOUR CODE HERE (DO NOT MODIFY METHOD HEADER)!
//}
/**
* Given the root of a binary search tree, generate a
* post-order traversal of the tree. The original tree
* should not be modified in any way.
*
* This must be done recursively.
*
* Must be O(n).
*
* @param <T> Generic type.
* @param root The root of a BST.
* @return List containing the post-order traversal of the tree.
*/
//public List<T> postorder(TreeNode<T> root) {
// WRITE YOUR CODE HERE (DO NOT MODIFY METHOD HEADER)!
//}
public static void main(String[] args) {
List<Integer> preorder_list = new ArrayList<Integer>();
Traversals tree = new Traversals();
TreeNode<Integer> root = new TreeNode(50);
TreeNode<Integer> a = new TreeNode(25);
TreeNode<Integer> b = new TreeNode(10);
TreeNode<Integer> c = new TreeNode(100);
TreeNode<Integer> d = new TreeNode(75);
TreeNode<Integer> e = new TreeNode(125);
TreeNode<Integer> f = new TreeNode(110);
root.setLeft(a);
a.setLeft(b);
root.setRight(c);
c.setLeft(d);
c.setRight(e);
e.setLeft(f);
}
}
TreeNode:
public class TreeNode<T extends Comparable<? super T>> {
private T data;
private TreeNode<T> left;
private TreeNode<T> right;
/**
* Constructs a TreeNode with the given data.
*
* @param data the data stored in the new node
*/
TreeNode(T data) {
this.data = data;
}
/**
* Gets the data.
*
* @return the data
*/
T getData() {
return data;
}
/**
* Gets the left child.
*
* @return the left child
*/
TreeNode<T> getLeft() {
return left;
}
/**
* Gets the right child.
*
* @return the right child
*/
TreeNode<T> getRight() {
return right;
}
/**
* Sets the data.
*
* @param data the new data
*/
void setData(T data) {
this.data = data;
}
/**
* Sets the left child.
*
* @param left the new left child
*/
void setLeft(TreeNode<T> left) {
this.left = left;
}
/**
* Sets the right child.
*
* @param right the new right child
*/
void setRight(TreeNode<T> right) {
this.right = right;
}
}
CodePudding user response：
There is no need to declare the list in main() or as a global variable. You can have the list instanciated inside the method. If root is null, you just return an empty list. If it's not you call preorder() recursively on the root, then the left sub-tree, and finally the right sub-tree, and add the results you get to the list.
public List<T> preorder(TreeNode<T> root) {
List<T> list = new ArrayList<>();
if (root != null) {
list.add(root.getData());
list.addAll(preorder(root.getLeft()));
list.addAll(preorder(root.getRight()));
}
return list;
}
Call:
List preorder_list = tree.preorder(root);
Ouput:
[50, 25, 10, 100, 75, 125, 110]
CodePudding user response：
You have to declare a list of nodes within the preorder() method, not within the main().
To achieve that, you can preorder() expect a list of nodes as one of the arguments.
In case if according to the requirements of your assignment method preorder() should take only one argument (a node), you can declare a helper method that expects two arguments: a node and a list that contains all discovered nodes.
Sidenote: don't omit generic type parameter in angle brackets (<Integer>) while instantiating Traversals and forget the diamond (<>) while creating new instances of nodes. Otherwise you'll get compiler warning because of the use of the row type usage.
That's how it might look like:
class Traversals<T extends Comparable<? super T>> {
public List<TreeNode<T>> preorder(TreeNode<T> root) {
return preorder(root, new ArrayList<>());
}
public List<TreeNode<T>> preorder(TreeNode<T> root, List<TreeNode<T>> nodes) {
if (root == null) {
return nodes;
}
nodes.add(root); // adding the current node
preorder(root.getLeft(), nodes); // exploring the left subtree
preorder(root.getRight(), nodes); // exploring the right subtree
return nodes;
}
public static void main(String[] args) {
Traversals<Integer> tree = new Traversals<>(); // don't omit generic parameter
TreeNode<Integer> root = new TreeNode<>(50);
TreeNode<Integer> a = new TreeNode<>(25);
TreeNode<Integer> b = new TreeNode<>(10);
TreeNode<Integer> c = new TreeNode<>(100);
TreeNode<Integer> d = new TreeNode<>(75);
TreeNode<Integer> e = new TreeNode<>(125);
TreeNode<Integer> f = new TreeNode<>(110);
root.setLeft(a);
a.setLeft(b);
root.setRight(c);
c.setLeft(d);
c.setRight(e);
e.setLeft(f);
List<TreeNode<Integer>> preorderNodes = tree.preorder(root);
for (TreeNode<Integer> node : preorderNodes) {
System.out.println(node);
}
}
public static class TreeNode<T extends Comparable<? super T>> {
// all TreeNode contents with no changes
@Override
public String toString() {
return "TreeNode{" "data=" data '}';
}
}
}
Output:
TreeNode{data=50}
TreeNode{data=25}
TreeNode{data=10}
TreeNode{data=100}
TreeNode{data=75}
TreeNode{data=125}
TreeNode{data=110}