class Node<E>{

    E data;
    Node<E> rchild;
    Node<E> lchild;
    
}

前序遍历: 根->左子树->右子树
中序遍历: 左子树->根->右子树
后序遍历; 左子树->右子树->根
层序遍历

package datastructure.tree;

import lombok.Getter;
import lombok.Setter;

import java.util.Queue;
import java.util.concurrent.LinkedBlockingDeque;

/**
 * 二叉树
 * 
 * <p>
 * 定义:二叉树是n(n>=0)个结点的有限集合，该集合或者为空集（称为空二叉树），或者由一个根结点和两棵互不相交的、分别称为根结点的左子树和右子树组成
 * </p>
 * <p>
 * 二叉树特点: 由二叉树定义以及图示分析得出二叉树有以下特点： 1）每个结点最多有两颗子树，所以二叉树中不存在度大于2的结点。
 * 2）左子树和右子树是有顺序的，次序不能任意颠倒。 3）即使树中某结点只有一棵子树，也要区分它是左子树还是右子树。
 * </p>
 * <p>
 * 二叉树性质: 1）在二叉树的第i层上最多有2i-1 个节点 。（i>=1） 2）二叉树中如果深度为k,那么最多有2k-1个节点。(k>=1）
 * 3）n0=n2+1 n0表示度数为0的节点数，n2表示度数为2的节点数。
 * 4）在完全二叉树中，具有n个节点的完全二叉树的深度为[log2n]+1，其中[log2n]是向下取整。 5）若对含 n
 * 个结点的完全二叉树从上到下且从左至右进行 1 至 n 的编号，则对完全二叉树中任意一个编号为 i 的结点有如下特性：
 * </p>
 * <p>
 * (1) 若 i=1，则该结点是二叉树的根，无双亲, 否则，编号为 [i/2] 的结点为其双亲结点; (2) 若 2i>n，则该结点无左孩子， 否则，编号为
 * 2i 的结点为其左孩子结点； (3) 若 2i+1>n，则该结点无右孩子结点， 否则，编号为2i+1 的结点为其右孩子结点。 。
 * </p>
 * 
 * @author liuyi27
 *
 */
@Setter
@Getter
public class BinaryTree {

	private Object data;
	private BinaryTree lchild, rchild;

	/**
	 * 前序遍历递归算法
	 * <p>
	 * 前序遍历通俗的说就是从二叉树的根结点出发，当第一次到达结点时就输出结点数据，按照先向左再向右的方向访问。
	 * </p>
	 */
	public void preOrderTraverse(BinaryTree tree) {
		if (tree == null) {
			return;
		}

		System.out.print(tree.getData());
		preOrderTraverse(tree.getLchild());
		preOrderTraverse(tree.getRchild());
	}

	/**
	 * 中序遍历递归算法
	 * <p>
	 * 中序遍历就是从二叉树的根结点出发，当第二次到达结点时就输出结点数据，按照先向左再向右的方向访问
	 * </p>
	 */
	public void inOrderTraverse(BinaryTree tree) {
		if (tree == null) {
			return;
		}

		inOrderTraverse(tree.getLchild());
		System.out.print(tree.getData());
		inOrderTraverse(tree.getRchild());
	}

	/**
	 * 后序遍历递归算法
	 * <p>
	 * 后序遍历就是从二叉树的根结点出发，当第三次到达结点时就输出结点数据，按照先向左再向右的方向访问
	 * </p>
	 */
	public void postOrderTraverse(BinaryTree tree) {
		if (tree == null) {
			return;
		}

		postOrderTraverse(tree.getLchild());
		postOrderTraverse(tree.getRchild());
		System.out.print(tree.getData());
	}

	/**
	 * 前序建立二叉树
	 */
	public static void preCreate() {

	}

	/**
	 * 层序遍历
	 * <p>
	 * 层次遍历就是按照树的层次自上而下的遍历二叉树
	 * </p>
	 * 
	 * @param node
	 * @param queue
	 */
	public void LayerOrder(BinaryTree node, Queue<BinaryTree> queue) {

		if (node != null && queue.isEmpty()) {
			// 将当前节点放入队列首指针所指位置
			queue.add(node);
			System.out.print(queue.poll().getData());
		} else {
			System.out.print(node.getData());
		}

		if (node.lchild != null) {
			queue.add(node.lchild);
		}

		if (node.rchild != null) {
			queue.add(node.rchild);
		}

		BinaryTree nextNode = queue.poll();
		if (nextNode != null) {
			this.LayerOrder(nextNode, queue);
		}

	}

	public static void main(String[] args) {

		BinaryTree biTree2L3L = new BinaryTree();
		biTree2L3L.setData("D");

		BinaryTree biTree2L = new BinaryTree();
		biTree2L.setData("B");
		biTree2L.setLchild(biTree2L3L);

		BinaryTree biTree2R = new BinaryTree();
		biTree2R.setData("C");

		BinaryTree biTree = new BinaryTree();
		biTree.setData("A");
		biTree.setLchild(biTree2L);
		biTree.setRchild(biTree2R);

		Queue<BinaryTree> queue = new LinkedBlockingDeque<BinaryTree>();
		biTree.LayerOrder(biTree, queue);
		System.out.println("");
		biTree.preOrderTraverse(biTree);
		System.out.println("");
		biTree.inOrderTraverse(biTree);
		System.out.println("");
		biTree.postOrderTraverse(biTree);


	}
}

//若是二叉搜索树,返回x和y的公共最低祖先LCA
 
node* LowestCommonAncestor1(node* root,node* x,node* y)
{
	if(!root || !x || !y) return NULL;
	if(x->value < root->value && y->value < root->value)
		return LowestCommonAncestor1(root->left,x,y);
	else if(x->value > root->value && y->value > root->value)
		return LowestCommonAncestor1(root->right,x,y);
	else 
		return root;
}
//若不是搜索二叉树,但是,每个结点都有父结点,空间换时间法,否则需要重重复复地扫描路径
node* LowestCommonAncestor2(node* x,node* y)
{
	stack<node*> st1,st2;
	while(x)
	{
		st1.push(x);
		x=x->p;
	}
	while(y)
	{
		st2.push(y);
		y=y->p;
	}
	node* pLCA=NULL;
	while(!st1.empty() && !st2.empty() && st1.top()==st2.top())
	{
		pLCA=st1.top();
		st1.pop();
		st2.pop();
	}	
	return pLCA;
}
//不用空间换时间法
int GetListLength(node* x)
{
	int Count=0;
	while(x)
	{
		++Count;
		x=x->p;
	}
	return Count;
}
int Myabs(int val)
{
	return val > 0 ? val : -val;
}
node* LowestCommonAncestor3(node* x,node* y)
{
	int LengthX=GetListLength(x);
	int LengthY=GetListLength(y);
	node* pLong=x,*pShort=y;
	if(LengthX < LengthY)
	{
		pLong=y;
		pShort=x;
	}
	for(int i=0;i<Myabs(LengthX-LengthY);++i)
		pLong=pLong->p;
	while( pLong && pShort && pLong !=pShort)
	{
		pLong=pLong->p;
		pShort=pShort->p;
	}
	if(pLong == pShort)
		return pLong;
	return NULL;
}
//既不是二叉搜索树,也不没有parent指针,只是一棵平凡的二叉树
bool GetNodePath(node* root, node* pNode, list<node*>& path);
node* LowestCommonAncestor4(node* root,node* x,node* y)
{
	list<node*> path1;
	list<node*> path2;
	GetNodePath(root,x,path1);
	GetNodePath(root,y,path2);
	node* pLCA=NULL;
	list<node*>::const_iterator it1=path1.begin();
	list<node*>::const_iterator it2=path2.begin();
	while(it1 != path1.end() && it2 != path2.end() && *it1 == * it2)
	{
		pLCA=*it1;
		++it1;
		++it2;
	}	
	return pLCA;

}

void FindPath(node* root,int expectedSum,vector<int>& Path,int currentSum);//先序遍历改装版
void FindPath(node* root,int expectedSum)
{
	int currentSum=0;
	vector<int> Path;
	FindPath(root,expectedSum,Path,currentSum);
}
void FindPath(node* root,int expectedSum,vector<int>& Path,int currentSum)//先序遍历改装版
{
	if(!root)
		return ;
	//访问根结点,同时将root->value加入辅助栈
	currentSum += root->value;
	Path.push_back(root->value);
	if(root->left==NULL && root->right ==NULL && currentSum == expectedSum)
	{
		for(vector<int>::size_type i=0; i < Path.size(); ++i)
			cout<<Path[i]<<' ';
		cout<<endl;
	}
	FindPath(root->left,expectedSum,Path,currentSum);
	FindPath(root->right,expectedSum,Path,currentSum);
	//递归栈中,此时返回时,会将父结点销毁,因为,局部函数生命周期已经到了.
	//所以辅助栈也需要和递归栈同步,将栈顶元素弹栈,同时当前路径减去栈顶元素
	Path.pop_back();
	currentSum-=root->value;
}