ターゲット

インプリメンテーション

public class Node{

int key;

int data;

Node lchild=null;

Node rchild=null;

public Node(int key,int data)

{

	this.key=key;

	this.data=data;

	

}

}

public class BinaryTree {

	 Node root=null;

	 public void add(int key,int data)

	 {

		 Node node=new Node(key,data);

		 if (root==null)

			 root=node;

		 else 

		 {

			 Node current=root;

			 Node pre=null;

			 while (true)

			 {

				 if (key<current.key)

				 {

					 pre=current;

					 current=current.lchild;

					 if (current==null)

					 {

						 pre.lchild=node;

						 break;

					 }

						 

				 }

				 else 

				 {	 pre=current;

				 current=current.rchild;

				 if (current==null)

					 {

					 pre.rchild=node;

					 break;

					 }

					 

				 }

					 

			 }

			 

		 }

			 

		 

	 }

	 

	 public Node findNode(int key)

	 {

		 Node current=root;

		 while (current!=null)

		 {

			 if (current.key==key)

				 return current;

			 else if (key<current.key)

				 current=current.lchild;

			 else current=current.rchild;

		 }

		 return null;

	 }

	 

	 public int findElement(int key)

	 {

		 Node current=root;

		 while (current!=null)

		 {

			 if (current.key==key)

				 return current.data;

			 else if (key<current.key)

				 current=current.lchild;

			 else current=current.rchild;

		 }

		 return 0;

	 }

	 

	 public boolean delete (int key)

	 {

		 Node current=root;

		 boolean isleftchild=false;

		 Node parent=root;

		 Node currentdouble=null;

		 

		 while (current!=null)

			 

		 {

			 if (root.key==key)

			 {

				 root=null;

				 return true;

			 }

			 

			 if (current.key==key)

			 {

				

				 // ， 

				 if (current.lchild==null && current.rchild==null)

				 {

					 if (isleftchild=true)

						 parent.lchild=null;

					 else parent.rchild=null;

					 return true;

					

				 }

				// ， 

				 if (current.lchild==null && current.rchild!=null)

				 {

					 if (isleftchild=true)

						 parent.lchild=current.rchild;

					 else parent.rchild=current.lchild;

					 return true;

					

				 }

				 

					// ， 

				 if (current.lchild!=null && current.rchild==null)

				 {

					 if (isleftchild=true)

						 parent.lchild=current.lchild;

					 else parent.rchild=current.lchild;

					

					 return true;

					

					

				 }

				 // ， ， ， 

				 if (current.lchild!=null && current.rchild!=null)

				 {

					 if (isleftchild=true)

						 parent.lchild=current.lchild;

					 else parent.rchild=current.lchild;

					

					 currentdouble=current.lchild;

					 Node rparent=null;

					 while (currentdouble!=null)

					 {

						 rparent=currentdouble;

						 currentdouble=currentdouble.rchild;

					 }

					 rparent.rchild=current.rchild;

					return true;

				 }

				 

				 

			 }

			 else if (key<current.key)

			 {   parent=current;

				 current=current.lchild;

				 isleftchild=true;

				 

			 }

			 else {

				 parent=current;

				 current=current.rchild;

				 isleftchild=false;

			 }

				 

			 

		 }

		 

		 return false;

	 }

	 

	 // 

	 public void preorder(Node node)

	 {

		 if (node!=null)

		 {

			 System.out.println(node.data);

			 preorder(node.lchild);

			 preorder(node.rchild);

			 

		 }

	 }

	 // 

	 public void midorder(Node node)

	 {

		 if (node!=null)

		 {

			 midorder(node.lchild);

			 

			 System.out.println(node.data);

		

			 midorder(node.rchild);

			 

		 }

	 }

	 

	 // 

	 public void lastorder(Node node)

	 {

		 if (node!=null)

		 {

			 lastorder(node.lchild);

			 lastorder(node.rchild);

			 System.out.println(node.data);

		

			

			 

		 }

	 }

	 

	 



}

public class Test {

	public static void main(String[] args)

	{

		BinaryTree bt=new BinaryTree();

		bt.add(100, 100);

		bt.add(50, 50);

		bt.add(150, 150);

		bt.add(10, 10);

		bt.add(60, 60);

		bt.add(120, 120);

		bt.add(180, 180);

		System.out.println(bt.findElement(50));

		

		System.out.println(bt.root.data);

		bt.preorder(bt.root);

		System.out.println(bt.root.key);

		System.out.println(bt.delete(50));

		bt.preorder(bt.root);

		

		

	}



}

参考資料