二叉树的java集合（遍历等）

package tree;

import java.util.*;

/**
* 二叉树的集合：遍历，打印，树的深度
*
*
*/
public class BinaryTree {
public static void main(String[] args) {
Node root=new Node(3);
root.left=new Node(5);
root.right=new Node(4);
root.left.left=new Node(1);
root.left.left.right=new Node(10);
root.left.right=new Node(2);
root.right.left=new Node(7);
root.right.right=new Node(8);
root.right.left.left=new Node(6);
root.right.left.right=new Node(9);
BinTree binTree=new BinTree();
int num=binTree.totalNum_recursion(root);
System.out.println("树节点的总数： "+num);
System.out.println("前序遍历（迭代）的结果");
binTree.preTravel_iter(root);
System.out.println("\n前序遍历（递归）的结果");
binTree.preTravel_recur(root);
System.out.println("\n中序遍历（迭代）的结果");
binTree.inTravel_iter(root);
System.out.println("\n中序遍历（递归）的结果");
binTree.inTravel_recur(root);
System.out.println("\n后序遍历（迭代）的结果");
binTree.postTravel_iter(root);
System.out.println("\n后序遍历（递归）的结果");
binTree.postTravel_recur(root);
System.out.println("\n分层遍历（迭代）的结果");
binTree.levelTravel(root);
System.out.println("\n求树的深度: "+ binTree.getDepth(root));

}
}

/**
* 对二叉树的操作
* @author HanJq
*
*/
class BinTree{
BinTree() {
}

//求总的节点数,方法一：使用迭代法求
public int totalNum_iterator(Node root){
if(root==null)
return 0;
List<Node> list=new ArrayList<Node>();
list.add(root);
int num=1;
while(!list.isEmpty()){
if(list.get(0).left!=null){
num++;
list.add(list.get(0).left);
}
if(list.get(0).right!=null){
num++;
list.add(list.get(0).right);
}
list.remove(0);
}
return num;
}

//求树节点总数，方法二：递归
public int totalNum_recursion(Node root){
if(root==null)
return 0;
else{
// int n=totalNum_recursion(root.left);
// System.out.print("; n="+n+" root1="+root.val);
// System.out.println();
// int m=totalNum_recursion(root.right);
// System.out.print("; m="+m+" root2="+root.val);
return totalNum_recursion(root.left)+totalNum_recursion(root.right)+1;
}
}

//=======树的前序遍历=======
//迭代
public void preTravel_iter(Node root){
if(root==null) return;
Stack<Node> stack=new Stack<Node>();
stack.push(root);
while(!stack.isEmpty()){
Node node=stack.pop();
System.out.print(node.val+" ");
if(node.right!=null){
stack.push(node.right);//根据栈的先进后出，先把右节点压人栈
}
if(node.left!=null){
stack.push(node.left);
}
}
}

//递归
public void preTravel_recur(Node root){
if(root==null)
return;
System.out.print(root.val+" ");
preTravel_recur(root.left);
preTravel_recur(root.right);
}

//=======树的中序遍历=======
//迭代
//用栈先把根节点的所有左孩子都添加到栈内，
// 然后输出栈顶元素，再处理栈顶元素的右子树
public void inTravel_iter(Node root){
if(root==null) return;
Stack<Node> stack=new Stack<Node>();
Node cur=root;
while(true){
while(cur!=null){
stack.push(cur);
cur=cur.left;
}
if(stack.isEmpty())
break;
cur=stack.pop();
System.out.print(cur.val+" ");
cur=cur.right;
}
}
public void inTravel_recur(Node root){
if(root==null)
return;
inTravel_recur(root.left);
System.out.print(root.val+" ");
inTravel_recur(root.right);
}

//=======树的后序遍历=======
//迭代
public void postTravel_iter(Node root){
if(root==null){
return;
}
Stack<Node> stack=new Stack<Node>();
Stack<Node> stack2=new Stack<Node>();//存储从stack弹出来的结点
stack.push(root);
while(!stack.isEmpty()){
Node cur=stack.pop();
stack2.push(cur);
if(cur.left!=null){
stack.push(cur.left);
}
if(cur.right!=null){
stack.push(cur.right);
}
}
while(!stack2.isEmpty())
System.out.print(stack2.pop().val+" ");
}

//递归
public void postTravel_recur(Node root){
if(root==null)
return;
postTravel_recur(root.left);
postTravel_recur(root.right);
System.out.print(root.val+" ");
}

//=======树的分层遍历=======
//迭代
public void levelTravel(Node root){
if(root==null)
return;
LinkedList<Node> linkedList=new LinkedList<Node>();
linkedList.add(root);
while(!linkedList.isEmpty()){
Node cur=linkedList.removeFirst();
System.out.print(cur.val+" ");
// System.out.println("size="+linkedList.size());
if(cur.left!=null){
linkedList.add(cur.left);
}
if(cur.right!=null){
linkedList.add(cur.right);
}
}
}

//递归
public void levelTraversal(Node root){
ArrayList<ArrayList<Integer>> ret=new ArrayList<ArrayList<Integer>>();
dfs(root,0,ret);
for(int i=0;i<ret.size();i++){
for(int j=0;j<ret.get(i).size();j++){
System.out.print(ret.get(i).get(j)+" ");
}
}
}
public void dfs(Node root,int level,ArrayList<ArrayList<Integer>> ret){
if(root==null)
return;
if(level>=ret.size()){
ret.add(new ArrayList<Integer>());
}
ret.get(level).add(root.val);
dfs(root.left,level+1,ret);
dfs(root.right,level+1,ret);
}

//打印链表
public void printList(Node root){
while(root!=null){
System.out.print(root.val+" ");
root=root.right;
}
}

//将二叉树变为有序的双向链表
public Node convertBST2DLLRec(Node root) {
root = convertBST2DLLSubRec(root);
// root会在链表的中间位置，因此要手动把root移到链表头
while(root.left != null){
root = root.left;
}
return root;
}
// 递归转换BST为双向链表(DLL)
public Node convertBST2DLLSubRec(Node root){
if(root==null || (root.left==null && root.right==null)){
return root;
}
Node tmp = null;
if(root.left != null){ // 处理左子树
tmp = convertBST2DLLSubRec(root.left);
while(tmp.right != null){ // 寻找最右节点
tmp = tmp.right;
}
tmp.right = root; // 把左子树处理后结果和root连接
root.left = tmp;
}
if(root.right != null){ // 处理右子树
tmp = convertBST2DLLSubRec(root.right);
while(tmp.left != null){ // 寻找最左节点
tmp = tmp.left;
}
tmp.left = root; // 把右子树处理后结果和root连接
root.right = tmp;
}
return root;
}

//======求某一节点的深度======================================
//递归
public int getLayor(Node root,int n,int l){
if(root==null){
return -1;
}
int i=-1;
if(root.val==n){
return l;
}
if((i=getLayor(root.left,n,l+1))!=-1){
return i;
}
if((i=getLayor(root.right,n,l+1))!=-1){
return i;
}
return i;
}
//迭代方法
public int getLayor2(Node root,int n){
int num=1;
if(root.val==n){
return 1;
}
Queue<Node> queue=new LinkedList<Node>();
queue.add(root);
Node cur=root;
while(!queue.isEmpty()){
cur=queue.remove();
if(cur.left!=null){
queue.add(cur.left);
cur.left.parent=cur;
if(cur.left.val==n)
break;
}
if(cur.right!=null){
queue.add(cur.right);
cur.right.parent=cur;
if(cur.right.val==n)
break;
}
}
while(cur.parent!=null){
cur=cur.parent;
num++;
}
return num+1;
}

//=======树的深度=======
//递归
public int getDepth(Node root){
if(root==null)
return 0;
int leftDepth=getDepth(root.left);
int rightDepth=getDepth(root.right);
return Math.max(leftDepth, rightDepth)+1;
}

//迭代
public int getDepth2(Node root){
if(root==null)
return 0;
int depth=0;
int currentnum=1;
int nextnum=0;
Queue<Node> queue=new LinkedList<Node>();
queue.add(root);
while(!queue.isEmpty()){
Node cur=queue.remove();
currentnum--;
if(cur.left!=null){
queue.add(cur.left);
nextnum++;
}
if(cur.right!=null){
queue.add(cur.right);
nextnum++;
}
if(currentnum==0){
depth++;
currentnum=nextnum;
nextnum=0;
}
}
return depth;
}

//======求二叉树节点个数================================================
//递归方法
public int nodeNum(Node root){
if(root==null){
return 0;
}
else{
return(nodeNum(root.left)+nodeNum(root.right)+1);
}
}
//迭代方法
public int nodeNum2(Node root){
if(root==null){
return 0;
}
int num=1;
ArrayList<Node> al=new ArrayList<Node>();
al.add(root);
while(!al.isEmpty()){
if(al.get(0).left!=null){
al.add(al.get(0).left);
num++;
}
if(al.get(0).right!=null){
al.add(al.get(0).right);
num++;
}
al.remove(0);
}
return num;
}

//======以下求二叉树最大路径和============================================
//max为每次递归之后的最大路径和
private int max;
//travel函数递归执行子树并求子树的最大路径
private int travel(Node node){
int val=node.val;
//lval,rval分别为左子树和右子树的最大路径值
int lval=0,rval=0;
//result是可以返回给上一级树的路径值
int result=val;
/*
* 每次的travel函数中max是该级子树的最大路径值（该级子树最大路径值并不一定可以返回给上一级）
* 只有val,val+lval,val+rval其中之一才可以返回给上一级
* 关键的是，max用来保存所有子树的最大路径值
*/
//逐级寻找应该返回到上一级的result和当前最大max
if(node.left!=null){
lval=travel(node.left);
if(lval>0){
result=val+lval;
}
if(max<lval){
max=lval;
}
}
if(node.right!=null){
rval=travel(node.right);
if(result<val+rval){
result=val+rval;
}
if(max<rval){
max=rval;
}
}
if(max<result){
max=result;
}
if(max<val+lval+rval){
max=val+lval+rval;
}
return result;
}
public int maxPathSum(Node root){
max=Integer.MIN_VALUE;
travel(root);
return max;
}
}

//创建树的节点
class Node {
Node left;
Node right;
Node parent;
int val;
Node(int val){
this.val=val;
}
}