木の後序を巡回する(再帰的および非再帰的java実装)

1992 ワード

木の後序は(再帰的および非再帰的java実装)木の基本的な遍歴を通して、木の関連する問題を解決する基礎です.二叉樹の結点定義:
class BinaryTree{  
public int value;  
public BinaryTree leftNode;  
public BinaryTree rightNode;  
BinaryTree(int x) { value = x; }  
}  
後から順に巡回します:左右の根の原則は木のすべての結点を巡回します;
void postOrder(BinaryTree root){
	if(root !=null){	
	postOrder(root.left);	
	postOrder(root.right);
	System.out.println(root.value);
	}
}
後順に巡回した非再帰的実現【java実現】
package com.mytest.mymain;
import java.util.Stack;
class BTree{
	public int value;  //public static int value;          8 8
	public BTree left;  
	public BTree right;  
	BTree(int x) { value = x; }  
}
public class PreOrderwithStack {
	public static void main(String[] args) {
		BTree root=new BTree(1);
		BTree Node2=new BTree(2);
		BTree Node3=new BTree(3);
		BTree Node4=new BTree(4);
		BTree Node5=new BTree(5);
		BTree Node6=new BTree(6);
		BTree Node7=new BTree(7);
		BTree Node8=new BTree(8);
	
		root.left=Node2;
		root.right=Node3;
		
		Node2.left=Node4;
		Node2.right=Node5;
		
		Node3.left=Node6;
		Node3.right=Node7;
		
		Node4.left=Node8;
		
		preorderfun(root);
		System.out.println();
		inorderfun(root);
		System.out.println();
		postorderfun(root);
	}
	public static void postorderfun(BTree root){
		Stack stack =new Stack();
		BTree proot;//               
		int flag;//root        ;
		if(root!=null){
			do{
				while(root!=null){// root         
					stack.push(root);
					root=root.left;
				  }
				
				//     ,                    ;
				proot=null;//               ,         ,                。
				flag=1;//root         ;  root null
				
				while(!stack.isEmpty() && flag==1){
					root=stack.peek();       //      ,     ;
					if(root.right==proot){
						root=stack.pop();
						System.out.print(root.value+"  ");
						proot=root;
					}else{
						root=root.right;
						flag=0;//root        ;
					}
				}
			}while(!stack.isEmpty());
		}
		
		
	}