非线性数据结构

树

树（tree）是n（n≥0）个节点的有限集。当n=0时，称为空树。在任意一个非空树中，有如下特点。

有且仅有一个特定的称为根的节点。
当n>1时，其余节点可分为m（m>0）个互不相交的有限集，每一个集合本身又是一个树，并称为根的子树。

二叉树

二叉树（binary tree）是树的一种特殊形式。这种树的每个节点最多有2个孩子节点。注意，这里是最多有2个，也可能只有1个，或者没有孩子节点。

基本概念

二叉树节点的两个孩子节点，一个被称为左孩子（left child），一个被称为右孩子（right child）。
满二叉树：一个二叉树的所有非叶子节点都存在左右孩子，并且所有叶子节点都在同一层级上，那么这个树就是满二叉树。
完全二叉树：对一个有n个节点的二叉树，按层级顺序编号，则所有节点的编号为从1到n。如果这个树所有节点和同样深度的满二叉树的编号为从1到n的节点位置相同，则这个二叉树为完全二叉树。

二叉树的链式存储结构

二叉树的数组存储结构

parent：左孩子2parent + 1，右孩子2parent + 2

二叉树的应用

二叉查找树：
- 如果左子树不为空，则左子树上所有节点的值均小于根节点的值
- 如果右子树不为空，则右子树上所有节点的值均大于根节点的值
- 左、右子树也都是二叉查找树

搜索节点的时间复杂度为O(logn)，和树的深度一样
二叉树的自平衡：红黑树、AVL树、树堆

二叉树的遍历

深度优先遍历
- 前序遍历：根节点，左子树，右子树
- 中序遍历：左子树，根节点，右子树
- 后序遍历：左子树，右子树，根节点
广度优先遍历：层序遍历

代码示例

package linkedlist;

import java.util.Arrays;
import java.util.LinkedList;
import java.util.Stack;
import java.util.Queue;

public class BinaryTree {
    /** * 创建二叉树 * @param inputList * @return */
    public static TreeNode createBinaryTree(LinkedList<Integer> inputList) {
        TreeNode node = null;
        if(inputList == null || inputList.isEmpty()) {
            return null;
        }
        Integer data = inputList.removeFirst();
        if(data != null) {
            node = new TreeNode(data);
            node.leftChild = createBinaryTree(inputList);
            node.rightChild = createBinaryTree(inputList);
        }
        return node;
    }

    /** * 前序遍历 * @param node */
    public static void preOrderTraversal(TreeNode node) {
        if(node == null) {
            return;
        }
        System.out.println(node.data);
        preOrderTraversal(node.leftChild);
        preOrderTraversal(node.rightChild);
    }

    /** * 中序遍历 * @param node */
    public static void inOrderTraversal(TreeNode node) {
        if(node == null) {
            return;
        }
        inOrderTraversal(node.leftChild);
        System.out.println(node.data);
        inOrderTraversal(node.rightChild);
    }

    /** * 后序遍历 * @param node */
    public static void postOrderTraversal(TreeNode node) {
        if(node == null) {
            return;
        }
        postOrderTraversal(node.leftChild);
        postOrderTraversal(node.rightChild);
        System.out.println(node.data);
    }

    /** * 非递归前序遍历 * @param root */
    public static void preOrderTraversalWithStack(TreeNode root) {
        Stack<TreeNode> stack = new Stack<>();
        TreeNode treeNode = root;
        while (treeNode != null || !stack.isEmpty()) {
            //迭代访问孩子的左节点并入栈
            while (treeNode != null){
                System.out.println(treeNode.data);
                stack.push(treeNode);
                treeNode = treeNode.leftChild;
            }
            //如果节点没有左孩子，弹出站顶节点，访问节点右孩子
            if(!stack.isEmpty()) {
                treeNode = stack.pop();
                treeNode = treeNode.rightChild;
            }
        }
    }
    public static void levelOrderTraversal(TreeNode root) {
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while(!queue.isEmpty()) {
            TreeNode node = queue.poll();
            System.out.println(node.data);
            if(node.leftChild != null) {
                queue.offer(node.leftChild);
            }
            if(node.rightChild != null) {
                queue.offer(node.rightChild);
            }
        }
    }
    /** * 二叉树节点 */
    private static class TreeNode {
        int data;
        TreeNode leftChild;
        TreeNode rightChild;

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

    /** * 测试 * @param args */
    public static void main(String[] args) {
        LinkedList<Integer> inputList = new LinkedList<>(Arrays.
                asList(new Integer[]{3,2,9,null,null,10,null,null,8,null,4}));
        TreeNode treeNode = createBinaryTree(inputList);
        System.out.println("前序遍历：");
        preOrderTraversal(treeNode);
        System.out.println("中序遍历：");
        inOrderTraversal(treeNode);
        System.out.println("后序遍历：");
        postOrderTraversal(treeNode);
        System.out.println("非递归前序遍历：");
        preOrderTraversalWithStack(treeNode);
        System.out.println("层序遍历：");
        levelOrderTraversal(treeNode);
    }
}

二叉堆

最大堆

最大堆的任何一个父节点的值，都大于或等于它左、右孩子节点的值

最小堆

最小堆的任何一个父节点的值，都小于或等于它左、右孩子节点的值

特点

最大堆的堆顶是整个堆中的最大元素；最小堆的堆顶是整个堆中的最小元素

二叉堆的基本操作

插入节点：插入位置是完全二叉树的最后一个位置，如果不符合，就进行和父节点交换位置(“上浮”)
删除节点(最小堆)：
- 删除的是处于堆顶的节点
- 为了继续维持完全二叉树的结构，我们把堆的最后一个节点临时补到原本堆顶的位置
- 让暂处堆顶位置的节点和它的左、右孩子进行比较，如果顶点节点大于左、右孩子节点中最小的一个，那么让节点“下沉”，让顶点节点和最小的孩子节点交换。
构建二叉堆：
- 把一个无序的完全二叉树调整为二叉堆，本质就是让所有非叶子节点依次“下沉”。
- 从最后一个非叶子节点开始，如果该节点大于它左、右孩子节点中最小的一个，该节点下沉。
- 依次调整每个非叶子节点，知道根节点
堆的插入和删除时间复杂度为O(logn)，堆的构建的时间复杂度为O(n)
二叉堆虽然是一个完全二叉树，但它的存储方式并不是链式存储，而是顺序存储。换句话说，二叉堆的所有节点都存储在数组中。

二叉堆代码实现

package linkedlist;

import java.util.Arrays;

public class BinaryHeap {
    /** * "上浮"调整 * @param array 待调整的堆 */
    public static void upAdjust(int[] array) {
        int childIndex = array.length - 1;
        int parentIndex = (childIndex - 1)/2;
        //保存插入的叶子节点，用于最后的赋值
        int temp = array[childIndex];
        while (childIndex > 0 && temp < array[parentIndex]) {
            //单向赋值即可
            array[childIndex] = array[parentIndex];
            childIndex = parentIndex;
            parentIndex = (childIndex - 1)/2;
        }
        array[childIndex]  = temp;
    }

    /** * “下沉调整” * @param array 待调整的堆 * @param parentIndex 要“下沉”的父节点 * @param length 堆的有效大小 */
    public static void downAdjust(int[] array, int parentIndex, int length) {
        int temp = array[parentIndex];
        int childIndex = 2 * parentIndex + 1;
        while(childIndex < length) {
            //如果有右孩子并且右孩子小于左孩子，则定位到右孩子
            if(childIndex + 1 < length && array[childIndex + 1] < array[childIndex]) {
                childIndex++;
            }
            //如果父节点小于任何一个孩子节点的值，那么直接跳出
            if(temp < array[childIndex]) {
                break;
            }
            //单向赋值即可
            array[parentIndex] = array[childIndex];
            parentIndex = childIndex;
            childIndex = 2 * parentIndex + 1;
        }
        array[parentIndex] = temp;
    }

    /** * 构建堆 * @param array 带调整的堆 */
    public static void buildHeap(int[] array) {
        for(int i = (array.length - 2)/2;i >= 0;i--) {
            downAdjust(array,i,array.length);
        }
    }

    /** * 测试 * @param args */
    public static void main(String[] args) {
        int[] array = new int[] {1,3,2,6,5,7,8,9,10,0};
        upAdjust(array);
        System.out.println(Arrays.toString(array));

        array = new int[] {7,1,3,10,5,2,8,9,6};
        buildHeap(array);
        System.out.println(Arrays.toString(array));
    }
}

优先队列

最大优先队列

最大优先队列，无论入队顺序如何，都是当前最大的元素优先出队

最小优先队列

最小优先队列，无论入队顺序如何，都是当前最小的元素优先出队

优先队列基本操作(最大优先队列)

入队：最大堆的插入
出队：删除堆顶节点

最大堆实现最大优先队列的代码

package linkedlist;

import java.util.Arrays;

/** * 最大堆实现最大优先队列 */
public class PriorityQueue {
    private int array[];
    private int size;

    /** * 构造函数，初始长度为32 */
    public PriorityQueue() {
        array = new int[32];
    }

    /** * 入队操作 * @param key 入队的元素 */
    public void enQueue(int key) {
        //长度不够，扩容
        if(size >= array.length) {
            resize();
        }
        array[size++] = key;
        upAdjust();
    }

    /** * 出队 * @return 出队的元素 * @throws Exception */
    public int deQueue() throws Exception{
        if(size <= 0) {
            throw new Exception("the queue is empty!");
        }
        int head = array[0];
        array[0] = array[--size];
        downAdjust();
        return head;
    }

    /** * 上浮操作，对子节点进行操作 */
    public void upAdjust() {
        int childIndex = size - 1;
        int parentIndex = (childIndex - 1) / 2;
        int temp = array[childIndex];
        //对子节点进行操作
        while(childIndex > 0 && temp > array[parentIndex]) {
            //单向赋值，父节点的值赋给子节点
            array[childIndex] = array[parentIndex];
            childIndex = parentIndex;
            parentIndex = (childIndex - 1) /2;
        }
        array[childIndex] = temp;
    }

    /** * 下沉操作，对父节点操作 */
    public void downAdjust() {
        int parentIndex = 0;
        int childIndex = 2 * parentIndex + 1;
        int temp = array[parentIndex];
        //对父节点操作
        while(childIndex < size) {
            if((childIndex + 1) < size && array[childIndex] < array[childIndex + 1]) {
                childIndex++;
            }
            if(temp >= array[childIndex]) {
                break;
            }
            array[parentIndex] = array[childIndex];
            parentIndex = childIndex;
            childIndex = parentIndex * 2 + 1;
        }
        array[parentIndex] = temp;
    }

    /** * 容量不够进行扩容 */
    public void resize() {
        int newSize = this.size * 2;
        this.array = Arrays.copyOf(this.array, newSize);
    }
    public static void main(String[] args) throws Exception {
        PriorityQueue priorityQueue = new PriorityQueue();
        priorityQueue.enQueue(3);
        priorityQueue.enQueue(5);
        priorityQueue.enQueue(10);
        priorityQueue.enQueue(2);
        priorityQueue.enQueue(7);
        System.out.println("出队元素：" + priorityQueue.deQueue());
        System.out.println("出队元素：" + priorityQueue.deQueue());
    }
}