データ構造とアルゴリズム——二叉木遍歴

まず、ツリー構造を次のように定義します.
 

class BNode{
	private String name;
	private BNode left,right;
	
	public String getName() {
		return name;
	}

	public void setName(String name) {
		this.name = name;
	}
	
	public BNode getLeft() {
		return left;
	}

	public void setLeft(BNode left) {
		this.left = left;
	}

	public BNode getRight() {
		return right;
	}

	public void setRight(BNode right) {
		this.right = right;
	}

	public BNode(String name)
	{
		this(name,null,null);
	}
	
	public BNode(String name,BNode left,BNode right){
		this.name = name;
		this.left = left;
		this.right = right;
	}
}

ノードの山を挿入
 

BNode root;
		
root = new BNode(" ");
root.setLeft(new BNode(" "));
root.setRight(new BNode(" "));
root.getLeft().setLeft(new BNode(" "));
root.getLeft().setRight(new BNode(" "));
root.getRight().setLeft(new BNode(" "));
root.getRight().setRight(new BNode(" "));

以下は簡単な前順遍歴、中順遍歴、後順遍歴です
 

	protected static void preOrder(BNode n)
	{
		if(n!=null){
			System.out.println(n.getName());
			preOrder(n.getLeft());
			preOrder(n.getRight());
		}
	}
	protected static void inOrder(BNode n)
	{
		if(n!=null){
			inOrder(n.getLeft());
			System.out.println(n.getName());
			inOrder(n.getRight());
		}
	}
	protected static void postOrder(BNode n)
	{
		if(n!=null){
			postOrder(n.getLeft());
			postOrder(n.getRight());
			System.out.println(n.getName());
		}
	}

以下は広さ優先遍歴
 

	protected static void wideOrder(BNode n)
	{
		LinkedList l = new LinkedList();
		if(n!= null){
			l.push(n);
		}
		
		while(!l.isEmpty()){
			BNode t = (BNode)l.removeLast();
			System.out.println(t.getName());
			
			if(t.getLeft()!=null){
				l.push(t.getLeft());
			}
			if(t.getRight()!=null){
				l.push(t.getRight());
			}
		}
	}

1、まずルートノードをキューに配置します.
2,キューの末尾をループし続け,ノードを取得できればステップ3を行い,そうでなければループを終了する.
3,そのノードの左右のサブノードを順番にキューヘッダに挿入する
次は非再帰順に二叉木を巡る実装であり,Stackというデータ構造に用いられ,スタックを押すときに右サブノードから左サブノードに注意する
 

	protected static void preOrder(BNode n)
	{
		Stack s = new Stack();
		
		if(n!=null){
			s.push(n);
		}		
		
		while(!s.isEmpty())
		{
			n = (BNode)s.pop();
			System.out.println(n.getName());
			if(n.getRight() != null){
				s.push(n.getRight());
			}
			if(n.getLeft()!=null){
				s.push(n.getLeft());
			}
		}
	}