データ構造の面接問題の1.2.1-二元の検索ツリーを並べ替えた双方向チェーン表

package questions;

/**
 * @title                 
 * @question          ，                   。           ，         。<br>
 *           .... 10<br>
 *           .... /\<br>
 *           ... 6 14<br>
 *           .. /\ /\<br>
 *           . 4 8 12 16<br>
 *                   4=6=8=10＝12=14=16
 * @author Sam
 *
 */
public class Ex1o2o1 {
	static BSTreeNode pHeader = null;//          
	static BSTreeNode pPrevios = null;//        

	/**
	 * 1.        ；<br>
	 * 2.         ，             ，                     ，  <br>
	 * 3.                        ，     ，          。
	 * 
	 * @param args
	 */
	public static void main(String[] args) {
		BSTreeNode tree = new BSTreeNode();
		tree.add(10);
		tree.add(6);
		tree.add(14);
		tree.add(4);
		tree.add(8);
		tree.add(12);
		tree.add(16);

		inOrderBSTree(tree);

		//   
		System.out.print("      ：");
		BSTreeNode node = pHeader;
		while (null != node) {
			System.out.print(String.format(" %d ", node.value));
			node = node.right;
		}
		System.out.println();
		System.out.print("      ：");
		node = pPrevios;
		while (null != node) {
			System.out.print(String.format(" %d ", node.value));
			node = node.left;
		}
	}

	/**
	 *     ，      
	 * 
	 * @param tree
	 */
	static void inOrderBSTree(BSTreeNode tree) {
		if (null == tree) {
			return;
		}
		if (null != tree.left) {
			inOrderBSTree(tree.left);
		}
		converToDoubleList(tree);
		if (null != tree.right) {
			inOrderBSTree(tree.right);
		}
	}

	/**
	 *     
	 * 
	 * @param tree
	 */
	static void converToDoubleList(BSTreeNode tree) {
		tree.left = pPrevios;//                    
		if (null == pPrevios) {//          ，         ，              
			pHeader = tree;
		} else {//
			pPrevios.right = tree;
		}
		pPrevios = tree;//              
	}

}

class BSTreeNode {
	int value;// value of node
	BSTreeNode left;// left child of node
	BSTreeNode right;// right child of node

	public void add(int intValue) {
		if (0 == value) {
			value = intValue;
		} else if (intValue < value) {
			if (null == left) {
				left = new BSTreeNode();
			}
			left.add(intValue);
		} else if (intValue > value) {
			if (null == right) {
				right = new BSTreeNode();
			}
			right.add(intValue);
		}
	}
}