package com.salpe; import java.util.logging.Logger; import org.junit.Test; public class BSTTest { private static final Logger s_logger = Logger.getLogger(BSTTest.class.getName()); @Test public void test() { // create test data BSTNode<Integer> node0 = new BSTNode<>(0, null, null); BSTNode<Integer> node2 = new BSTNode<>(2, null, null); BSTNode<Integer> node01 = new BSTNode<>(1, node0, node2); // create BST BST<Integer> bst = new BST<>(node01); // convert BST to doubly linked list; BSTNode<Integer> head = bst.toDoublyLinkedlIst(); while (head != null) { s_logger.info(" --> "+head.data.toString()); head = head.right; } } /** * Binary Tree Node model * * @param <T> */ static class BSTNode<T extends Comparable<T>> { T data; BSTNode<T> left; BSTNode<T> right; BSTNode(T data, BSTNode<T> left, BSTNode<T> right) { this.data = data; this.left = left; this.right = right; } @Override public String toString() { return "BSTNode [data=" + data + "]"; } } /** * Binary Tree Representation * * @param <T> */ static class BST<T extends Comparable<T>> { BSTNode<T> root; public BST(BSTNode<T> root) { this.root = root; } public BSTNode<T> toDoublyLinkedlIst() { BSTNode<T> tail = toDoublyLinkedlIst0(root); // get head of linked list ; BSTNode<T> head = tail; while (head.left != null) { head = head.left; } return head; } public BSTNode<T> toDoublyLinkedlIst0(BSTNode<T> node) { if (node.left == null && node.right == null) { return node; } BSTNode<T> nodeLeft = toDoublyLinkedlIst0(node.left); nodeLeft.right = node; BSTNode<T> nodeRight = toDoublyLinkedlIst0(node.right); nodeRight.left = node; // returns tail or right most element return nodeRight; } } }
Saturday, May 14, 2016
Convert binary tree in to doubly linked list (Java Code)
Subscribe to:
Post Comments (Atom)
No comments:
Post a Comment