Java实现二叉树的三种遍历方式

​
​

活动地址：CSDN21天学习挑战赛

二叉树的基础遍历

1：前序遍历：先访问根结点，然后再访问左子树，最后访问右子树；
2：中序遍历：先访问左子树，然后再访问根结点，最后访问右子树；
3：后序遍历：先访问左子树，然后再访问右子树，最后访问根结点；

示例如下：

前序遍历的API设计：

public Queue<Key> preErgodic():使用前序遍历，获取整个树中的所有键
private void preErgodic(Node x,Queue<Key> keys):使用前序遍历，把指定树x中的所有键放入到keys队列中
1
2

实现步骤：

1. 把当前结点的key放入到队列中；
2. 找到当前结点的左子树，如果不为空，递归遍历左子树；
3. 找到当前结点的右子树，如果不为空，递归遍历右子树；

代码实现：

 //使用前序遍历获取整个树中所有的键
    public Queue<Key> preErgoidic(){
        Queue<Key> keys = new Queue<>();
        preErgoidic(root,keys);
        return keys;
    }


    //使用前序遍历获取指定树x的所有键，并放到Keys队列中
    private void preErgoidic(Node x, Queue<Key> keys){
        if(x == null){
            return;
        }
        //把x结点的key放入到keys中
        keys.enQueue(x.key);

        //递归遍历x结点的左子树
        if(x.left != null){
            preErgoidic(x.left,keys);
        }

        //递归遍历x结点的右子树
        if(x.right != null){
            preErgoidic(x.right,keys);
        }

    }
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

中序遍历的API设计：

public Queue midErgodic():使用中序遍历，获取整个树中的所有键
private void midErgodic(Node x,Queue keys):使用中序遍历，把指定树x中的所有键放入到keys队列中
1
2

实现步骤：

1. 找到当前结点的左子树，如果不为空，递归遍历左子树；
2. 把当前结点的key放入到队列中；
3. 找到当前结点的右子树，如果不为空，递归遍历右子树；

代码实现：

 //使用中序遍历获取整个树中所有的键
    public Queue<Key> midErgoidic(){
        Queue<Key> keys = new Queue<>();
        midErgoidic(root,keys);
        return keys;
    }

    //使用中序遍历获取指定树x的所有键，并放到Keys队列中
    private void midErgoidic(Node x, Queue<Key> keys) {
        if(x == null){
            return;
        }

        //递归遍历x结点的左子树
        if(x.left != null){
            midErgoidic(x.left,keys);
        }

        //把x结点的key放入到keys中
        keys.enQueue(x.key);

        //递归遍历x结点的右子树
        if(x.right != null){
            midErgoidic(x.right,keys);
        }
    }
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

后序遍历的API设计：

public Queue afterErgodic():使用中序遍历，获取整个树中的所有键
private void afterErgodic(Node x,Queue keys):使用中序遍历，把指定树x中的所有键放入到keys队列中
1
2

实现步骤：

1. 找到当前结点的左子树，如果不为空，递归遍历左子树；
2. 找到当前结点的右子树，如果不为空，递归遍历右子树；
3. 把当前结点的key放入到队列中；

代码实现：

 //后续遍历
    public Queue<Key> afterErgoidic(){
        Queue<Key> keys = new Queue<>();
        afterErgoidic(root,keys);
        return keys;
    }

    //使用中序遍历获取指定树x的所有键，并放到Keys队列中
    private void afterErgoidic(Node x, Queue<Key> keys) {
        if(x == null){
            return;
        }

        //递归遍历x结点的左子树
        if(x.left != null){
            afterErgoidic(x.left,keys);
        }

        //递归遍历x结点的右子树
        if(x.right != null){
            afterErgoidic(x.right,keys);
        }

        //把x结点的key放入到keys中
        keys.enQueue(x.key);
    }

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