자바 이 진 트 리 관련 코드 구현 - 데이터 구조

/*1.    ：2014-11-5
 *2.   ：  
 *3.   ：  
 *3.    ：    
 *4.    ：    
 * **/
package Tree;
import Tree.node;
public interface TreeNode {
// class Node {};
 // 1.           
 int GetNodeNum(node root);
 // 2.        
 int GetDepth(node root);
 // 3.     ，    ，    
 void PreOrderTraverse(node root);
 void InOrderTraverse(node root);
 void PostOrderTraverse(node root);
 // 4.       （       ，    ）
 void LevelTraverse(node root);
// 5.                
// 6.      K      
// 7.             
// 8.              
// 9.              
// 10.        
// 11.                   
// 12.             
// 13.                    
// 14.             
}

package Tree;
//*    。
public class node {
 public Object data; //        。
 public node leftChild; //          。
 public  node rightChild; //          。
 public node(Object value) {
  this.data = value;
  leftChild = null;
  rightChild = null;
 }
}

/*1.    ：2014-11-13
 *2.   ：  
 *3.   ：  
 *3.    ：        
 *4.    ：    
 * **/
package Tree;
import Tree.node;
import Tree.ArrayQueue;
public class BinaryTreeNode implements TreeNode {
 private node root; //    
 BinaryTreeNode() {
  root = null;
 }
 // 1.           
 //     ：
 // （1）       ，     0
 // （2）        ，        =         +         + 1
 public int GetNodeNum(node root) {
  if (root == null) //     
   return 0;
  return GetNodeNum(root.rightChild) + GetNodeNum(root.leftChild) + 1;
 };
 // 2.        
 //     ：
 // （1）       ，       0
 // （2）        ，       = max(     ，      ) + 1
 public int GetDepth(node root) {
  if (root == null) //     
   return 0;
  int depthLeft = GetDepth(root.leftChild);
  int depthRight = GetDepth(root.rightChild);
  return depthLeft > depthRight ? (depthLeft + 1) : (depthRight + 1);
 };
 // 3.     ，    ，    
 //         ：
 // （1）       ，   
 // （2）        ，     ，       ，       
 // private void Visit(Node root){    
 // if (root == null)
 // return ;
 // System.out.print("......");
 // Visit(root.leftChild); //        
 // Visit(root.rightChild); //        
 // };
 public void PreOrderTraverse(node root) {
  if (root == null)
   return;
  System.out.print(root.data + " ");
  PreOrderTraverse(root.leftChild);
  PreOrderTraverse(root.rightChild);
  // Visit(root);     
 };
 //         
 // （1）       ，   。
 // （2）        ，       ，     ，       
 public void InOrderTraverse(node root) {
  if (root == null)
   return;
  InOrderTraverse(root.leftChild);
  System.out.print(root.data + " ");
  InOrderTraverse(root.rightChild);
  //
 };
 //         
 // （1）       ，   
 // （2）        ，       ，       ，     
 public void PostOrderTraverse(node root) {
  PostOrderTraverse(root.leftChild);
  PostOrderTraverse(root.rightChild);
  System.out.print(root.data + " ");
 };
 // 4.       （       ，    ）
 //      ，        。
 //       ，      ：      ，  ，         
 //     ，      。
 public void LevelTraverse(node root) {
  ArrayQueue q = new ArrayQueue();
  if (root == null)
   return;
  q.enQueue(root);
  while (!q.isEmpty()) {
   root.data = q.getFront();
   q.deQueue();
   System.out.print(root.data + " "); //     
   if (root.leftChild != null)
    q.enQueue(root.leftChild);
   if (root.rightChild != null)
    q.enQueue(root.rightChild);
  }
  return;
 }
// 5.      K      
//     ：
// （1）         k<1  0
// （2）          k==1，  1
// （3）         k>1，      k-1          k-1       
 int GetNodeNumKthLevel(node root, int k)  
 {  
     if(root == null || k < 1)  
         return 0;  
     if(k == 1)  
         return 1;  
     int numLeft = GetNodeNumKthLevel(root.leftChild, k-1); //     k-1        
     int numRight = GetNodeNumKthLevel(root.rightChild, k-1); //     k-1        
     return (numLeft + numRight);  
 }  
// 6.             
//     ：
// （1）       ，  0
// （2）               ，  1
// （3）        ，          ，                        
 int GetLeafNodeNum(node root)  
 {  
     if(root == null)  
         return 0;  
     if(root.leftChild == null && root.rightChild == null)  
         return 1;  
     int numLeft = GetLeafNodeNum(root.leftChild); //             
     int numRight = GetLeafNodeNum(root.leftChild); //             
     return (numLeft + numRight);  
 }   
// 7.              
//        。                         。
//     ：
// （1）          ，   
// （2）           ，      ，   
// （3）           ，                  ，     
 boolean StructureCmp(node root1, node root2)  
 {  
     if(root1 == null && root2 == null) //    ，     
         return true;  
     else if(root1 == null || root2 == null) //      ，     ，     
         return false;  
     boolean resultLeft = StructureCmp(root1.leftChild,root2.leftChild); //           
     boolean resultRight = StructureCmp(root1.rightChild, root2.rightChild); //          
     return (resultLeft && resultRight);  
 }   
// 8.              
//     ：
// （1）       ，   
// （2）        ，           AVL                 1，   ，     
 boolean IsAVL(node root, int  height)  
 {  
     if(root == null) //   ，     
     {  
         height = 0;  
         return true;  
     }  
     int heightLeft = 0;  
     boolean resultLeft = IsAVL(root.leftChild, heightLeft);  
     int heightRight = 0;  
     boolean resultRight = IsAVL(root.rightChild, heightRight);  
     if(resultLeft && resultRight && abs(heightLeft - heightRight) <= 1) //          AVL，         1，     
     {  
         height = max(heightLeft, heightRight) + 1;  
         return true;  
     }  
     else  
     {  
         height = max(heightLeft, heightRight) + 1;  
         return false;  
     }  
 }
 private int max(int heightLeft, int heightRight) {
  return heightLeft>heightRight?heightLeft:heightRight;
 }
 private int abs(int i) {
  if(i>0) return i;
  else return -i;
 }  
 //9.         
 public node insert(node root, Object x)
 {
     node p = null ;
     p.data=x;
     p.leftChild=null;
     p.rightChild=null;
     if(root == null){
         root = p;    
     }    
       
     else if(root.leftChild== null){
      root.leftChild = insert(root.leftChild,x);    
     }
     else if(root.rightChild== null){
         root.rightChild= insert(root.rightChild,x);    
     }
     return root;
 }
}

package Tree;
/**
 *
 * @author   
 */
public class ArrayQueue implements Queue {
    private Object[] data;
    private int front;
    private int rear;
    public ArrayQueue(int capacity) {
        this.data = new Object[capacity];
        this.front = this.rear = 0;
    }
    public ArrayQueue() {
        this(1024);
    }
    public void clear() {
        this.front = this.rear = 0;
    }
    public boolean isEmpty() {
        return this.front == this.rear;
    }
    public Object getFront() {
        if (isEmpty()) {
            throw new UnsupportedOperationException("    ");
        }
        return data[front];
    }
    public void enQueue(Object o) {
        if (isFull()) {
            throw new UnsupportedOperationException("    ");
        }
        this.data[rear++] = o;
        rear %= data.length;
    }
    public Object deQueue() {
        throw new UnsupportedOperationException("Not supported yet."); //To change body of generated methods, choose Tools | Templates.
    }
    private boolean isFull() {
        return ((rear + 1) % data.length) == front;
    }
}