木の後序を巡回する(再帰的および非再帰的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());
}
}