现在的位置: 首页 > 综合 > 正文

BinaryTree 迭代器实现 非递归实现

2013年12月05日 ⁄ 综合 ⁄ 共 6815字 ⁄ 字号 评论关闭

迭代器抽象类

本实现摘自 数据结构与问题求解,其实现非常符合Java风格以及面向对象思想。

// ******************PUBLIC OPERATIONS**********************
//     first and advance are abstract; others are final
// boolean isValid( )   --> Truse if at valid position in tree
// AnyType retrieve( )  --> Return item in current position
// void first( )        --> Set current position to first
// void advance( )      --> Advance (prefix)

/**
 * Tree iterator class.
 */
abstract class TreeIterator<AnyType> {
	/**
	 * Construct the iterator. The current position is set to null.
	 * 
	 * @param theTree
	 *            the tree to which the iterator is permanently bound.
	 */
	public TreeIterator(BinaryTree<AnyType> theTree) {
		t = theTree;
		current = null;
	}

	/**
	 * Set the current position to the first item, according to the traversal
	 * scheme.
	 */
	abstract public void first();

	/**
	 * Test if current position references a valid tree item.
	 * 
	 * @return true if the current position is not null; false otherwise.
	 */
	final public boolean isValid() {
		return current != null;
	}

	/**
	 * Return the item stored in the current position.
	 * 
	 * @return the stored item.
	 * @throws NoSuchElementException
	 *             if the current position is invalid.
	 */
	final public AnyType retrieve() {
		if (current == null)
			throw new NoSuchElementException("TreeIterator retrieve");
		return current.getElement();
	}

	/**
	 * Advance the current position to the next node in the tree, according to
	 * the traversal scheme. If the current position is null, then throw an
	 * exception. This is the alternate strategy, that we did not use for lists.
	 * 
	 * @throws NoSuchElementException
	 *             if the current position is null.
	 */
	abstract public void advance();

	/** The tree. */
	protected BinaryTree<AnyType> t; // Tree
	/** Current position. */
	protected BinaryNode<AnyType> current; // Current position
}

在实现非递归的遍历时,实际上模拟了递归。最复杂的还是后序遍历,一旦明白了这个其他也就是顺其自然的事情。

后序遍历: 

1、left 

2、right 

3、root

root实际上pop了三次。

/**
 * Postorder iterator class.
 * 
 */
class PostOrder<AnyType> extends TreeIterator<AnyType> {
	/**
	 * Construct the iterator. The current position is set to null.
	 * 
	 * @param theTree
	 *            the tree to which the iterator is permanently bound.
	 */
	public PostOrder(BinaryTree<AnyType> theTree) {
		super(theTree);
		s = new Stack<StNode<AnyType>>();
		s.push(new StNode<AnyType>(t.getRoot()));
	}

	/**
	 * Set the current position to the first item, according to the postorder
	 * traversal scheme.
	 */
	public void first() {
		s.clear();
		if (t.getRoot() != null) {
			s.push(new StNode<AnyType>(t.getRoot()));
			advance();
		}
	}

	/**
	 * Advance the current position to the next node in the tree, according to
	 * the postorder traversal scheme.
	 * 
	 * @throws NoSuchElementException
	 *             if iteration has been exhausted prior to the call.
	 */
	public void advance() {
		if (s.isEmpty()) {
			if (current == null)
				throw new NoSuchElementException("PostOrder Advance");
			current = null;
			return;
		}

		StNode<AnyType> cnode;

		for (;;) {
			cnode = s.pop();

			if (++cnode.timesPopped == 3) {
				current = cnode.node;
				return;
			}

			s.push(cnode);
			if (cnode.timesPopped == 1) {
				if (cnode.node.getLeft() != null)
					s.push(new StNode<AnyType>(cnode.node.getLeft()));
			} else // cnode.timesPopped == 2
			{
				if (cnode.node.getRight() != null)
					s.push(new StNode<AnyType>(cnode.node.getRight()));
			}
		}
	}

	// An internal class for tree iterators
	protected static class StNode<AnyType> {
		BinaryNode<AnyType> node;
		int timesPopped;

		StNode(BinaryNode<AnyType> n) {
			node = n;
			timesPopped = 0;
		}
	}

	/** An internal stack if visited nodes. */
	protected Stack<StNode<AnyType>> s; // The stack of StNode objects
}


/**
 * Inorder iterator class.
 */
class InOrder<AnyType> extends PostOrder<AnyType> {
	/**
	 * Construct the iterator. The current position is set to null.
	 * 
	 * @param theTree
	 *            the tree to which the iterator is permanently bound.
	 */
	public InOrder(BinaryTree<AnyType> theTree) {
		super(theTree);
	}

	/**
	 * Advance the current position to the next node in the tree, according to
	 * the inorder traversal scheme.
	 * 
	 * @throws NoSuchElementException
	 *             if iteration has been exhausted prior to the call.
	 */
	public void advance() {
		if (s.isEmpty()) {
			if (current == null)
				throw new NoSuchElementException("InOrder advance");
			current = null;
			return;
		}

		StNode<AnyType> cnode;

		for (;;) {
			cnode = s.pop();

			if (++cnode.timesPopped == 2) {
				current = cnode.node;
				if (cnode.node.getRight() != null)
					s.push(new StNode<AnyType>(cnode.node.getRight()));
				return;
			}

			// First time through
			s.push(cnode);
			if (cnode.node.getLeft() != null)
				s.push(new StNode<AnyType>(cnode.node.getLeft()));
		}
	}
}


/**
 * Preorder iterator class.
 */
class PreOrder<AnyType> extends TreeIterator<AnyType> {
	/**
	 * Construct the iterator. The current position is set to null.
	 * 
	 * @param theTree
	 *            the tree to which the iterator is permanently bound.
	 */
	public PreOrder(BinaryTree<AnyType> theTree) {
		super(theTree);
		s = new Stack<BinaryNode<AnyType>>();
		s.push(t.getRoot());
	}

	/**
	 * Set the current position to the first item, according to the preorder
	 * traversal scheme.
	 */
	public void first() {
		s.clear();
		if (t.getRoot() != null) {
			s.push(t.getRoot());
			advance();
		}
	}

	/**
	 * Advance the current position to the next node in the tree, according to
	 * the preorder traversal scheme.
	 * 
	 * @throws NoSuchElementException
	 *             if iteration has been exhausted prior to the call.
	 */
	public void advance() {
		if (s.isEmpty()) {
			if (current == null)
				throw new NoSuchElementException("PreOrder Advance");
			current = null;
			return;
		}

		current = s.pop();

		if (current.getRight() != null)
			s.push(current.getRight());
		if (current.getLeft() != null)
			s.push(current.getLeft());
	}

	/** An internal stack of visited nodes */
	private Stack<BinaryNode<AnyType>> s; // Stack of BinaryNode objects
}

/**
 * Level-order iterator class.
 */
class LevelOrder<AnyType> extends TreeIterator<AnyType> {
	/**
	 * Construct the iterator. The current position is set to null.
	 * 
	 * @param theTree
	 *            the tree to which the iterator is permanently bound.
	 */
	public LevelOrder(BinaryTree<AnyType> theTree) {
		super(theTree);
		q = new ArrayDeque<BinaryNode<AnyType>>();
		q.add(t.getRoot());
	}

	/**
	 * Set the current position to the first item, according to the level-order
	 * traversal scheme.
	 */
	public void first() {
		q.clear();
		if (t.getRoot() != null) {
			q.add(t.getRoot());
			advance();
		}
	}

	/**
	 * Advance the current position to the next node in the tree, according to
	 * the level-order traversal scheme.
	 * 
	 * @throws NoSuchElementException
	 *             if iteration has been exhausted prior to the call.
	 */
	public void advance() {
		if (q.isEmpty()) {
			if (current == null)
				throw new NoSuchElementException("LevelOrder advance");
			current = null;
			return;
		}

		current = q.remove();

		if (current.getLeft() != null)
			q.add(current.getLeft());
		if (current.getRight() != null)
			q.add(current.getRight());
	}

	/** An internal queue of visited nodes */
	private Queue<BinaryNode<AnyType>> q; // Queue of BinaryNode objects
}

public class TestTreeIterators {
	// Test program
	public static void main(String[] args) {
		BinaryTree<Integer> t = new BinaryTree<Integer>();

		testItr("PreOrder", new PreOrder<Integer>(t)); // Test empty tree

		BinaryTree<Integer> t1 = new BinaryTree<Integer>(1);
		BinaryTree<Integer> t3 = new BinaryTree<Integer>(3);
		BinaryTree<Integer> t5 = new BinaryTree<Integer>(5);
		BinaryTree<Integer> t7 = new BinaryTree<Integer>(7);
		BinaryTree<Integer> t2 = new BinaryTree<Integer>();
		BinaryTree<Integer> t4 = new BinaryTree<Integer>();
		BinaryTree<Integer> t6 = new BinaryTree<Integer>();

		t2.merge(2, t1, t3);
		t6.merge(6, t5, t7);
		t4.merge(4, t2, t6);

		t = t4;

		testItr("Preorder", new PreOrder<Integer>(t));
		testItr("Postorder", new PostOrder<Integer>(t));
		testItr("Inorder", new InOrder<Integer>(t));
		testItr("Level order", new LevelOrder<Integer>(t));
	}

	public static <AnyType> void testItr(String type, TreeIterator<AnyType> itr) {
		try {
			System.out.print(type + ":");
			for (itr.first(); itr.isValid(); itr.advance())
				System.out.print(" " + itr.retrieve());
			System.out.println();
			itr.advance();
		} catch (NoSuchElementException e) {
			System.out.println(e + " (as expected)");
		}
	}
}

抱歉!评论已关闭.