The goal of this assignment is to complete #8 from the textbook Write a function

Question

The goal of this assignment is to complete #8 from the textbook

Write a function that takes a binary search tree as input and produces a linked list of the entries, with the entries sorted (smallest entries at the front of the list and largest entries at the back). Hint: use in-order traversal. Use the following bst values along with the included header and template file for your assingment.

bintree.h & bintree.template can be found here : https://www.cs.colorado.edu/~main/chapter10/

Explanation / Answer

Hi,

As you mentioned the traversal will be inorder so that we get the sorted linked list.

The function goes as follows:

package main.com.app.logic;

// bst to dll will generate a sorted dll public */
public class TreeToDoublyLinkedList {
   public static void main(String args[]){
       TreeNode t = new TreeNode(5);
       TreeNode t3 = new TreeNode(3);
       TreeNode t1 = new TreeNode(1);
       TreeNode t7 = new TreeNode(7);
       TreeNode t9 = new TreeNode(9);
       TreeNode t8 = new TreeNode(8);
       t.setLeft(t3);
       t3.setLeft(t1);
       t.setRight(t7);
       t7.setRight(t9);
       t9.setLeft(t8);
       DoublyLinkedListnode dll = convert(t);
       dll.print();
   }
   static class DoublyLinkedListnode{
       int data;
       DoublyLinkedListnode next;
       DoublyLinkedListnode prev;

       public DoublyLinkedListnode(int data) {
           this.data = data;
       }
       public DoublyLinkedListnode() {
       }
       public int getData() {
           return data;
       }
       public DoublyLinkedListnode getPrev() {
           return prev;
       }
       public void setPrev(DoublyLinkedListnode prev) {
           this.prev = prev;
       }

       public void setData(int data) {
           this.data = data;
       }
       public DoublyLinkedListnode getNext() {
           return next;
       }
       public void setNext(DoublyLinkedListnode next) {
           this.next = next;
       }
       public void print(){
           DoublyLinkedListnode t = this;
           while(t!=null){
               System.out.print(t.getData()+"->");
               t = t.getNext();
           }
       }
   }
   static class TreeNode{
       int data;
       TreeNode left;
       TreeNode right;

       public TreeNode(int data) {
           this.data = data;
       }

       public int getData() {
           return data;
       }

       public void setData(int data) {
           this.data = data;
       }

       public TreeNode getLeft() {
           return left;
       }

       public TreeNode setLeft(TreeNode left) {
           this.left = left;
           return this;
       }

       public TreeNode getRight() {
           return right;
       }

       public TreeNode setRight(TreeNode right) {
           this.right = right;
           return this;
       }
   }

   private static DoublyLinkedListnode convert(TreeNode t){
       DoublyLinkedListnode d =convert(t,new PreviousDoublyLinkedListNode());
       while(d.prev!=null){
           d = d.prev;
       }
       return d;
   }
   private static DoublyLinkedListnode convert(TreeNode t, PreviousDoublyLinkedListNode d){
       if(t==null) return null;
       convert(t.getLeft(),d);
       DoublyLinkedListnode dn = new DoublyLinkedListnode(t.getData());
       if(d.val!=null){
           d.val.setNext(dn);
       }
       dn.setPrev(d.val);
       d.val = dn;
       convert(t.getRight(),d);
       return dn; // this node will be in the middle of the dll.
   }
   static class PreviousDoublyLinkedListNode{
       DoublyLinkedListnode val;
   }
}

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.