二叉树节点类
public class BinTreeNode {
private int data;
private BinTreeNode right;
private BinTreeNode left;
public BinTreeNode(){
this.data = 0;
this.left = null;
this.right = null;
}
public BinTreeNode(int data,BinTreeNode left, BinTreeNode right){
this.data = data;
this.left = left;
this.right = right;
}
public int getSize(){
if(this==null){
return 0;
}
else{
return 1+this.left .getSize()+this.right.getSize();
}
}
public int getHeight() {
if(this==null){
return -1;
}
else{
return 1+Math.max(this.left.getHeight(), this.right.getHeight());
}
}
public int getData() {
return data;
}
public void setData(int data) {
this.data = data;
}
public BinTreeNode getLeft() {
return left;
}
public void setLeft(BinTreeNode left) {
this.left = left;
}
public BinTreeNode getRight() {
return right;
}
public void setRight(BinTreeNode right) {
this.right = right;
}
}
/*
* 该类为一般排序树的基本操作（有寻找，插入，删除），包含先序，中序，后序，层次遍历的非递归实现。
* 注意为非平衡情况下的操作。
*/
import java.lang.reflect.Array;
import java.util.Queue;
import java.util.Stack;
import java.util.concurrent.LinkedBlockingDeque;
public class BinTreeSort {
private BinTreeNode root;
private BinTreeNode hot;
public BinTreeSort (int c){
root = new BinTreeNode (c,null,null);
}
public BinTreeNode getRoot() {
// TODO Auto-generated method stub
return root;
}
public boolean isEmpty() {
// TODO Auto-generated method stub
return root == null;
}
public int getSize() {
// TODO Auto-generated method stub
return root.getSize();
}
public int getHeight() {
// TODO Auto-generated method stub
return root.getHeight();
}
//层次遍历
public void layoutprint(){
BinTreeNode p = root;
Queue<BinTreeNode> q = new LinkedBlockingDeque<BinTreeNode>();
q.add(p);
while(!q.isEmpty()){
p = q.poll();
System.out.println(""+p.getData());
if(p.getLeft()!=null) q.add(p.getLeft());
if(p.getRight()!=null) q.add(p.getRight());
}
}
//中序遍历非递归
public void inorderprint(){
Stack<BinTreeNode> s = new Stack<BinTreeNode>();
BinTreeNode p = root;
goleft(p,s);
while(!s.isEmpty()){
p=s.pop();
System.out.println(""+p.getData());
if(p.getRight()!=null) goleft(p.getRight(),s);
}
}
private void goleft(BinTreeNode p,Stack<BinTreeNode> s){
BinTreeNode q = p;
while(q!=null){
s.push(q);
q=q.getLeft();
}
}
//先序遍历
public void fristprint(){
Stack<BinTreeNode> s = new Stack<BinTreeNode>();
BinTreeNode p = root;
visitleft(p, s);
while(!s.isEmpty()){
p=s.pop();
visitleft(p, s);
}
}
private void visitleft(BinTreeNode p,Stack<BinTreeNode> s){
BinTreeNode q = p;
while(q!=null){
System.out.println(""+q.getData());
if(q.getRight()!=null) s.push(q.getRight());
q=q.getLeft();
}
}
//后序遍历
public void lastprint (){
BinTreeNode p = root;
Stack<lastnode> s = new Stack<lastnode>();
lastnode lnode = new lastnode();
lnode.node=p;
lnode.flag=1;
s.add(lnode);
while(!s.isEmpty()){
lnode = s.pop();
if(lnode.flag == 3) System.out.println(""+lnode.node.getData());
else{
s.push(lnode);
if(lnode.node.getRight()!=null){
lnode.flag++;
lastnode londe1 = new lastnode(lnode.node.getRight(), 1);
s.push(londe1);
}
else{
lnode.flag++;
}
if(lnode.node.getLeft()!=null){
lnode.flag++;
lastnode londe1 = new lastnode(lnode.node.getLeft(), 1);
s.push(londe1);
}
else{
lnode.flag++;
}
}
}
}
private class lastnode{
BinTreeNode node;
int flag;
public lastnode(){
}
public lastnode(BinTreeNode p,int i){
this.node = p;
this.flag =i;
}
}
//寻找操作
public BinTreeNode search(int x){
BinTreeNode p = root;
hot = p;
while(p!=null){
if(p.getData()==x){
return p;
}
hot = p;
p=p.getData()<x?p.getRight():p.getLeft();
}
return null;
}
//插入操作
public void insert(int x){
BinTreeNode p = null;
p=search(x);
if(p!=null){
return ;
}
else{
if(hot.getData()>x){
hot.setLeft(new BinTreeNode(x,null,null));
}
else{
hot.setRight(new BinTreeNode(x,null,null));
}
}
}
//删除操作
public boolean remove(int x){
BinTreeNode p = null;
p=search(x);
if(p==null){
return false;
}
else{
if(p.getLeft()==null){
if(hot.getLeft()==p){
hot.setLeft(p.getRight());
}
if(hot.getRight()==p){
hot.setRight(p.getRight());
}
}
if(p.getRight()==null){
if(hot.getRight()==p){
hot.setRight(p.getLeft());
}
if(hot.getLeft()==p){
hot.setLeft(p.getLeft());
}
}
else{
BinTreeNode q = p.getRight();
hot = p;
while(q.getLeft()!=null){
hot =q;
q=q.getLeft();
}
p.setData(q.getData());
hot.setRight(q.getRight());
}
return true;
}
}
public static void main(String[] args){
BinTreeSort bval = new BinTreeSort(10);
bval.insert(11);
bval.insert(13);
bval.insert(8);
bval.insert(6);
bval.insert(12);
bval.insert(15);
bval.insert(1);
bval.insert(21);
bval.insert(9);
bval.insert(5);
System.out.println(".......层次遍历..........");
bval.layoutprint();
System.out.println("........中序遍历.........");
bval.inorderprint();
System.out.println(".........先序遍历........");
bval.fristprint();
System.out.println(".........后序遍历........");
bval.lastprint();
bval.remove(10);
System.out.println(".......层次遍历..........");
bval.layoutprint();
System.out.println("........中序遍历.........");
bval.inorderprint();
System.out.println(".........先序遍历........");
bval.fristprint();
System.out.println(".........后序遍历........");
bval.lastprint();
}
}