두 갈래 찾기 트 리 간단 실현

트 리 찾기 는 데이터 구조 로 다양한 동적 집합 작업 을 지원 합 니 다. 임의의 키워드 노드 를 찾 고 최대 노드 를 되 돌려 주 며 최소 노드 를 되 돌려 주 고 전구 와 후계 결점 을 되 돌려 주 며 삽입 과 삭 제 를 지원 합 니 다. 하위 사전 으로 도 사용 할 수 있 고 우선 대기 열 로 도 사용 할 수 있 습 니 다.
    이 진 트 리 는 기본 데이터 구조 에 속 하고 이 진 트 리 에서 실 행 된 절 본 작업 의 시간 은 나무의 높이 와 정비례 한다.다음은 이 진 트 리 찾기 의 간단 한 실현 으로 학습 에 참고 할 수 있 습 니 다.

  
  
  
  
  1. /** 
  2.  *    
  3. * @author Jayson
  4.  */ 
  5. public class TwoSearchTree<T> 
  6.     private class Node 
  7.     { 
  8.         private int key;        //  
  9.         private Object data;    //  
  10.         private Node left;      //  
  11.         private Node right;     //  
  12.         private Node parent;    //  
  13.         public Node(int key,Object data,Node parent,Node left,Node right) 
  14.         { 
  15.             this.key=key; 
  16.             this.data=data; 
  17.             this.parent=parent; 
  18.             this.left=left; 
  19.             this.right=right; 
  20.         } 
  21.     } 
  22.  
  23.     private Node root; 
  24.     private int height; 
  25.     public TwoSearchTree(int key){ 
  26.      
  27.         this.root=new Node(key,null,null,null,null); 
  28.     } 
  29.  
  30.     public TwoSearchTree(int key,T data) 
  31.     { 
  32.         this.root=new Node(key,data,null,null,null);     
  33.     } 
  34.  
  35.     public Node getNode(Node current,int key) 
  36.     { 
  37.         if(current==null||key==current.key) 
  38.         { 
  39.             return current; 
  40.         } 
  41.         if(key<current.key) 
  42.         { 
  43.             return getNode(current.left,key); 
  44.         } 
  45.         else 
  46.         { 
  47.             return getNode(current.right,key); 
  48.         } 
  49.     } 
  50.     /* 
  51.      *  
  52.      */ 
  53.     public Node getNodeByKey(int key) 
  54.     { 
  55.         return getNode(root,key); 
  56.     } 
  57.      
  58.     public T getData(Node node) 
  59.     { 
  60.         return (T)node.data; 
  61.     } 
  62.     /* 
  63.      *    
  64.      */ 
  65.     public Node getMax(Node current) 
  66.     { 
  67.         if(current.right==null
  68.         { 
  69.             return current; 
  70.         } 
  71.         else 
  72.         { 
  73.             return getMax(current.right); 
  74.         } 
  75.     } 
  76.     /* 
  77.      *    
  78.      */ 
  79.     public Node getMin(Node current) 
  80.     { 
  81.         if(current.left==null
  82.         { 
  83.             return current; 
  84.         } 
  85.         else 
  86.         { 
  87.             return getMin(current.left); 
  88.         } 
  89.     } 
  90.     /* 
  91.      *    
  92.      */ 
  93.     public Node getSucceed(Node current){ 
  94.         if(current.right!=null
  95.         { 
  96.             return getMin(current.right); 
  97.         } 
  98.         Node now=current.parent; 
  99.         while(now!=null&&current==now.right) 
  100.         { 
  101.             current=now; 
  102.             now=now.parent; 
  103.         } 
  104.         return now; 
  105.     } 
  106.     /* 
  107.      *    
  108.      */ 
  109.     public void addElement(int key,T data) 
  110.     { 
  111.         if(root==null
  112.         { 
  113.             root=new Node(key,data,null,null,null); 
  114.         } 
  115.         else 
  116.         { 
  117.             Node current=root; 
  118.             while(current!=null
  119.             { 
  120.                 if(key<current.key) 
  121.                 { 
  122.                     if(current.left==null
  123.                     { 
  124.                         Node newNode=new Node(key,data,current,null,null); 
  125.                         current.left=newNode; 
  126.                         break
  127.                     } 
  128.                     current=current.left; 
  129.                 } 
  130.                 else 
  131.                 { 
  132.                     if(current.right==null
  133.                     { 
  134.                         Node newNode=new Node(key,data,current,null,null); 
  135.                         current.right=newNode; 
  136.                         break
  137.                     } 
  138.                     current=current.right; 
  139.                 } 
  140.             } 
  141.         } 
  142.     } 
  143.     /* 
  144.      *    
  145.      */ 
  146.     public Node delElement(Node node) 
  147.     { 
  148.         Node rear=null
  149.         Node next=null
  150.         if(node.left==null||node.right==null
  151.         { 
  152.             rear=node; 
  153.         } 
  154.         else 
  155.         { 
  156. // ,
  157.             rear=getSucceed(node); 
  158.         } 
  159.         if(rear.left!=null
  160.         { 
  161.             next=rear.left; 
  162.         } 
  163.         else 
  164.         { 
  165.             next=rear.right; 
  166.         } 
  167.         if(next!=null
  168.         { 
  169.             next.parent=rear.parent; 
  170.         } 
  171.         if(rear.parent==null)    
  172.         { 
  173.             root=next; 
  174.         } 
  175.         else if(rear==rear.parent.left) 
  176.         { 
  177.             rear.parent.left=next; 
  178.         } 
  179.         else 
  180.         { 
  181.             rear.parent.right=next; 
  182.         } 
  183.         if(rear!=next)   
  184.         { 
  185.             node.key=rear.key; 
  186.             node.data=rear.data; 
  187.         } 
  188.         return rear; 
  189.     } 
  190.     /* 
  191.      *    
  192.      */ 
  193.     public int deep(Node node) 
  194.         if(node==null
  195.         { 
  196.             return 0
  197.         } 
  198.         if(node.left==null&&node.right==null
  199.         { 
  200.             return 1
  201.         } 
  202.         else 
  203.         { 
  204.             int deep1=deep(node.left); 
  205.             int deep2=deep(node.right); 
  206.             int deep=deep1>deep2 ? deep1:deep2; 
  207.             return deep+1
  208.         }    
  209.     } 
  210.  
  211.     public int deep(){ 
  212.         return deep(root); 
  213.     } 
  214.      
  215.     public void browseAllElement(Node node) 
  216.     {    
  217.         //
  218.         if(node!=null
  219.         { 
  220.             System.out.print("("+node.key+","+node.data+")"+" "); 
  221.             browse(node.left); 
  222.             browse(node.right); 
  223.         } 
  224.     } 
  225.     public void browseAllElement() 
  226.     { 
  227.         browseAllElement(root); 
  228.         System.out.println(""); 
  229.     } 
  1. /*
  2. *
  3. */
  4.     public static void main(String[] star){ 
  5.         TwoSearchTree<String> tst=new TwoSearchTree<String>(8,"d"); 
  6.         tst.addElement(12,"e"); 
  7.         tst.addElement(2,"a"); 
  8.         tst.addElement(4,"b"); 
  9.         tst.addElement(14,"f"); 
  10.         tst.addElement(16,"g"); 
  11.         tst.addElement(6,"c"); 
  12.         tst.addElement(1,"h"); 
  13.         tst.addElement(11,"i"); 
  14.         tst.delElement(tst.getNodeByKey(8)); // 8
  15.         tst.browseAllElement(); 
  16.         System.out.println(tst.deep()); 
  17.     } 

좋은 웹페이지 즐겨찾기