【数据结构】二叉树(2)

代码如下

public void preOrder() {
		Stack<BinaryTreeNode> stack = new Stack<BinaryTreeNode>();
		visitAlongLeft(root,stack);
		}
	}
private void visitAlongLeft(BinaryTreeNode root,Stack<BinaryTreeNode> stack) {
		while (root != null) {
			System.out.print(root.data + "  ");
			if (root.rchild != null)
				stack.push(root.rchild);
			root = root.lchild;
		}
	}

3.中序非递归遍历

public void inOrder() {
		Stack<BinaryTreeNode> stack = new Stack<BinaryTreeNode>();
		goAlongLeft(root,stack);
		}
	}
private void goAlongLeft(BinaryTreeNode root,Stack<BinaryTreeNode> stack) {
		while (root != null) {
			stack.push(root);
			root = root.lchild;
		}
	}

注：两个辅助函数的命名一个是visitAlongLeft一个是goAlongLeft也能看出来他们的区别。

代码如下

private void goAlongRight(BinaryTreeNode root,Stack<BinaryTreeNode> stack2) {
		while (root != null) {
			stack2.push(root); // 访问
			if (root.lchild != null)
				stack1.push(root.lchild);
			root = root.rchild;
		}
	}
public void postOrder() {
		Stack<BinaryTreeNode> myStack1 = new Stack<BinaryTreeNode>();
		Stack<BinaryTreeNode> myStack2 = new Stack<BinaryTreeNode>();
		goAlongRight(root,myStack2);
		}
		while (myStack2.size() > 0) {
			BinaryTreeNode node = myStack2.poll();
			System.out.print(node.data + "  ");
		}
	}

5.中序非递归遍历和先序思路类似，层序非递归遍历比较简单在此不再解释

6.创建二叉树

先序递归遍历同时也提供了一种创建二叉树的方法，大致思路是首先创建树根，然后递归创建左子树再递归创建右子树。

（编辑：ASP站长网）