数据结构-二叉树的遍历

作者: 鼬殿 | 来源:发表于2020-05-25 19:15 被阅读0次

遍历是数据结构中的常见操作
把所有元素都访问一遍

线性数据结构的遍历比较简单

正序遍历
逆序遍历

根据结点访问顺序的不同，二叉树的常见遍历方式有4种

前序遍历（Preorder Traversal）
中序遍历（Inorder Traversal）
后序遍历（Postorder Traversal）
层序遍历（Level Order Traversal）

前序遍历（Preorder Traversal）

访问顺序
根节点、前序遍历左子树、前序遍历右子树
7、4、2、1、3、5、9、8、11、10、12

    /**
     * 前序遍历
     */
    public void preorderTraversal() {
        preorderTraversal(root);
    }
    
    private void preorderTraversal(Node<E> node) {
        if (node == null) return;
        System.out.println(node.element);
        preorderTraversal(node.left);
        preorderTraversal(node.right);
    }

中序遍历（Inorder Traversal）

访问顺序

中序遍历左子树、根节点、中序遍历右子树
1、2、3、4、5、7、8、9、10、11、12
中序遍历右子树、根节点、中序遍历左子树
12、11、10、9、8 、7、5、4、3、2、1

二叉搜索树的中序遍历结果是升序或者降序的

    /**
     * 中序遍历
     */
    public void inorderTraversal() {
        inorderTraversal(root);
    }
    
    private void inorderTraversal(Node<E> node) {
        if (node == null) return;
        inorderTraversal(node.left);
        System.out.println(node.element);
        inorderTraversal(node.right);
    }

后序遍历（Postorder Traversal）

后序遍历左子树、后序遍历右子树、根节点
1、3、2、5、4、8、10、12、11、9、7

    /**
     * 后序遍历
     */
    public void postorderTraversal() {
        postorderTraversal(root);
    }
    
    private void postorderTraversal(Node<E> node) {
        if (node == null) return;
        postorderTraversal(node.left);
        postorderTraversal(node.right);
        System.out.println(node.element);
    }

层序遍历（Level Order Traversal）

从上到下、从左到右依次访问每一个节点
7、4、9、2、5、8、11、1、3、10、12

实现思路：使用队列

将根节点入队
循环执行以下操作，直到队列为空
将队头节点 A 出队，进行访问
将 A 的左子节点入队
将 A 的右子节点入队

    /**
     * 层序遍历
     */
    public void levelOrderTraversal(){
        if (root == null) return;
        Queue<Node<E>> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            Node<E> node = queue.poll();
            System.out.println(node.element);
            if (node.left != null) {
                queue.offer(node.left);
            }
            if (node.right != null) {
                queue.offer(node.right);
            }
        }
    }

遍历接口设计

    /**
     * 前序遍历
     */
    public void preorderTraversal(Visitor<E> visitor) {
        preorderTraversal(root,visitor);
    }
    
    private void preorderTraversal(Node<E> node,Visitor<E> visitor) {
        if (node == null || visitor == null) return;
        visitor.visit(node.element);
        preorderTraversal(node.left,visitor);
        preorderTraversal(node.right,visitor);
    }
    
    /**
     * 中序遍历
     */
    public void inorderTraversal(Visitor<E> visitor) {
        inorderTraversal(root,visitor);
    }
    
    private void inorderTraversal(Node<E> node,Visitor<E> visitor) {
        if (node == null || visitor == null) return;
        inorderTraversal(node.left,visitor);
        visitor.visit(node.element);
        inorderTraversal(node.right,visitor);
    }
    
    /**
     * 后序遍历
     */
    public void postorderTraversal(Visitor<E> visitor) {
        postorderTraversal(root,visitor);
    }
    
    private void postorderTraversal(Node<E> node,Visitor<E> visitor) {
        if (node == null || visitor == null) return;
        postorderTraversal(node.left,visitor);
        postorderTraversal(node.right,visitor);
        visitor.visit(node.element);
    }
    
    /**
     * 层序遍历
     */
    public void levelOrderTraversal(Visitor<E> visitor){
        if (root == null || visitor == null) return;
        Queue<Node<E>> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            Node<E> node = queue.poll();
            visitor.visit(node.element);
            if (node.left != null) {
                queue.offer(node.left);
            }
            if (node.right != null) {
                queue.offer(node.right);
            }
        }
    }
    
    public static interface Visitor<E> {
        void visit(E elemet);
    }

利用上一章节二叉搜索树调用层序遍历

 package njf;
import java.util.Comparator;

import njf.printer.BinaryTreeInfo;
import njf.printer.BinaryTrees;
import njf.BinarySearchTree.Visitor;
import njf.file.Files;

public class Main {
    static void test1() {
        Integer data[] = new Integer[] {
                7, 4, 9, 2, 5, 8, 11, 3, 12, 1
        };
        
        BinarySearchTree<Integer> bst = new BinarySearchTree<>();
        for (int i = 0; i < data.length; i++) {
            bst.add(data[i]);
        }
        BinaryTrees.println(bst);
        bst.levelOrderTraversal(new Visitor<Integer>() {
            @Override
            public void visit(Integer elemet) {
                System.out.print("_" + elemet + "_");
            }
        });
//      bst.preorderTraversal(new Visitor<Integer>() {
//          @Override
//          public void visit(Integer elemet) {
//              System.out.print("_" + elemet + "_");
//              
//          }
//      });
    }
    
    public static void main(String[] args) {
        test1();
    }
}

打印结果如下：

             ┌───7_p(null)───┐
             │               │
        ┌─4_p(7)─┐       ┌─9_p(7)─┐
        │        │       │        │
   ┌─2_p(4)─┐  5_p(4) 8_p(9)   11_p(9)─┐
   │        │                          │
1_p(2)    3_p(2)                    12_p(11)
_7__4__9__2__5__8__11__1__3__12_

遍历接口增强

/**
     * 前序遍历
     */
    public void preorderTraversal(Visitor<E> visitor) {
        if (visitor == null) return;
        preorderTraversal(root,visitor);
    }
    
    private void preorderTraversal(Node<E> node,Visitor<E> visitor) {
        if (node == null || visitor.stop) return;
        visitor.stop = visitor.visit(node.element);
        preorderTraversal(node.left,visitor);
        preorderTraversal(node.right,visitor);
        return;
    }
    
    /**
     * 中序遍历
     */
    public void inorderTraversal(Visitor<E> visitor) {
        if (visitor == null) return;
        inorderTraversal(root,visitor);
    }
    
    private void inorderTraversal(Node<E> node,Visitor<E> visitor) {
        if (node == null || visitor.stop) return;
        inorderTraversal(node.left,visitor);
        if (visitor.stop) return;
        visitor.stop = visitor.visit(node.element);
        inorderTraversal(node.right,visitor);
    }
    
    /**
     * 后序遍历
     */
    public void postorderTraversal(Visitor<E> visitor) {
        if (visitor == null) return;
        postorderTraversal(root,visitor);
    }
    
    private void postorderTraversal(Node<E> node,Visitor<E> visitor) {
        if (node == null || visitor.stop) return;
        postorderTraversal(node.left,visitor);
        postorderTraversal(node.right,visitor);
        if (visitor.stop) return;
        visitor.stop = visitor.visit(node.element);
    }
    
    /**
     * 层序遍历
     */
    public void levelOrderTraversal(Visitor<E> visitor){
        if (root == null || visitor == null) return;
        Queue<Node<E>> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            Node<E> node = queue.poll();
            if (visitor.visit(node.element)) return;
            if (node.left != null) {
                queue.offer(node.left);
            }
            if (node.right != null) {
                queue.offer(node.right);
            }
        }
    }
    /**
     * java抽象类
     */
    public static abstract class Visitor<E> {
        boolean stop;
        /**
         * @return 如果返回true，就代表停止遍历
         */
        public abstract boolean visit(E elemet);
    }

利用上一章节二叉搜索树调用层序遍历

package njf;
import java.util.Comparator;

import njf.printer.BinaryTreeInfo;
import njf.printer.BinaryTrees;
import njf.BinarySearchTree.Visitor;
import njf.file.Files;

public class Main {
    static void test5() {
        Integer data[] = new Integer[] {
                7, 4, 9, 2, 1
        };
        
        BinarySearchTree<Integer> bst = new BinarySearchTree<>();
        for (int i = 0; i < data.length; i++) {
            bst.add(data[i]);
        }
        BinaryTrees.println(bst);
        
        bst.preorderTraversal(new Visitor<Integer>() {
            public boolean visit(Integer element) {
                System.out.print(element + " ");
                return element == 2 ? true : false;
            }
        });
        System.out.println();
        
        bst.inorderTraversal(new Visitor<Integer>() {
            public boolean visit(Integer element) {
                System.out.print(element + " ");
                return element == 4 ? true : false;
            }
        });
        System.out.println();
        
        bst.postorderTraversal(new Visitor<Integer>() {
            public boolean visit(Integer element) {
                System.out.print(element + " ");
                return element == 4 ? true : false;
            }
        });
        System.out.println();
        
        bst.levelOrderTraversal(new Visitor<Integer>() {
            public boolean visit(Integer element) {
                System.out.print(element + " ");
                return element == 9 ? true : false;
            }
        });
        System.out.println();
    }
    
    public static void main(String[] args) {
        test5();
    }
}

打印结果如下：

             ┌─7_p(null)─┐
             │           │
        ┌─4_p(7)       9_p(7)
        │
   ┌─2_p(4)
   │
1_p(2)
7 4 2 
1 2 4 
1 2 4 
7 4 9

前序遍历 – 非递归

    public void preorder(Visitor<E> visitor) {
        if (visitor == null || root == null) return;
        Node<E> node = root;
        Stack<Node<E>> stack = new Stack<>();
        while (true) {
            if (node != null) {
                if (visitor.visit(node.element)) return;
                if (node.right != null) {
                    stack.push(node.right);
                }
                node = node.left;
            }else if(stack.isEmpty()){
                return; 
            }else {
                node = stack.pop();
            }
        }
    }

    public void preorder(Visitor<E> visitor) {
        if (visitor == null || root == null) return;
        Stack<Node<E>> stack = new Stack<>();
        stack.push(root);
        while (!stack.isEmpty()) {
            Node<E> node = stack.pop();
            if (visitor.visit(node.element)) return;
            if (node.right != null) {
                stack.push(node.right);
            }
            if (node.left != null) {
                stack.push(node.left);
            }
        }
    }

中序遍历 – 非递归

public void inorder(Visitor<E> visitor) {
        if (visitor == null || root == null) return;
        Stack<Node<E>> stack = new Stack<>();
        Node<E> node = root;
        while (true) {
            if (node != null) {
                stack.push(node);
                node = node.left;
            }else if (stack.isEmpty()) {
                return;
            }else {
                node = stack.pop();
                if (visitor.visit(node.element)) return;
                node = node.right;
            }
        }
    }

后序遍历 – 非递归

public void postorder(Visitor<E> visitor) {
        if (visitor == null || root == null) return;
        // 记录上一次弹出访问的节点
        Node<E> prev = null;
        Stack<Node<E>> stack = new Stack<>();
        stack.push(root);
        while (!stack.isEmpty()) {
            Node<E> top = stack.peek();
            if (top.isLeaf()|| (prev != null && prev.parent == top)) {//没有子节点
                prev = stack.pop();
                if (visitor.visit(prev.element)) return;
            }else {
                if (top.right != null) {
                    stack.push(top.right);
                }
                if (top.left != null) {
                    stack.push(top.left);
                }
            }
        }
    }

练习：计算二叉树的高度

递归法

public int height() {
      return height(root);
}
    
    /**
     * 计算二叉树的高度，利用递归
     */
private int height(Node<E> node) {
    if (node == null) return 0;
    return 1 + Math.max(height(node.left), height(node.right));
}

层序遍历

    /**
     * 计算二叉树的高度，利用层序遍历
     */
    public int height() {
        if (root == null) return 0;
        // 树的高度
        int height = 0;
        // 存储着每一层的元素数量
        int levelSize = 1;
        Queue<Node<E>> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            Node<E> node = queue.poll();
            levelSize --;
            if (node.left != null) {
                queue.offer(node.left);
            }
            if (node.right != null) {
                queue.offer(node.right);
            }
            if (levelSize == 0) {// 意味着即将要访问下一层
                levelSize = queue.size();
                height ++;
            }
        }
        return height;
    }

练习: 判断一棵树是否为完全二叉树

◼ 如果树为空，返回 false
◼ 如果树不为空，开始层序遍历二叉树(用队列)
如果 node.left!=null，将 node.left 入队
如果 node.left==null && node.right!=null，返回 false
如果 node.right!=null，将 node.right 入队
如果 node.right==null
那么后面遍历的节点应该都为叶子节点，才是完全二叉树
否则返回 false

代码实现

public boolean isCompleteTree() {
        if (root == null) return false;
        Queue<Node<E>> queue = new LinkedList<>();
        queue.offer(root);
        boolean isLeaf = false;
        while (!queue.isEmpty()) {
            Node<E> node = queue.poll();
            //如果出现叶子结点，但是后面结点又不是叶子结点，false
            if (isLeaf && !(node.left == null && node.right == null)) return false;
            if (node.left != null) {
                queue.offer(node.left);
            }else if(node.right != null) {// node.left == null && node.right != null
                return false;
            }
            if(node.right != null) {
                queue.offer(node.right);
            }else {// node.right == null
                isLeaf = true;
            }
        }
        return true;
    }

利用上一章节二叉搜索树验证是否为完全二叉树

package njf;
import java.util.Comparator;

import njf.printer.BinaryTreeInfo;
import njf.printer.BinaryTrees;
import njf.BinarySearchTree.Visitor;
import njf.file.Files;

public class Main {
    static void test7() {
        Integer data[] = new Integer[] {
                7, 4, 10, 2, 5, 9, 11, 3, 1
        };
        
        BinarySearchTree<Integer> bst = new BinarySearchTree<>();
        for (int i = 0; i < data.length; i++) {
            bst.add(data[i]);
        }
        BinaryTrees.println(bst);
        System.out.println("是否为完全二叉树" + bst.isCompleteTree());
    }
    
    public static void main(String[] args) {
        test7();
    }
}

结果如下：

             ┌───7_p(null)────┐
             │                │
        ┌─4_p(7)─┐       ┌─10_p(7)─┐
        │        │       │         │
   ┌─2_p(4)─┐  5_p(4) 9_p(10)   11_p(10)
   │        │
1_p(2)    3_p(2)
是否为完全二叉树true

根据遍历结果重构二叉树

◼ 以下结果可以保证重构出唯一的一棵二叉树

前序遍历 + 中序遍历
例如：
前序遍历：4 2 1 3 6 5
中序遍历：1 2 3 4 5 6
后序遍历 + 中序遍历

◼ 前序遍历 + 后序遍历
✓ 如果它是一棵真二叉树（Proper Binary Tree），结果是唯一的
✓ 不然结果不唯一

前驱节点（predecessor）

◼ 前驱节点：中序遍历时的前一个节点

如果是二叉搜索树，前驱节点就是前一个比它小的节点

实现思路：
◼ 如果node.left != null
举例：6、13、8

predecessor = node.left.right.right.right...

终止条件：right 为 null

◼ 如果node.left == null && node.parent != null
举例：7、11、9、1

predecessor = node.parent.parent.parent...

终止条件：node 在 parent 的右子树中

◼ 如果node.left == null && node.parent == null
那就没有前驱节点
举例：没有左子树的根节点

代码实现:

    /**
     * 是否为前驱结点
     */
    private Node<E> predecessor(Node<E> node) {
        if (node == null) return node;
        // 前驱节点在左子树当中（left.right.right.right....）
        Node<E> p = node.left;
        if (p != null) {
            while (p.right != null) {
                p = p.right;
            }
            return p;
        }
        // 从父结点、祖父节点中寻找前驱节点
        while (node.parent != null && node.parent.left == node) {
            node = node.parent;
        }
        // node.parent == null
        // node == node.parent.right
        return node.parent;
    }

后继节点（successor）

后继节点：中序遍历时的后一个节点

如果是二叉搜索树，后继节点就是后一个比它大的节点

◼ 如果node.right != null
举例：1、8、4

successor = node.right.left.left.left...

终止条件：left 为 null

◼ 如果node.right == null && node.parent != null
举例：7、6、3、11

successor = node.parent.parent.parent...

终止条件：node 在 parent 的左子树中

◼ 如果node.right == null && node.parent == null
那就没有前驱节点
举例：没有右子树的根节点

    /**
     * 是否为后继结点
     */
    private Node<E> successor(Node<E> node) {
        if (node == null) return node;
        // 后继节点在右子树当中（right.left.left.left....）
        Node<E> p = node.right;
        if (p != null) {
            while (p.left != null) {
                p = p.left;
            }
            return p;
        }
        // 从父结点、祖父节点中寻找前驱节点
        while (node.parent != null && node.parent.right == node) {
            node = node.parent;
        }
        // node.parent == null
        // node == node.parent.left
        return node.parent;
    }