二叉树的定义：
二叉树(BinaryTree)是n(n≥0)个结点的有限集，它或者是空集(n=0)，或者由一个根结点及两棵互不相交的、分别称作这个根的左子树和右子树的二叉树组成。
二叉树的遍历方式主要有：先序遍历(NLR)，中序遍历(LNR)，后序遍历(LRN)，和层次遍历。
注意：
由二叉树的先序序列和中序序列可以唯一地确定一颗二叉树；
由二叉树的后序序列和中序序列可以唯一地确定一颗二叉树；
由二叉树的层序序列和中序序列可以唯一地确定一棵二叉树；
但，由二叉树的先序序列和后序序列无法唯一地确定一棵二叉树。
Java实现链式存储的二叉树以及其各种遍历算法：
树节点：
public class TreeNode {
? ? private E data;? //数据域
? ? private TreeNode lchild;? //左孩子
? ? private TreeNode rchild;? //右孩子
? ?
? ? TreeNode(){}
? ?
? ? TreeNode(E e){
? ? ? ? this.data = e;
? ? }
? ?
? ? TreeNode(E data,TreeNode lchild, TreeNode rchild){
? ? ? ? this.data = data;
? ? ? ? this.lchild = lchild;
? ? ? ? this.rchild = rchild;
? ? }
? ?
? ? public void setData(E data){
? ? ? ? this.data = data;
? ? }
? ?
? ? public E getData(){
? ? ? ? return this.data;
? ? }
? ?
? ? public void setLchild(TreeNode lchild){
? ? ? ? this.lchild = lchild;
? ? }
? ?
? ? public TreeNode getLchild(){
? ? ? ? return this.lchild;
? ? }
? ?
? ? public void setRchild(TreeNode rchild){
? ? ? ? this.rchild = rchild;
? ? }
? ?
? ? public TreeNode getRchild(){
? ? ? ? return this.rchild;
? ? }
}
二叉树的Java实现：
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.Stack;
/**
?* @author Cherish
?* 二叉树的链式存储结构
?* @param
?*/
public class BinaryTree {
? ? private TreeNode root;? //根节点
? ? private List nodeList = null;? //二叉树节点的链式结构
? ?
? ? public BinaryTree(){
? ? ? ?
? ? }
? ?
? ? public BinaryTree(TreeNode root){
? ? ? ? this.root = root;
? ? }
? ?
? ? //把一个数组转化为一颗完全二叉树
? ? public TreeNode buildTree(E[] array){
? ? ? ? nodeList = new LinkedList();? ? ? ?
? ? ? ? //将数组中的元素依次转换为TreeNode节点，存放于链表中
? ? ? ? for(int i=0; i< array.length; i++){
? ? ? ? ? ? nodeList.add(new TreeNode(array[i]));?
? ? ? ? }
? ? ? ? //对前（array.length / 2 - 1）个父节点，按照父节点与孩子节点的数字关系建立完全二叉树
? ? ? ? //对完全二叉树，按从上到下，从左到右的顺序依次编号0,1,2,3....N,则i>0的节点，其左孩子为（2*i+1），
? ? ? ? //其右孩子为（2*i+2）
? ? ? ? for(int j=0; j < (array.length/2-1);j++){
? ? ? ? ? ? //左孩子
? ? ? ? ? ? nodeList.get(j).setLchild(nodeList.get(j*2+1));
? ? ? ? ? ? //右孩子
? ? ? ? ? ? nodeList.get(j).setRchild(nodeList.get(j*2+2));
? ? ? ? }
? ? ? ? //最后一个父节点：因为最后一个父节点可能没有右孩子，所以单独处理
? ? ? ? int index = array.length/2 -1;
? ? ? ? //左孩子
? ? ? ? nodeList.get(index).setLchild(nodeList.get(index*2+1));
? ? ? ? //右孩子：如果数组的长度为奇数才有右孩子
? ? ? ? if(array.length % 2 == 1){
? ? ? ? ? ? nodeList.get(index).setRchild(nodeList.get(index*2+2));
? ? ? ? }
? ? ? ? root=nodeList.get(0); //设置根节点
? ? ? ? return root;
? ? }
? ?
? ? //得到树的高度
? ? public int height(TreeNode node){
? ? ? ? if(node == null){
? ? ? ? ? ? return 0;
? ? ? ? }else{
? ? ? ? ? ? int i = height(node.getLchild());
? ? ? ? ? ? int j = height(node.getRchild());
? ? ? ? ? ? return (i? ? ? ? }
? ? }
? ?
? ? //得到节点的个数
? ? public int size(TreeNode node){
? ? ? ? if(node == null){
? ? ? ? ? ? return 0;
? ? ? ? }else{
? ? ? ? ? ? return 1+ size(node.getLchild())+size(node.getRchild());
? ? ? ? }
? ? }
? ?
? ? //递归实现先序遍历 NLR
? ? public void preOrder(TreeNode node){
? ? ? ? if(node != null){
? ? ? ? ? ? System.out.print(node.getData() + " ");
? ? ? ? ? ? preOrder(node.getLchild());
? ? ? ? ? ? preOrder(node.getRchild());
? ? ? ? }
? ? }
? ? //非递归实现先序遍历 NLR
? ? public void nonRecPreOrder(TreeNode node){
? ? ? ? Stack> nodeStack = new Stack>();
? ? ? ? TreeNode nodeTemp = node; //nodeTemp作为遍历指针
? ? ? ? while(nodeTemp != null || !nodeStack.isEmpty()){? //当nodeTemp非空或栈非空时循环
? ? ? ? ? ? if(nodeTemp != null){? //根指针非空，遍历左子树
? ? ? ? ? ? ? ? nodeStack.push(nodeTemp);? //根指针进栈
? ? ? ? ? ? ? ? System.out.print(nodeStack.peek().getData() + " "); //根指针退栈，访问根节点
? ? ? ? ? ? ? ? nodeTemp = nodeTemp.getLchild();? //每遇到非空二叉树先向左走
? ? ? ? ? ? }else{ //再向右子树走
? ? ? ? ? ? ? ? nodeTemp = nodeStack.pop();
? ? ? ? ? ? ? ? nodeTemp = nodeTemp.getRchild();
? ?