Question

In: Computer Science

(Java) Implement a RightThreadTree class as an extension of a BinarySearchTree A right-threaded tree is a...

(Java) Implement a RightThreadTree class as an extension of a BinarySearchTree

A right-threaded tree is a binary search tree in which each right link that would normally be null is a "thread" that links that node to its inorder successor. The thread enables nonrecursive algorithms to be written for search and inorder traversals that are more efficient than recursive ones. Implement a RightThreadTree class as an extension of a BinarySearchTree. You will also need an RTNode that extends the Node class to include a flag that indicates whether a node's right link is a real link or a thread.

Solutions

Expert Solution

```
/**
```

 *    Java Program to Implement Threaded Binary Tree

```
 **/
```
```
 
```
```
import java.util.Scanner;
```
```
 
```
```
/** Class TBSTNode **/
```
```
class TBSTNode
```
```
{
```
```
    int ele;
```
```
    TBSTNode left, right;
```
```
    boolean leftThread, rightThread;
```
```
 
```
```
    /** Constructor **/
```
```
    public TBSTNode(int ele)
```
```
    {
```

        this(ele, null, null, true, true);

```
    }
```
```
 
```
```
    /** Constructor **/
```

    public TBSTNode(boolean leftThread, boolean rightThread)

```
    {
```
```
        this.ele = Integer.MAX_VALUE;
```
```
        this.left = this;
```
```
        this.right = this;
```
```
        this.leftThread = leftThread;
```
```
        this.rightThread = rightThread;
```
```
    }
```
```
 
```
```
    /** Constructor **/
```

    public TBSTNode(int ele, TBSTNode left, TBSTNode right, boolean leftThread, boolean rightThread)

```
    {
```
```
        this.ele = ele;
```
```
        this.left = left;
```
```
        this.right = right;
```
```
        this.leftThread = leftThread;
```
```
        this.rightThread = rightThread;
```
```
    }
```
```
}
```
```
 
```
```
/** Class ThreadedBinarySearchTree **/
```
```
class ThreadedBinarySearchTree
```
```
{
```
```
    private TBSTNode root;
```
```
 
```
```
    /** Constructor **/
```
```
    public ThreadedBinarySearchTree () 
```
```
    {
```

        root = new TBSTNode(true, false);

```
    }
```
```
 
```
```
    /** Function to clear tree **/
```
```
    public void clear()
```
```
    {
```

        root = new TBSTNode(true, false);

```
    }
```
```
 
```

    /** Function to insert an element **/

```
    public void insert(int ele) 
```
```
    {
```

        TBSTNode ptr = findNode(root, ele);

```
 
```
```
        /** element already present **/
```
```
        if (ptr == null)
```
```
            return;         
```
```
 
```
```
        if (ptr.ele < ele) 
```
```
        { 
```

            TBSTNode nptr = new TBSTNode(ele, ptr, ptr.right, true, true);

```
            ptr.right = nptr;
```
```
            ptr.rightThread = false;
```
```
        }
```
```
        else
```
```
        {
```

            TBSTNode nptr = new TBSTNode(ele, ptr.left, ptr, true, true);

```
            ptr.left = nptr;
```
```
            ptr.leftThread = false;
```
```
        }
```
```
    }
```
```
 
```
```
    /** function to find node **/
```

    public TBSTNode findNode(TBSTNode r, int ele)

```
    {
```
```
        if (r.ele < ele)
```
```
        {
```
```
            if (r.rightThread)
```
```
                return r;
```

            return findNode(r.right, ele);

```
        }
```
```
        else if (r.ele > ele)
```
```
        {
```
```
            if (r.leftThread)
```
```
                return r;
```

            return findNode(r.left, ele);

```
        }
```
```
        else
```
```
            return null;        
```
```
    }
```
```
 
```

    /** Function to search for an element **/

```
    public boolean search(int ele) 
```
```
    {
```

        return findNode(root, ele) == null;

```
    }
```
```
 
```
```
    /** Function to print tree **/
```
```
    public void inOrder() 
```
```
    {
```
```
        TBSTNode temp = root;
```
```
        for (;;)
```
```
        {
```
```
            temp = insucc(temp);
```
```
            if (temp == root)
```
```
                break;
```

            System.out.print(temp.ele +" ");

```
        }
```
```
    } 
```
```
 
```

    /** Function to get inorder successor **/

    public TBSTNode insucc(TBSTNode tree)

```
    {
```
```
        TBSTNode temp;
```
```
        temp = tree.right;
```
```
        if (!tree.rightThread)
```
```
            while (!temp.leftThread)
```
```
                temp = temp.left;
```
```
        return temp;
```
```
    }
```
```
}
```
```
 
```

/** Class ThreadedBinarySearchTreeTest **/

public class ThreadedBinarySearchTreeTest

```
{
```

    public static void main(String[] args)

```
    {                 
```

        Scanner scan = new Scanner(System.in);

        /** Creating object of ThreadedBinarySearchTree **/

        ThreadedBinarySearchTree tbst = new ThreadedBinarySearchTree();

        System.out.println("Threaded Binary Search Tree Test\n");

```
        char ch;
```

        /**  Perform tree operations  **/

```
        do    
```
```
        {
```

            System.out.println("\nThreaded Binary Search Tree Operations\n");

            System.out.println("1. insert ");

            System.out.println("2. search");

            System.out.println("3. clear");

```
 
```

            int choice = scan.nextInt();

```
            switch (choice)
```
```
            {
```
```
            case 1 : 
```

                System.out.println("Enter integer element to insert");

                tbst.insert( scan.nextInt() );

                break;

```
            case 2 : 
```

                System.out.println("Enter integer element to search");

                System.out.println("Search result : "+ tbst.search( scan.nextInt() ));

```
                break;       
```
```
            case 3 : 
```

                System.out.println("\nTree Cleared\n");

```
                tbst.clear();
```
```
                break;           
```
```
            default : 
```

                System.out.println("Wrong Entry \n ");

```
                break;   
```
```
            }
```
```
            /**  Display tree  **/ 
```

            System.out.print("\nTree = ");

```
            tbst.inOrder();            
```
```
            System.out.println();
```
```
 
```

            System.out.println("\nDo you want to continue (Type y or n) \n");

            ch = scan.next().charAt(0);

        } while (ch == 'Y'|| ch == 'y');

```
    }
```
```
}
```

venereology answered 2 hours ago

Next > < Previous

Related Solutions

in JAVA: implement a class called tree (from scratch) please be simple so i can understand...

in JAVA: implement a class called tree (from scratch) please be simple so i can understand thanks! tree(root) node(value, leftchild,rightchild) method: insert(value)

Implement a Binary tree using an array using class.

In C++, Implement the heapafication operation. Do not re-implement the binary tree class. Simply create a...

In C++, Implement the heapafication operation. Do not re-implement the binary tree class. Simply create a funcntion that takes in a binary tree and heapafies it. Meaning it takes in a pointer to a binary tree and converts it into a heap. (You may choose max or min heap).

Use Java programming to implement the following: Implement the following methods in the UnorderedList class for...

Use Java programming to implement the following: Implement the following methods in the UnorderedList class for managing a singly linked list that cannot contain duplicates. Default constructor Create an empty list i.e., head is null. boolean insert(int data) Insert the given data into the end of the list. If the insertion is successful, the function returns true; otherwise, returns false. boolean delete(int data) Delete the node that contains the given data from the list. If the deletion is successful, the...

Lab 5: Binary Search Tree Implement operations for a Binary Search Tree class starting from the...

Lab 5: Binary Search Tree Implement operations for a Binary Search Tree class starting from the template provided under the PolyLearn assignment, using the class TreeNode that is also provided. You may (should) implement helper methods that make your code easier to write, read, and understand. You will also need to write test cases of your own as you develop the methods. You may use iterative and/or recursive functions in your implementation. The following starter files are available . •...

JAVA * create Q3 class to implement comparator for a TreeSet. The purpose of ...

JAVA * create Q3 class to implement comparator for a TreeSet. The purpose of * the comparator is to compare the alphabetic order of integers. With Q3, * the order of Integer elements will be sort according to the order of * digit Unicode. * For example, the value of {11,3,31,2} will return {11,2,3,31} * NOTE: You don't need to compare each digit one by one. Just compare them System.out.println("Q3...

Java the goal is to create a list class that uses an array to implement the...

Java the goal is to create a list class that uses an array to implement the interface below. I'm having trouble figuring out the remove(T element) and set(int index, T element). I haven't added any custom methods other than a simple expand method that doubles the size by 2. I would prefer it if you did not use any other custom methods. Please use Java Generics, Thank you. import java.util.*; /** * Interface for an Iterable, Indexed, Unsorted List ADT....

Implement a function to find a node in a binary search tree. Using the following class...

Implement a function to find a node in a binary search tree. Using the following class and function definition. If a node with a matching value is found, return a pointer to it. If no match is found, return nullptr. #include <iostream> class BTNode { public: int item; BTNode *left; BTNode *right; BTNode(int i, BTNode *l=nullptr, BTNode *r=nullptr):item(i),left(l),right(r){} }; BTNode *root = nullptr; BTNode *find(int item) { //implement code here return nullptr; } int main() { root = new...

Java program that uses binary tree and recursions to implement Tower of Hanoi game where there...

Java program that uses binary tree and recursions to implement Tower of Hanoi game where there can be any amount of disks and there are either 3,4, or 5 pegs to store the disks(# of pegs and disks is manually inputted by user), in Tower of Hanoi game, the object of the game is move all the pieces from the 1st peg to the right most peg or the opposite side. You can place disks on top of each other...

java. Consider a binary tree with integer values in its nodes, implement a method that returns...

java. Consider a binary tree with integer values in its nodes, implement a method that returns the sum of the values contained in all of the nodes of the binary tree with root n.Hint: use recursion.

Subjects