树的相关概念：
二叉树(binary tree)是树形结构的一个重要类型。
二叉树由结点的有限集合构成，这个有限集合或者为空集(empty)，或者由一个根结点(root)及两颗不相交的分别称为这个根的左子树(left subtree)和右子树(right subtree)的二叉树(它们也是结点的集合)。 这是一个递归的定义。二叉树可以是空集合，因此根可以有空的左子树或右子树，或者左右子树皆为空。
1、满二叉树
如果一颗二叉树的任何结点或者是树叶，或者恰有两颗非空子树，则此二叉树称为满二叉树。（除了叶结点外每一个结点都有左右子叶且叶子结点都处在最底层的二叉树）
2、扩充二叉树
对于原来二叉树里度数为1的分支结点，在它下面增加一个空树叶；对于原来二叉树的树叶，在它下面增加两个空树叶，由此得到的二叉树称为扩充二叉树。
扩充二叉树是一种满二叉树。
3、Huffman树
给出m个实数W0,W1,…,Wm-1(m≥2)，求一个具有m个外部结点的扩充二叉树，每个外部结点ki有一个Wi与之对应，作为它的权，使得带权外部路径长度
为最小，其中li是从根到外部结点ki的路径长度。得到的二叉树成为Huffman树。
二叉的Huffman树也是一种满二叉树。4、完全二叉树
如果一棵二叉树最多只有最下面的两层结点度数可以小于2，并且最下面一层的结点都集中在该层最左边的若干位置上，则此二叉树成为完全二叉树。
堆实质上是一棵完全二叉树结点的层次序列，此完全二叉树的每个结点对应于一个关键码，根结点对应于关键码。（若设二叉树的深度为h，除第 h 层外，其它各层 (1～h-1) 的结点数都达到最大个数，第 h 层所有的结点都连续集中在最左边，这就是完全二叉树。）
5、二叉搜索树
如果一棵二叉树的每个结点对应于一个关键码，整个二叉树各结点对应的关键码组成一个关键码集合，并且此关键码集合中的各个关键码在二叉树中是按一定次序排列的，这时称此二叉树为二叉搜索树(Binary Search Tree,BST)。（二叉查找树（Binary Search Tree），或者是一棵空树，或者是具有下列性质的二叉树： 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值； 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值； 它的左、右子树也分别为二叉排序树）
（Ps:根节点的层数为1，深度为1）
结点所拥有的子树的个数称为该结点的度(Degree); 树中各结点度的最大值称为该树的度; 称度为m的树为m叉树。
********************************************************
二叉树三种周游（traversal）方式：
public class BinaryTree {
private Node root;
public BinaryTree(Node root){
this.root = root;
}
public BinaryTree(){}
public BinaryTree init(int[] a){
Node root = new Node("0", null, null);
BinaryTree bt = new BinaryTree(root);
for(int item:a){
insertChild(item,root);
}
return bt;
}
public void insertChild(int item,Node root){
if(root.left==null){
root.left = new Node(item+"", null, null);
}else if(root.right == null){
root.right = new Node(item+"",null,null);
}else{
insertChild(item,root.left);
}
}
public void firstPrint(Node root){
System.out.print(root.data+"->");
if(root.left!=null){
firstPrint(root.left);
}
if(root.right!=null){
firstPrint(root.right);
}
}
public void middlePrint(Node root){
if(root.left!=null){
middlePrint(root.left);
}
System.out.print(root.data+"->");
if(root.right!=null){
middlePrint(root.right);
}
}
public void lastPrint(Node root){
if(root.left!=null){
lastPrint(root.left);
}
if(root.right!=null){
lastPrint(root.right);
}
System.out.print(root.data+"->");
}
public static void main(String[] args){
BinaryTree bt = new BinaryTree();
bt=bt.init(new int[]{1,2,3,4,5,6,7,8,9});
System.out.println("tree is ok!root="+bt.root.data);
bt.firstPrint(bt.root);
System.out.println("qianxu------");
bt.middlePrint(bt.root);
System.out.println("zhongxu---------");
bt.lastPrint(bt.root);
System.out.println("houxu--------");
}
}
public class Node {
String data;
Node left;
Node right;
public Node(String data,Node left,Node right){
this.data = data;
this.left = left;
this.right = right;
}
public Node(){
data = null;
left = null;
right = null;
}
}
二叉树的三种遍历方式：前序遍历、中序遍历、以及后序遍历。 上边程序中组装起来的树（下面的示例就根据这个树进行展开）：
程序输出结果： 0->1->3->5->7->9->8->6->4->2->qianxu------
9->7->5->8->3->6->1->4->0->2->zhongxu---------
9->7->8->5->6->3->4->1->2->0->houxu--------
********************************************************************* 怎么从顶部开始逐层打印二叉树数据： 思路：使用队列，先将根节点入队，然后将节点出队，如果该节点有左右子树，将子树入队，然后递归这个步骤。
public void turnToPrint(Node root){
//System.out.println("queue="+queue);
queue.offer(root);
Node temp = queue.poll();
if(temp==null){
return;
}
System.out.print( temp.data+"->");
if(temp.left!=null){
queue.offer(temp.left);
}
if(temp.right!=null){
queue.offer(temp.right);
}
temp = queue.poll();
while(temp!=null){
turnToPrint(temp);
temp = queue.poll();
}
}
queue为：
private LinkedList<Node> queue = new LinkedList<Node>();
public BinaryTree(Node root){
this.root = root;
queue.offer(this.root);
}
输出结果：
bt.turnToPrint(bt.queue.poll());
0->2->1->4->3->6->5->8->7->9
这个也是按照层次输出，不过为什么是从右往左呢？
*********************************************************************
如何判断一棵二叉树是否是平衡二叉树：
（Ps：平衡二叉树（Balanced Binary Tree）又被称为AVL树（有别于AVL算法），且具有以下性质：它是一 棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。） 思路：分别求根节点的左右子树的高度，并判断是否平衡，然后分别递归左右子树。
public int treeDeepth(Node root){ //树的深度
int deep=0;
if(root!=null){
int deepL=treeDeepth(root.left);
int deepR=treeDeepth(root.right);
deep = deepL>=deepR?deepL+1:deepR+1;
}
return deep;
}
public boolean isBalanced(Node root){//判断是否是平衡二叉树
if(root==null){
return true;
}
int left = treeDeepth(root.left);
int right = treeDeepth(root.right);
if(Math.abs(left-right)>1){
return false;
}else{
if(isBalanced(root.left)&&isBalanced(root.right)){
return true;
}else{
return false;
}
}
}
public static void main(String[] args){
BinaryTree bt = new BinaryTree();
//bt=bt.init(new int[]{1,2,3,4,5,6,7,8,9});
bt=bt.init(new int[]{1,2});
System.out.println(bt.isBalanced(bt.root));0到9的树为false；0到2的树为true；0-9的树的deepth为6；结果正确。
*********************************************************************打印二叉树中的所有路径： 思路：先将所有节点装入一个list容器中，然后每次遍历出一条路径，就将相应的叶子节点移除，然后下次判断的时候如果该节点有子节点，而且该子节点还在list容器中，那么该路径就是另一条新路径。代码如下：
private List<Node> nodeSet = new ArrayList<Node>(); //用来装所有的节点
public void printPaths(Node root,List<Node> nodes){ //输出所有的路径
while (nodes.size()>0){
List<Node> path = getPath(root,new ArrayList<Node>(),nodes);
if(path!=null){
printList(path);
}
}
}
private List<Node> getPath(Node root, List<Node> path,
List<Node> nodes) { //返回一条路径
path.add(root);
if(!notleaf(root)){
nodes.remove(root); //如果是叶子就要将他从vector里面移除
return path;
}
//List<Node> paths =path;
if(root.left!=null&&nodes.contains(root.left)){
return getPath(root.left,path,nodes);
}else if(root.right!=null&&nodes.contains(root.right )){
return getPath(root.right,path,nodes);
}else{
nodes.remove(root);
return null;
}
}
private boolean notleaf(Node node){ //是不是叶子节点 不是 =true
return node.left!=null||node.right!=null;
}
public void printList(List<Node> paths){ //打印链表
for(Node n:paths){
System.out.print(n.data+"->");
}
System.out.println();
}
public void getNodes(Node root){ //得到树的所有节点
if(root==null){
return ;
}
nodeSet.add(root);
getNodes(root.left);
getNodes(root.right);
}
public static void main(String[] args){
BinaryTree bt = new BinaryTree();
bt=bt.init(new int[]{1,2,3,4,5,6,7,8,9});
bt.getNodes(bt.root); //初始化nodeSet
bt.printPaths(bt.root,bt.nodeSet);
这里输出的结果是：
0->1->3->5->7->9->
0->1->3->5->8->
0->1->3->6->
0->1->4->
0->2->
*********************************************************************
上面这些代码都在一个class里面完成，完整的class如下：
package com.coding;
import java.util.AbstractQueue;
import java.util.Iterator;
import java.util.List;
public class BinaryTree {
private Node root;
private LinkedList<Node> queue = new LinkedList<Node>();
private List<Node> nodeSet = new ArrayList<Node>(); //用来装所有的节点
public BinaryTree(Node root){
this.root = root;
queue.offer(this.root);
}
public BinaryTree(){}
public BinaryTree init(int[] a){
Node root = new Node("0", null, null);
BinaryTree bt = new BinaryTree(root);
for(int item:a){
insertChild(item,root);
}
return bt;
}
public void insertChild(int item,Node root){
if(root.left==null){
root.left = new Node(item+"", null, null);
}else if(root.right == null){
root.right = new Node(item+"",null,null);
}else{
insertChild(item,root.left);
}
}
public void firstPrint(Node root){
System.out.print(root.data+"->");
if(root.left!=null){
firstPrint(root.left);
}
if(root.right!=null){
firstPrint(root.right);
}
}
public void middlePrint(Node root){
if(root.left!=null){
middlePrint(root.left);
}
System.out.print(root.data+"->");
if(root.right!=null){
middlePrint(root.right);
}
}
public void lastPrint(Node root){
if(root.left!=null){
lastPrint(root.left);
}
if(root.right!=null){
lastPrint(root.right);
}
System.out.print(root.data+"->");
}
public void turnToPrint(Node root){ //按层次输出二叉树
//System.out.println("queue="+queue);
queue.offer(root);
Node temp = queue.poll();
if(temp==null){
return;
}
System.out.print( temp.data+"->");
if(temp.left!=null){
queue.offer(temp.left);
}
if(temp.right!=null){
queue.offer(temp.right);
}
temp = queue.poll();
while(temp!=null){
turnToPrint(temp);
temp = queue.poll();
}
}
public int treeDeepth(Node root){ //树的深度
int deep=0;
if(root!=null){
int deepL=treeDeepth(root.left);
int deepR=treeDeepth(root.right);
deep = deepL>=deepR?deepL+1:deepR+1;
}
return deep;
}
public boolean isBalanced(Node root){//判断是否是平衡二叉树
if(root==null){
return true;
}
int left = treeDeepth(root.left);
int right = treeDeepth(root.right);
if(Math.abs(left-right)>1){
return false;
}else{
if(isBalanced(root.left)&&isBalanced(root.right)){
return true;
}else{
return false;
}
}
}
//public void getPath(int index ,List<Node> nodes){ //打印所有路径 index=root节点的索引
//List<Node> path = new ArrayList<Node>(); //保存路径
//Node root = nodes.get(index);
//if(root==null)
//return;
//if(root.left==null&&root.right ==null){
//System.out.println(root.data);
//}
//do{
//Node temp = root;
//while(notleaf(temp)){
//path.add(temp);
//if(temp.left!=null&&nodes.contains(temp.left)){
//temp=temp.left;
//}else if(temp.right!=null&&nodes.contains(temp.right)){
//temp=temp.right;
//}else{
//path.clear();
//nodes.remove(temp);
//temp=root;
//continue;
//}
//}
//printList(path);
//nodes.remove(path.get(path.size()-1));
//path.clear();
//temp=root;
//
//}while(nodes.size()>0);
//
//}
public void printPaths(Node root,List<Node> nodes){ //输出所有的路径
while (nodes.size()>0){
List<Node> path = getPath(root,new ArrayList<Node>(),nodes);
if(path!=null){
printList(path);
}
}
}
private List<Node> getPath(Node root, List<Node> path,
List<Node> nodes) { //返回一条路径
path.add(root);
if(!notleaf(root)){
nodes.remove(root); //如果是叶子就要将他从vector里面移除
return path;
}
//List<Node> paths =path;
if(root.left!=null&&nodes.contains(root.left)){
return getPath(root.left,path,nodes);
}else if(root.right!=null&&nodes.contains(root.right )){
return getPath(root.right,path,nodes);
}else{
nodes.remove(root);
return null;
}
}
private boolean notleaf(Node node){ //是不是叶子节点 不是 =true
return node.left!=null||node.right!=null;
}
public void printList(List<Node> paths){ //打印链表
for(Node n:paths){
System.out.print(n.data+"->");
}
System.out.println();
}
public void getNodes(Node root){ //得到树的所有节点
if(root==null){
return ;
}
nodeSet.add(root);
getNodes(root.left);
getNodes(root.right);
}
public static void main(String[] args){
BinaryTree bt = new BinaryTree();
bt=bt.init(new int[]{1,2,3,4,5,6,7,8,9});
bt.getNodes(bt.root); //初始化nodeSet
bt.printPaths(bt.root,bt.nodeSet);
//System.out.println(bt.notleaf(bt.root.left));;
//bt.getPath(0,bt.nodeSet);
//bt=bt.init(new int[]{1,2});
//bt.turnToPrint(bt.queue.poll());
//System.out.println(bt.treeDeepth(bt.root));
//System.out.println("tree is ok!root="+bt.root.data);
//bt.firstPrint(bt.root);
//System.out.println("qianxu------");
//bt.middlePrint(bt.root);
//System.out.println("zhongxu---------");
//bt.lastPrint(bt.root);
//System.out.println("houxu--------");
}
}