I would like to share my own algorithm for converting a binary tree data structure to a sorted doubly linked list using recursion. I believe this is a very easy and efficient way to achieve the goal.
// Tree.java
public class Tree {
private static class Node {
int data;
Node left;
Node right;
/** Node constructor that adds the data
*
* @param newData is the data to be inserted
*/
Node (int newData) {
data = newData;
left = null;
right = null;
}
}
private Node root;
Tree () {
root = null;
}
/** insert a new data into the tree incapsulation method
*
* @param newData is the data to be inserted
*/
public void insert (int newData) {
root = insert(root, newData);
}
/** insert data actual implementation method
* in this version of binary tree, the data will be appended
* to the right tree if it is equal
*
* @param node is the current node
* @param newData is the data to be inserted
* @return the node in which newData is inserted
*/
private Node insert (Node node, int newData) {
if (node == null)
node = new Node (newData);
else if (newData < node.data)
node.left = insert (node.left, newData);
else // if (newData >= node.data)
node.right = insert (node.right, newData);
return node;
}
/** convert a binary tree data structure into a sorted
* doubly linked list structure
* this encapsulates the actual implementation and
* takes care of the last linking process
*
* the head of the doubly linked list will be saved in root
*/
public void convertTree() {
Node temp = root;
root = null;
temp = convertTree(temp);
// root holds the latest node
linkNodes (root, temp);
root = temp;
}
/** actual implementation method for the converting
* algorithm by recursion
* will link the current node and the previous node
*
* @param node is the current node
* @return the head of the doubly linked list
*/
private Node convertTree(Node node) {
if (node == null)
return null;
Node ret = convertTree(node.left);
if (root == null)
// this is the first node
ret = node;
else
// root holds the previous node
linkNodes (root, node);
root = node;
convertTree(node.right);
return ret;
}
/** a simple helper method to link two nodes into a list
*
* @param a is the smaller list element
* @param b is the very next list element
*/
private void linkNodes (Node a, Node b) {
a.right = b;
b.left = a;
}
}
The basic idea is this: I will recursively enter into nodes in the increasing order. For each node, I will double-link its node and the previous node; the previous node is saved in the root field. After linking, the method will save its current node into the root field. This will take care of the doubly-linked list except for the first and the last nodes. For the last set of linking process, I make sure to work it out in the encapsulation function.
The reason I am saving the current (or previous) node in the root field is because Java does not have a static local variable within a method. I could, of course, create a new field for this purpose, but I did not want to do so just for this functionality. In order to use only the resources that are available to me, I decided to temporarily make use of the root field as a local static variable.
In order to determine whether I have reached the starting node (i.e., the node with the smallest data value), I check whether the root field is null, because root is set to null in the encapsulation method as an initialization. Once I reach the starting node, I set the root field to point to the current (or previous depending on the context) node.
This algorithm, I believe, is fairly fast because there is no waste of node assignment here in the linking process; that is, for every pair of nodes, there is only one set of linking assignments (i.e., 2) needed, so exactly 2N node assignments are required for a binary tree of size N.
No comments:
Post a Comment