Я пытаюсь изменить двоичное представление дерева поиска так, чтобы каждый узел содержал дополнительный атрибут parent. Мой код имеет BSTInterface, как указано.
Вот интерфейс, который я реализую:
package chapter7;
/**
*
* @author Guangming Xing, updated Uta Ziegler
*
* @param <K> the unique key use to store and find elements in the binary search tree
* @param <T> the elements stored in the binary search tree
*/
public interface BSTInterface<K,T> {
/**
* Inserts the element with the specified key in the tree if the binary search
* tree does not already contains an entry with the specified key
*
* @param key the unique identifier for the element
* @param element the element
* @throws IllegalArgumentException key or element is null.
*/
void insert(K key, T element);
/**
* Removes the element with the specified key from the binary search tree.
*
* @param the unique key of the element to be deleted
* @throws IllegalArgumentException key is null.
*/
T remove(K key);
/**
* Find the element with the specified key in the binary search tree and return it
*
* @param the unique key of the element to be deleted
* @throws IllegalArgumentException key is null.
*/
T find(K key);
/**
* Determine whether the specified key is in the binary search tree and return
* tru or false
*
* @param the unique key of the element to be looked for
* @throws IllegalArgumentException key is null.
*/
boolean contains (K key);
/**
* Returns the number of elements in the binary search tree.
*/
int size();
/**
* Computes the complete path from the root to the key in the BST.
* Returns the list of keys from root to the node(inclusive) that contains key.
* If the key is not in the BST, return null.
*
*/
List<K> accessPath(K key);
}
Вот мое решение до сих пор:
import java.util.*;
class BinarySearchTreeWithParent implements BSTInterface{
// BST node
static class Node {
int key;
Node left, right, parent;
};
static Node root;
// Utitlity function to create a new node
public static Node newNode(int data){
Node temp = new Node();
temp.key = data;
temp.left = null;
temp.right = null;
temp.parent=null;
return temp;
}
static Node insert(int key, Node root){
// Create a new Node containing
// the new element
Node newnode = newNode(key);
// Pointer to start traversing from root and
// traverses downward path to search
// where the new node to be inserted
Node x = root;
// Pointer y maintains the trailing
// pointer of x
Node y = null;
while (x != null) {
y = x;
if (key < x.key)
x = x.left;
else
x = x.right;
}
newnode.parent = y;
// If the root is null i.e the tree is empty
// The new node is the root node
if (y == null)
y = newnode;
// If the new key is less then the leaf node key
// Assign the new node to be its left child
else if (key < y.key)
y.left = newnode;
// else assign the new node its right child
else if (key > y.key)
y.right = newnode;
// Returns the pointer where the
// new node is inserted
return y;
}
// Helper function to find minimum value node in subtree rooted at curr
public static Node minimumKey(Node curr)
{
while(curr.left != null) {
curr = curr.left;
}
return curr;
}
// Function to delete node from a BST
public static Node deleteNode(Node root, int key)
{
// pointer to store parent node of current node
Node parent = null;
// start with root node
Node curr = root;
// search key in BST and set its parent pointer
while (curr != null && curr.data != key){
// update parent node as current node
parent = curr;
// if given key is less than the current node, go to left subtree
// else go to right subtree
if (key < curr.data) {
curr = curr.left;
}
else {
curr = curr.right;
}
}
// return if key is not found in the tree
if (curr == null) {
return root;
}
// Case 1: node to be deleted has no children i.e. it is a leaf node
if (curr.left == null && curr.right == null)
{
// if node to be deleted is not a root node, then set its
// parent left/right child to null
if (curr != root) {
if (parent.left == curr) {
parent.left = null;
} else {
parent.right = null;
}
}
// if tree has only root node, delete it and set root to null
else {
root = null;
}
}
// Case 2: node to be deleted has two children
else if (curr.left != null && curr.right != null)
{
// find its in-order successor node
Node successor = minimumKey(curr.right);
// store successor value
int val = successor.data;
// recursively delete the successor. Note that the successor
// will have at-most one child (right child)
deleteNode(root, successor.data);
// Copy the value of successor to current node
curr.data = val;
}
// node to be deleted has only one child
else
{
// find child node
Node child = (curr.left != null)? curr.left: curr.right;
// if node to be deleted is not a root node, then set its parent
// to its child
if (curr != root)
{
if (curr == parent.left) {
parent.left = child;
} else {
parent.right = child;
}
}
// if node to be deleted is root node, then set the root to child
else {
root = child;
}
}
return root;
}
// Iterative function to search in given BST
public static boolean contains(int key) {
// start with root node
Node curr = root;
// pointer to store parent node of current node
Node parent = null;
// traverse the tree and search for the key
while (curr != null && curr.data != key){
// update parent node as current node
parent = curr;
// if given key is less than the current node, go to left subtree
// else go to right subtree
if (key < curr.data) {
curr = curr.left;
} else {
curr = curr.right;
}
}
// if key is not present in the key
if (curr == null)
return false;
return true;
}
public static Node find(int key) {
// start with root node
Node curr = root;
// pointer to store parent node of current node
Node parent = null;
// traverse the tree and search for the key
while (curr != null && curr.data != key){
// update parent node as current node
parent = curr;
// if given key is less than the current node, go to left subtree
// else go to right subtree
if (key < curr.data) {
curr = curr.left;
} else {
curr = curr.right;
}
}
// if key is not present in the key
if (curr == null) {
return null;
}
if (parent == null)
return key;
return parent.data;
}
// return size of tree
public static int size(){
if (root == null)
return 0;
// Using level order Traversal.
Queue<Node> q = new LinkedList<Node>();
q.offer(root);
int count = 1;
while (!q.isEmpty())
{
Node tmp = q.poll();
// when the queue is empty:
// the poll() method returns null.
if (tmp != null){
if (tmp.left != null){
// Increment count
count++;
// Enqueue left child
q.offer(tmp.left);
}
if (tmp.right != null){
// Increment count
count++;
// Enqueue left child
q.offer(tmp.right);
}
}
}
return count;
}
// Pair class
class Pair<U, V>
{
public final U first; // first field of a Pair
public final V second; // second field of a Pair
// Constructs a new Pair with specified values
private Pair(U first, V second)
{
this.first = first;
this.second = second;
}
// Factory method for creating a Typed Pair immutable instance
public static <U, V> Pair <U, V> of(U a, V b)
{
// calls private constructor
return new Pair<>(a, b);
}
}
public static ArrayList<Integer> ListaccessPath(int key)
{
ArrayList<Integer> arr = new ArrayList<>();
// create an empty stack to store a pair of tree node and
// its path from the root node
Deque<Pair<Node, String>> stack = new ArrayDeque<>();
// push root node
stack.add(Pair.of(root, ""));
// loop till stack is not empty
while (!stack.isEmpty())
{
// we pop a node from the stack and push the data to output stack
Pair<Node, String> pair = stack.poll();
// fetch current node
Node curr = pair.first;
String path = pair.second;
// add current node to the existing path
String separator = (path.equals("")) ? "\n" : " -> ";
path += (separator + curr.data);
// if leaf node, print the path
if (curr.key == key) {
return arr;
}
// push left and right child of popped node to the stack
if (curr.right != null) {
stack.add(Pair.of(curr.right, path));
}
if (curr.left != null) {
stack.add(Pair.of(curr.left, path));
}
}
return arr;
}
}
Однако я получаю несколько ошибок относительно реализации интерфейса, не являющегося типом.
Вот мои ошибки:
BinarySearchTreeWithParent.java - Line 5: BSTInterface cannot be resolved to a type
BinarySearchTreeWithParent.java - Line 87: data cannot be resolved or is not a field
BinarySearchTreeWithParent.java - Line 93: data cannot be resolved or is not a field
BinarySearchTreeWithParent.java - Line 131: data cannot be resolved or is not a field
BinarySearchTreeWithParent.java - Line 135: data cannot be resolved or is not a field
BinarySearchTreeWithParent.java - Line 138: data cannot be resolved or is not a field
BinarySearchTreeWithParent.java - Line 177: data cannot be resolved or is not a field
BinarySearchTreeWithParent.java - Line 183: data cannot be resolved or is not a field
BinarySearchTreeWithParent.java - Line 206: data cannot be resolved or is not a field
BinarySearchTreeWithParent.java - Line 212: data cannot be resolved or is not a field
BinarySearchTreeWithParent.java - Line 225: Type mismatch: cannot convert from int to BinarySearchTreeWithParent.Node
BinarySearchTreeWithParent.java - Line 227: data cannot be resolved or is not a field
BinarySearchTreeWithParent.java - Line 283: The method of cannot be declared static; static methods can only be declared in a static or top level type
BinarySearchTreeWithParent.java - Line 313: data cannot be resolved or is not a field
BSTInterface.java - Line 59: List cannot be resolved to a type