【Javaデータ構造】ツリー

コア:ツリー内のノードごとに最大2つのサブノードのみ(t>=0&&t<=2)
次に、2つのフォークソートツリー(左の子供は親ノードより小さく、右の子供は親ノードより大きい)を実装します.
1.ノードの挿入
核心思想:
(1)ノードが存在しない場合は,直接挿入する.
(2)ルートノードから対応するノード、すなわち新しいノードの親ノードを検索し、親ノードが見つかった場合、新しいノードの値に基づいて、新しいノードが左サブノードに接続されているか右サブノードに接続されているかを決定します.
2.ノードの検索
核心思想:
ルートノードから検索を開始し、親ノード値よりもノード値が小さい場合は左サブツリーを検索します.そうでない場合は右サブツリーを検索し、検索されるまでノードが存在しない場合はnullを返します.
3.ノードの変更
核心思想:まずノードを探して、相応のノードを見つけてから、修正します(キーワードは修正しないでください).
4.ツリーを巡る
二叉木を巡るには、先序遍歴、中序遍歴、後序遍歴の3つの方法があります.
≪優先パス|Primary遍歴|emdw≫:ノードにアクセスし、ノードの左サブツリーを遍歴し、ノードの右サブツリーを遍歴します.
中順遍歴:ノードの左サブツリーを遍歴し、ノードにアクセスし、ノードの右サブツリーを遍歴します.
後順ループ:ノードの左サブツリーをループし、ノードの右サブツリーをループし、ノードにアクセスします.
ツリーの各ノードモデル:

package cn.edu.Tree;

public class Node {
		//   
	    private int keyData;
	    
	    //    
	    private int otherData;
	    
	    //    
	    private Node leftNode;
	    
	    //    
	    private Node rightNode;


		public Node(int keyData, int otherData) {
			super();
			this.keyData = keyData;
			this.otherData = otherData;
		}


		public int getKeyData() {
			return keyData;
		}


		public void setKeyData(int keyData) {
			this.keyData = keyData;
		}


		public int getOtherData() {
			return otherData;
		}


		public void setOtherData(int otherData) {
			this.otherData = otherData;
		}


		public Node getLeftNode() {
			return leftNode;
		}


		public void setLeftNode(Node leftNode) {
			this.leftNode = leftNode;
		}


		public Node getRightNode() {
			return rightNode;
		}


		public void setRightNode(Node rightNode) {
			this.rightNode = rightNode;
		}
	    
	    //    
		public void display(){
			System.out.println(this.keyData+" "+this.otherData);
		}
}

ツリーのモデル:

package cn.edu.Tree;

public class Tree {
		// 
	    private Node root=null;
	    
	    //    
	    public void insert(int keyData,int otherData){
	    	Node newNode=new Node(keyData,otherData);
	    	
	    	//       
	    	if(root==null){
	    		root=newNode;
	    	}else{
	    	  Node current=root;
	    	  Node parent;
	    	  while(true){
	    	    parent=current;
		    if(keyData<current.getKeyData()){
			    current=current.getLeftNode();
			    if(current==null){
			    	parent.setLeftNode(newNode);
			    	break;
			    }
			   }else{
			    current=current.getRightNode();
			    if(current==null){
			     parent.setRightNode(newNode);
			    	break;
			    }
			   }
	    		}
	    	}
	    }
	    
	    //    
	    public Node find(int keyData){
	    	Node current=root;
	    	while(current.getKeyData()!=keyData){
	    		if(keyData<current.getKeyData()){
	    			current=current.getLeftNode();
	    		}else{
	    			current=current.getRightNode();
	    		}
	    		
	    		if(current==null){
	    			return null;
	    		}
	    	}
	    	return current;
	    }
	    
	    //    
	    public void delete(int keyData){
	    	
	    }
	    
	    //    
	    public void change(int keyData,int otherData){
	    	Node findNode=find(keyData);
	    	findNode.setOtherData(otherData);
	    }
	    
	    //    
	    public void preOrder(Node node){
	    	if(node!=null){
	    		node.display();
	    		preOrder(node.getLeftNode());
	    		preOrder(node.getRightNode());
	    	}
	    }
	    
	    //    
	    public void inOrder(Node node){
	    	if(node!=null){
	    		inOrder(node.getLeftNode());
	    		node.display();
	    		inOrder(node.getRightNode());
	    	}
	    }
	    
	    //    
	    public void endOrder(Node node){
	    	if(node!=null){
	    		endOrder(node.getLeftNode());
	    		endOrder(node.getRightNode());
	    		node.display();
	    	}
	    }
	    
	    public Node getRoot(){
	    	return this.root;
	    }
}

遍歴テスト:

package cn.edu.Tree;

public class TestTree {
		public static void main(String[] args) {
			Tree tree=new Tree();
			tree.insert(80, 80);
			tree.insert(49, 49);
			tree.insert(42, 42);
			tree.insert(30, 30);
			tree.insert(45, 45);
			tree.insert(90, 90);
			tree.insert(150, 150);
			tree.insert(130, 130);
			tree.insert(82, 82);
			
			
			tree.preOrder(tree.getRoot());
			/*       
			    80 80
				49 49
				42 42
				30 30
				45 45
				90 90
				82 82
				150 150
				130 130
			 * */
			System.out.println("-----------------------");
			tree.inOrder(tree.getRoot());
			/*      
			    30 30
				42 42
				45 45
				49 49
				80 80
				82 82
				90 90
				130 130
				150 150
			 * */
			System.out.println("-----------------------");
			tree.endOrder(tree.getRoot());
			/*      
			    30 30
				45 45
				42 42
				49 49
				82 82
				130 130
				150 150
				90 90
				80 80


			 * */
			
			/*tree.change(2, 22);
			
			Node findNode=tree.find(2);
			findNode.display();*/
		}
}

転載は出典を明記してください.http://blog.csdn.net/acmman/article/details/50487767