二叉树的一些属性：
int datdID;
double data;
TreeNode leftTree;
TreeNode rightTree;
TreeNode parent;
//构建一个二叉树，将数据都放入了一个LIST里面
int selfID = 0;
public TreeNode creatTree(List<Double>datas,TreeNode tree){
if(datas.size()!=0){
TreeNode node = new TreeNode();
node.setDatdID(selfID);
node.setData(datas.get(0));
//System.out.println(node.getData());
node.setLeftTree(null);
node.setRightTree(null);
if(tree==null){
datas.remove(0);
tree = node;
}else{
TreeNode P = searchParent(node.getData(),tree);
node.setParent(P);
if(P.getData()>node.getData()){
P.setLeftTree(node);
}else{
P.setRightTree(node);
}
datas.remove(0);
}
creatTree(datas,tree);
}
return tree;
}
下列操作分别是查找节点的父节点以及4种遍历，其中要注意一下非递归方式去遍历
public TreeNode searchParent(double data,TreeNode tree){ TreeNode P = new TreeNode(); if(tree.getLeftTree()==null&&tree.getRightTree()==null){ return tree; }else{ if(data<tree.getData()){ if(tree.getLeftTree()==null){ return tree; }else{ P=searchParent(data,tree.getLeftTree()); } }else{ if(tree.getRightTree()==null){ return tree; }else{ P=searchParent(data,tree.getRightTree()); } } return P; } } //前序遍历(深度遍历) public void PreOrderTraversal(TreeNode tree){ if(tree!=null){ System.out.println(tree.getData()); PreOrderTraversal(tree.getLeftTree()); PreOrderTraversal(tree.getRightTree()); } } //中序遍历 public void MidOrderTraversal(TreeNode tree){ if(tree!=null){ MidOrderTraversal(tree.getLeftTree()); System.out.println(tree.getData()); MidOrderTraversal(tree.getRightTree()); } } //后续遍历 public void AftOrderTraversal(TreeNode tree){ if(tree!=null){ AftOrderTraversal(tree.getRightTree()); System.out.println(tree.getData()); AftOrderTraversal(tree.getLeftTree()); } } //层次遍历(广度遍历) public void LayerOrder(TreeNode root) { System.out.println(root.getData()); List<TreeNode>list = new ArrayList(); list.add(root); int level = 1; int count = 0; while(!list.isEmpty()){ List<TreeNode>childList = new ArrayList(); while(!list.isEmpty()){ childList.add(list.get(0)); list.remove(0); } boolean flag = false; //宽度 System.out.println("第"+count+++"层有节点 "+childList.size()+"个"); for(int i = 0;i<childList.size();i++){ if(childList.get(i).getLeftTree()!=null){ System.out.println(childList.get(i).getLeftTree().getData()); list.add(childList.get(i).getLeftTree()); flag = true; } if(childList.get(i).getRightTree()!=null){ System.out.println(childList.get(i).getRightTree().getData()); list.add(childList.get(i).getRightTree()); flag = true; } } if(flag){ level++; } } //深度 System.out.println("二叉树一共"+level+"层"); } //非递归方法实现前序遍历 public void preordernorec(TreeNode root){ TreeNode pnode = root; Stack stack = new Stack(); stack.push(root); while(!stack.isEmpty()){ root = (TreeNode) stack.pop(); System.out.println(root.getData()); if(root.getRightTree()!=null){ stack.push(root.getRightTree()); } if(root.getLeftTree()!=null){ stack.push(root.getLeftTree()); } } } //交换二叉树的左右儿子，即二叉树的镜像 public TreeNode exchange(TreeNode tree){ if(tree==null){ return tree; }else{ // System.out.println(tree.getData()); TreeNode temp = tree.getLeftTree(); tree.setLeftTree(tree.getRightTree()); tree.setRightTree(temp); exchange(tree.getLeftTree()); exchange(tree.getRightTree()); } return tree; } //判断是否为完全二叉树 public Boolean IsComplete(TreeNode tree){ List<TreeNode>list = new ArrayList(); list.add(tree); int level = lengthTree(tree); int count = 0; boolean flag = true; List<TreeNode> listresult = new ArrayList(); while(level>2){ List<TreeNode>childList = new ArrayList(); while(!list.isEmpty()){ childList.add(list.get(0)); list.remove(0); } //宽度 System.out.println("第"+count+++"层有节点 "+childList.size()+"个"); for(int i = 0;i<childList.size();i++){ if(childList.get(i).getLeftTree()!=null){ list.add(childList.get(i).getLeftTree()); }else{ flag = false; } if(childList.get(i).getRightTree()!=null){ list.add(childList.get(i).getRightTree()); }else{ flag = false; } if(flag == false){ break; } } listresult = childList; if(flag == false){ break; } level = level-1; } int childLength = listresult.size(); for(int i = 0;i<childLength;i++){ if(listresult.get(i).getLeftTree()==null){ flag =false; } } return flag; } //判断是否为平衡二叉树 public Boolean IsBanlance(TreeNode tree){ if(tree==null){ return true; }else{ if(tree.getLeftTree()!=null&&tree.getRightTree()!=null){ int leftLength = lengthTree(tree.getLeftTree()); int rightLength = lengthTree(tree.getRightTree()); if(Math.abs(leftLength-rightLength)>1){ return false; } }else { if(tree.getLeftTree()!=null){ IsBanlance(tree.getLeftTree()); } if(tree.getRightTree()!=null){ IsBanlance(tree.getRightTree()); } } } return true; } //求树的深度 public int lengthTree(TreeNode root) { List<TreeNode>list = new ArrayList(); list.add(root); int level = 1; while(!list.isEmpty()){ List<TreeNode>childList = new ArrayList(); while(!list.isEmpty()){ childList.add(list.get(0)); list.remove(0); } boolean flag = false; for(int i = 0;i<childList.size();i++){ if(childList.get(i).getLeftTree()!=null){ list.add(childList.get(i).getLeftTree()); flag = true; } if(childList.get(i).getRightTree()!=null){ list.add(childList.get(i).getRightTree()); flag = true; } } if(flag){ level++; } } //深度 return level; }
//平衡二叉树的旋转
//左旋变换
public TreeNode SingleRotateWithLeft(TreeNode k2){
TreeNode k1 = new TreeNode();
k1 = k2.getLeftTree();
k2.setLeftTree(k1.getRightTree());
k1.setRightTree(k2);
return k1;
}
//右旋变化换
public TreeNode SingleRotateWithRight(TreeNode k2){
TreeNode k1 = new TreeNode();
k1 = k2.getRightTree();
k2.setRightTree(k1.getLeftTree());
k1.setLeftTree(k2);
return k1;
}
//先进行一次右旋再进行一次左旋
public TreeNode DoubleRotateWithLeft(TreeNode k3){
k3.setLeftTree(SingleRotateWithRight(k3.getLeftTree()));
return SingleRotateWithLeft(k3);
}
//先进行一次左旋再进行一次右旋
public TreeNode DoubleRotateWithRight(TreeNode k3){
k3.setRightTree(SingleRotateWithLeft(k3.getRightTree()));
return SingleRotateWithRight(k3);
}
//http://blog.csdn.net/a454042522/article/details/8591421 http://www.cppblog.com/cxiaojia/archive/2012/08/20/187776.html
//可以参考一下，