数据结构-树论 数据结构树的基本概念

数据结构-树论

作者：Kitten

树结构的定义

除根结点外，其余每个结点有且仅有一个父亲结点。

树结构的术语解释

基础术语

• 结点：树结构里面的每一个元素。
• 父子关系：每个结点之间的连线关系。
• 子树：当结点大于1时，对于当前结点而言，其余的结点分为的互不相交的集合称为子树。

子树是相对而言，子树概念关系着算法递归的实现。

• 度：一个结点拥有的子树数量称为结点的度。

度是对于每一个结点而言的。每个结点都有它的度，最主要的概念用途就是用来区分叶子结点的。

• 叶子：度为0的结点。
• 孩子：当前结点它的子树的称为它的孩子结点
• 双亲：对于当前结点来说它的父结点也称之为它的双亲结点。
• 兄弟：拥同一个双亲的其它结点，对于当前结点来说，其它结点就是它的兄弟结点。
• 森林：由n个互不相交的树结构构成的整体数据结构称为森林

重要术语

• 结点的高度：结点到叶子结点的最长路径

是相对于每个结点而言的，每个结点拥有它自己的高度。

• 结点的深度：根结点到该结点的边个数

相对于每个结点而言的，每个结点拥有它自己的深度。

• 结点的层数：结点的深度+1

对于每个结点而言的，每个结点拥有它自己的层度。

• 树的高度：根结点的高度

它是对于整颗树而言的，就是根结点到叶子结点的最长路径等于树的高度

树的分类

我们通常所熟悉的树结构有：二叉树，平衡二叉树，二叉查找树，B树（BTree和B+Tree），红黑树，完全二叉树，满二叉树。

其中B树系列不是二叉树结构，而是多叉树（N叉树）结构。

其中红黑树是基于平衡二叉树演变来的，平衡二叉树又是基于二叉树演变来的，完全二叉树它是堆排序（大顶堆，小顶堆）实现的基础。

二叉树

一种特殊的树形结构，每个节点至多有颗子树，在二叉树的第n层至多有2^(n-1) 个结点个数。

完全二叉树

除了最后一层叶子结点之外，其它的结点个数必须达到最大，并且最后一层结点都是连续靠左排序。

右图最后一层叶子结点不是靠左连续排序，所以它不是一颗完全二叉树。

满二叉树

除了最后一层叶子结点之外，每个结点都有左右两个子结点。

树结构实现的方式

链表实现树结构

缺点：链表查找的时间复杂度为O(n)

链表是逻辑连续，在物理上是不连续的，在做遍历的时候链表无法利用CPU的缓存。而数组它是连续的空间，CPU可以把连续的数组空间一起放到CPU缓存行中做计算。虽然时间复杂度差不多但是数组的查询效率要高的多。

数组实现树结构

树结构使用数组实现会出现空间的浪费，而链表不会，但是数组可以使用巧妙的方法来实现较为链表更为高效的性能，时间复杂度为：O(log n)，也不需要额外的指针，所以一颗完全的二叉树就是用数组来实现的。

非完全二叉树会存空闲不连续的内存空间（比如下标为6的数组必须空着而不能存7，否则就不满足树结构的定义了。正是因为用数组实现二叉树结构，才会对于那些叶子结点靠左连续排列的树结构称之为完全二叉树。

实现方法的选择

如果需要的树形结构如果满足满二叉树就优先选择数组来实现，普通二叉树优先选择链表。

二叉树的遍历

??前序遍历

分析

先从根结点开始先输出根结点，如果存在左结点，把左结点当作子树作为参数，递归调用前序遍历方法。

左结点处理结束，如果存在右结点，把右结点当作子树作为参数，递归调用前序遍历方法。

口诀：根左右

如示例图中结点输出顺序为：A => B => C => D => E => F => G => H => K

代码实现

定义一个结点

public class TreeNode<T> {
    public T data;
    public TreeNode<T> left;
    public TreeNode<T> right;     
}

public void preEach(TreeNode<?> root) {
    // 输出
    print(root);
    if (root.getLeft() != null) {
        preEach(root.getLeft());
    }
    if (root.getRight() != null) {
        preEach(root.getRight());
    }
}

??中序遍历

分析

先从根结点的左结点开始，如果存在左结点，把左结点当作子树作为参数，递归调用前序遍历方法。

如果左子树处理完成，则输出根结点。

继续处理右结点，如果存在右结点，把右结点当作子树作为参数，递归调用前序遍历方法

口诀：左根右

右图结点输出顺序为： B => D => C => A => E => H => G => K => F

代码实现

public void midEach(TreeNode<?> root) {
    if (root.getLeft() != null) {
        midEach(root.getLeft());
    }
    // 输出
    print(root);
    if (root.getRight() != null) {
        midEach(root.getRight());
    }
}

??后序遍历

分析

先从根结点的左结点开始，如果存在左结点，把左结点当作子树作为参数，递归调用前序遍历方法。

继续处理右结点，如果存在右结点，把右结点当作子树作为参数，递归调用前序遍历方法

等到右子树处理全部处理完成，则输出根结点。

口诀：左右根

右图结点输出顺序为：D => C => B => H => K => G => F => E => A

代码实现

public void postEach(TreeNode<?> root) {
    if (root.getLeft() != null) {
        postEach(root.getLeft());
    }
    if (root.getRight() != null) {
        postEach(root.getRight());
    }
    //输出
    print(root);
}

??层次遍历

实现方法

public void levelOrderTraversal(TreeNode<?> root) {
    if (root == null) {
        return;
    }
    // 使用队列
    Queue<TreeNode<?>> queue = new LinkedList<>();
    queue.offer(root);
    while (!queue.isEmpty()) {
        int size = queue.size();
        for (int i = 0; i < size; i++) {
            TreeNode<?> node = queue.poll();
            if (node == null) {
                continue;
            }
            // 输出
            print(node);
            if (node.getLeft() != null) {
                queue.offer(node.getLeft());
            }
            if (node.getRight() != null) {
                queue.offer(node.getRight());
            }
        }
    }
}

前中后遍历都属于深度优先遍历（DFS），层次遍历属于广度优先遍历（BFS）。

重要口诀：根结点输出，遇见根结点则输出结果。