二叉検索ツリーは簡単に実現できます.
検索ツリーは、任意のキーワードノードを検索し、最大ノードに戻り、前駆者と後継者のノードに戻り、挿入と削除を含む様々な動的なセット動作をサポートするデータ構造であり、優先キューとしても使用できる.
二叉ルックアップツリーは基本的なデータ構造であり、二叉ルックアップツリーで実行される節本動作の時間はツリーの高さに比例する.以下は二叉検索ツリーの簡単な実現で、学習の参考になります.
二叉ルックアップツリーは基本的なデータ構造であり、二叉ルックアップツリーで実行される節本動作の時間はツリーの高さに比例する.以下は二叉検索ツリーの簡単な実現で、学習の参考になります.
- /**
- *
- * @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());
- }
- }