数据结构与算法——二叉树(上)

Cypress 2019-07-01

1. 什么是树?

前面说到的几种数据结构都是线性的,例如链表、栈、队列等,今天就来学习一种非线性的数据结构——树。先来看看几种树的结构:

数据结构与算法——二叉树(上)

有没有发现,其实树这种结构跟我们现实生活中的“树”非常的相似,像上图中的这棵“树”,节点 A 称作 B 和 C 的父节点,节点 B 和 C 在同一级,叫做兄弟节点。没有父节点的 A 节点叫做根节点,没有子节点的节点叫做叶子节点或叶节点,例如图中的 D E F G。

树的节点还涉及到三个概念,分别是高度、深度、层。

节点高度:节点到叶子节点的最长路径

节点深度:根节点到这个节点所经历的边的个数

节点的层:节点深度 + 1

树的高度:根节点的高度

结合下面的图你就能够理解了,高度是从下到上数的,深度是从上到下数的:

数据结构与算法——二叉树(上)

2. 二叉树

树的形态多种多样,但是我们平常最常用的还是二叉树,顾名思义,二叉树就是每个节点最多只有两个子节点的树。

数据结构与算法——二叉树(上)

在上图中的几种二叉树中,有两个是比较特殊的,分别是满二叉树和完全二叉树

满二叉树:树的叶子节点全在最底层,并且除了叶子节点,每个节点都有左右两个子节点,例如上图中的树 2。

完全二叉树:叶子节点都在最底下两层,最底层的节点全都靠左排列,并且除了最后一层,其他层的节点都必须有左右两个节点,例如上图中的树 3。

完全二叉树的概念有点不太好理解,你可以多思考一下,其实满二叉树就是完全二叉树的一种特殊情况。完全二叉树的这种特性是为了方便其在数组中的存储,不至于浪费太多的内存空间,等后面说到堆的时候你就更能理解了。
除了使用数组存储二叉树外,最常用的便是使用链表法来储存二叉树了。下面说到的二叉树的遍历便是这种存储方法。

3. 二叉树的遍历

二叉树的一种常见操作就是需要遍历得到树种的全部数据,最常用的遍历方式有三种:前序遍历、中序遍历、后序遍历。

  • 前序遍历:对于树中的任意节点来说,先遍历这个节点,然后遍历这个节点的左子节点,最后遍历这个节点的右子节点。(父左右)
  • 中序遍历:对于树中的任意节点来说,先遍历这个节点的左子节点,然后遍历这个节点本身,最后遍历这个节点的右子节点。(左父右)
  • 后序遍历:对于树中的任意节点来说,先遍历这个节点的左子节点,然后遍历这个节点的右子节点,最后遍历这个节点本身。(左右父)

数据结构与算法——二叉树(上)

其实树的遍历是一种很典型的递归操作,代码也可以使用递归来实现,你可以看看我实现的代码。

//1.前序遍历
    public void preOrder(Node head){
        if (head == null) return;
        System.out.print(head.getData() + "  ");
        preOrder(head.left);
        preOrder(head.right);
    }

    //2.中序遍历
    public void midOrder(Node head){
        if (head == null) return;
        midOrder(head.left);
        System.out.print(head.getData() + "  ");
        midOrder(head.right);
    }

    //3.后序遍历
    public void postOrder(Node head){
        if (head == null) return;
        postOrder(head.left);
        postOrder(head.right);
        System.out.print(head.getData() + "  ");
    }

相关推荐