Inorder prechod stromom nerekurzívne

Created: 2008-06-19 - 17:04

Prechod stromom inorder (do sirky) nerekurzivna metoda... Myslim, ze by mala fungovat vseobecne, teda pre tento konkretny strom to ide... A aj ked napr. vymenite k7 a k9 tak to ide... cize.. ide to a basta :). edit: jasne, aby som nezabudol musite mat galcikovu triedu Node.java


import java.util.Stack;

public class Stromy {
	public static void prechodStromuNerekurzvine(Node vrchol) {
		Stack<Node> vrcholy = new Stack<Node>();
		vrcholy.push(vrchol);
		boolean jeKoniec = false;
		boolean koniec = false;
		
		//kym nie je koniec
		while (!jeKoniec) {
			//prehladavaj strom smerom dolava a ukladaj do zasobnika
			while (vrchol.left != null) {
				vrcholy.push(vrchol.left);
				vrchol = vrchol.left;
			}
			//ak si na najlavejsom vrchole vyberaj zo zasobnika a 
			//hladaj ci nema niekto praveho syna
			while (vrchol.right == null) {
				if(vrcholy.isEmpty()){
					koniec = true;
					break;
				}
				vrchol = vrcholy.pop();
				System.out.println(vrchol.content);
				if (vrcholy.isEmpty())
					jeKoniec = true;
			}
			//ak niekto ma praveho syna
			if (vrchol.right != null) {
				vrchol = vrchol.right;
				//ak uz nema laveho tak vypisuj zaradom pravych synov
				if (vrchol.left == null){
					System.out.println(vrchol.content);
					jeKoniec = false;
				}
				//inac uloz dany vrchol do zasobnika a pokracuj s tym lavym
				else {
					vrcholy.push(vrchol);
					jeKoniec = false;
				}
			}
			//toto tu je aby sa to nakonci necyklilo...
			if(koniec)
				break;
		}
	}

	public static void main(String[] args) {
		System.out.println("Binarny strom:");
		// Vytvorenie a test obycajneho binarneho stromu
		Node k2 = new Node(2, null, new Node(3, null, null));
		Node k7 = new Node(7, new Node(4, null, null), k2);
		Node k9 = new Node(9, new Node(6, null, null), new Node(10,new Node(11,null,null),new Node(12,null,null)));
		Node root = new Node(5, k9, k7);
		prechodStromuNerekurzvine(root);
	}
}