【数据结构与算法】二叉树

二叉树

基本信息

二叉树是一种非线性结构，二叉树是说一个节点至多有两个子节点的树。

下图中的树是二叉树：

合法的二叉树

下图中这个则不是二叉树：

非二叉树

节点3有三个子节点，所有不是二叉树。

在一个二叉树中，每个值都叫做一个节点（图中每一个绿色的圆形），起始节点也叫做根节点，比如图1中的节点1，如果一个节点没有子节点，那么该节点也叫做叶子节点，树中的一个节点最多有两个子节点，也就是左边的叫做左节点，左节点与下方的节点也是一个树，叫做左子树，相反，右侧的节点叫做右节点，右节点与子节点组成一个树叫做右子树，同一个节点下的两个节点互相叫做兄弟节点，某个节点的最近上层节点，叫做父节点。反之叫做XX的子节点。

树有高的的概念，一个树的高度就是一个树的最大层数，根节点所在的高度最高。比如下图：

二叉树1

这个二叉树中，树的高度就是3，根节点的高度是3，节点2和节点3的高度是2，节点4和5的高度是1。

与高度相反的说法是深度，树的深度就是3，根节点的高度是1，节点2和节点3的高度是2，节点4和5的高度是3。

二叉树可以采用数组或者链表等数据结构来存储，不过通常使用链表，一个二叉树的载体通常是如下一种结构：

public class TreeNode {
    // 节点值
    int val;
    // 左子节点
    TreeNode left;
    // 右子节点
    TreeNode right;

    public TreeNode() {
    }

    public TreeNode(int val) {
        this.val = val;
    }

    public TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

TreeNode中有节点的值、左右孩子节点以为构造方法等信息。

遍历方式

二叉树的遍历通常有两种方式，一种叫做深度优先遍历，一种叫做广度优先遍历。

深度优先遍历

深度优先遍历是说遍历先深入到树的底层，然后再遍历节点，按照节点的输出顺序不同，具体分为前序遍历、中序遍历、后序遍历，三者中的中就是代表根根节点的位置，左右子树的顺序，永远是先左后右的顺序。

二叉树遍历

前序遍历

对于每一个子树，先访问根节点，然后左子树，然后右子树。

无论什么遍历，肯定都需要从根节点1开始遍历，下图是根节点为1这个子树的左右子树情况，绿色是左子树，红色是右子树（后面不做赘述），按照线序遍历，结果应该是[1, 1的左子树, 1的右子树]。此时1的左子树和右子树并未真正的遍历，所以需要遍历。

节点1的左右子树

遍历1的左子树，也就是上图中的绿色部分，在这个左子树中根节点是2，其左右子树如下图所示：

节点2的左右子树

节点为2的这个子树前序遍历结果是[2, 4]。此时节点1这个子树的左子树就遍历完成了，那么[1, 1的左子树, 1的右子树]就变为了[1, 2, 4, 1的右子树]。

接下来遍历节点1的右子树，也就是根节点为3这个子树，如下图所示：

1的右子树

节点5和6是叶子节点，按照前序遍历，得到结果是[3, 5, 6]。此时[1, 2, 4, 1的右子树]中的1的右子树就可以使用[3, 5, 6]替换，最终结果为[1, 2, 4, 4, 5, 6]。

中序遍历

对于每一个子树，先访问左子树，然后根节点，然后右子树。

二叉树遍历

上图中的中序遍历结果是[4, 2, 1, 5, 3, 6]。

后序遍历

对于每一个子树，先访问左子树，然后右子树，然后根节点。

二叉树遍历

上图的后序遍历结果是[4, 2, 5, 6, 3, 1]。

广度优先遍历

广度优先遍历又叫做层序遍历，就是按照层顺序从左到右遍历。

广度优先遍历

按照途中箭头所示一层一层遍历。

代码实现

深度优先遍历

通过上面的分析可以看出来，深度优先遍历是经典的递归思想。

首先创建一个节点的载体类：

public static class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    public TreeNode() {
    }

    public TreeNode(int val) {
        this.val = val;
    }

    public TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

前序遍历

public class DFS {
    // 中序遍历
    public static void preOrderDfs(TreeNode node) {
        if (node == null) {
            return;
        }
        // 打印节点信息
        System.out.printf(node.val + "\t");
        preOrderDfs(node.left);
        preOrderDfs(node.right);
    }

    public static void main(String[] args) {
        TreeNode n1 = new TreeNode(1);
        TreeNode n2 = new TreeNode(2);
        TreeNode n3 = new TreeNode(3);
        TreeNode n4 = new TreeNode(4);
        TreeNode n5 = new TreeNode(5);
        TreeNode n6 = new TreeNode(6);
        n1.left = n2;
        n1.right = n3;
        n2.left = n4;
        n3.left = n5;
        n3.right = n6;
        DFS.preOrderDfs(n1);
    }
}

运行结果如下：

运行结果

中序遍历

public class DFS {
    public static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        public TreeNode() {
        }

        public TreeNode(int val) {
            this.val = val;
        }

        public TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }

    // 中序遍历
    public static void midOrderDfs(TreeNode node) {
        if (node == null) {
            return;
        }
        // 打印节点信息
        midOrderDfs(node.left);
        System.out.printf(node.val + "\t");
        midOrderDfs(node.right);
    }

    public static void main(String[] args) {
        TreeNode n1 = new TreeNode(1);
        TreeNode n2 = new TreeNode(2);
        TreeNode n3 = new TreeNode(3);
        TreeNode n4 = new TreeNode(4);
        TreeNode n5 = new TreeNode(5);
        TreeNode n6 = new TreeNode(6);
        n1.left = n2;
        n1.right = n3;
        n2.left = n4;
        n3.left = n5;
        n3.right = n6;
        DFS.midOrderDfs(n1);
    }
}

运行结果如下：

中序遍历

后序遍历

public class DFS {
    public static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        public TreeNode() {
        }

        public TreeNode(int val) {
            this.val = val;
        }

        public TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }

    // 后序遍历
    public static void postOrderDfs(TreeNode node) {
        if (node == null) {
            return;
        }
        // 打印节点信息
        postOrderDfs(node.left);
        postOrderDfs(node.right);
        System.out.printf(node.val + "\t");
    }

    public static void main(String[] args) {
        TreeNode n1 = new TreeNode(1);
        TreeNode n2 = new TreeNode(2);
        TreeNode n3 = new TreeNode(3);
        TreeNode n4 = new TreeNode(4);
        TreeNode n5 = new TreeNode(5);
        TreeNode n6 = new TreeNode(6);
        n1.left = n2;
        n1.right = n3;
        n2.left = n4;
        n3.left = n5;
        n3.right = n6;
        DFS.postOrderDfs(n1);
    }
}

运行结果如下：

后序遍历结果

广度优先遍历

广度优先遍历可以使用队列来实现

先将根节点入队
当队列不为空的时候出队，出队的时候，判断出队节点是否左右子节点部位空，将不为空的节点入队，循环下去。

import java.util.LinkedList;
import java.util.Queue;

public class DFS {
    public static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        public TreeNode() {
        }

        public TreeNode(int val) {
            this.val = val;
        }

        public TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }

    // 广度优先
    public static void bfs(TreeNode node) {
        if (node == null) {
            return;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(node);
        while (!queue.isEmpty()) {
            int size = queue.size(); // 每行的size
            for (int i = 0; i < size; i++) {
                TreeNode poll = queue.poll();
                if (poll != null) {
                    System.out.printf(poll.val + "\t");
                    if (poll.left != null) {
                        queue.offer(poll.left);
                    }
                    if (poll.right != null) {
                        queue.offer(poll.right);
                    }
                }
            }
        }
    }

    public static void main(String[] args) {
        TreeNode n1 = new TreeNode(1);
        TreeNode n2 = new TreeNode(2);
        TreeNode n3 = new TreeNode(3);
        TreeNode n4 = new TreeNode(4);
        TreeNode n5 = new TreeNode(5);
        TreeNode n6 = new TreeNode(6);
        n1.left = n2;
        n1.right = n3;
        n2.left = n4;
        n3.left = n5;
        n3.right = n6;
        DFS.bfs(n1);
    }
}

运行结果如下：

广度优先遍历

【数据结构与算法】二叉树

二叉树

基本信息

遍历方式

深度优先遍历

前序遍历

中序遍历

后序遍历

广度优先遍历

代码实现

深度优先遍历

前序遍历

中序遍历

后序遍历

广度优先遍历

添加新评论

最新文章

最近回复

分类

归档

其它