## Saturday, June 7, 2014

### Threaded Binary Tree : Construction and Inorder Traversal [Java]

`Threaded Binary Trees: Instead of containing a null pointer in its right field, a node with an empty right subtree points to its inorder successor. Such a pointer is called a thread. Note that the rightmost node in each tree still has a null right pointer, since it has no inorder successor. Such trees are called right in--threaded binary trees. A threaded binary tree eliminates the need for a stack in a nonrecursive traversal even if a father field is not available.`

`To implement a right in-threaded binary tree under the dynamic node implementation of a binary tree, and extra logical field, rthread, is included within each node to indicate whether or not its right pointer is a thread. For consistency, the rthread field of the rightmost node of a tree (i.e. the last node in the tree's inorder traversal) is also set to true, although its right field remains null.`

`The inorder traversal of a binary tree gives its elements in ascending order. So if the user inputs (-999 is end marker for input):`

`1 2 5 2 3 4 6 7 4 5 7 7 -999`

`the output will be`

`1 2 2 3 4 4 5 5 6 7 7 7`

`which is in ascending order, as expected.`

`Important sections of the code are italicized. They should be understood carefully.`

```import java.util.Scanner;

class nodetype {

int info;
nodetype left;  /*reference to left son*/

nodetype right; /*reference to right son*/

rhtread is TRUE if right is
*/

}

static nodetype maketree(int x) {
nodetype p;

p = getnode();
p.info = x;
p.left = null;
p.right = null;
return p;
}

static nodetype getnode() {
return new nodetype();
}

static void setleft(nodetype p, int x) {
nodetype q;

if (p == null) {
System.out.println("Void insertion\n");
} else if (p.left != null) {
System.out.println("Invalid insertion\n");
} else {
q = getnode();
q.info = x;
p.left = q;
q.left = null;
/* The inorder successor of node(q) is node(p) */
q.right = p;
}/*end if*/

}/*end setleft*/

static void setright(nodetype p, int x) {
nodetype q, r;

if (p == null) {
System.out.println("Void insertion\n");
System.out.println("Invalid insertion\n");
} else {
q = getnode();
q.info = x;
/* save the inorder successor of node(p) */
r = p.right;
p.right = q;
q.left = null;
/*the inorder successor of node(q) is the previous suuccessor of node(p)*/
q.right = r;
} /* end else */

}     /* end setright */

static void intrav3(nodetype tree) {
nodetype p, q;
p = tree;
do {
q = null;
while (p != null) { /* Traverse left branch */

q = p;
p = p.left;
}/*end while*/

if (q != null) {
System.out.print(q.info + " ");
p = q.right;
while (q.rthread && p != null) {
System.out.print(p.info + " ");
q = p;
p = p.right;
}/* end while */

}/* end if */

} while (q != null);
}

public static void main(String[] args){
nodetype ptree;
nodetype p = null, q;
int number;

System.out.println("Binary Tree Traversal\n\n");
System.out.println("Enter numbers :");
Scanner scan = new Scanner(System.in);
number = scan.nextInt();

ptree = maketree(number);

while((number=scan.nextInt())!=-999){
p = q = ptree;
while(q!=null){
p=q;
if(number<p.info)
q = p.left;
else if(number>=p.info){
q = p.right;
}
setright(p, number);
break;
}
}
}

if (number<p.info)
setleft(p, number);
}

System.out.println("\nInorder traversal : ");
intrav3(ptree);
}
}```