学習ログ---再帰的でないツリーカーソルループ(前後の階層)

実装:

// 
public class MyBiTree {

	private MyBiTreeNode  root;// 
	
	
	
	MyBiTree()
	{
		this.root = null;
	}
	
	MyBiTree(Object data,MyBiTree left,MyBiTree right)
	{
		MyBiTreeNode l,r;
		if(left==null)
		{
			l = null;
		}
		else
		{
		   l=left.root; 
		}
		
		if(right==null)
		{
			r = null;
		}
		else
		{
			r = right.root;
		}
		
		this.root = new MyBiTreeNode(data,l,r);
	}
	
	// 
	public static void printBiTree(MyBiTreeNode root,int level)
	{
		if(root!=null)
		{
			printBiTree(root.getRightChild(),level+1);
			
			if(level!=0)
			{
				// 6*（level-1） 
				for(int i=0;i<6*(level-1);i++)
				{
					System.out.print(" ");
				}
				System.out.print("-----");
			}
			System.out.println(root.getData());
		
		    printBiTree(root.getLeftChild(),level+1);
		}
	}
	
	// 
	public static MyBiTreeNode getTreeNode(Object data,MyBiTreeNode left,MyBiTreeNode right)
	{
		MyBiTreeNode node = new MyBiTreeNode(data,left,right);
		return node;
	}
	
	// 
	public static MyBiTreeNode search(MyBiTreeNode root,Object obj)
	{
		MyBiTreeNode node=null;
		if(root==null)
		{
			return null;
		}
		if(root.getData().equals(obj))
		{
			return root;
		}
		if(root.getLeftChild()!=null)
		{
			node = search(root.getLeftChild(),obj);
		}
		if(root.getRightChild()!=null)
		{
			node = search(root.getRightChild(),obj);
		}
		
		return node;
	}
}

ツリーノードクラス

// 
public class MyBiTreeNode {

	private MyBiTreeNode leftChild; //  
	private MyBiTreeNode rightChild; //  
	private Object data; //  

	MyBiTreeNode() {
		this.leftChild = null;
		this.rightChild = null;
	}
    
	MyBiTreeNode(Object data,MyBiTreeNode leftNode,MyBiTreeNode rightNode)
	{
		this.data = data;
		this.leftChild = leftNode;
		this.rightChild = rightNode;
	}
	
	
	public MyBiTreeNode getLeftChild() {
		return leftChild;
	}

	public void setLeftChild(MyBiTreeNode leftChild) {
		this.leftChild = leftChild;
	}

	public MyBiTreeNode getRightChild() {
		return rightChild;
	}

	public void setRightChild(MyBiTreeNode rightChild) {
		this.rightChild = rightChild;
	}

	public Object getData() {
		return data;
	}

	public void setData(Object data) {
		this.data = data;
	}
}

カーソルループクラス:
resetメソッドは初期化です.
スタックに要素がない場合、isCompleteはfalse、終了フラグです.
このうちnextメソッドとは、印刷対象の次のノードを取得し、nextメソッドで取得したノードが処理するノードである.

public class MyBiTreeIterator {
   
	MyBiTreeNode root; // 
	MyBiTreeNode curr;//  ；
	boolean isComplete;  // 
	
	MyBiTreeIterator()
	{
		
	}
	、
	MyBiTreeIterator(MyBiTreeNode root)
	{
		this.root = root;
	}
	
	public void reset()
	{
		
	}
	
	public void next()
	{
	  	
	}
	
	public boolean endOfBiTree()
	{
	  return isComplete;	
	}
	
	public Object getData()
	{
		return this.curr.getData();
	}
}

前の順序:

// 
public class MyBiTreePreIterator extends MyBiTreeIterator{
   
	Stack<MyBiTreeNode> stack = new Stack<MyBiTreeNode>();
     
	
	MyBiTreePreIterator()
	{
		
	}
	MyBiTreePreIterator(MyBiTreeNode root)
	{
	   super(root);	
	}
	
	@Override
	public void next() {
		// TODO Auto-generated method stub
		if(this.isComplete)
		{
			System.out.println(" ！");
			return ;
		}
		if(this.curr.getRightChild()!=null)
		{
			stack.push(this.curr.getRightChild());
		}
		if(this.curr.getLeftChild()!=null)
		{
			stack.push(this.curr.getLeftChild());
		}
		
		if(!stack.empty())
		{
			this.curr = stack.pop();
		}
		else
		{
			this.isComplete = true;
		}
	}
	
	@Override
	public void reset() {
		// TODO Auto-generated method stub
		if(this.root==null)
		{
			this.isComplete = true;
		}
		else
		{
			this.isComplete = false;
		}
		if(this.root==null)
		{
			return ;
		}
		this.curr = this.root;
	}
}

中間パス:
getFarLeftは、印刷用に最も左側のノードを見つけます.
nextメソッドは、次の処理が必要なノードを見つけることです.
上の順を比較すると,ここでは左ルート右の方法であるため,各ノードを処理するには,プロセス中に通りかかったノードをスタックに入れ,getFarLeft法で最も左側のノードを探し出し,currentノードに値を与える.このノードのdataを印刷してnextの方法で次のノードを探して、先に右側のノードがあるかどうかを判断して、もしあるならば、getFarLeftの方法でこのノードの最も左側のノードを探して、もしないならばスタックの中の要素で上へ探します.

//// 
public class MyBiTreeInIterator extends MyBiTreeIterator {
  
	Stack<MyBiTreeNode> stack = new Stack<MyBiTreeNode>();
    
	MyBiTreeInIterator()
	{
		
	}
	MyBiTreeInIterator(MyBiTreeNode root)
	{
		super(root);
	}
    
	// 
	public MyBiTreeNode getFarLeft(MyBiTreeNode node)
	{
	   if(node==null)
	   {
		   return null;
	   }
	   while(node.getLeftChild()!=null)
	   {
		  stack.push(node);
		  node = node.getLeftChild(); 
	   }
	   return node;
	}
	
	@Override
	public void next() {
		// TODO Auto-generated method stub
		if(this.isComplete)
		{
			System.out.println(" ！");
			return ;
		}
		
		// next， ， 。
		if(this.curr.getRightChild()!=null)
		{
			// 。
			this.curr = getFarLeft(this.curr.getRightChild());
		}
		else if(!stack.isEmpty())
		{
			this.curr = stack.pop();
		}
		else
		{
			this.isComplete = true;
		}
	}

	@Override
	// ， getFarLeft 。
	public void reset() {
		// TODO Auto-generated method stub
		if(this.root==null)
		{
			this.isComplete = true;
		}
		else
		{
			this.isComplete = false;
		}
		if(this.root==null)
		{
			return ;
		}
		this.curr = getFarLeft(this.root);
	}
}

中順遍歴(2)

 public static void inTraverse(BinaryTree root) {
  Stack s = new Stack();
  BinaryTree p = root;
  while(p!=null || !s.isEmpty()) {
   if(p!=null) {
   // push ， 
    s.push(p);
    p = p.lchild;
   }
   else {
   // p ， ， p ， 
    p = (BinaryTree)s.pop();
    visit(p);
    p = p.rchild;
   }
  }
 }

後の順序:
ダブルスタックメソッド!すべての要素の順序をtempスタックに入れます.stackスタックは中間スタックです.

/// 
public class MyBiTreePostIterator extends MyBiTreeIterator{
  
	Stack<MyBiTreeNode> stack = new Stack<MyBiTreeNode>();
	Stack<MyBiTreeNode> temp = new Stack<MyBiTreeNode>();

	MyBiTreePostIterator()
	{
		
	}
	MyBiTreePostIterator(MyBiTreeNode root)
	{
	   super(root);	
	}
	
	
	@Override
	public void next() {
		// TODO Auto-generated method stub
		if(this.isComplete)
		{
			System.out.println(" ！");
			return ;
		}
		if(!temp.isEmpty())
		{
			this.curr = temp.pop();
		}
		else
		{
			this.isComplete = true;
		}
	}
	@Override
	public void reset() {
		// TODO Auto-generated method stub
		if (this.root == null) {
			this.isComplete = true;
		} else {
			this.isComplete = false;

		}
		if (this.root == null) {
			return;
		}
		this.curr = root;
		
		while (this.curr != null || stack.size() > 0)
		{    
                    while (this.curr != null) {    
                        temp.push(this.curr);
                        //System.out.println(this.curr.getData());
                        stack.push(this.curr);    
                        curr = this.curr.getRightChild();    
                    }    
                    if (stack.size() > 0) {    
                        this.curr = stack.pop();    
                        this.curr = this.curr.getLeftChild();    
                    }    
                }   
		this.curr = temp.pop();
	}
}

層順遍歴
ここではキューを使用します.

// 
public class MyBiTreeLevIterator extends MyBiTreeIterator {
   
	Queue<MyBiTreeNode> queue = new LinkedList<MyBiTreeNode>();
	
	MyBiTreeLevIterator()
	{
		
	}
	
	MyBiTreeLevIterator(MyBiTreeNode root)
	{
	  super(root);	
	}

	@Override
	public void next() {
		// TODO Auto-generated method stub
		if(this.isComplete)
		{
			System.out.println(" ！");
			return ;
		}
		if(!queue.isEmpty())
		{
			this.curr = queue.remove();
			if(this.curr.getLeftChild()!=null)
			{
				queue.add(this.curr.getLeftChild());
			}
			if(this.curr.getRightChild()!=null)
			{
				queue.add(this.curr.getRightChild());
			}
		}
		else
		{
			this.isComplete = true;
		}
	}

	@Override
	public void reset() {
		// TODO Auto-generated method stub
		if (this.root == null) {
			this.isComplete = true;
		} else {
			this.isComplete = false;

		}
		if (this.root == null) {
			return;
		}
		this.curr = root;
		if(this.curr.getLeftChild()!=null)
		{
			queue.add(this.curr.getLeftChild());
		}
		if(this.curr.getRightChild()!=null)
		{
			queue.add(this.curr.getRightChild());
		}
	}
	
	
}

後序遍歴の牛の追い詰め方法:
遍歴しながらflagで印刷が必要かどうかを判断し、flagでない場合は、そのノードの両側のサブノードを見つける必要があります.

public static void main(String[] args) {
		// 
		BiTreeNode root = Test.makeTree();
		
		final Object flag = new Object(); //  
		Deque<Object> stack = new LinkedList<Object>();
		stack.push(root);
		while (!stack.isEmpty()){
			if (stack.peek() == flag){ //  
				stack.pop();
				BiTreeNode node = (BiTreeNode)stack.pop();
				System.out.print(node.getData());
			}else{
			         //  
				BiTreeNode node = (BiTreeNode)stack.peek();
				stack.push(flag); //  ， 
				if (node.getRightChild() != null) 
					stack.push(node.getRightChild());
				if (node.getLeftChild() != null) 
					stack.push(node.getLeftChild());
			}
		}
		System.out.println();
	}

}

テスト:

public class Test {
    
	public static MyBiTreeNode makeTree()
	{
		MyBiTreeNode b,c,d,e,f,g;
		g = MyBiTree.getTreeNode(new Character('G'), null, null);
		d = MyBiTree.getTreeNode(new Character('D'), null, g);
		b = MyBiTree.getTreeNode(new Character('B'), d, null);
		e = MyBiTree.getTreeNode(new Character('E'), null, null);
		f = MyBiTree.getTreeNode(new Character('F'), null, null);
	    c = MyBiTree.getTreeNode(new Character('C'), e, f);
	    return MyBiTree.getTreeNode(new Character('A'), b, c);
	}
	
	public static void main(String[] args) {
		
		MyBiTreeNode root;
		root = Test.makeTree();
		System.out.println(" ：");
		MyBiTreeIterator it = new MyBiTreePreIterator(root);
		
		for(it.reset();!it.endOfBiTree();it.next())
		{
		   System.out.print(it.getData()+" ");	
		}
		System.out.println();
		
		System.out.println(" ：");
		it = new MyBiTreeInIterator(root);
		
		
		for(it.reset();!it.endOfBiTree();it.next())
		{
		   System.out.print(it.getData()+" ");	
		}
		System.out.println();
		
		System.out.println(" ：");
		it = new MyBiTreePostIterator(root);
		
		
		for(it.reset();!it.endOfBiTree();it.next())
		{
		   System.out.print(it.getData()+" ");	
		}
		System.out.println();
		
		System.out.println(" ：");
		it = new MyBiTreeLevIterator(root);
		
		
		for(it.reset();!it.endOfBiTree();it.next())
		{
		   System.out.print(it.getData()+" ");	
		}
		System.out.println();
	}

}