Javaで二叉木の非再帰の前序、中序、後序遍歴アルゴリズムを実現する

4533 ワード

      2   , 

package BinaryTree;

public class TreePoint  {
	public String name;
	private TreePoint leftNode;
	private TreePoint rightNode;
	private TreePoint parent;
	private boolean visit=false;
	
	public TreePoint(String name){
		this.name = name;
	}
	
	public TreePoint(String name,TreePoint leftNode,TreePoint rightNode){
		this.name = name;
		this.leftNode = leftNode;
		this.rightNode = rightNode;
	}
	
	public TreePoint getLeftNode(){
		if(leftNode!= null&&leftNode.isVisited()){
			return null;
		}
		return leftNode;
	}
	
	public void setLeftNode(TreePoint leftNode){
		this.leftNode = leftNode;
	}
	
	public TreePoint getRightNode(){
		if(rightNode!= null&&rightNode.isVisited()){
			return null;
		}
		return rightNode;
	}
	
	public void setRightNode(TreePoint rightNode){
		this.rightNode= rightNode;
	}
	
	public boolean isVisited(){
		return visit;
	}
	
	public void setVisit(boolean visit){
		this.visit = visit;
	}
	
	public TreePoint getParent(){
		return parent;
	}
	
	public void setParent(TreePoint parent){
		this.parent = parent;
	}
	
	public String toString(){
		setVisit(true);
		return name;
	}
}
package BinaryTree;

import java.util.Stack;

public class TreeTest {
	private static TreePoint root=null;
	
	public static void TreeInit(){
		TreePoint A = new TreePoint("A");
		root = A;
		TreePoint B = new TreePoint("B");
		TreePoint C = new TreePoint("C");
		A.setLeftNode(B);
		A.setRightNode(C);
		B.setParent(A);
		C.setParent(A);
		TreePoint D = new TreePoint("D");
		TreePoint E = new TreePoint("E");
		B.setLeftNode(D);
		B.setRightNode(E);
		D.setParent(B);
		E.setParent(B);
		TreePoint F = new TreePoint("F");
		TreePoint G = new TreePoint("G");
		C.setLeftNode(F);
		C.setRightNode(G);
		F.setParent(C);
		G.setParent(C);
		TreePoint H = new TreePoint("H");
		TreePoint I = new TreePoint("I");
		E.setLeftNode(H);
		E.setRightNode(I);
		H.setParent(E);
		I.setParent(E);
		TreePoint J = new TreePoint("J");
		G.setRightNode(J);
		J.setParent(G);
	}
	
	public static void check(TreePoint root,String SortName){
		if(root==null){
			System.out.println("  ");
			System.exit(0);
		}
		System.out.println(SortName);
	}
	
	public void testFirst(){
		 check(root,"    ");
		 TreePoint next = root;
		 while(next!=null){
			 if(!next.isVisited()){
				 System.out.print(next+" ");
			 }
			 TreePoint flag = next.getLeftNode();
			 if(flag==null){
				 flag = next.getRightNode();
				 if(flag == null){
					 next = next.getParent();
					 continue;
				 }
				 next = flag;
				 continue;
			 }
			 next = flag;
		 }
	}
	
	public void testMiddle(){
		check(root,"    ");
		TreePoint next = root;
		while(next!=null){
			TreePoint flag = next.getLeftNode();
			if(flag==null){  //          ,      
				if(!next.isVisited()){
					System.out.print(next+" ");
				}
				flag=next.getRightNode();
				if(flag==null){
					next = next.getParent();
				}else{
					next = flag;
				}
			}else{
				next = flag;
			}
		}
	}
	
	public void testLast(){
		check(root,"    ");
		TreePoint next = root;
		while(next!= null){
			TreePoint flag = next.getLeftNode();
			if(flag==null){
				flag = next.getRightNode();
				if(flag==null){
					if(!next.isVisited()){
						System.out.print(next+" ");
					}
					next = next.getParent();
				}else{
					next = flag;
				}
			}else{
				next = flag;
			}
		}
	}
	
	public void Middle(){
		Stack s = new Stack();
		check(root,"    ");
		TreePoint next=root;
		while(next!=null||!s.isEmpty()){
			if(next!=null){
				s.push(next);
				next = next.getLeftNode();
			}else{
				next = (TreePoint) s.pop();
				System.out.print(next+" ");
				next = next.getRightNode();
			}
		}
	}
	
	public void Last(){
		Stack s = new Stack();
		TreePoint next = root;
		while(next!=null||!s.isEmpty()){
			while(next!=null){
				s.push(next);
				next = next.getLeftNode();
			}
				next = s.pop();
				if(next.getRightNode()==null){
					System.out.print(next+" ");
				}else{
					next = next.getRightNode();
			}
		}
	}
	
	public static void main(String args[]){
		TreeTest tt = new TreeTest();
		tt.TreeInit();
	//	tt.testFirst();
	//	tt.testMiddle();
//		tt.testLast();
//		tt.Middle();
		tt.Last();
		
	}

}