树
二叉树
- 和链表一样，是动态数据结构，只不过有两个指向下一个节点的指针，依次类推也可以得到多叉树
- 将数据存储在一个单独的节点中（即一个对象中），该节点包括至少三部分内容（即对象的属性）
- 存储的数据
- 指向左子树的指针，即左孩子（可能为空）
- 指向右子树的指针，即右孩子（可能为空）
- 有一个唯一的根节点（没有父节点），每个节点最多有两个孩子（可能只有一个孩子），每个节点最多只有一个父节点，若一个孩子都没有的节点称之为叶子节点
- 二叉树分类：
- 满二叉树：除啦叶子节点之外，都有两个孩子
- 完全二叉树：节点一层一层从左到右依次排列出的二叉树，此时缺失叶子节点的节点只能出现在右下方
- 平衡二叉树：对于任意节点，左子树和右子树高度最多相差 1，即最大深度和最小深度最多相差 1，所以满二叉树和完全二叉树都是平衡二叉树
二分搜索树
- 首先是一颗二叉树，但是所有的节点都大于其左子树的节点，小于其右子树的节点（没有重复的元素），即每一课子树都是一颗二分搜索树
- 正因为二分搜索树的上述特点，所以查找效率才会很高，但是存储元素就必须有可比较性
- 存入的第一个元素永远是树根，若顺序存储到树中则会退化成链表结构
Import java. Util. LinkedList;
Import java. Util. Queue;
Import java. Util. Stack;
/**
* @ClassName: BST
* @Description: 自定义二分搜索树
*/
public class BST<E extends Comparable<E>> { //使用二分搜索树存储必须实现比较器接口
Private class Node {
Private Node left, right; //指向左子树和右子树的指针
Private E data; //存储节点的数据
/**
* @MethodName: Node
* @Description: 创建节点
* @Param element: 传入的数据
*/
Public Node (E element) {
This. Data = element;
This. Left = null;
This. Right = null;
}
}
Private Node root; //存储根节点
Private int size; //记录树中元素个数
Public BST () {
This. Root = null;
This. Size = 0;
}
Public int getSize () {
Return this. Size;
}
Public boolean isEmpty () {
Return this. Size == 0;
}
/**
* @MethodName: add
* @Description: 将元素节点添加到树中
* @Param element: 要添加的元素
* @Return void
*/
Public void add (E element) {
This. Root = this.Add (root, element);
//将节点添加到以根节点为根的子树中
//之后根节点指针指向这颗已经插入元素的树
}
/**
* @MethodName: add
* @Description: 将元素插入到以该节点为根的子树中，并返回这个已添加节点的子树
* @Param node: 要插入的子树
* @Param element: 要插入的元素
* @Return BST<E>. Node 返回插入元素的子树（子树也是节点，因为节点也挂着左右指针所以是子树）
*/
Private Node add (Node node, E element) {
If (node == null) { //若遍历到树的末端
This. Size++; //插入元素时将元素个数加 1
Return new Node (element);
//返回插入节点的子树，这里子树就是叶子节点，即新节点本身
}
If (element.CompareTo (node. Data) < 0) {
//若要插入的元素小于当前节点，就应该将该元素插入到左子树中
Node. Left = add (node. Left, element);
//返回的已插入元素，并以左孩子节点为根的子树
//之后将该子树挂到当前节点左指针上
} else if (element.CompareTo (node. Data) > 0) {
//若要插入的元素小于当前节点，就应该将该元素插入到右子树中
Node. Right = add (node. Right, element);
//返回的已插入元素，并以右孩子节点为根的子树
//之后将该子树挂到当前节点右指针上
}
Return node;
//若当前节点内容等于当前节点，相当于已经插入到以该节点为根的子树上了，不必重复插入
//也可以说经过上面的步骤插入完毕了，就直接返回以该节点为根的子树即可
}
/**
* @MethodName: contains
* @Description: 判断树中是否包含该元素
* @Param element: 要判断的元素
* @Return boolean
*/
Public boolean contains (E element) {
Return this.Contains (this. Root, element);
//查询以根节点为根的子树中是否包含该元素
}
/**
* @MethodName: contains
* @Description: 在以某节点为根的子树中是否包含改元素
* @Param node: 要查询的以该节点为根的子树
* @Param element: 要查询的元素
* @Return boolean
*/
Private boolean contains (Node node, E element) {
If (node == null) { //若遍历到树的末端
Return false; //末端是 null，肯定没有与该元素相等的元素，返回 false
}
If (element.CompareTo (node. Data) < 0) { //要查询的元素比当前节点小
Return contains (node. Left, element); //查询左子树
} else if (element.CompareTo (node. Data) > 0) { //要查询的元素比当前节点大
Return contains (node. Right, element); //查询右子树
} else { //若相等则返回 true
Return true;
}
}
/**
* @MethodName: minimum
* @Description: 返回树中最小的节点元素
* @Return E
*/
Public E minimum () {
If (this. Size == 0) { //若树中没有元素，直接抛出异常
Throw new IllegalArgumentException ("BST is empty");
}
/**
* 非递归方式，其实就是链表遍历到末尾节点
*/
// Node cur = this. Root; //当前节点为根节点，即第一个节点
// while (cur. Left != null) { //若当前节点的左（下一个）节点不是 null，说明未到末端
// cur = cur. Left; //指针后移
// }
// return cur. Data; //返回最后节点的内容
Return this.Minimum (this. Root). Data;
}
/**
* @MethodName: minimum
* @Description: 返回以该节点为根的子树中最小的节点
* @Param node: 以该节点为根的子树
* @Return BST<E>. Node
*/
Private Node minimum (Node node) {
If (node. Left == null) { //若该节点左孩子为空，说明已经到达树的末端
Return node; //该节点就是最小的节点，直接返回该节点即可
}
Return this.Minimum (node. Left); //返回以该节点左孩子节点为根的子树中最小的节点
}
/**
* @MethodName: maximum
* @Description: 返回树中最大的节点元素
* @Return E
*/
Public E maximum () {
If (this. Size == 0) { //若树中没有元素，直接抛出异常
Throw new IllegalArgumentException ("BST is empty");
}
/**
* 非递归方式，其实就是链表遍历到末尾节点
*/
// Node cur = this. Root; //当前节点为根节点，即第一个节点
// while (cur. Right != null) { //若当前节点的右（下一个）节点不是 null，说明未到末端
// cur = cur. Right; //指针后移
// }
// return cur. Data; //返回最后节点的内容
Return this.Maximum (this. Root). Data;
}
/**
* @MethodName: maximum
* @Description: 返回以该节点为根的子树中最大的节点
* @Param node: 以该节点为根的子树
* @Return BST<E>. Node
*/
Private Node maximum (Node node) {
If (node. Right == null) { //若该节点右孩子为空，说明已经到达树的末端
Return node; //该节点就是最大的节点，直接返回该节点即可
}
Return this.Maximum (node. Right); //返回以该节点右孩子节点为根的子树中最小的节点
}
/**
* @MethodName: removeMin
* @Description: 删除树中最小节点并返回节点内容
* @Return E
*/
Public E removeMin () {
/**
* 分析：
* 删除最小元素节点时，该最小节点只可能有右孩子，但是该右孩子可能为空
* 删除最小节点操作就是将该节点删除后，使用其右子树替补到被删除的位置
*/
E ret = this.Minimum (); //查出要最小节点元素
This. Root = this.RemoveMin (this. Root);
//删除以根节点为根的子树中最小节点
//之后根节点指针指向这颗已经删除最小节点的树
Return ret; //返回最小节点元素
}
/**
* @MethodName: removeMin
* @Description: 删除掉以该节点为根的子树中最小节点，并返回这个已删除最小节点的子树
* @Param node: 要删除的子树
* @Return BST<E>. Node
*/
Private Node removeMin (Node node) {
If (node. Left == null) { //若该节点左孩子为空，说明已经到达树的末端，即该节点就是要被删除的节点
Node rightNode = node. Right; //要删除的节点的右子树不能丢，右子树可能为空，逻辑是一样的所以无影响
Node. Right = null; //将当前被删除节点与树脱离关系，方便垃圾回收机制回收
This. Size--; //删除节点后需要将成员数减 1
Return rightNode;
//由于当前子树只有右子树，所以根据定义，当前节点就是最小节点
//所以已删除最小节点的子树就是当前节点的右子树，直接返回右子树即可
}
Node. Left = this.RemoveMin (node. Left);
//返回的已删除最小节点子树，并以左孩子为根
//之后将该子树挂到当前节点左指针上（用新的删除最小节点子树替换原来未删除最小节点子树）
Return node; //将替换过子树的节点返回
}
/**
* @MethodName: removeMax
* @Description: 删除树中最大节点并返回节点内容
* @Return E
*/
Public E removeMax () {
/**
* 分析：
* 删除最大元素节点时，该最大节点只可能有左孩子，但是该左孩子可能为空
* 删除最大节点操作就是将该节点删除后，使用其左子树替补到被删除的位置
*/
E ret = this.Maximum (); //查出要最小节点元素
This. Root = this.RemoveMax (this. Root);
//删除以根节点为根的子树中最大节点
//之后根节点指针指向这颗已经删除最小节点的树
Return ret; //返回最小节点元素
}
/**
* @MethodName: removeMax
* @Description: 删除掉以该节点为根的子树中最大节点，并返回这个已删除最大节点的子树
* @Param node: 要删除的子树
* @Return BST<E>. Node
*/
Public Node removeMax (Node node) {
If (node. Right == null) { //若该节点右孩子为空，说明已经到达树的末端，即该节点就是要被删除的节点
Node leftNode = node. Left; //要删除的节点的右子树不能丢，右子树可能为空，逻辑是一样的所以无影响
Node. Left = null; //将当前被删除节点与树脱离关系，方便垃圾回收机制回收
This. Size--; //删除节点后需要将成员数减 1
Return leftNode;
//由于当前子树只有左子树，所以根据定义，当前节点就是最小节点
//所以已删除最小节点的子树就是当前节点的左子树，直接返回左子树即可
}
Node. Right = removeMax (node. Right);
//返回的已删除最小节点子树，并以右孩子为根
//之后将该子树挂到当前节点右指针上（用新的删除最大节点子树替换原来未删除最大节点子树）
Return node; //将替换过子树的节点返回
}
/**
* @MethodName: remove
* @Description: 删除树中任意元素
* @Param element: 要删除的元素
* @Return void
*/
Public void remove (E element) {
This. Root = this.Remove (this. Root, element);
//删除以根节点为根的子树中的该元素
//之后将根节点指针指向这颗已经删除该元素的树
}
/**
* @MethodName: remove
* @Description: 删除指定以该节点为根的子树中的元素，并返回这颗删除指定元素的子树
* @Param node: 指定的子树
* @Param element: 指定的删除元素
* @Return BST<E>. Node
*/
Private Node remove (Node node, E element) {
If (node == null) { //若遍历到末端，即空子树，该元素一定不可能在这颗空的子树中
Return null; //所以什么也不用做直接返回该空节点，返回 null 也是一样的
}
If (element.CompareTo (node. Data) < 0) { //若要删除元素小于当前节点元素
Node. Left = remove (node. Left, element); //应该从左子树中查找该元素并删除
//返回已删除元素的子树，并以左孩子为根
//之后将该子树挂到当前节点左指针上（用新的删除指定元素子树替换原来未删除指定元素子树）
Return node; //将替换过的子树节点返回
} else if (element.CompareTo (node. Data) > 0) { //要删除元素大于当前节点元素
Node. Right = remove (node. Right, element); //应该从右子树中查找该元素并删除
//返回已删除元素的子树，并以右孩子为根
//之后将该子树挂到当前节点右指针上（用新的删除指定元素子树替换原来未删除指定元素子树）
Return node; //将替换过的子树节点返回
} else { //若要删除元素等于当前节点元素，该节点就是要删除节点
If (node. Left == null) {
//若当前要删除节点没有左子树，则删除当前节点和删除最小节点操作一致
Node rightNode = node. Right;
Node. Right = null;
This. Size--;
Return rightNode;
}
If (node. Right == null) {
//若当前要删除节点没有右子树，则删除当前节点和删除最大节点操作一致
Node leftNode = node. Left;
Node. Left = null;
This. Size--;
Return leftNode;
}
//若当前节点既有左子树，又有右子树
//使用后继
Node successor = this.Minimum (node. Right); //找到后继节点，准备将后继节点替换删除节点
//后继就是离当前节点元素最近，且比当前元素大的节点（刚刚比当前节点元素大的元素节点）
//同时也是当前节点的右子树中的最小值
Successor. Right = this.RemoveMin (node. Right); //后继节点右子树指向删除该后继节点的子树
//successor. Right = remove (node. Right, successor. Data); //也可以使用递归调用，来获取删除后继节点的子树
Successor. Left = node. Left; //后继节点左子树指向原来节点的左子树
Node. Left = node. Right = null; //将原来节点与该树脱离关系，方便垃圾回收机制回收
Return successor; //返回删除该元素的子树
/*
//使用前驱
Node precursor = this.Maximum (node. Left); //找到前驱节点，准备将前驱节点替换删除节点
//前驱就是离当前节点元素最近，且比当前元素小的节点（刚刚比当前节点元素小的元素节点）
//同时也是当前节点的左子树中的最大值
Precursor. Left = this.RemoveMax (node. Left); //前驱节点左子树指向删除该前驱节点的子树
Precursor. Right = node. Right; //前驱节点右子树指向原来节点的右子树
Node. Left = node. Right = null; //将原来节点与该树脱离关系，方便垃圾回收机制回收
Return precursor; //返回删除该元素的子树
*/
}
}
/**
* @MethodName: traversal
* @Description: 递归遍历整棵树
* @Return void
*/
Public void traversal () {
This.Traversal (this. Root); //遍历以根节点为根的子树
}
/**
* @MethodName: traversal
* @Description: 递归遍历指定子树的所有节点
* @Param node: 指定的子树节点
* @Return void
*/
Private void traversal (Node node) {
If (node == null) { //若遍历到末端
Return; //没有节点，什么也做
}
//System.Out.Println (node. Data); //前序遍历，先处理自己，后处孩子节点，即深度优先
Traversal (node. Left);
//System.Out.Println (node. Data); //中序遍历，输出已是排好序
Traversal (node. Right);
//System.Out.Println (node. Data); //后序遍历，先处理孩子节点，后处理自己
}
/**
* @MethodName: DFT
* @Description: 非递归遍历整棵树的所有节点，深度优先
* @Return void
*/
Public void DFT () {
Stack<Node> stack = new Stack<>(); //借助与栈，记录下一个要遍历的节点
Stack.Push (this. Root); //将根节点压入栈
While (! Stack.IsEmpty ()) { //若栈不为空
Node cur = stack.Pop (); //将栈顶元素弹出
System.Out.Println (cur. Data); //操作节点
//先将右子节点入栈，因为栈是先进先出
If (cur. Right != null) { //若当前节点右指针不为空
Stack.Push (cur. Right); //将右子节点入栈
}
If (cur. Left != null) { //若当前节点左指针不为空
Stack.Push (cur. Left); //将左子节点入栈
}
}
}
/**
* @MethodName: BFT
* @Description: 非递归遍历整棵树所有节点，广度优先
* @Return void
*/
Public void BFT () {
Queue<Node> queue = new LinkedList<>(); //借助与队列，记录下一个要遍历的节点
Queue.Add (this. Root); //将根节点入队
While (! Queue.IsEmpty ()) { //若队列不为空
Node cur = queue.Remove (); //将队首元素出队
System.Out.Println (cur. Data); //操作节点
//先将左子节点入队，因为队列是先进后出
If (cur. Left != null) { //若当前节点左指针不为空
Queue.Add (cur. Left); //将右子节点入队
}
If (cur. Right != null) { //若当前节点右指针不为空
Queue.Add (cur. Right); //将右子节点入队
}
}
}
/**
* @MethodName: floor
* @Description: 查找在该树中，离该元素最近且小于该元素的节点
* @Param element: 要查找的元素
* @Return E
*/
Public E floor (E element) {
If (this. Size == 0 || element.CompareTo (minimum ()) < 0) {
Return minimum (); //截断小于该树中小于最小值的输入
}
Return this.Floor (this. Root, element). Data;
}
/**
* @MethodName: floor
* @Description: 查找以该节点为根的子树中，离该元素最近且小于该元素的节点
* @Param node: 以该节点为根的子树
* @Param element: 要查找的元素
* @Return BST<E>. Node
*/
Private Node floor (Node node, E element) {
/**
* 分析：
* 与树的搜索一致，从根节点遍历到要查找的节点，只不过在向左查找时
* 查找到的节点不一定是 floor 值，比如下列树中：若匹配元素是 54 时，
* 会依次走过 50-70-60-55-null，而 54 的 floor 值应该是 50 才对，反观当
* 匹配元素是 46 时，会依次走过 50-30-40-45-null，46 的 floor 值就是 45
* 还有一个问题，就是若匹配元素是 10，会一直向上返回 null，解决这个
* 问题就可以在上层截断小于该树中最小元素的输入即可
* 50
* / \
* / \
* 30 70
* / \ / \
* 20 40 60 80
* /\ /\ /\ /\
* 15 25 35 45 55 65 75 85
*/
If (node == null) { //当遍历到结尾时
Return null; //返回 null，什么也不做
}
If (node.Data.CompareTo (element) == 0) { //要匹配元素与树中元素相等时
Return node; //返回该元素即可
}
If (element.CompareTo (node. Data) < 0) { //当匹配元素小于当前节点时
Return floor (node. Left, element); //返回上一次返回的节点（直接抛出）
} else { //当匹配元素大于当前节点时
Node tempNode = floor (node. Right, element);
//暂存上次返回的节点，用来判断上次是否存储过节点信息
Return tempNode == null ? Node : tempNode;
//若上次存储过节点信息就不做操作，直接向上抛出，若没有存储过节点就存储上当前节点在向上抛
}
}
/**
* @MethodName: ceil
* @Description: 查找在该树中，离该元素最近且大于该元素的节点
* @Param element: 要查找的元素
* @Return E
*/
Public E ceil (E element) {
If (this. Size == 0 || element.CompareTo (maximum ()) > 0) {
Return maximum (); //截断大于该树中最大值的输入
}
Return this.Ceil (this. Root, element). Data;
}
/**
* @MethodName: ceil
* @Description: 查找以该节点为根的子树中，离该元素最近且大于该元素的节点
* @Param node: 以该节点为根的子树
* @Param element: 要查找的元素
* @Return BST<E>. Node
*/
Private Node ceil (Node node, E element) {
/**
* 分析：
* 与树的搜索一致，从根节点遍历到要查找的节点，只不过在向右查找时
* 查找到的节点不一定是 ceil 值，比如下列树中：若匹配元素是 54 时，会
* 依次走过 50-70-60-55-null，54 的 ceil 值就是 55，反观当匹配元素是 46
* 时，会依次走过 50-30-40-45-null，而 45 的 ceil 值应该是 50 才对，还有
* 一个问题，就是若匹配元素是 10，会一直向上返回 null，解决这个问题
* 就可以在上层截断大于该树中最大元素的输入即可
* 50
* / \
* / \
* 30 70
* / \ / \
* 20 40 60 80
* /\ /\ /\ /\
* 15 25 35 45 55 65 75 85
*/
If (node == null) { //当遍历到结尾时
Return null; //返回 null，什么也不做
}
If (element.CompareTo (node. Data) == 0) { //要匹配元素与树中元素相等时
Return node; //返回该元素即可
}
If (element.CompareTo (node. Data) < 0) { //当匹配元素小于当前节点时
Node tempNode = ceil (node. Left, element);
//暂存上次返回的节点，用来判断上次是否存储过节点信息
Return tempNode == null ? Node : tempNode;
//若上次存储过节点信息就不做操作，直接向上抛出，若没有存储过节点就存储上当前节点在向上抛
} else { //当匹配元素大于当前节点时
Return ceil (node. Right, element); //返回上一次返回的节点（直接抛出）
}
}
}
快速写出前中后序遍历结果
平衡二叉树
对于普通的二分搜索树来说，若是将元素顺序加入到树中，该树就会向一侧进行倾斜，进而退化为链表，所以需要在添加和删除元素时添加一种机制将倾斜的二叉树转化为平衡二叉树
此时就要为每个节点增加一个高度值，每个叶子节点的高度为 1（即每次新增的节点初始高度为 1），向上依次加 1 高度，根据平衡二叉树的定义，每个节点的左右子树的高度差最多应该是 1，进而来判断当前二叉树是否为平衡二叉树
维护平衡的原理
在添加或删除时才导致整棵树不平衡，所破坏的平衡性将反映在该更新的节点的祖先节点中，因为在插入或删除时该节点的祖先节点的高度值就会相应的变化，只有高度改变时平衡因子绝对值才会有可能超过 1，所以应该在加入或删除节点时判断是否是平衡，若不平衡则将这颗树转化为平衡二叉树
基于二分搜索树实现
/**
* @ClassName: AVLTree
* @Description: 自定义平衡二叉树
*/
public class AVLTree<E extends Comparable<E>> {
Private class Node {
Private Node left, right; //指向左子树和右子树的指针
Private E data; //存储节点的数据
Private int height; //存储以当前节点为根的树高度
/**
* @MethodName: Node
* @Description: 创建节点
* @Param element: 传入的数据
*/
Public Node (E element) {
This. Data = element;
This. Left = null;
This. Right = null;
This. Height = 1; //每个叶子节点的高度都为 1
}
}
Private int size;
Private Node root;
Public AVLTree () {
This. Root = null;
This. Size = 0;
}
/**
* @MethodName: getHeight
* @Description: 获取指定节点的高度
* @Param node: 指定的节点
* @Return int
*/
Private int getHeight (Node node) {
If (node == null) { //若指定节点是空节点，空节点的高度是 0
Return 0; //返回 0
}
Return node. Height; //若不是空节点则返回当前节点的高度
}
/**
* @MethodName: getBalanceFactor
* @Description: 获取指定节点的平衡因子
* @Param node: 指定的节点
* @Return int
*/
Private int getBalanceFactor (Node node) {
If (node == null) {
Return 0; //|0-0|=0
}
Return this.GetHeight (node. Left) - this.GetHeight (node. Right);
}
/**
* @MethodName: rightRotate
* @Description: 将指定节点为根的子树进行右旋转后并返回
* @Param y: 指定的节点
* @Return AVLTree<E>. Node
*/
Private Node rightRotate (Node y) {
Node x = y.left;
Node T 3 = x.right;
x.right = y;
y.left = T 3;
y.height = 1 + Math.Max (this.GetHeight (y.left), this.GetHeight (y.right));
x.height = 1 + Math.Max (this.GetHeight (x.left), this.GetHeight (y.right));
Return x;
}
/**
* @MethodName: leftRotate
* @Description: 将指定节点为根的子树进行左旋转后并返回
* @Param y: 指定的节点
* @Return AVLTree<E>. Node
*/
Private Node leftRotate (Node y) {
Node x = y.right;
Node T 2 = x.left;
x.left = y;
y.right = T 2;
y.height = 1 + Math.Max (this.GetHeight (y.left), this.GetHeight (y.right));
x.height = 1 + Math.Max (this.GetHeight (x.left), this.GetHeight (y.right));
Return x;
}
/**
* @MethodName: goBalance
* @Description: 节点高度和平衡的维护，该方法应该在插入或删除元素后调用（return 前）
* @Param node: 要维护的节点
* @Return AVLTree<E>. Node
*/
Private Node goBalance (Node node) {
If (node == null) { //若传入的节点是 null
Return null; //返回 null，不需要维护
}
Node. Height = 1 + Math.Max (this.GetHeight (node. Left), this.GetHeight (node. Right));
//在当前节点下插入元素后，当前的高度应该是左右子树中最高哪一个再加 1
If (this.GetBalanceFactor (node) > 1 && this.GetBalanceFactor (node. Left) >= 0) {
//由于左子树的左子树中插入或删除元素导致的不平衡
Return this.RightRotate (node); //将该节点右旋转
}
If (this.GetBalanceFactor (node) < -1 && this.GetBalanceFactor (node. Right) <= 0) {
//由于右子树的右子树中插入或删除元素导致的不平衡
Return this.LeftRotate (node); //将该节点左旋转
}
If (this.GetBalanceFactor (node) > 1 && this.GetBalanceFactor (node. Left) < 0) {
//由于左子树的右子树中插入或删除元素导致的不平衡
Node. Left = this.LeftRotate (node. Left); //先将左子树左旋转
Return this.RightRotate (node); //在将该节点右旋转
}
if (this.GetBalanceFactor (node) < -1 && this.getBalanceFactor(node.right) > 0) {
//由于右子树的左子树中插入或删除元素导致的不平衡
Node. Right = this.RightRotate (node. Right); //先将右子树右旋转
Return this.LeftRotate (node); //在将该节点左旋转
}
Return node;
}
/**
* @MethodName: add
* @Description: 将元素节点添加到树中
* @Param element: 要添加的元素
* @Return void
*/
Public void add (E element) {
This. Root = this.Add (root, element);
//将节点添加到以根节点为根的子树中
//之后根节点指针指向这颗已经插入元素的树
}
/**
* @MethodName: add
* @Description: 将元素插入到以该节点为根的子树中，并返回这个已添加节点的子树
* @Param node: 要插入的子树
* @Param element: 要插入的元素
* @Return BST<E>. Node 返回插入元素的子树（子树也是节点，因为节点也挂着左右指针所以是子树）
*/
Private Node add (Node node, E element) {
If (node == null) { //若遍历到树的末端
This. Size++; //插入元素时将元素个数加 1
Return new Node (element);
//返回插入节点的子树，这里子树就是叶子节点，即新节点本身
}
If (element.CompareTo (node. Data) < 0) {
//若要插入的元素小于当前节点，就应该将该元素插入到左子树中
Node. Left = add (node. Left, element);
//返回的已插入元素，并以左孩子节点为根的子树
//之后将该子树挂到当前节点左指针上
} else if (element.CompareTo (node. Data) > 0) {
//若要插入的元素小于当前节点，就应该将该元素插入到右子树中
Node. Right = add (node. Right, element);
//返回的已插入元素，并以右孩子节点为根的子树
//之后将该子树挂到当前节点右指针上
}
Return this.GoBalance (node);
//若当前节点内容等于当前节点，相当于已经插入到以该节点为根的子树上了，不必重复插入
//也可以说经过上面的步骤插入完毕了，就直接返回以该节点为根的子树即可
}
/**
* @MethodName: minimum
* @Description: 返回以该节点为根的子树中最小的节点
* @Param node: 以该节点为根的子树
* @Return BST<E>. Node
*/
Private Node minimum (Node node) {
If (node. Left == null) { //若该节点左孩子为空，说明已经到达树的末端
Return node; //该节点就是最小的节点，直接返回该节点即可
}
Return this.Minimum (node. Left); //返回以该节点左孩子节点为根的子树中最小的节点
}
/**
* @MethodName: remove
* @Description: 删除树中任意元素
* @Param element: 要删除的元素
* @Return void
*/
Public void remove (E element) {
This. Root = this.Remove (this. Root, element);
//删除以根节点为根的子树中的该元素
//之后将根节点指针指向这颗已经删除该元素的树
}
/**
* @MethodName: remove
* @Description: 删除指定以该节点为根的子树中的元素，并返回这颗删除指定元素的子树
* @Param node: 指定的子树
* @Param element: 指定的删除元素
* @Return BST<E>. Node
*/
Private Node remove (Node node, E element) {
If (node == null) { //若遍历到末端，即空子树，该元素一定不可能在这颗空的子树中
Return null; //所以什么也不用做直接返回该空节点，返回 null 也是一样的
}
If (element.CompareTo (node. Data) < 0) { //若要删除元素小于当前节点元素
Node. Left = remove (node. Left, element); //应该从左子树中查找该元素并删除
//返回已删除元素的子树，并以左孩子为根
//之后将该子树挂到当前节点左指针上（用新的删除指定元素子树替换原来未删除指定元素子树）
Return this.GoBalance (node); //将替换过的子树节点返回
} else if (element.CompareTo (node. Data) > 0) { //要删除元素大于当前节点元素
Node. Right = remove (node. Right, element); //应该从右子树中查找该元素并删除
//返回已删除元素的子树，并以右孩子为根
//之后将该子树挂到当前节点右指针上（用新的删除指定元素子树替换原来未删除指定元素子树）
Return this.GoBalance (node); //将替换过的子树节点返回
} else { //若要删除元素等于当前节点元素，该节点就是要删除节点
If (node. Left == null) {
//若当前要删除节点没有左子树，则删除当前节点和删除最小节点操作一致
Node rightNode = node. Right;
Node. Right = null;
This. Size--;
Return this.GoBalance (rightNode);
}
If (node. Right == null) {
//若当前要删除节点没有右子树，则删除当前节点和删除最大节点操作一致
Node leftNode = node. Left;
Node. Left = null;
This. Size--;
Return this.GoBalance (leftNode);
}
//若当前节点既有左子树，又有右子树
//使用后继
Node successor = this.Minimum (node. Right); //找到后继节点，准备将后继节点替换删除节点
//后继就是离当前节点元素最近，且比当前元素大的节点（刚刚比当前节点元素大的元素节点）
//同时也是当前节点的右子树中的最小值
//successor. Right = this.RemoveMin (node. Right); //后继节点右子树指向删除该后继节点的子树
Successor. Right = this.Remove (node. Right, successor. Data);
Successor. Left = node. Left; //后继节点左子树指向原来节点的左子树
Node. Left = node. Right = null; //将原来节点与该树脱离关系，方便垃圾回收机制回收
Return this.GoBalance (successor); //返回删除该元素的子树
}
}
Public int getSize () {
Return this. Size;
}
Public boolean isEmpty () {
Return this. Size == 0;
}
}
红黑树
红黑树与 2-3 树的等价性
- 满足二分搜索树的基本性质（左孩子小于父节点，右孩子大于父节点）
- 有两种节点
- 2 节点：存放单个元素的节点，有两个分叉，左分叉指向小于当前节点，右分叉指向大于当前节点
- 3 节点：存放两个元素的节点，有三个分叉，左分叉指向小于左节点，中分叉指向大小介于两节点之间，右分叉指向大于右节点
- 是一颗绝对平衡的树，这与添加节点时的机制有关
2-3 树转化为红黑树
若将 2-3 树转化成普通的二分搜索树就成了红黑树，对于转化的红黑树来说，不一定是平衡二叉树（只是黑平衡），因为最坏的情况下查询节点所经过的节点都是 3 节点时，是慢于平衡二叉树的一倍的，但是由于添加删除节点时的机制，相比平衡二叉树的平衡维护来说，红黑树的维护比平衡二叉树快些，综合所有操作来看，红黑树的性能更优
红黑树维持平衡原理
由 2-3 树得到的红黑树可知以下 5 个性质
- 每个节点不是黑色就是红色
- 根节点是黑色的
- 每个叶子节点是黑色的（最后的空节点才算叶子节点，即空节点是黑色）
- 红色节点的子节点是黑色的，红色节点一定是向左倾斜的，黑色节点的右子节点一定是黑色的
- 从任意节点到达叶子节点，所经过的黑色节点是一样多的
代码实现
/**
* @ClassName: RBTree
* @Description: 基于二分搜索树的自定义红黑树
*/
public class RBTree<E extends Comparable<E>> {
Private static final boolean RED = true; //红色常量
Private static final boolean BLACK = false; //黑色常量
Private class Node {
Private Node left, right; //指向左子树和右子树的指针
Private E data; //存储节点的数据
Private boolean color; //该节点的颜色，使用定义的常量，即每个节点不是黑色就是红色
/**
* @MethodName: Node
* @Description: 创建节点
* @Param element: 传入的数据
*/
Public Node (E element) {
This. Data = element;
This. Left = null;
This. Right = null;
This. Color = RED;
//由于新增的节点在 2-3 树中是与叶子节点中与其他节点做融合
//所以在红黑树中新增节点一定先是红色
}
}
Private Node root; //存储根节点
Private int size; //记录树中元素个数
Public RBTree () {
This. Root = null;
This. Size = 0;
}
Public int getSize () {
Return this. Size;
}
Public boolean isEmpty () {
Return this. Size == 0;
}
/**
* @MethodName: isRed
* @Description: 返回该节点是否是红色，空节点返回黑色
* @Param node: 要判断的节点
* @Return boolean
*/
Private boolean isRed (Node node) {
If (node == null) {
Return BLACK;
}
Return node. Color;
}
/**
* @MethodName: leftRotate
* @Description: 将指定节点为根的子树进行左旋转后并返回
* @Param x: 指定的节点
* @Return RBTree<E>. Node
*/
Private Node leftRotate (Node x) {
Node y = x.right;
x.right = y.left;
y.left = x;
y.color = x.color;
x.color = RED;
Return y;
}
/**
* @MethodName: rightRotate
* @Description: 将指定节点为根的子树进行右旋转后并返回
* @Param y: 指定的节点
* @Return AVLTree<E>. Node
*/
Private Node rightRotate (Node x) {
Node y = x.left;
Node T 3 = y.right;
x.left = T 3;
y.right = x;
y.color = x.color;
x.color = RED;
Return y;
}
/**
* @MethodName: flipColor
* @Description: 将指定节点为根的子树进行颜色翻转后并返回
* @Param x: 指定的节点
* @Return RBTree<E>. Node
*/
Private Node flipColor (Node x) {
x.color = RED;
x.left. Color = BLACK;
x.right. Color = BLACK;
Return x;
}
/**
* @MethodName: goAddRBTree
* @Description: 添加节点时红黑树性质维护，该方法应该在插入或删除元素后调用（return 前）
* @Param node: 以该节点为根的红黑树
* @Return RBTree<E>. Node
*/
Private Node goAddRBTree (Node node) {
If (this.IsRed (node. Right) && !This.IsRed (node. Left)) {
Node = this.LeftRotate (node);
}
If (this.IsRed (node. Left) && this.IsRed (node. Left. Left)) {
Node = this.RightRotate (node);
}
If (this.IsRed (node. Left) && this.IsRed (node. Right)) {
Node = this.FlipColor (node);
}
Return node;
}
/**
* @MethodName: add
* @Description: 将元素节点添加到树中
* @Param element: 要添加的元素
* @Return void
*/
Public void add (E element) {
This. Root = this.Add (root, element);
This. Root. Color = BLACK; //添加完毕后根节点一个保持为黑色的，即根节点是黑色的
}
/**
* @MethodName: add
* @Description: 将元素插入到以该节点为根的子树中，并返回这个已添加节点的子树
* @Param node: 要插入的子树
* @Param element: 要插入的元素
* @Return BST<E>. Node 返回插入元素的子树（子树也是节点，因为节点也挂着左右指针所以是子树）
*/
Private Node add (Node node, E element) {
If (node == null) { //若遍历到树的末端
This. Size++; //插入元素时将元素个数加 1
Return new Node (element);
//返回插入节点的子树，这里子树就是叶子节点，即新节点本身
}
If (element.CompareTo (node. Data) < 0) {
//若要插入的元素小于当前节点，就应该将该元素插入到左子树中
Node. Left = add (node. Left, element);
//返回的已插入元素，并以左孩子节点为根的子树
//之后将该子树挂到当前节点左指针上
} else if (element.CompareTo (node. Data) > 0) {
//若要插入的元素小于当前节点，就应该将该元素插入到右子树中
Node. Right = add (node. Right, element);
//返回的已插入元素，并以右孩子节点为根的子树
//之后将该子树挂到当前节点右指针上
}
Return this.GoAddRBTree (node); //维护红黑树的性质
//若当前节点内容等于当前节点，相当于已经插入到以该节点为根的子树上了
//就直接返回以该节点为根的子树即可
}
}
线段树
对于经常操作某个区间的综合统计信息，若使用数组这种方式通常需要将整个数组遍历进行操作，此时效率是比较低的，而且若查询的经常是某一个区间或某几个区间的不同组合时，每次重复的查询更是没有必要的，所以若将每个区间的综合统计信息都先暂存起来，用的时候直接取再进行少量的组合，就可以大大的提高效率
-
若只是查询操作使用数组来进行存储每个区间的信息查询是最快的，但是若是要更新则可能需要将暂存起来的所有值都更新一遍，效率也比较低
-
若使用树结构存储每个区间的信息，查询虽然稍微慢了些，但是整体更新时就无需将整个树都更新，只是将有关的节点更新即可，进而效率会有提升，就是线段树存在的意义
- 由于单个元素的个数可能是奇数，所以可能不是满二叉树，但是永远是一颗平衡二叉树
- 要知道对于满二叉树中，每一层节点数量都是上一层的两倍，而且当前层的节点数量是上面所有节点综合减 1，所以为了使用静态数组存储，若当前有 n 个元素，考虑最坏情况就需要 4 n 的容量来存储
- 考虑最好的情况，若是满二叉树时（n 是 2 的倍数），即，使用 2 n 的容量就可以存储这颗树
- 考虑最坏的情况，是非满二叉树时（n 不是 2 的倍数），即，使用 4 n 的容量就可以绰绰有余的存储这颗树
- 至于每个节点的父节点和子节点可以参考堆中的规律
- 为了可以使用数组表示这颗线段树，就需要将这颗二叉树的最后一层没有孩子节点的节点，想象成连接着 null 的的子节点
/**
* @ClassName: SegmentTree
* @Description: 基于静态数组实现的线段树
*/
public class SegmentTree<E> {
Private E[] array; //存储用户数据副本
Private E[] tree; //由用户数据转化成的线段树
private SegmentTree. Stat<E> stat; //存储用户指定的统计方法
public static interface Stat<E> { //用户的统计函数接口
E stat (E a, E b); //统计方法
}
/**
* @MethodName: SegmentTree
* @Description: 使用数组转化成对应的线段树
* @Param array: 要转化的数组
* @Param stat: 统计两个元素的统计方法，使用的是 SegmentTree. Stat 内部静态接口的方法
*/
public SegmentTree (E[] array, SegmentTree. Stat<E> stat) {
This. Array = (E[]) new Object[array. Length];
//用来存储用户传来数组的副本，线段树结构应该是对用户屏蔽的
For (int i = 0; i < array. Length; i++) {
This. Array[i] = array[i];
}
This. Stat = stat;
This. Tree = (E[]) new Object[array. Length * 4]; //创建 4 倍容器存储线段树
This.BuildSegmentTree (0, 0, this. Array. Length - 1);
//在根节点位置，整个数组区间内，构建线段树
}
/**
* @MethodName: buildSegment
* @Description: 构建以当前节点为根，且指定边界的线段树
* @Param treeIndex: 当前根节点索引
* @Param left: 左边界
* @Param right: 右边界
* @Return void
*/
Private void buildSegmentTree (int treeIndex, int left, int right) {
If (left == right) { //若左右边界相等时，就是区间内只剩下一个元素，无法在分，即到达树末端
This. Tree[treeIndex] = this. Array[left]; //该节点就是单独的一个区间，存储在末端即可
Return;
}
Int middle = (left + right) / 2; //该区间的中点索引，也是左右子节点的边界
Int leftTreeIndex = leftChild (treeIndex); //左子节点索引
Int rightTreeIndex = rightChild (treeIndex); //右子节点索引
//int middle = left + (right - left) / 2;
//若传入的左右边界较大，相加可能超过 int 的表示范围
//使用以上方式，先获取之间的距离，在将该距离相加到左区间上即可避免
BuildSegmentTree (leftTreeIndex, left, middle);
//构建以左子节点为根的左半区间的线段树
BuildSegmentTree (rightTreeIndex, middle + 1, right);
//构建以左子节点为根的右半区间的线段树
This. Tree[treeIndex] = this.Stat.Stat (this. Tree[leftTreeIndex], this. Tree[rightTreeIndex]);
//构建完毕节子节点后，该节点应该存储的是两个子节点的统计信息融合
}
/**
* @MethodName: leftChild
* @Description: 获取当前节点左子节点的索引
* @Param index: 当前节点的索引
* @Return int
*/
Private int leftChild (int index) {
Return index * 2 + 1;
}
/**
* @MethodName: rightChild
* @Description: 获取当前节点右子节点的索引
* @Param index: 当前节点的索引
* @Return int
*/
Private int rightChild (int index) {
Return index * 2 + 2;
}
/**
* @MethodName: query
* @Description: 在整个区间内查询某个区间内的统计信息
* @Param queryLeft: 左查询区间
* @Param queryRight: 右查询区间
* @Return E
*/
Public E query (int queryLeft, int queryRight) {
If (queryLeft < 0 || queryRight < 0 ||
QueryLeft >= this. Array. Length || queryRight >= this. Array. Length) {
//对左右区间做合法校验
Throw new IllegalArgumentException ("Index is illegal");
}
Return query (0, 0, this. Array. Length - 1, queryLeft, queryRight);
//返回在整个区间内查询某个区间的统计信息
}
/**
* @MethodName: query
* @Description: 在线段树中查询某个区间的子区间的统计信息
* @Param indexTree: 以该节点为根的线段树节点索引
* @Param left: 该线段树节点的左边界
* @Param right: 改线段树节点的右边界
* @Param queryLeft: 查询左边界
* @Param queryRight: 查询有边界
* @Return E
*/
Private E query (int indexTree, int left, int right, int queryLeft, int queryRight) {
If (queryLeft == left && queryRight == right) {
//若查询区间和当前节点区间刚好对应，该节点存储的就是要查询区间的统计信息
Return this. Tree[indexTree]; //直接返回该节点的统计信息
}
Int middle = (left + right) / 2; //该区间的中点索引，也是左右子节点的边界
Int leftChildIndex = this.LeftChild (indexTree); //左子节点索引
Int rightChildIndex = this.RightChild (indexTree); //右子节点索引
If (queryRight <= middle) { //若查询区间位于当前节点区间左侧
Return query (leftChildIndex, left, middle, queryLeft, queryRight);
//左子树中找并返回结果
} else if (queryLeft >= middle + 1) { //若查询区间位于当前节点区间右侧侧
Return query (rightChildIndex, middle + 1, right, queryLeft, queryRight);
//右子树中找并返回结果
} else { //若查询区间在当前节点区间左侧有覆盖，又在右侧有覆盖
E leftRst = query (leftChildIndex, left, middle, queryLeft, middle);
//将左区间查询的结果暂存
E rightRst = query (rightChildIndex, middle + 1, right, middle + 1, queryRight);
//将右区间查询结果暂存
Return this.Stat.Stat (leftRst, rightRst); //将左右区间查询结果综合后返回
}
}
/**
* @MethodName: set
* @Description: 用户根据索引修改元素内容，同时线段树也应该跟着变化
* @Param index: 用户指定的索引
* @Param element: 要修改成的内容
* @Return void
*/
Public void set (int index, E element) {
if (index < 0 || index > this. Array. Length) {
Throw new IllegalArgumentException ("Set failed, Index is illegal");
}
This. Array[index] = element;
This.Set (0, 0, this. Array. Length - 1, index, element);
}
/**
* @MethodName: set
* @Description: 修改以当前节点为根的子树中的索引的值
* @Param indexTree: 当前节点
* @Param left: 当前节点的左边界
* @Param right: 当前节点的有边界
* @Param index: 要修改的元素索引，其实也可以看作一个只有一个元素区间
* @Param element: 要修改成的元素
* @Return void
*/
Private void set (int indexTree, int left, int right, int index, E element) {
If (left == right) { //若左右边界相等时，就是区间内只剩下一个元素，无法在分，即到达树末端
This. Tree[indexTree] = element; //也就是说找到了要修改的元素（区间），直接修改为要修改成的内容即可
Return; //并返回
}
Int middle = (left + right) / 2; //该区间的中点索引，也是左右子节点的边界
Int leftChildIndex = this.LeftChild (indexTree); //左子节点索引
Int rightChildIndex = this.RightChild (indexTree); //右子节点索引
If (index <= middle) { //若当前要修改的元素位于当前节点左半区间时
Set (leftChildIndex, left, middle, index, element); //从左子节点中寻找到并修改
} else { //index >= middle + 1 //若当前要修改的元素位于当前节点右半区间时
Set (rightChildIndex, middle + 1, right, index, element); //从右子节点中寻找到并修改
}
This. Tree[indexTree] = this.Stat.Stat (this. Tree[leftChildIndex], this. Tree[rightChildIndex]);
//将左或右子树的值修改后，应该将当前节点重新用两个子节点进行统计
}
/**
* @MethodName: get
* @Description: 用户根据指定索引获取元素
* @Param index: 指定的索引
* @Return int
*/
Public E get (int index) {
if (index < 0 || index >= this. Array. Length) {
Throw new IllegalArgumentException ("Get failed, Index is illegal");
}
Return this. Array[index];
}
/**
* @MethodName: getSize
* @Description: 获取已存入元素个数
* @Return int
*/
Public int getSize () {
Return this. Array. Length;
}
}
字典树
在存储字符串大量字符串时，若使用基于二叉树实现映射虽然已经达到了一定的查询效率，为了进一步的提高效率，就可以采用字典树这种数据结构，就可以将查询效率只与当前字符串长度有关，字典树是一颗多叉树，将每个字符串中的字符作为节点来存储，从根节点开始到叶子节点遍历就可得到存储的字符串
Import java. Util. ArrayList;
Import java. Util. Stack;
/**
* @ClassName: Trie
* @Description: 自定义字典树
*/
Public class Trie {
Private class Node {
Private Character c; //存储的字符
Private boolean isEnd; //是否是字符串的结束标志
private ArrayList<Node> next; //下一个节点，由于是多个采用动态数组存储
Public Node (Character c, boolean isWord) {
This. C = c;
This. IsEnd = isWord;
this. Next = new ArrayList<>();
}
Public Node (Character c) {
This (c, false);
}
Public Node () {
This (null, false);
}
}
Private Node root; //根节点
Private int size; //存储的字符串个数
Public Trie () {
This. Root = new Node (); //根节点存储 null
This. Size = 0;
}
/**
* @MethodName: add
* @Description: 将指定字符串添加到字典树中
* @Param string: 指定的字符串
* @Return void
*/
Public void add (String string) {
Node cur = this. Root; //当前节点是根节点
For (int i = 0; i < string.Length (); i++) { //遍历传入的整个字符串
Char c = string.CharAt (i); //获取当前遍历到的字符，以便后续操作
Node node = new Node (c); //将该字符包装成节点
If (cur.Next.IsEmpty ()) { //若当前节点的子节点为空
Cur.Next.Add (node); //直接添加该节点即可
Cur = cur.Next.Get (0); //并当前节点指针指向新添加的节点
}
//遍历该节点的子节点们
For (int j = 0; j < cur.Next.Size (); j++) {
If (c == cur.Next.Get (j). C) { //若有与要添加节点相同的节点，就无需重复添加
Cur = cur.Next.Get (j); //直接引用该节点即可
Break; //跳出循环，向下层接着寻找添加
}
If (j == cur.Next.Size () - 1) { //若到最后一个子节点时
Cur.Next.Add (node); //还未跳出循环，说明就没有相同的，那就添加该节点
}
}
}
If (! Cur. IsEnd) { //若添加完毕该字符串后，当前节点不是字符串结尾
Cur. IsEnd = true; //将该字节点标注成字符串结尾
This. Size++; //同时存储字符串的数量加一个
}
}
/**
* @MethodName: contains
* @Description: 判断该字符串是否存储在该树中
* @Param string: 要做判断的字符串
* @Return boolean
*/
Public boolean contains (String string) {
Node pre = this.Prefix (this. Root, string);
Return pre != null && pre. IsEnd; //若有该前缀并且还是该前缀还是字符串结尾，就返回 true
}
/**
* @MethodName: isPrefix
* @Description: 判断存储在该树中是否存储以该前缀开头的字符串
* @Param prefix: 指定的前缀
* @Return boolean
*/
Public boolean isPrefix (String prefix) {
Return this.Prefix (this. Root, prefix) != null; //若有该前缀就返回 true
}
/**
* @MethodName: remove
* @Description: 删除树中存储的字符串，若字符串不存在则什么也不做
* @Param string: 要删除的字符串
* @Return void
*/
Public void remove (String string) {
If (! This.Contains (string)) {
//若字符串不存在则什么也不做
Return;
}
Stack<Node> stack = new Stack<>(); //创建一个栈，用来存储该字符串的所有节点
Stack.Push (this. Root); //将根节点先入栈
For (int i = 0; i < string.Length (); i++) { //遍历整个字符串
Node node = this.Prefix (stack.Peek (), String.ValueOf (string.CharAt (i)));
//从当前栈顶节点（父节点）中查询该字符对应的子节点
Stack.Push (node); //并压入栈中
}
Stack.Peek (). IsEnd = false; //当前栈顶就是该删除字符串的结尾字符节点，将结束标志置为 false
This. Size--; //删除字符串中需要将树中元素个数减 1
While (! Stack.IsEmpty ()) { //执行删除操作，依次从栈顶子节点向树的上方删除
Node delNode = stack.Pop (); //当前要删除的节点出栈
If (delNode.Next.IsEmpty () && delNode. IsEnd == false) {
//若当前要删除节点下已经没有其他节点依赖，并且不是结尾节点才能删除
//也就是说当前叶子节点，并且不是结尾节点
Node pre = stack.Peek (); //由于上面当前节点已经出栈，所以当前栈顶是当前节点的父节点
Int delNodeIndex = pre.Next.IndexOf (delNode); //从父节点的子节点中查询该子节点的索引
Pre.Next.Remove (delNodeIndex); //根据索引删除该子节点
}
}
}
/**
* @MethodName: Prefix
* @Description: 返回以该节点为子树，其中存在的前缀最后一个节点，找不到就返回 null
* @Param cur: 以该节点为子树的节点
* @Param prefix: 要查询的前缀
* @Return Trie. Node
*/
Private Node Prefix (Node cur, String prefix) {
For (int i = 0; i < prefix.Length (); i++) { //遍历传入的整个前缀字符串
Char c = prefix.CharAt (i); //获取当前遍历到的字符，以便后续操作
If (cur.Next.IsEmpty ()) { //若当前节点的子节点为空
Return null; //说明肯定没有该字符，返回 null
}
For (int j = 0; j < cur.Next.Size (); j++) {
If (c == cur.Next.Get (j). C) { //若有要查询的节点
Cur = cur.Next.Get (j); //当前指针后移
Break; //跳出循环，接着向下找
}
If (j == cur.Next.Size () - 1) { //若到最后一个子节点
Return null; //还未跳出循环，说明就没有相同的，返回 null
}
}
}
Return cur; //遍历完整个要查询的字符串后，将最后一个指针返回回去
}
/**
* @MethodName: getSize
* @Description: 获取当前树中存储的字符串个数
* @Return int
*/
Public int getSize () {
Return this. Size;
}
/**
* @MethodName: isEmpty
* @Description: 判断当前树是否为空
* @Return boolean
*/
Public boolean isEmpty () {
Return this. Size == 0;
}
/**
* @MethodName: bfs
* @Description: 层序遍历树结构
* @Return void
*/
Public void bfs () {
ArrayList<Node> root = new ArrayList<>();
Root.Add (this. Root);
Bfs (root, 0);
}
/**
* @MethodName: bfs
* @Description: 递归的层序遍历该动态数组中的所有节点的子节点
* @Param childNodes: 存储节点的动态数组
* @Param depth: 深度
* @Return void
*/
private void bfs (ArrayList<Node> childNodes, int depth) {
ArrayList<Node> grandsonNodes = new ArrayList<>(); //所有孙元素节点
For (Node child : childNodes) { //遍历所有子节点
For (int i = 0; i < depth; i++) {
System.Out.Print ("--");
}
System.Out.Println (child. C); //输出所有子节点
GrandsonNodes.AddAll (child. Next); //将该子节点下的子节点加入到孙节点元素中
}
If (! GrandsonNodes.IsEmpty ()) { //若当前孙节点数组中有节点就需要递归调用
Bfs (grandsonNodes, depth + 1);
}
}
}
Comments NOTHING