1、二叉树定义     

计算机中数据结构的一种，计算机中数据结构的一种每个节点最多有两个子树的树结构。通常子树被称作“左子树”（left subtree）和“右子树”（right subtree）。二叉树常被用于实现二叉查找树和二叉堆。

完全二叉树：只有最下面的两层结点度能够小于2，并且最下面一层的结点都集中在该层最左边的若干位置的二叉树

满二叉树：除最后一层无任何子节点外，每一层上的所有结点都有两个子结点二叉树。

2、相关术语定义

树的结点：包含一个数据元素及若干指向子树的分支；孩子结点：结点的子树的根称为该结点的孩子；双亲结点：B 结点是A 结点的孩子，则A结点是B 结点的双亲；兄弟结点：同一双亲的孩子结点； 堂兄结点：同一层上结点；祖先结点: 从根到该结点的所经分支上的所有结点子孙结点：以某结点为根的子树中任一结点都称为该结点的子孙结点层：根结点的层定义为1；根的孩子为第二层结点，依此类推；树的深度：树中最大的结点层结点的度：结点子树的个数树的度： 树中最大的结点度。叶子结点：也叫终端结点，是度为 0 的结点；分枝结点：度不为0的结点；

3、二叉树性质

(1) 在非空二叉树中，第i层的结点总数不超过  , i>=1；(2) 深度为h的二叉树最多有  个结点(h>=1)，最少有h个结点；(3) 对于任意一棵二叉树，如果其叶结点数为N0，而度数为2的结点总数为N2，则N0=N2+1；(4) 具有n个结点的完全二叉树的深度为 (5)有N个结点的完全二叉树各结点如果用顺序方式存储，则结点之间有如下关系：若I为结点编号则 如果I>1，则其父结点的编号为I/2；如果2*I<=N，则其左儿子（即左子树的根结点）的编号为2*I；若2*I>N，则无左儿子；如果2*I+1<=N，则其右儿子的结点编号为2*I+1；若2*I+1>N，则无右儿子。(6)给定N个节点，能构成h(N)种不同的二叉树。h(N)为卡特兰数的第N项。h(n)=C(2*n，n)/(n+1)。(7)设有i个枝点，I为所有枝点的道路长度总和，J为叶的道路长度总和J=I+2i

4、三种遍历顺序

先序遍历首先访问根，再先序遍历左（右）子树，最后先序遍历右（左）子树中序遍历首先中序遍历左（右）子树，再访问根，最后中序遍历右（左）子树后序遍历首先后序遍历左（右）子树，再后序遍历右（左）子树，最后访问根

5、根据其中两种遍历方式重建二叉树，java代码实现

5.1 已知前序和中序遍历，用java重建二叉树

方法一

package com.jason.algorithm;import java.util.HashMap;public class Solution {	public static void main(String[] args) {		int PRe[] = { 1, 2, 4, 7, 3, 5, 6, 8 };		int in[] = { 4, 7, 2, 1, 5, 3, 8, 6 };		Solution solution = new Solution();		solution.reConstructBinaryTree(pre, in);	}	public TreeNode reConstructBinaryTree(int[] pre, int[] in) {		if (pre == null || in == null) {			return null;		}		HashMap<Integer, Integer> hashMap = new HashMap<Integer, Integer>();		for (int i = 0; i < in.length; i++) {			hashMap.put(in[i], i);		}		return preIn(pre, 0, pre.length - 1, in, 0, in.length - 1, hashMap);	}	// {1,2,4,7,3,5,6,8} pre 根左右	// {4,7,2,1,5,3,8,6} in 左根右	// {7,4,2,5,8,6,3,1} end	//       1	//     2    3	//   4    5    6	//    7      8	// 根据前序和中序还原二叉树	public TreeNode preIn(int[] p, int pi, int pj, int[] n, int ni, int nj,			HashMap<Integer, Integer> map) {		if (pi > pj) {			return null;		}		TreeNode head = new TreeNode(p[pi]);		int index = map.get(p[pi]);		// 根据前序遍历知道根节点，根据中序遍历知道根左边的为左子树，右边的为右子树		head.left = preIn(p, pi + 1, pi + index - ni, n, ni, index - 1, map);		head.right = preIn(p, pi + index - ni + 1, pj, n, index + 1, nj, map);		System.out				.println("head =" + (head != null ? head.val : " ")						+ " head.left ="						+ (head.left != null ? head.left.val : " ")						+ " head.right ="						+ (head.right != null ? head.right.val : " "));		return head;	}}
方法二
public class BinaryTree {	public static void main(String[] args) {		int inorder[] = { 4, 7, 2, 1, 5, 3, 8, 6 };		int preorder[] = { 1, 2, 4, 7, 3, 5, 6, 8 };		BinaryTree binaryTree = new BinaryTree();		// 利用前序和中序，创建二叉树		binaryTree.buildTree(preorder, inorder);	}	int pInorder;	int pPreorder;	public TreeNode buildTree(int[] preorder, int[] inorder, TreeNode node) {		if (pPreorder > 7) {			return null;		}		TreeNode head = new TreeNode(preorder[pPreorder++]);		if (inorder[pInorder] != head.val) {			head.right = buildTree(preorder, inorder, head);		}		pInorder++;		if (node == null || inorder[pInorder] != node.val) {			head.left = buildTree(preorder, inorder, node);		}		System.out				.println("head =" + (head != null ? head.val : " ")						+ " head.left ="						+ (head.left != null ? head.left.val : " ")						+ " head.right ="						+ (head.right != null ? head.right.val : " "));		return head;	}	public TreeNode buildTree(int[] preorder, int[] inorder) {		return buildTree(preorder, inorder, null);	}}
TreeNode.java
package com.jason.algorithm; public class TreeNode {      int val;      TreeNode left;      TreeNode right;      TreeNode(int x) { val = x; }  }
5.2 已知后序和中序遍，用java重建二叉树
public class BinaryTree {	public static void main(String[] args) {		int inorder[] = { 4, 7, 2, 1, 5, 3, 8, 6 };		int postorder[] = { 7, 4, 2, 5, 8, 6, 3, 1 };		BinaryTree binaryTree = new BinaryTree();		// 利用后序和中序，创建二叉树		binaryTree.buildTree(inorder, postorder);	}	int pInorder;	int pPostorder;	public TreeNode buildTree(int[] inorder, int[] postorder, TreeNode node) {		if (pPostorder < 0) {			return null;		}		TreeNode head = new TreeNode(postorder[pPostorder--]);		if (inorder[pInorder] != head.val) {			head.right = buildTree(inorder, postorder, head);		}		pInorder--;		if (node == null || inorder[pInorder] != node.val) {			head.left = buildTree(inorder, postorder, node);		}		System.out				.println("head =" + (head != null ? head.val : " ")						+ " head.left ="						+ (head.left != null ? head.left.val : " ")						+ " head.right ="						+ (head.right != null ? head.right.val : " "));		return head;	}	public TreeNode buildTree(int[] inorder, int[] postorder) {		pInorder = inorder.length - 1;		pPostorder = postorder.length - 1;		return buildTree(inorder, postorder, null);	}}
5.3 已知前序和后序求中序遍历
如果只有前序和后序遍历只能确定树的根，无法确定左子树和右子树，目前还没想到求解方法。如果你有好的实现方法，欢迎留言一起学习，谢谢！