目录：
一、树1 .概括2 .一些基本术语二、二叉树1 .概括2 .重要特性三、二叉树的存储结构1 .顺序记忆2 .连锁记忆4、二叉树的遍历1 .根据遍历序列确定二叉树2 .遍历序列到二叉树3 .估计遍历和构造树的代码
一、树
1. 概述
与线性表中一一对应的线性关系不同，树表示更复杂的数据元素之间的非线性关系。 直观地看，树是由分支关系定义的层次结构，是一对多关系树的定义。 树(Tree )有n ) n=0)个节点的有限集合，只有一个根节点(Root )时，剩下的节点可以分为m ) m )个互不相交的有限集合T1、T2、Tm、的树的定义本身是递归的
2. 一些基本术语
树的节点：包括一个数据元素及其子树的分支度。 将节点所具有的子树的数度** 0的节点称为叶或终端节点。 度不是0**的节点称为非终结节点或分支节点的子树的根，该节点的子树称为子树(child )，对应的节点称为子树的子树(child )，同一个子树的子树称为兄弟)节点的祖先从根开始将某节点作为根的子树中的任意一个节点称为该节点的子孙节点的层次(Level )从根开始定义，根是第一层，根的孩子是第二层。 因此，将树中的节点的最大层次定义为树的深度(depth )或高度二、二叉树
)1. 概述
。 一般树中分别约束了最多2个子树二叉树和完全二叉树(对于二叉树的最底层，从右向左删除节点)。
2. 重要特性
二叉树在第I层中最多2i-1个节点深度为k的二叉树最多2k-1个节点的高度(或深度)为k的完全二叉树至少具有2k-2个叶的节点的非空二叉树的叶的节点数为度2的节点数上加1，即假设一粒度为m的二叉树，度为1的节点为n1，度为2的节点为n2，度为m的节点数为nm，则叶的节点数： n0*****=1n2***2n3***.m-1(nm是具有n个节点的完全二叉树) 深度为log2n 1编号的性质： n个节点的完全二叉树(其深度为log2n 1)，对各节点从上到下，从左到右依次编号(1(n )，I为某节点a的编号时) I不等于1 *2In时，a没有左边的孩子**； *2i 1n时，a右边的儿童号码为2I1； 2i 1 n的情况下，a没有右边的孩子**； 使用
三、二叉树的存储结构
1. 顺序存储
数组存储数据元素。 从容纳的观点来看，该序贯容纳结构只适用于完全二叉树。 这是因为在最坏的情况下，深度为k并且只有k个节点的单个树(树上不存在角度为2的节点)需要长度为2k-1的一维数组。
2. 链式存储
以链表形式存储数据元素和数据元素之间的关系。请注意，
四、二叉树的遍历
1. 由遍历序列确定二叉树
由先后顺序和中序决定，下一个顺序的最后一个是根，下一个是右子根。2. 根据遍历序列估计二叉树
由层次和中序决定 前序 遍历序列 和 后序 遍历序列 相同 的树：只有根结点前序 遍历 和 中序 遍历 相同 的二叉树：所有结点没有jmddg（右单分支树中序 遍历 和 后序 遍历 相同 的二叉树：所有结点没有右子树（左单分支树）前序遍历 和 后序 遍历 相反 的二叉树：没有jmddg或者没有右子树（只有一个叶子结点）<u style="text-decoration: none; border-bottom: 1px dashed grey;">高度等于其结点数</u>前序 遍历 和 中序 遍历 相反 的二叉树：所有结点没有右子树（左单分支树）中序 遍历 和 后序 遍历 相反 的二叉树：所有结点没有jmddg（右单分支树）3. 遍历和建树代码
二叉树的建树深度优先遍历（先序，中序和后序）广度优先遍历（先序，后序）/* BitTree.java */ package com.java.tree; import java.util.LinkedList; import java.util.Queue; /** * Created by Jaco.Young. * 2018-06-13 18:26 */ public class BitTree { //代表由先序和中序唯一确定的树的根结点 private TreeNode root; /** * 提供给外部调用的方法 * 字符数组pre表示先序遍历序列，mid表示中序遍历序列 */ public void build(char[] pre, char[] mid){ //将创建树的根结点赋值给 root root = buildTree(pre,0, pre.length-1, mid, 0, mid.length-1); } /** * 前提条件，树中不存在重复元素 * 由先序遍历序列和中序遍历序列，构造二叉树的方法 * 我们建树的过程总是将序列不断地分割成jmddg、右子树 * lPre、rPre和lMid、rMid，分别就表示要对先序和中序的哪一部分进行建树 */ private TreeNode buildTree(char[] pre, int lPre, int rPre, char[] mid, int lMid, int rMid){ //在先序遍历序列中，找到当前这棵树的根结点 char root = pre[lPre]; //在中序遍历序列中，根据先序中的根结点来查找在中序中的位置 int rootIndex = getRootIndex(mid, lMid, rMid, root); //如果没有找到，说明所给的参数异常 if(rootIndex == -1){ throw new IllegalArgumentException("Illegal Argument!"); } //计算当前这棵树，左右子树的个数 //整个中序序列：[jmddg(lMid) root(rootIndex) 右子树(rMid)] //jmddg[lMid,rootIndex-1] int lNum = rootIndex - lMid; //rootIndex-1 -lMid + 1 //右子树[rootIndex+1,rMid] int rNum = rMid - rootIndex; //rMid - (rootIndex + 1) + 1 //开始构建当前根结点的jmddg和右子树 //先构建jmddg TreeNode lchild; //作为jmddg的根结点 //以当前结点为根的树，没有jmddg if(lNum == 0){ lchild = null; }else{ //当前这个树的jmddg，仍然是一棵树，递归构造这棵树的jmddg //设x为当前树先序中jmddg最后一个元素的下标，则：x - (lpre + 1) = lNum //得：x = lPre + lNum lchild = buildTree(pre, lPre + 1, lPre+lNum, mid, lMid, rootIndex - 1); } //构建右子树 TreeNode rchild; if(rNum == 0){ rchild = null; }else{ //当前结点的右子树，仍然包含很多节点，需要递归的构造其右子树 rchild = buildTree(pre, lPre + lNum + 1, rPre, mid, rootIndex + 1, rMid); } //构造完整的二叉树 return new TreeNode(root,lchild,rchild); } //在中序遍历序列中，根据先序中的根结点来查找在中序中的位置 private int getRootIndex(char[] mid, int lMid, int rMid, char root) { for(int i = lMid; i <= rMid; i++){ if(mid[i] == root){ return i; } } return -1; } //二叉树每一个结点的结构 private class TreeNode{ //结点中存储的数据 char item; //指向左孩子结点 TreeNode lChild; //指向右孩子结点 TreeNode rChild; //构造方法,完成初始化 public TreeNode(char item, TreeNode lChild, TreeNode rChild){ this.item = item; this.lChild = lChild; this.rChild = rChild; } } //提供三个让外界调用的方法 public void preTraverse() { preOrder(root); } public void midTraverse() { midOrder(root); } public void postTraverse() { postOrder(root); } //先序遍历 DLR private void preOrder(TreeNode root) { if( root != null) { //先访问根节点 System.out.print(root.item + " "); //递归访问jmddg preOrder(root.lChild); //递归访问右子树 preOrder(root.rChild); } } //中序遍历 LDR private void midOrder(TreeNode root) { if(root != null) { //递归访问jmddg midOrder(root.lChild); //访问根 System.out.print(root.item + " "); //递归访问右子树 midOrder(root.rChild); } } //后续遍历 // LRD private void postOrder(TreeNode root) { if(root != null) { //递归访问jmddg postOrder(root.lChild); //递归访问右子树 postOrder(root.rChild); //访问根 System.out.print(root.item + " "); } } //广度优先遍历 BFS public void BFS() { //创建一个能放TreeNode对象的队列 Queue<TreeNode> queue = new LinkedList<>(); //将树的根节点入队列 queue.add(root); //循环执行广度优先遍历 while(!queue.isEmpty()) { //将当前的队头元素出队列 TreeNode node = queue.remove(); //访问出队列的节点 System.out.print(node.item + " "); //出队列的节点是否有左孩子，有则将其左孩子入队列 if(node.lChild != null) { //有左孩子 queue.add(node.lChild); } //出队列的节点是否有右孩子，如果右，将其右孩子如队列 if(node.rChild != null) { queue.add(node.rChild); } } } } /* Test.java*/ package com.java.tree; /** * 测试类 * Created by Jaco.Young. * 2018-06-13 20:16 */ public class Test { public static void main(String[] args){ //构造先序遍历序列和中序遍历序列 char[] pre = {'A','B','E', 'K', 'L', 'F', 'D', 'H', 'J'}; char[] mid = {'K', 'E', 'L', 'B', 'F', 'A', 'H', 'D', 'J'}; BitTree bitTree = new BitTree(); //根据遍历序列构建二叉树 bitTree.build(pre, mid); //先序遍历 bitTree.preTraverse(); System.out.println(); //中序遍历 bitTree.midTraverse(); System.out.println(); //后序遍历 bitTree.postTraverse(); System.out.println(); //广度优先遍历 bitTree.BFS(); } }运行结果为：A B E K L F D H JK E L B F A H D JK L E F B H J D AA B D E F H J K L