package com.elementary.algorithm.tree;

public class ThreadBinaryTreeOperator {

	//use pre order input character constructor a binary tree;
	public ThreadBinaryTree<Character> constructorBinaryTree(){
		index=0;
		ThreadBinaryTree<Character> root=null;
		root=constructor(root);
		preorderTraverse(root);
		return inorderTraverseThreading(root);
	}
	//use preorder traverse to validate the tree's structure;
	private void preorderTraverse(ThreadBinaryTree<Character> node){
		if(node!=null){
			visitNode(node);
			preorderTraverse(node.leftChild);
			preorderTraverse(node.rightChild);
		}
	}
	//construct the threading binary tree, complete the leaf node's thread;
	private ThreadBinaryTree<Character> pre;
	private ThreadBinaryTree<Character> inorderTraverseThreading(ThreadBinaryTree<Character> root){
		ThreadBinaryTree<Character> head=new ThreadBinaryTree<Character>();
		head.data='@';
		head.leftBranch=BranchType.LINE;
		head.leftChild=root;
		head.rightBranch=BranchType.THREAD;
		head.rightChild=head;
		pre=head;
		threading(root);
		head.rightChild=pre;
		return head;
	}
	private void threading(ThreadBinaryTree<Character> node){
		if(node!=null){
			threading(node.leftChild);
			if(node.leftChild==null){
				node.leftBranch=BranchType.THREAD;
				node.leftChild=pre;
			}
			if(pre.rightChild==null){
				pre.rightBranch=BranchType.THREAD;
				pre.rightChild=node;	
			}
			pre=node;
			threading(node.rightChild);
		}
	}
	private void visitNode(ThreadBinaryTree<Character> node){
		System.out.print(node.data);
	}
	private int index=0;
	private char getNodeData(int index){
		final char[] dataArray={'A','B','C','@','@','D','E','@','G','@','@','F','@','@','@'};
		char data=dataArray[index]; 
		return data;
	}
	//constructor ThreadBinaryTree basic branch;
	private ThreadBinaryTree<Character> constructor(ThreadBinaryTree<Character> node){
		char data=getNodeData(index++);
		if(data!='@'){
			node =new ThreadBinaryTree<Character>();
			node.data=data;
			ThreadBinaryTree<Character> child=constructor(node.leftChild);
			node.leftChild=child;
			if(child!=null){
				node.leftBranch=BranchType.LINE;
			}else{
				node.rightBranch=BranchType.THREAD;
			}
			child=constructor(node.rightChild);
			node.rightChild=child;
			if(child!=null){
				node.rightBranch=BranchType.LINE;
			}else{
				node.rightBranch=BranchType.THREAD;
			}
		}
		return node;
	}
	


	public static void main(String[] args) {
		ThreadBinaryTreeOperator operator=new ThreadBinaryTreeOperator(); 
		ThreadBinaryTree<Character> threadBinaryTreeRoot = operator.constructorBinaryTree();
		
	}
}

@@ -279,29 +279,106 @@
 ;%0A%09%09
-preorderTraverse(root
+System.out.println(%22call the preorder traverse:%22);%0A%09%09preorderTraverse(root);%0A%09%09System.out.println(
 );%0A%09
@@ -661,24 +661,521 @@
 ld);%0A%09%09%7D%0A%09%7D%0A
+%09private void threadTreeInorderTraverse(ThreadBinaryTree%3CCharacter%3E root)%7B%0A%09%09ThreadBinaryTree%3CCharacter%3E node=root.leftChild;%0A%09%09while(node!=root)%7B%0A%09%09%09while(node.leftBranch!=BranchType.THREAD)%7B%0A%09%09%09%09node=node.leftChild;%0A%09%09%09%7D%0A%09%09%09visitNode(node);%0A%09%09%09while(node.rightBranch==BranchType.THREAD && node.rightChild!=root)%7B//never forget compare node.rightChild with root element, otherwise you will get a never stop loop%0A%09%09%09%09node=node.rightChild;%0A%09%09%09%09visitNode(node);%0A%09%09%09%7D%0A%09%09%09node=node.rightChild;%0A%09%09%7D%0A%09%7D%0A
 %09//construct
@@ -1612,16 +1612,104 @@
 (root);%0A
+%09%09//threading  the last one%0A%09%09pre.rightBranch=BranchType.THREAD;%0A%09%09pre.rightChild=head;%0A
 %09%09head.r
@@ -3234,16 +3234,159 @@
 Tree();%0A
-
 %09%09
+System.out.println(%22call the threading inorder traverse:%22);%0A%09%09operator.threadTreeInorderTraverse(threadBinaryTreeRoot);%0A%09%09System.out.println();
 %0A%09%7D%0A%7D%0A

complete threaded binary tree inorder traverse.