树

基础认识

二叉树

二叉树，顾名思义就是一个结点有两个分叉就是二叉树

创建一个二叉树

1
2
3
4
5
6
7
8
9
10
public static class BinaryTreeNode {

    private int data;  //节点的具体数据
    private BinaryTreeNode leftChirld;  //左孩子
    private BinaryTreeNode rightChirld; //右孩子
    private BinaryTreeNode(int x)
    {
        data=x;
    }
}

满二叉树

所有结点（除了叶子结点外）都有左节点和右节点

完全二叉树

假设完全二叉树高度为k，则完全二叉树需要符合以下两点：
1）所有叶子节点都出现在k层或k-1层，并且从1~k-1层必须达到最大节点数。
2）第k层可以是不满的，但是第k层的所有节点必须集中在最左边。

平衡二叉树

二叉搜索树

红黑树

  1. 根节点是【黑色】
  2. 每个节点要么是【黑色】要么是【红色】
  3. 每个【红色】节点的两个子节点一定都是【黑色】
  4. 每个叶子节点（NIL）都是【黑色】
  5. 任意一个节点的路径到叶子节点所包含的【黑色】节点的数量是相同的—这个也称之为【黑色完美平衡】
  6. 新插入的节点必须是【红色】->为什么？如果新插入的节点是【黑色】，那不管是在插入到那里，一定会破坏黑色完美平衡的，因为任意一个节点的路径到叶子节点的黑色节点的数量肯定不一样了（第 6 点我自己加的，实际特性的定义是前 5 个

左旋

以某个节点作为固定支撑点（围绕该节点旋转）,其右子节点变为旋转节点的父节点，右子节点的左子节点变为旋转节点的右子节点，左子节点保持不变

右旋

以某个节点作为固定支撑点（围绕该节点旋转）,其左子节点变为旋转节点的父节点，左子节点的右子节点变为旋转节点的左子节点，右子节点保持不变

节点数

1
2
3
4
5
6
7
// 定义：count(root) 返回以 root 为根的树有多少节点
int count(TreeNode root) {
    // base case
    if (root == null) return 0;
    // 自己加上子树的节点数就是整棵树的节点数
    return 1 + count(root.left) + count(root.right);
}

遍历

DFS

深度优先遍历

在我的理解中，其实深度优先遍历很简单，比如说是[1,2,3],就是随机选择一个点开始，比如说选择1，然后接着就是2和3随机选择一个，比如说选择2，最后就是3，路径就是[1,2,3]

算法实现思路：

首先所有数据的组合是一个数组，这个数组以树的方式类进行排列

树的话遍历的画需要知道第几层，于是path这个栈来了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
package algorithm;

import java.util.*;

public class demo {
    public static List<List<Integer>> s(int[] nums)
    {
        int lens=nums.length;
        List<List<Integer>> res = new ArrayList<>();
        if(lens==0)
        {
            return res;
        }
        //path  递归到第一层
        //path  已经选了哪些树
        //used  表示哪个树已经被触碰过了
        Deque<Integer> path = new ArrayDeque<Integer>();
        boolean[] used = new boolean[lens];
        dfs(nums,lens,0,path,used,res);
        return res;
    }

    private static void dfs(int[] nums, int lens, int depth, Deque<Integer> path, boolean[] used, List<List<Integer>> res) {
        if(depth==lens)
        {
            res.add(new ArrayList<>(path));
            return;
        }
        for (int i = 0; i < lens; i++) {
            if(used[i])
            {
               continue;
            }
            path.addLast(nums[i]);
            used[i]=true;
            dfs(nums,lens,depth+1,path,used,res);
            path.removeLast();
            used[i]=false;
        }
    }
    }
}

层次遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
    public static List<List<Integer>> levelOrder(TreeNode root) {
    List<List<Integer>> result= new ArrayList<>();
    if(root==null){
        return result;
    }
    //创建队列，将root加入，建立第一层
    Queue<TreeNode> queue = new LinkedList<>();
    queue.offer(root);
    //遍历每一层节点的同时将下一层节点放进队列
    while(!queue.isEmpty()){
        int size = queue.size();
        List<Integer> level = new ArrayList<>();
        //遍历上层节点，拓展队列，将下层节点加到队列
        for(int i=0;i<size;i++){
            TreeNode node = queue.poll();
            level.add(node.val);
            if(node.left!=null){
                queue.offer(node.left);
            }
            if(node.right!=null){
                queue.offer(node.right);
            }
        }
        //将第x层遍历list放进最终大的list
        result.add(level);    
    }
    return result;
}

前序遍历

快速排序其实用的就是 二叉树的前序遍历

归并排序用的是 分治思想

1
2
3
4
5
6
7
8
public void inorder(TreeNode root, List<Integer> res) {
        if (root == null) {
            return;
        };
        res.add(root.val);
        inorder(root.left, res);
        inorder(root.right, res);
    }

前中后序遍历中的前中后，讲的是根节点的位置，比如

前序遍历：先是根节点，接着左节点，最后右节点

中序遍历：先是左节点，接着根节点，最后右节点

后序遍历：先是左节点，接着右节点，最后根节点

中序遍历

1
2
3
4
5
6
7
8
public void inorder(TreeNode root, List<Integer> res) {
        if (root == null) {
            return;
        };
        inorder(root.left, res);
        res.add(root.val);
        inorder(root.right, res);
    }

后序遍历

1
2
3
4
5
6
7
8
public void inorder(TreeNode root, List<Integer> res) {
        if (root == null) {
            return;
        };
        inorder(root.left, res);
        inorder(root.right, res);
    res.add(root.val);
    }