数据结构与算法

一.数据结构

1.定义：是计算机存储、组织数据的方式。数据结构是指相互之间存在一种或多种特定关系的数据元素的集合

2.分类

可分为两大类：逻辑结构和物理结构

• 逻辑结构可分为：集合结构、线性结构、树形结构、圆形结构
• 物理结构可分为：顺序存储结构、链表存储结构

3.线性表

image.png

• 线性表可分为：顺序存储方式线性表、链表存储方式线性表

（1）顺序存储方式线性表（可看ArrayList的源码）

• 优点：查询快（可直接根据索引查找相应的数据）

• 缺点：增删慢（需要将数据遍历copy到另外一个新的数组中，并且增删后，增删的这个数据后的所以数据都需要变动位置）

  
  image.png
  image.png

（2）链表存储方式线性表（可看LinkedList源码）

• 优点：增删快（可直接在任意位置添加数据，并且只需要变动之前相邻两个数据的第一个数据的next----new的数据；new的数据的next---之前第二个数据）
• 缺点：查询慢（需要一个个查询，当然他可以根据你的角标和count/2做对比，如果是小于，则从前半段开始顺着着，否则，从后半段开始逆着找）

二.栈和队列（可看Stack源码）

1.栈

定义：允许插入和删除的一端称为栈顶（top），另一端称为栈底（bottom）,不含任何数据元素的栈称为空栈。栈又称为后进先出的线性表

栈的顺序存储结构
栈的链式存储结构

2.队列

定义：只允许在一端进行插入操作，在另一端进行删除操作的线性表。插入的一端称为队尾，删除的一端称为队头

• 队列的链式存储结构（可看LinekedList源码的offer（插入）和poll（删除）方法）

  
  定义
  image.png
  空队列

3.二叉树（前序遍历、中序遍历、后序遍历）

public class BinaryTree {

    private TreeModle root;

    public static void main(String[] args) {
        BinaryTree binaryTree = new BinaryTree();
        binaryTree.createBinaryTree();
        System.out.println("height:" + binaryTree.getHeight());
        System.out.println("size:" + binaryTree.getSize());
//        binaryTree.preorder(binaryTree.root);
//        System.out.println("------------------");
//        binaryTree.midorder(binaryTree.root);
//        System.out.println("------------------");
//        binaryTree.nextorder(binaryTree.root);
//        System.out.println("------------------");
//        binaryTree.noPreOrder(binaryTree.root);
        ArrayList<String> data = new ArrayList<>();
        String[] s = {"A", "B", "D", "#", "#", "E", "#", "#", "C", "#", "F","#","#"};
        for (int i = 0; i < s.length; i++) {
            data.add(s[i]);
        }
        binaryTree.createBinaryTreePre(data);
        binaryTree.preorder(binaryTree.root);


    }


    public BinaryTree() {
        root = new TreeModle(1, "A");
    }

    /**
     * 构建二叉树
     * <p>
     * A
     * B     C
     * D     E     F
     */
    public void createBinaryTree() {
        TreeModle nodeB = new TreeModle(2, "B");
        TreeModle nodeC = new TreeModle(3, "C");
        TreeModle nodeD = new TreeModle(4, "D");
        TreeModle nodeE = new TreeModle(5, "E");
        TreeModle nodeF = new TreeModle(6, "F");
        root.leftTreeModle = nodeB;
        root.rightTreeModle = nodeC;
        nodeB.leftTreeModle = nodeD;
        nodeB.rightTreeModle = nodeE;
        nodeC.rightTreeModle = nodeF;

    }


    /**
     * 返项创建二叉树（ABD##E##C#F##）
     * @param data
     */
    public void createBinaryTreePre(ArrayList<String> data) {
        createBinaryTree(data.size(), data);

    }

    private TreeModle createBinaryTree(int size, ArrayList<String> data) {
        if (data.size() == 0) {
            return null;
        }
        String d = data.get(0);
        int index = size - data.size();
        TreeModle treeModle;
        if (d.equals("#")) {
            treeModle = null;
            data.remove(0);
            return treeModle;


        }

        treeModle = new TreeModle(index, d);
        if (index == 0) {
            //创建根节点
            root = treeModle;
        }
        data.remove(0);
        treeModle.leftTreeModle = createBinaryTree(size, data);
        treeModle.rightTreeModle = createBinaryTree(size, data);

        return treeModle;

    }

    /**
     * 求二叉树的高度
     */
    public int getHeight() {
        return getHeight(root);
    }

    private int getHeight(TreeModle treeModle) {
        if (treeModle == null) {
            return 0;
        } else {
            int i = getHeight(treeModle.leftTreeModle);
            int j = getHeight(treeModle.rightTreeModle);
            return (i < j) ? j + 1 : i + 1;
        }
    }

    /**
     * 获取二叉树的节点数
     */
    public int getSize() {
        return getSize(root);
    }

    private int getSize(TreeModle treeModle) {
        if (treeModle == null) {
            return 0;
        } else {
            return 1 + getSize(treeModle.leftTreeModle) + getSize(treeModle.rightTreeModle);
        }

    }

    /**
     * 前序遍历二叉树---迭代(跟左右)
     */
    public void preorder(TreeModle root) {
        if (root == null) {
            return;
        }
        System.out.println(root.getData());
        preorder(root.leftTreeModle);
        preorder(root.rightTreeModle);

    }

    /**
     * 前序遍历二叉树---非迭代
     */
    public void noPreOrder(TreeModle root) {
        if (root == null) {
            return;
        }
        Stack<TreeModle> stack = new Stack<>();
        stack.push(root);
        while (!stack.isEmpty()) {
            //弹出和入栈
            TreeModle pop = stack.pop();
            System.out.println(pop.getData());
            if (pop.rightTreeModle != null) {
                stack.push(pop.rightTreeModle);
            }
            if (pop.leftTreeModle != null) {
                stack.push(pop.leftTreeModle);
            }


        }
    }

    /**
     * 中序遍历二叉树---迭代(左跟右)
     */

    public void midorder(TreeModle treeModle) {
        if (treeModle == null) {
            return;
        }

        midorder(treeModle.leftTreeModle);
        System.out.println(treeModle.getData());
        midorder(treeModle.rightTreeModle);

    }

    /**
     * 后续遍历---迭代（左右跟）
     */
    public void nextorder(TreeModle treeModle) {
        if (treeModle == null) {
            return;
        }
        nextorder(treeModle.leftTreeModle);
        nextorder(treeModle.rightTreeModle);
        System.out.println(treeModle.getData());
    }

    class TreeModle {
        public int index;
        public String data;
        public TreeModle leftTreeModle;
        public TreeModle rightTreeModle;

        public TreeModle(int index, String data) {
            this.index = index;
            this.data = data;
            this.leftTreeModle = null;
            this.rightTreeModle = null;
        }

        public int getIndex() {
            return index;
        }

        public void setIndex(int index) {
            this.index = index;
        }

        public String getData() {
            return data;
        }

        public void setData(String data) {
            this.data = data;
        }

        public TreeModle getLeftTreeModle() {
            return leftTreeModle;
        }

        public void setLeftTreeModle(TreeModle leftTreeModle) {
            this.leftTreeModle = leftTreeModle;
        }

        public TreeModle getRightTreeModle() {
            return rightTreeModle;
        }

        public void setRightTreeModle(TreeModle rightTreeModle) {
            this.rightTreeModle = rightTreeModle;
        }
    }


}

4.查找二叉树

public class SearchBinaryTree {

    private TreeNode root;

    public static void main(String[] args) {
        SearchBinaryTree binaryTree = new SearchBinaryTree();
        int[] arrays = {55, 22, 88, 66, 1, 5, 50};
        for (int s : arrays) {
            binaryTree.put(s);
        }

//        binaryTree.delete(55);
        binaryTree.midBinaryTree(binaryTree.root);


    }

    public SearchBinaryTree() {

    }

    /**
     * 查找二叉树
     *
     * @param data
     * @return
     */
    public TreeNode put(int data) {

        TreeNode node = null;
        TreeNode parent = null;
        if (root == null) {
            //创建根节点,然后return掉，不走下面的了
            node = new TreeNode(0, data);
            root = node;
            return node;
        }

        node = root;
        while (node != null) {
            parent = node;//作为父节点
            //不为空去判断传进来的数据和其相比
            if (data > node.data) {//传进来的数据大，放在根节点的右边，给TreeNode对象重新赋值后再去遍历
                node = node.rightChild;
            } else if (data < node.data) {//传来的数据小于父节点，放在左边，给TreeNode对象重新赋值后再去遍历
                node = node.leftChild;
            } else if (data == node.data) {
                return node;
            }

        }
        //循环结束后，代表要存放该数据
        //创建新的节点
        node = new TreeNode(0, data);
        if (data > parent.data) {
            parent.rightChild = node;
        } else if (data < parent.data) {
            parent.leftChild = node;
        }
        node.parent = parent;

        return node;

    }

    /**
     * 删除二叉树
     */
    public void delete(TreeNode deleteNode) {
        //第一种情况删除没有子节点的节点
        if (deleteNode.leftChild == null && deleteNode.rightChild == null) {
            root = null;
        } else if (deleteNode == deleteNode.parent.leftChild) {
            deleteNode.parent.leftChild = null;
        }


    }


    public void midBinaryTree(TreeNode node) {
        if (node == null) {
            return;
        }

        midBinaryTree(node.leftChild);
        System.out.println(node.data);
        midBinaryTree(node.rightChild);

    }


    class TreeNode {
        public int data;
        public TreeNode leftChild;
        public TreeNode rightChild;
        public TreeNode parent;
        private int key;

        public TreeNode(int key, int data) {
            this.data = data;
            this.key = key;
            this.leftChild = null;
            this.rightChild = null;
            this.parent = null;
        }

        public int getData() {
            return data;
        }

        public void setData(int data) {
            this.data = data;
        }

        public TreeNode getLeftChild() {
            return leftChild;
        }

        public void setLeftChild(TreeNode leftChild) {
            this.leftChild = leftChild;
        }

        public TreeNode getRightChild() {
            return rightChild;
        }

        public void setRightChild(TreeNode rightChild) {
            this.rightChild = rightChild;
        }

        public TreeNode getParent() {
            return parent;
        }

        public void setParent(TreeNode parent) {
            this.parent = parent;
        }

        public int getKey() {
            return key;
        }

        public void setKey(int key) {
            this.key = key;
        }
    }
}