javaæé äºåæ ï¼å¯ä»¥éè¿é¾è¡¨æ¥æé ï¼å¦ä¸ä»£ç ï¼
public class BinTree {
public final static int MAX=40;
BinTree []elements = new BinTree[MAX];//å±æ¬¡éåæ¶ä¿åå个èç¹
int front;//å±æ¬¡éåæ¶éé¦
int rear;//å±æ¬¡éåæ¶éå°¾
private Object data; //æ°æ®å
æ°
private BinTree left,right; //æåå·¦,å³å©åç»ç¹çé¾
public BinTree()
{
}
public BinTree(Object data)
{ //æé æå¼ç»ç¹
this.data = data;
left = right = null;
}
public BinTree(Object data,BinTree left,BinTree right)
{ //æé æå¼ç»ç¹
this.data = data;
this.left = left;
this.right = right;
}
public String toString()
{
return data.toString();
}
//ååºéåäºåæ
public static void preOrder(BinTree parent){
if(parent == null)
return;
System.out.print(parent.data+" ");
preOrder(parent.left);
preOrder(parent.right);
}
//ä¸åºéåäºåæ
public void inOrder(BinTree parent){
if(parent == null)
return;
inOrder(parent.left);
System.out.print(parent.data+" ");
inOrder(parent.right);
}
//ååºéåäºåæ
public void postOrder(BinTree parent){
if(parent == null)
return;
postOrder(parent.left);
postOrder(parent.right);
System.out.print(parent.data+" ");
}
// å±æ¬¡éåäºåæ
public void LayerOrder(BinTree parent)
{
elements[0]=parent;
front=0;rear=1;
while(front<rear)
{
try
{
if(elements[front].data!=null)
{
System.out.print(elements[front].data + " ");
if(elements[front].left!=null)
elements[rear++]=elements[front].left;
if(elements[front].right!=null)
elements[rear++]=elements[front].right;
front++;
}
}catch(Exception e){break;}
}
}
//è¿åæ çå¶èç¹ä¸ªæ°
public int leaves()
{
if(this == null)
return 0;
if(left == null&&right == null)
return 1;
return (left == null ? 0 : left.leaves())+(right == null ? 0 : right.leaves());
}
//ç»æè¿åæ çé«åº¦
public int height()
{
int heightOfTree;
if(this == null)
return -1;
int leftHeight = (left == null ? 0 : left.height());
int rightHeight = (right == null ? 0 : right.height());
heightOfTree = leftHeight<rightHeight?rightHeight:leftHeight;
return 1 + heightOfTree;
}
//å¦æ对象ä¸å¨æ ä¸,ç»æè¿å-1;å¦åç»æè¿å该对象å¨æ ä¸æå¤çå±æ¬¡,è§å®æ ¹èç¹ä¸ºç¬¬ä¸å±
public int level(Object object)
{
int levelInTree;
if(this == null)
return -1;
if(object == data)
return 1;//è§å®æ ¹èç¹ä¸ºç¬¬ä¸å±
int leftLevel = (left == null?-1:left.level(object));
int rightLevel = (right == null?-1:right.level(object));
if(leftLevel<0&&rightLevel<0)
return -1;
levelInTree = leftLevel<rightLevel?rightLevel:leftLevel;
return 1+levelInTree;
}
//å°æ ä¸çæ¯ä¸ªèç¹çå©å对æ¢ä½ç½®
public void reflect()
{
if(this == null)
return;
if(left != null)
left.reflect();
if(right != null)
right.reflect();
BinTree temp = left;
left = right;
right = temp;
}
// å°æ ä¸çææèç¹ç§»èµ°,并è¾åºç§»èµ°çèç¹
public void defoliate()
{
if(this == null)
return;
//è¥æ¬èç¹æ¯å¶èç¹ï¼åå°å
¶ç§»èµ°
if(left==null&&right == null)
{
System.out.print(this + " ");
data = null;
return;
}
//移走左åæ è¥å
¶åå¨
if(left!=null){
left.defoliate();
left = null;
}
//移走æ¬èç¹ï¼æ¾å¨ä¸é´è¡¨ç¤ºä¸è·ç§»èµ°...
String innerNode += this + " ";
data = null;
//移走å³åæ è¥å
¶åå¨
if(right!=null){
right.defoliate();
right = null;
}
}
/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
BinTree e = new BinTree("E");
BinTree g = new BinTree("G");
BinTree h = new BinTree("H");
BinTree i = new BinTree("I");
BinTree d = new BinTree("D",null,g);
BinTree f = new BinTree("F",h,i);
BinTree b = new BinTree("B",d,e);
BinTree c = new BinTree("C",f,null);
BinTree tree = new BinTree("A",b,c);
System.out.println("ååºéåäºåæ ç»æ: ");
tree.preOrder(tree);
System.out.println();
System.out.println("ä¸åºéåäºåæ ç»æ: ");
tree.inOrder(tree);
System.out.println();
System.out.println("ååºéåäºåæ ç»æ: ");
tree.postOrder(tree);
System.out.println();
System.out.println("å±æ¬¡éåäºåæ ç»æ: ");
tree.LayerOrder(tree);
System.out.println();
System.out.println("Fæå¨çå±æ¬¡: "+tree.level("F"));
System.out.println("è¿æ£µäºåæ çé«åº¦: "+tree.height());
System.out.println("--------------------------------------");
tree.reflect();
System.out.println("交æ¢æ¯ä¸ªèç¹çå©åèç¹å......");
System.out.println("ååºéåäºåæ ç»æ: ");
tree.preOrder(tree);
System.out.println();
System.out.println("ä¸åºéåäºåæ ç»æ: ");
tree.inOrder(tree);
System.out.println();
System.out.println("ååºéåäºåæ ç»æ: ");
tree.postOrder(tree);
System.out.println();
System.out.println("å±æ¬¡éåäºåæ ç»æ: ");
tree.LayerOrder(tree);
System.out.println();
System.out.println("Fæå¨çå±æ¬¡: "+tree.level("F"));
System.out.println("è¿æ£µäºåæ çé«åº¦: "+tree.height());
}