2019-08-26

数据结构 - 树

二叉树遍历

定义二叉树

/**
 * @author kb_jay
 * @time 2019/8/26
 **/
public class Node<T> {
    public T data;
    public Node leftChild;
    public Node rightChild;

    public Node() {
    }

    public Node(T data) {
        this(data, null, null);
    }

    public Node(T data, Node leftChild, Node rightChild) {
        this.data = data;
        this.leftChild = leftChild;
        this.rightChild = rightChild;
    }
}

遍历二叉树

前序遍历（递归跟非递归）

//递归
public static void firstRoot(Node root) {
    if (root == null) {
        return;
    }

    System.out.println(root.data);
    firstRoot(root.leftChild);
    firstRoot(root.rightChild);
}

//非递归
public static void firstRootStack(Node root) {
    Stack<Node> stack = new Stack<>();
    while (root != null || stack.size() > 0) {
        //输出并压栈左孩子
        while (root != null) {
            System.out.println(root.data);
            stack.push(root);
            root = root.leftChild;
        }
		//出栈遍历右孩子
        if (stack.size() > 0) {
            Node node = stack.pop();
            root = node.rightChild;
        }
    }
}

中序遍历（递归跟非递归）

public static void centerRoot(Node root) {
    if (root == null) {
        return;
    }

    centerRoot(root.leftChild);
    System.out.println(root.data);
    centerRoot(root.rightChild);
}

public static void centerRootStack(Node root) {
    Stack<Node> stack = new Stack<>();
    while (root != null || stack.size() > 0) {
        while (root != null) {
            stack.push(root);
            root = root.leftChild;
        }

        if (stack.size() > 0) {
            root = stack.pop();
            System.out.println(root.data);
            root = root.rightChild;
        }
    }
}

后序遍历（递归跟非递归）

public static void lastRoot(Node node) {
    if (node == null) {
        return;
    }

    lastRoot(node.leftChild);
    lastRoot(node.rightChild);
    System.out.println(node.data);
}

public static void lastRootStack(Node root) {
    Stack<Node> stack = new Stack<>();
    //记录前一个输出的node
    Node pre = null;
    while (root != null || stack.size() > 0) {
        while (root != null) {
            stack.push(root);
            root = root.leftChild;
        }

        if (stack.size() > 0) {
            Node temp = stack.peek().rightChild;
            if (temp == null || temp == pre) {
                pre = stack.pop();
                System.out.println(pre.data);
                root = null;
            } else {
                root = temp;
            }
        }
    }
}

层序遍历

public static void layerOut(Node root) {
    Queue<Node> queue = new ArrayDeque<>();
    while (root != null) {
        System.out.println(root.data);

        if (root.leftChild != null) {
            queue.offer(root.leftChild);
        }

        if (root.rightChild != null) {
            queue.offer(root.rightChild);
        }
        //如果队列为空，返回null， 栈的pop方法，如果栈为空，则报异常
        root = queue.poll();
    }
}

二分搜索树

任意一个节点的值大于左边的所有节点的值，小于右边的所有节点的值。
1. 中序遍历是有序的。

2-3 树

满足二分搜索树
一个节点可以存放1个或者2个元素
二三树是绝对平衡树
二三树添加元素不会往空节点添加，第一步肯定是跟叶子节点合并

AVL树

平衡二叉树
任何一个节点的左右孩子到叶子节点的距离相差不超过1
它是为了解决二分搜索树的退化问题
每次更新数据都需要通过旋转来维持平衡，所以实际开发中用红黑树会更多

红黑树

红黑树是一个自平衡的二叉搜索树，并不是严格的avl树。
它是为了解决二分搜索树在数据更新的过程中复杂度退化的问题。
红黑树高度近似log2n，近似平衡，红黑树是有2-3-4树演变过来的，因为2-3-4树有绝对平衡性，所以将红色节点去掉之后的高度<=log2n，而红色节点的儿子不能是黑色节点，所以红黑树中从跟节点到叶子节点有一个黑色就最多有一个红色，我们将红色加回来之后的高度<2*log2n
插入查找删除时间复杂度是log2n
是由2-3-4树演变过来的我们将红黑树中的红色节点跟父亲节点合并之后就是一个绝对平衡的2-3-4树
红黑树的平衡过程其实跟魔方复原差不多，记住规则就行（变色跟旋转）
四条性质：根黑；叶子节点的子节点是黑色；红色节点不相邻；根节点到叶子节点的路径上黑色节点个数一致。通过234树理解这个还是很好理解的。