树的遍历非递归算法及应用

介绍树的三种非递归遍历代码的Java实现及应用。

算法

创建内部接口 Visitor ，通过传入方法来实现对遍历元素的定制操作。

1
2
3
4
5
6
7
8
9
public interface Visitor<E>{
    boolean stop = false; // 标记停止位置，设置为true代表停止遍历
    boolean visit(TreeNode<E> node);
}

protected Visitor visitor = (node) -> {  // 默认visitor，若没有传入则使用
    System.out.print(node.element + " ");
    return false;
};

使用：

1
2
3
4
5
6
BinaryTree<Integer> tree = new BinaryTree<>();
tree.preorder((node) -> {  
    if(node.element == 2) return true;
    node.element ++;
    return false;
})

先序遍历

递归：

1
2
3
4
5
6
7
private void preorder1(Visitor visitor){  //设置为private，在public方法中有对visitor为空的判断
    if(root==null || visitor.stop) return;

    visitor.visit(root); // 先对父节点进行操作
    preorder1(root.left,visitor);
    preorder1(root.right,visitor);
}

非递归：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
private void preorder2(Visitor visitor) {
    TreeNode<E> node = root;
    Stack<TreeNode<E>> stack = new LinkedStack<TreeNode<E>>();
    List<TreeNode<E>> visited = new LinkedList<TreeNode<E>>(); //记录访问过的节点
    if(visitor.stop) return;
    visitor.visit(node);
    visited.add(node);
    stack.push(node);
    while(visited.size() < size) {  //size是tree的节点个数
        if(visitor.stop) return;
        // 来到这里，node已经被访问了，有left就立即访问，放入栈中，成为下一次访问的父节点（返回处）
        if(node.left != null && !visited.contains(node.left)) {
            visitor.visit(node.left);
            visited.add(node.left);
            stack.push(node.left);
            node = node.left;
        } else 
            // 有right就立即访问，放入栈中，成为下一次访问的父节点（返回处）
            if (node.right != null && !visited.contains(node.right)) {
            visitor.visit(node.right);
            visited.add(node.right);
            stack.push(node.right);
            node = node.right;
        } else { // 左右节点都没有了就弹栈，查看父节点的右节点
            node = stack.pop();
        }
    }
}

中序遍历

递归：

1
2
3
4
5
6
7
8
private void inorder1(Visitor visitor){ 
    if(root==null || visitor.stop) return;

    inorder1(root.left,visitor);
    if(visitor.stop) return;
    visitor.visit(root);
    inorder1(root.right,visitor);
}

非递归：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
private void inorder2(Visitor visitor){
    TreeNode<E> node = root;
    List<TreeNode<E>> visited = new LinkedList<TreeNode<E>>();
    Stack<TreeNode<E>> stack = new LinkedStack<TreeNode<E>>();
    stack.push(node);
    while(node.left != null) { //一直找到最左节点
        stack.push(node.left);
        node = node.left;
    }
    node = stack.pop();
    while(visited.size() < size) {
        if(node.left != null && !visited.contains(node.left)) {
            stack.push(node); //有左节点才需要把该节点位置保存，否则直接访问
            node = node.left;
        } else {
            if(visitor.stop) return;
            visitor.visit(node);
            visited.add(node);  //先访问父节点，后判断是否有右节点
            if(node.right != null && !visited.contains(node.right)) {
                node = node.right;
            } else {
                node = stack.pop();
            }
        }
    }
}

后序遍历

递归：

1
2
3
4
5
6
7
8
private void postorder1(Visitor visitor){
    if(root==null || visitor.stop) return;

    postorder1(root.left,visitor);
    postorder1(root.right,visitor);
    if(visitor.stop) return;
    visitor.visit(root);
}

非递归：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
private void postorder2(TreeNode<E> root,Visitor visitor){
    TreeNode<E> node = root;
    List<TreeNode<E>> visited = new LinkedList<TreeNode<E>>();
    Stack<TreeNode<E>> stack = new LinkedStack<TreeNode<E>>();
    stack.push(node);
    while(node.left != null) {
        stack.push(node.left);
        node = node.left;
    }
    node = stack.pop();
    while(visited.size() < size) {
        if((node.left != null && !visited.contains(node.left)) ||
           (node.right != null && !visited.contains(node.right))) {  //只有有需要访问的子节点
            stack.push(node);  //要访问子节点了，先把这个节点保存起来
            if(node.left != null && !visited.contains(node.left)) {
                node = node.left;
            } else {
                node = node.right;
            }
        } else {
            if(visitor.stop) return;
            visitor.visit(node);
            visited.add(node); //当左右节点访问完了，再访问父节点
            node = stack.pop(); //访问完这棵子树，弹栈
        }
    }
}

层序遍历

1
2
3
4
5
6
7
8
9
10
11
private void levelorder(Visitor visitor){
    Queue<TreeNode<E>> queue = new LinkedQueue<TreeNode<E>>();
    queue.offer(root);
    while(!queue.isEmpty()){
        TreeNode<E> node = queue.poll();
        if(visitor.stop) break;
        visitor.visit(node);
        if(node.left!=null) queue.offer(node.left);
        if(node.right!=null) queue.offer(node.right);
    }
}

应用

计算树的高度

计算树的节点数量

复制树

非递归：(先序遍历)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
public BinaryTree<E> copy() {
    TreeNode<E> newRoot = new TreeNode<>(root.element);
    TreeNode<E> p = newRoot;
    TreeNode<E> node = root;
    List<TreeNode<E>> visited = new LinkedList<TreeNode<E>>();
    Stack<TreeNode<E>> stack = new LinkedStack<TreeNode<E>>();
    visited.add(newRoot);
    while (visited.size() != size) {
        if(node.left != null && !visited.contains(node.left)) {
            stack.push(node);
            TreeNode<E> newNode = new TreeNode<E>(node.left.element);
            visited.add(node.left);
            p.left = newNode;
            newNode.parent = p;
            node = node.left;
            p = p.left;
        } else if(node.right != null && !visited.contains(node.right)) {
            stack.push(node);  // p只能按照parent的顺序返回，因此这里即使已经访问完这棵子树，仍需要将node压入栈中保存位置，否则node会与p不同步
            TreeNode<E> newNode = new TreeNode<E>(node.right.element);
            visited.add(node.right);
            p.right = newNode;
            newNode.parent = p;
            node = node.right;
            p = p.right;
        } else {
            node = stack.pop();
            p = p.parent;
        }
    }
    BinaryTree<E> newTree = new BinaryTree<>();
    newTree.size = size;
    newTree.root = newRoot;
    return newTree;
}

留言

⬆︎TOP