2. 实现
// 递归实现
private void travPre(BSTNode<T> tree) {
if (tree == null) return;
System.out.print(tree.key + " ");
travPre(tree.left);
travPre(tree.right);
}
// 迭代实现
public void travPre2(BSTNode<T> tree) {
Stack<BSTNode<T>> stack = new Stack<>();
while (true) {
visitAlongVine(tree, stack);
if (stack.isEmpty()) break;
tree = stack.pop();
}
}
private void visitAlongVine(BSTNode<T> tree, Stack<BSTNode<T>> stack) {
while (tree != null) {
System.out.print(tree.key + " ");
stack.push(tree.right);
tree = tree.left;
}
}
六、中序遍历
1. 描述
对于中序遍历，则首先遍历左子树
再遍历根节点
最后遍历右子树
具体过程如下：
2. 实现
// 递归实现
private void travIn(BSTNode<T> tree) {
if (tree == null) return;
travIn(tree.left);
System.out.print(tree.key + " ");
travIn(tree.right);
}
// 迭代实现
public void travIn2(BSTNode<T> tree) {
Stack<BSTNode<T>> stack = new Stack<>();
while (true) {
goAlongVine(tree, stack);
if (stack.isEmpty()) break;
tree = stack.pop();
System.out.print(tree.key + " ");
tree = tree.right;
}
}
private void goAlongVine(BSTNode<T> tree, Stack<BSTNode<T>> stack) {
while (tree != null) {
stack.push(tree);
tree = tree.left;
}
}
七、后序遍历
1. 描述
对于后序遍历，则首先遍历左子树
再遍历根右子树
最后遍历根节点
具体过程如下：
2. 实现
// 递归实现
private void travPost(BSTNode<T> tree) {
if (tree == null) return;
travPost(tree.left);
travPost(tree.right);
System.out.print(tree.key + " ");
}
// 迭代实现
public void travPost2(BSTNode<T> tree) {
Stack<BSTNode<T>> stack = new Stack<>();
if (tree != null) stack.push(tree);
while (!stack.isEmpty()) {
if (stack.peek() != tree.parent)
gotoHLVFL(stack);
tree = stack.pop();
System.out.print(tree.key + " ");
}
}
private void gotoHLVFL(Stack<BSTNode<T>> stack) {
BSTNode<T> tree;
while ((tree = stack.peek()) != null)
if (tree.left != null) {
if (tree.right != null) stack.push(tree.right);
stack.push(tree.left);
} else
stack.push(tree.right);
stack.pop();
}
八、层次遍历
1. 描述
对于层次遍历而言就相对简单，即由上到下逐层遍历；
2. 实现
public void travLevel() {
Queue<BSTNode<T>> queue = new LinkedList<>();
queue.offer(root);
while (!queue.isEmpty()) {
BSTNode<T> x = queue.poll();
System.out.print(x.key + " ");
if (x.left != null) queue.offer(x.left);
if (x.right != null) queue.offer(x.right);
}
}
总结
正是因为二叉树同时具有向量和列表的特性，所以他的使用场景非常广泛，当然他还有很多的变种，这些我们后续会继续讲到；
对于文中的动图大家可以在这个网站自行实验；
