数据结构之树

目的
一、数据结构

目的

程序 = 数据结构 + 算法

了解数据结构、算法思想、优缺点、合理运用到项目中，常见算法：

一、数据结构

1. 树

1.1 基础

2021-07-29_Tree

节点高度：节点到叶子节点最长路径；

节点深度：根节点到节点经历边的个数；

节点层次：节点深度 + 1；

节点的度：含有子节点个数；

树高度：根节点高度；

树的度：最大节点的度。

树是一种特殊的图。每个节点只有一个父节点，且不能形成环。
实例：家谱

最小生成树：n个顶点的连通图中选择n-1条边，构成权值之和最小的连通子图，被称为最小生成树。

1.2 扩展

二叉树、B-树、B+树、红黑树、堆、伸展树。

二叉树：每个节点最多含有两个子树的树称为二叉树；

满二叉树：叶节点除外的所有节点均含有两个子树的树被称为满二叉树；

完全二叉树：除最后一层外，所有层都是满节点，且最后一层缺右边连续节点的二叉树称为完全二叉树； —-> 底层用数组存效率高

哈夫曼树（最优二叉树）：带权路径最短的二叉树称为哈夫曼树或最优二叉树。

B+树是应文件系统所需而产生的一种B-树的变形树。一棵m阶的B+树和m 阶的B-
树的差异在于：
⑴有n 棵子树的结点中含有n 个关键码；
⑵所有的叶子结点中包含了全部关键码的信息，及指向含有这些关键码记录的指针，且
叶子结点本身依关键码的大小自小而大的顺序链接。
⑶所有的非终端结点可以看成是索引部分，结点中仅含有其子树根结点中最大（或最小）关键码。

B+与B-树区别来源

2.二叉查找树

所有左边节点及子节点的值都小于父节点值，所有右边节点及子节点的值大于父节点值。

平均时间复杂段为 logn; 如果为特殊的，类似单链表的二叉查找树，时间复杂度为：O(n)。

2.1 二叉树的序列化与反序列化

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Codec {

    public static void main(String[] args) {
        //1,2,3,null,null,4,5
        TreeNode treeNode = new TreeNode(1);
        treeNode.left = new TreeNode(2);
        treeNode.right = new TreeNode(3);
        treeNode.right.left = new TreeNode(4);
        treeNode.right.right = new TreeNode(5);

        String serializeStr = serialize(treeNode);
        System.out.println(serializeStr);

        TreeNode ret = deserialize(serializeStr);
        System.out.println(ret);
    }
    
    // Encodes a tree to a single string.
    String serialize(TreeNode root) {
        
        if(root == null)
        {
            return "[]";
        }
        List<TreeNode> list = new ArrayList<>();
        list.add(root);
        // [1,2,3,null,null,4,5]
        for(int i =0;i<list.size();i++)
        {
            TreeNode node = list.get(i);
            if(node ==null)
            {
                continue;
            }
            list.add(node.left);
            list.add(node.right);
        }
        
        //[1,2,3,null,null,4,5]
        while(list.get(list.size()-1) ==null)
        {
            list.remove(list.size()-1);
        }
        
        StringBuilder sb = new StringBuilder("[");
        sb.append(list.get(0).val);
        
        for(int i=1;i<list.size();i++)
        {
            if(list.get(i) == null)
            {
                sb.append(",null");
            }
            else
            {
                sb.append(","+list.get(i).val);
            }
        }
        sb.append("]");
        return sb.toString();
    }

    // Decodes your encoded data to tree.
    TreeNode deserialize(String data) {
        
        if(data == null || data.equals("[]"))
        {
            return null;
        }
        
        //1,2,3,null,null,4,5
        String[] datas = data.substring(1,data.length()-1).split(",");
        boolean isLeft = true;
        TreeNode node = new TreeNode(Integer.parseInt(datas[0]));
        List<TreeNode> list = new ArrayList<>();
        list.add(node);
        int index=0;
        for(int i =1;i<datas.length;i++)
        {
            if(!datas[i].equals("null"))
            {
                TreeNode node1 = new TreeNode(Integer.parseInt(datas[i]));
                if(isLeft)
                {
                    list.get(index).left= node1;
                }
                else
                {
                    list.get(index).right=node1;
                }
                list.add(node1);
            }
            
            if(!isLeft)
            {
                index++;
            }
            
            isLeft = !isLeft;
        }
        return list.get(0);
    }
}

// Your Codec object will be instantiated and called as such:
// Codec ser = new Codec();
// Codec deser = new Codec();
// TreeNode ans = deser.deserialize(ser.serialize(root));
//分析： 1. 考查树存储结构       -----> 用List<TreeNode> 存储带有子节点的各节点
//      2. 遍历、取值

2.2 树的遍历（前序、中序、后序）

//不同的顺序，决定不同的遍历；根的遍历顺序 // 前序遍历：根前，从左到右 // 中序遍历：根中，从左到右 // 后序遍历：根后，从左到右

2.2.1 常规遍历

// 常规遍历写法
public class BasicTreeOrder {
    public static void main(String[] args) {

        //1,2,3,null,null,4,5
        TreeNode treeNode = new TreeNode(1);
        treeNode.left = new TreeNode(2);
        treeNode.right = new TreeNode(3);
        treeNode.right.left = new TreeNode(4);
        treeNode.right.right = new TreeNode(5);

        BasicTreeOrder bt = new BasicTreeOrder();
        System.out.println("前序遍历： " + bt.preOrderTraversal(treeNode));
        System.out.println("中序遍历： " + bt.inOrderTraversal(treeNode));
        System.out.println("后序遍历： " + bt.postOrderTraversal(treeNode));
    }

    public List<Integer> preOrderTraversal(TreeNode root) {

        if (root == null) {
            return null;
        }

        List<Integer> ret = new ArrayList<Integer>();
        List<Integer> left = preOrderTraversal(root.left);
        List<Integer> right = preOrderTraversal(root.right);

        //不同的顺序，决定不同的遍历； 根的遍历顺序
        // 前序遍历：根前，从左到右
        // 中序遍历：根中，从左到右
        // 后序遍历：根后，从左到右
        ret.add(root.val);
        if (left != null) {
            ret.addAll(left);
        }
        if (right != null) {
            ret.addAll(right);
        }

        return ret;
    }

    public List<Integer> inOrderTraversal(TreeNode root) {

        if (root == null) {
            return null;
        }
        List<Integer> ret = new ArrayList<Integer>();
        List<Integer> left = inOrderTraversal(root.left);
        List<Integer> right = inOrderTraversal(root.right);

        //不同的顺序，决定不同的遍历； 根的遍历顺序
        // 前序遍历：根前，从左到右
        // 中序遍历：根中，从左到右
        // 后序遍历：根后，从左到右
        if (left != null) {
            ret.addAll(left);
        }
        ret.add(root.val);
        if (right != null) {
            ret.addAll(right);
        }

        return ret;
    }
    
    public List<Integer> postOrderTraversal(TreeNode root) {

        if (root == null) {
            return null;
        }
        List<Integer> ret = new ArrayList<Integer>();
        List<Integer> left = postOrderTraversal(root.left);
        List<Integer> right = postOrderTraversal(root.right);

        //不同的顺序，决定不同的遍历； 根的遍历顺序
        // 前序遍历：根前，从左到右
        // 中序遍历：根中，从左到右
        // 后序遍历：根后，从左到右
        if (left != null) {
            ret.addAll(left);
        }
        if (right != null) {
            ret.addAll(right);
        }
        ret.add(root.val);

        return ret;
    }
}
class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

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

2.2.2 前序遍历

基于栈实现（注意遍历顺序）

public class PreOrder {
    
    /**
     * 前序遍历 (根前，从左到右）
     *
     * @param treeNode 树
     * @return 遍历结果
     */
    public List<Integer> preOrder(TreeNode treeNode) {

        List<Integer> result = new ArrayList<Integer>();
        if (treeNode == null) {
            return result;
        }

        Stack<TreeNode> stack = new Stack<TreeNode>();
        stack.push(treeNode);
        while (!stack.isEmpty()) {
            TreeNode node = stack.pop();
            if (node.right != null) {
                stack.push(node);
            }
            if (node.left != null) {
                stack.push(node.left);
            }
            result.add(node.val);
        }
        return result;
    }
}

2.3 二叉树的右视角

/**
 * https://leetcode-cn.com/problems/binary-tree-right-side-view/
 * 二叉树右视角
 * <p>
 * 给定一个二叉树的 根节点 root，想象自己站在它的右侧，按照从顶部到底部的顺序，返回从右侧所能看到的节点值。
 *
 */
public class RightSideView {

    public static void main(String[] args) {
        //1,2,3,null,null,4,5
        TreeNode treeNode = new TreeNode(1);
        treeNode.left = new TreeNode(2);
        treeNode.right = new TreeNode(3);
        treeNode.left.left = new TreeNode(4);
        //treeNode.right.right = new TreeNode(5);


        System.out.println(new RightSideView().rightSideView(treeNode));
    }

    /**
     * 每一层最右边节点 1,2,3,null,null,4,5
     *
     * @param root 树
     * @return 集合
     */
    public List<Integer> rightSideView(TreeNode root) {
        List<Integer> ret = new ArrayList<>();
        if (root == null) {
            return ret;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        
        boolean findRight;
        while (!queue.isEmpty()) {
            //只处理当前层级 (随节点数变化的）
            int size = queue.size();
            findRight = false;
            for (int i = 0; i < size; i++) {
                TreeNode node = queue.poll();
                if (!findRight) {
                    ret.add(node.val);
                    findRight = true;
                }
                if (node.right != null) {
                    queue.offer(node.right);
                }
                if (node.left != null) {
                    queue.offer(node.left);
                }
            }
        }
        return ret;
    }
}

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

    TreeNode(int x) {
        val = x;
    }

}
//分析： 1. 考查树存储结构       -----> 用List<TreeNode> 存储带有子节点的各节点
//      2. 遍历、取值

参考

«算法图解»

”程序员小灰“ 公众号 (推荐)
项目：https://gitee.com/xushj/algorithm/tree/master/src/main/java/tree

约瑟夫问题

网课（腾讯课堂）

欢迎拍砖,多多交流,转载请注明出处:[没长正的技术专栏](http://blog.meizhangzheng.com) 如涉及侵权问题，请发送邮件到xsj34567@163.com，如情况属实本人将会尽快删除。

数据结构之树

目的

一、数据结构

1. 树

1.1 基础

1.2 扩展

2.二叉查找树

2.1 二叉树的序列化与反序列化

2.2 树的遍历（前序、中序、后序）

2.2.1 常规遍历

2.2.2 前序遍历

2.3 二叉树的右视角

参考

Comments