두 갈래 찾기 트 리 간단 실현
24897 단어 데이터 구조두 갈래 찾기 트 리
이 진 트 리 는 기본 데이터 구조 에 속 하고 이 진 트 리 에서 실 행 된 절 본 작업 의 시간 은 나무의 높이 와 정비례 한다.다음은 이 진 트 리 찾기 의 간단 한 실현 으로 학습 에 참고 할 수 있 습 니 다.
- /**
- *
- * @author Jayson
- */
- public class TwoSearchTree<T>
- {
- private class Node
- {
- private int key; //
- private Object data; //
- private Node left; //
- private Node right; //
- private Node parent; //
- public Node(int key,Object data,Node parent,Node left,Node right)
- {
- this.key=key;
- this.data=data;
- this.parent=parent;
- this.left=left;
- this.right=right;
- }
- }
-
- private Node root;
- private int height;
- public TwoSearchTree(int key){
-
- this.root=new Node(key,null,null,null,null);
- }
-
- public TwoSearchTree(int key,T data)
- {
- this.root=new Node(key,data,null,null,null);
- }
-
- public Node getNode(Node current,int key)
- {
- if(current==null||key==current.key)
- {
- return current;
- }
- if(key<current.key)
- {
- return getNode(current.left,key);
- }
- else
- {
- return getNode(current.right,key);
- }
- }
- /*
- *
- */
- public Node getNodeByKey(int key)
- {
- return getNode(root,key);
- }
-
- public T getData(Node node)
- {
- return (T)node.data;
- }
- /*
- *
- */
- public Node getMax(Node current)
- {
- if(current.right==null)
- {
- return current;
- }
- else
- {
- return getMax(current.right);
- }
- }
- /*
- *
- */
- public Node getMin(Node current)
- {
- if(current.left==null)
- {
- return current;
- }
- else
- {
- return getMin(current.left);
- }
- }
- /*
- *
- */
- public Node getSucceed(Node current){
- if(current.right!=null)
- {
- return getMin(current.right);
- }
- Node now=current.parent;
- while(now!=null&¤t==now.right)
- {
- current=now;
- now=now.parent;
- }
- return now;
- }
- /*
- *
- */
- public void addElement(int key,T data)
- {
- if(root==null)
- {
- root=new Node(key,data,null,null,null);
- }
- else
- {
- Node current=root;
- while(current!=null)
- {
- if(key<current.key)
- {
- if(current.left==null)
- {
- Node newNode=new Node(key,data,current,null,null);
- current.left=newNode;
- break;
- }
- current=current.left;
- }
- else
- {
- if(current.right==null)
- {
- Node newNode=new Node(key,data,current,null,null);
- current.right=newNode;
- break;
- }
- current=current.right;
- }
- }
- }
- }
- /*
- *
- */
- public Node delElement(Node node)
- {
- Node rear=null;
- Node next=null;
- if(node.left==null||node.right==null)
- {
- rear=node;
- }
- else
- {
- // ，
- rear=getSucceed(node);
- }
- if(rear.left!=null)
- {
- next=rear.left;
- }
- else
- {
- next=rear.right;
- }
- if(next!=null)
- {
- next.parent=rear.parent;
- }
- if(rear.parent==null)
- {
- root=next;
- }
- else if(rear==rear.parent.left)
- {
- rear.parent.left=next;
- }
- else
- {
- rear.parent.right=next;
- }
- if(rear!=next)
- {
- node.key=rear.key;
- node.data=rear.data;
- }
- return rear;
- }
- /*
- *
- */
- public int deep(Node node)
- {
- if(node==null)
- {
- return 0;
- }
- if(node.left==null&&node.right==null)
- {
- return 1;
- }
- else
- {
- int deep1=deep(node.left);
- int deep2=deep(node.right);
- int deep=deep1>deep2 ? deep1:deep2;
- return deep+1;
- }
- }
-
- public int deep(){
- return deep(root);
- }
-
- public void browseAllElement(Node node)
- {
- //
- if(node!=null)
- {
- System.out.print("("+node.key+","+node.data+")"+" ");
- browse(node.left);
- browse(node.right);
- }
- }
- public void browseAllElement()
- {
- browseAllElement(root);
- System.out.println("");
- }
- /*
- *
- */
- public static void main(String[] star){
- TwoSearchTree<String> tst=new TwoSearchTree<String>(8,"d");
- tst.addElement(12,"e");
- tst.addElement(2,"a");
- tst.addElement(4,"b");
- tst.addElement(14,"f");
- tst.addElement(16,"g");
- tst.addElement(6,"c");
- tst.addElement(1,"h");
- tst.addElement(11,"i");
- tst.delElement(tst.getNodeByKey(8)); // 8
- tst.browseAllElement();
- System.out.println(tst.deep());
- }
- }
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
정수 반전Udemy 에서 공부 한 것을 중얼거린다 Chapter3【Integer Reversal】 (예) 문자열로 숫자를 반전 (toString, split, reverse, join) 인수의 수치 (n)가 0보다 위 또는 ...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
