数据结构-二叉树

 二叉树(Binary tree)是数据结构里树形结构的一个重要类型,常常用在时间复杂度或空间复杂度为logN的场景。  

二叉树

二叉树是n个有限元素的集合,该集合或者为空、或者由一个称为根(root)的元素及两个不相交的、被分别称为左子树和右子树的二叉树组成,是有序树。

public class TreeNode {

    public int val;
    public TreeNode left;
    public 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;
    }
    
}

术语

①节点:包含一个数据元素及若干指向子树分支的信息。
②节点的度:一个节点拥有子树的数目称为节点的度。
③叶子节点:也称为终端节点,没有子树的节点或者度为零的节点。
④分支节点:也称为非终端节点,度不为零的节点称为非终端节点。
⑤树的度:树中所有节点的度的最大值。
⑥节点的层次:从根节点开始,假设根节点为第1层,根节点的子节点为第2层,依此类推,如果某一个节点位于第L层,则其子节点位于第L+1层 。
⑦树的深度:也称为树的高度,树中所有节点的层次最大值称为树的深度。
⑧有序树:如果树中各棵子树的次序是有先后次序,则称该树为有序树。
⑨无序树:如果树中各棵子树的次序没有先后次序,则称该树为无序树。
⑩森林:由m(m≥0)棵互不相交的树构成一片森林。如果把一棵非空的树的根节点删除,则该树就变成了一片森林,森林中的树由原来根节点的各棵子树构成 。

二叉树节点的深度:指从根节点到该节点的最长简单路径边的条数。
二叉树节点的高度:指从该节点到叶子节点的最长简单路径边的条数。

二叉树的性质

性质1 二叉树第i层上的结点数目最多为2^(i-1)个 (i≥1)。

性质2 深度为k的二叉树至多有2^k-1个结点(k≥1)。

性质3 在任意-棵二叉树中,若终端结点(叶子节点)的个数为n0,度为2的结点数为n2,则no=n2+1。

特殊的二叉树

 二叉树按照特点, 满二叉树、完全二叉树、二叉搜索数、平衡二叉搜索树

满二叉树

 满二叉树:如果一棵二叉树只有度为0的结点和度为2的结点,并且度为0的结点在同一层上,则这棵二叉树为满二叉树。

这棵二叉树为满二叉树,也可以说深度为n,有2^(n-1)个节点的二叉树。

完全二叉树

 完全二叉树:在完全二叉树中,除了最底层叶子节点可能没填满外,其余每层节点数都达到最大值,并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第n层,则该层包含 1~ 2^(n-1) 个节点。

二叉搜索树

二叉搜索树是有数值的,二叉搜索树是一个有序树。
若它的左子树不空,则左子树上所有结点的值均小于它的根结点的值;
若它的右子树不空,则右子树上所有结点的值均大于它的根结点的值;
它的左、右子树也分别为二叉排序树

平衡二叉搜索树

 平衡二叉搜索树:又被称为AVL(Adelson-Velsky and Landis)树,且具有以下性质:它是一棵空树或它的左右两个子树的高度差的绝对值不超过1,并且左右两个子树都是一棵平衡二叉树。

 

二叉树的存储方式

 二叉树可以链式存储,也可以顺序存储。

链式存储

链式存储

顺序存储

顺序存储

二叉树顺序存储特点: 如果父节点的数组下标是i,那么它的左孩子下标是 2*i + 1,右孩子下标是 2*i + 2

二叉树的遍历方式

二叉树主要有两种遍历方式:

1、深度优先遍历:先往深走,遇到叶子节点再往回走。
2、广度优先遍历:一层一层的去遍历。
这两种遍历是图论中最基本的两种遍历方式
 
从深度优先遍历和广度优先遍历进一步拓展,才有如下遍历方式:
深度优先遍历
前序遍历(递归法,迭代法)
中序遍历(递归法,迭代法)
后序遍历(递归法,迭代法)
广度优先遍历
层次遍历(迭代法)

public class TreeNode {

    public int val;
    public TreeNode left;
    public 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;
    }

}

深度优先遍历

前序遍历,对树中的任意节点来说,先打印节点本身,然后打印它的左子树,最后打印它的右子树。 (根左右)
中序遍历,对树中的任意节点来说,先打印它的左子树,然后再打印它的本身,最后打印它的右子树。 (左根右)
后序遍历,对于树中的任意节点来说,先打印左子树,然后打印右子树,最后才打印节点本身。 (左右根)

二叉树遍历

前序遍历

二叉树的前序遍历:按照访问根节点——左子树——右子树的方式遍历这棵树,而在访问左子树或者右子树的时候,我们按照同样的方式遍历,直到遍历完整棵树。

144. 二叉树的前序遍历

递归法

class Solution {

    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<Integer>();
        preorder(root, res);
        return res;
    }

    public void preorder(TreeNode root, List<Integer> res) {
        // 结束条件 遍历到的根节点为空
        if (root == null) {
            return;
        }
        // 根节点——左子树——右子树
        res.add(root.val);
        preorder(root.left, res);
        preorder(root.right, res);
    }
}

时间复杂度:O(n),其中 n 是二叉树的节点数。每一个节点恰好被遍历一次。
空间复杂度:O(n),为递归过程中栈的开销,平均情况下为O(logn),最坏情况下树呈现链状,为 O(n)。


中序遍历

94. 二叉树的中序遍历

后序遍历

145. 二叉树的后序遍历

class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<Integer>();
        postorder(root, res);
        return res;
    }

    public void postorder(TreeNode root, List<Integer> res) {
        if (root == null) {
            return;
        }
        // 左右根
        postorder(root.left, res);
        postorder(root.right, res);
        res.add(root.val);
    }
}

广度优先遍历

广度优先搜索(BFS)两个场景:层序遍历、最短路径。

层序遍历

102. 二叉树的层序遍历

二叉树层序遍历动图

/**
 *
 * 
 *  参考:https://leetcode.cn/problems/binary-tree-level-order-traversal/solution/bfs-de-shi-yong-chang-jing-zong-jie-ceng-xu-bian-l/
*/
public List<List<Integer>> levelOrder(TreeNode root) {
    List<List<Integer>> res = new ArrayList<>();

    // 保存遍历结果  队列是先进先出 保证每次从队列头出队
    Queue<TreeNode> queue = new ArrayDeque<>();
    if (root != null) {
        queue.add(root);
    }
    // 结束条件
    while (!queue.isEmpty()) {
        // 上一层的节点个数  通过n来控制遍历节点个数  保证把队列
        int n = queue.size();
        // 当前层遍历到节点的值
        List<Integer> level = new ArrayList<>();
        // 上一层有n个节点 需要从队列头部出队n次
        for (int i = 0; i < n; i++) { 
            // 从队列头出队 
            TreeNode node = queue.poll();
            level.add(node.val);
            // 把当前层遍历到的节点放到队列尾部
            if (node.left != null) {
                queue.add(node.left);
            }
            if (node.right != null) {
                queue.add(node.right);
            }
        }
        res.add(level);
    }

    return res;
}
/**
  * 1. 获取根节点集合
  * 2. 根据根节点获取下一层的节点
  * 3. 循环  只要根节点集合不为空就循环
  */
public List<List<Integer>> levelOrder(TreeNode root) {

    if (root == null) {
        return Collections.emptyList();
    }

    List<List<Integer>> list = new ArrayList<List<Integer>>();
    list.add(Collections.singletonList(root.val));

    List<TreeNode> rootNodes = Collections.singletonList(root);
    while (true) {
        // 根据根节点集合获取下一层节点
        List<TreeNode> levelNodes = getLevelNodes(rootNodes);
        if (levelNodes == null || levelNodes.size() == 0) {
            break;
        }
        // 根据节点获取值
        List<Integer> levelList = getValues(levelNodes);
        list.add(levelList);
        // 更新根节点集合
        rootNodes = levelNodes;
    }

    return list;
}

public List<Integer> getValues(List<TreeNode> levelNodes) {
    List<Integer> list = new ArrayList();
    for (TreeNode node : levelNodes) {
        list.add(node.val);
    }
    return list;
}

public List<TreeNode> getLevelNodes(List<TreeNode> rootNodes) {
    if (rootNodes == null || rootNodes.size() == 0) {
        return Collections.emptyList();
    }

    List<TreeNode> list = new ArrayList();
    for (TreeNode node : rootNodes) {
        if (node.left != null) {
            list.add(node.left);
        }
        if (node.right != null) {
            list.add(node.right);
        }
    }
    return list;
}

最短路径

1162. 地图分析

参考资料

[1] 《数据结构》(C语言版) 严蔚敏 吴伟民
[2] 二叉树理论基础篇
[3] 二叉树
[4] 二叉树的性质及相关证明
[5] 23-二叉树基础(上):什么样的二叉树适合用数组来存储?