Java 八大数据结构之二叉树和红黑树

一：介绍
数据结构是计算机存储、组织数据的形式，指相互之间存在一种或多种特定关系的数据元素的汇合。

二：二叉树
节点：个别代表一些实体，在Java面向对象编程中，节点个别代表对象
边：个别从一个节点到另一个节点的惟一办法就是沿着一条顺着有边的路线后退。在Java当中通常示意援用。

1.门路：顺着节点的边从一个节点走到另一个节点，所通过的节点的顺序排列就称为“门路”。
2.根：树顶端的节点称为根。一棵树只有一个根，如果要把一个节点和边的汇合称为树，那么从根到其余任何一个节点都必须有且只有一条门路。A是根节点。
3.父节点：若一个节点含有子节点，则这个节点称为其子节点的父节点；B是D的父节点。
4.子节点：一个节点含有的子树的根节点称为该节点的子节点；D是B的子节点。
5.兄弟节点：具备雷同父节点的节点互称为兄弟节点；比方上图的D和E就互称为兄弟节点。
6.叶节点：没有子节点的节点称为叶节点，也叫叶子节点，比方上图的H、E、F、G都是叶子节点
7.子树：每个节点都能够作为子树的根，它和它所有的子节点、子节点的子节点等都蕴含在子树中。
8.节点的档次：从根开始定义，根为第一层，根的子节点为第二层，以此类推。
9.深度：对于任意节点n,n的深度为从根到n的惟一门路长，根的深度为0；
10.高度：对于任意节点n,n的高度为从n到一片树叶的最长门路长，所有树叶的高度为0；

二叉树的特点：
二叉树：树的每个节点最多只能有两个子节点
二叉搜寻树：若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值； 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值； 它的左、右子树也别离为二叉排序树。

中序遍历:左子树——》根节点——》右子树（上图：4,5,8,9,10,11,15,20）
前序遍历:根节点——》左子树——》右子树（上图：10,8,4,5,9,15,11,20）
后序遍历:左子树——》右子树——》根节点（上图：5,4,9,8,11,20,15,10）

实现二叉树的减少，查找，排序等

public class MyTree {    //示意根节点    private Node root;    //外部类实现节点数据    public class Node {         int data;//节点数据        private Node leftChild;//左子树的援用        private Node rightChild;//右子节点的援用        public Node(int data) {            this.data = data;        }        //打印节点内容        public void display() {            System.out.println(data);        }    }    //查找节点    //查找某个节点，咱们必须从根节点开始变量，1查找值比以后节点大，则搜寻右子树，查找值等于以后节点值，进行搜寻，查找值小于以后节点值，则搜寻左子树；    public Node find(int key) {        Node current = root;        while (current != null) {            if (current.data > key) {//以后值比查找值大，搜寻左子树                current = current.leftChild;            } else if (current.data < key) {//以后值比查找值小，搜寻右子树                current = current.rightChild;            } else {                return current;            }        }        return null;//遍历残缺个树没找到，返回null    }    //插入节点    public boolean insert(int data) {        Node newNode = new Node(data);        if (root == null) {//以后树为空树，没有任何节点            root = newNode;            return true;        } else {            Node current = root;            Node parentNode = null;            while (current != null) {                parentNode = current;                if (current.data > data) {//以后值比插入值大，搜寻左子节点                    current = current.leftChild;                    if (current == null) {//左子节点为空，间接将新值插入到该节点                        parentNode.leftChild = newNode;                        return true;                    }                } else {                    current = current.rightChild;                    if (current == null) {//右子节点为空，间接将新值插入到该节点                        parentNode.rightChild = newNode;                        return true;                    }                }            }        }        return false;    }    //中序遍历    public void infixOrder(Node current){        if(current != null){            infixOrder(current.leftChild);            System.out.print(current.data+" ");            infixOrder(current.rightChild);        }    }    //前序遍历    public void preOrder(Node current){        if(current != null){            System.out.print(current.data+" ");            preOrder(current.leftChild);            preOrder(current.rightChild);        }    }    //后序遍历    public void postOrder(Node current){        if(current != null){            postOrder(current.leftChild);            postOrder(current.rightChild);            System.out.print(current.data+" ");        }    }    //找到最大值    public Node findMax(){        Node current = root;        Node maxNode = current;        while(current != null){            maxNode = current;            current = current.rightChild;        }        return maxNode;    }    //找到最小值    public Node findMin(){        Node current = root;        Node minNode = current;        while(current != null){            minNode = current;            current = current.leftChild;        }        return minNode;    }}

调用

     MyTree myTree=new MyTree();                //二叉搜寻树，插入数据左子树小于节点数据，右子树大于节点数据                myTree.insert(10);                myTree.insert(8);                myTree.insert(15);                myTree.insert(4);                myTree.insert(9);                myTree.insert(11);                myTree.insert(20);                myTree.insert(5);                //中序遍历               myTree.infixOrder(myTree.find(10));                //前序遍历                myTree.preOrder(myTree.find(10));                //后序遍历                myTree.postOrder(myTree.find(10));                //获取最大值                System.out.println(myTree.findMax().data);                //获取最小值                System.out.println(myTree.findMin().data);                //获取数值为9的节点                System.out.println(myTree.find(9));                                                //后果                //中序遍历                System.out: 4 5 8 9 10 11 15 20                //前序遍历                System.out: 10 8 4 5 9 15 11 20                 //后序遍历                System.out: 5 4 9 8 11 20 15 10                 //最大值                System.out: 20                //最小值                System.out: 4                //获取数值为9的节点，援用                com.ruan.mygitignore.MyTree$Node@c115983

三：红黑树
红黑树，Red-Black Tree 「RBT」是一个自均衡(不是相对的均衡)的二叉查找树(BST)，树上的每个节点都遵循上面的规定:
1.每个节点都有红色或彩色
2.树的根始终是彩色的 (黑土地孕育黑树根， )
3.所有叶子都是彩色。（叶子是NIL结点）
4.每个红色结点的两个子结点都是彩色。（从每个叶子到根的所有门路上不能有两个间断的红色结点）
5.从节点（包含根）到其任何后辈NULL节点(叶子结点下方挂的两个空节点，并且认为他们是彩色的)的每条门路都具备雷同数量的彩色节点

当咱们向原有的红黑树中增加数据，可能会毁坏红黑树的规定
（1）向原红黑树掺入值为14的新节点：

（2）向原红黑树插入值为21的新节点：

因为父节点22是红色节点，因而这种状况突破了红黑树的规定4（每个红色节点的两个子节点都是彩色），必须进行调整，使之从新合乎红黑树的规定。
调整的形式有：变色，左旋转，右旋转
变色：
为了从新合乎红黑树的规定，尝试把红色节点变为彩色，或者把彩色节点变为红色。
下图所示意的是红黑树的一部分，须要留神节点25并非根节点。因为节点21和节点22间断呈现了红色，不合乎规定4，所以把节点22从红色变成彩色：

但这样并不算完，因为凭空多出的彩色节点突破了规定5，所以产生连锁反应，须要持续把节点25从彩色变成红色：

此时依然没有完结，因为节点25和节点27又造成了两个间断的红色节点，须要持续把节点27从红色变成彩色：

左旋转：
逆时针旋转红黑树的两个节点，使得父节点被本人的右孩子取代，而本人成为本人的左孩子。说起来很怪异，大家看下图：

图中，身为右孩子的Y取代了X的地位，而X变成了本人的左孩子。此为左旋转。
右旋转：
顺时针旋转红黑树的两个节点，使得父节点被本人的左孩子取代，而本人成为本人的右孩子。大家看下图：

图中，身为左孩子的Y取代了X的地位，而X变成了本人的右孩子。此为右旋转。
咱们以方才插入节点21的状况为例：
首先，咱们须要做的是变色，把节点25及其下方的节点变色：

此时节点17和节点25是间断的两个红色节点，那么把节点17变成彩色节点？恐怕不适合。这样一来岂但突破了规定4，而且依据规定2（根节点是彩色），也不可能把节点13变成红色节点。
变色已无奈解决问题，咱们把节点13看做X，把节点17看做Y，像方才的示意图那样进行左旋转：


因为根节点必须是彩色节点，所以须要变色，变色后果如下：

这样就完结了吗？并没有。因为其中两条门路(17 -> 8 -> 6 -> NIL)的彩色节点个数是4，其余门路的彩色节点个数是3，不合乎规定5。
这时候咱们须要把节点13看做X，节点8看做Y，像方才的示意图那样进行右旋转：


最初依据规定来进行变色：

如此一来，咱们的红黑树变得从新合乎规定。这一个例子的调整过程比较复杂，经验了如下步骤：
变色 -> 左旋转 -> 变色 -> 右旋转 -> 变色
我感觉能够这样也能实现：

参考博客：https://blog.csdn.net/qq_3661...

END:给时光以生命，给岁月以文化