【从蛋壳到满天飞】JAVA 数据结构解析和算法实现,全部文章大概的内容如下:
Arrays(数组)、Stacks(栈)、Queues(队列)、LinkedList(链表)、Recursion(递归思想)、BinarySearchTree(二分搜索树)、Set(集合)、Map(映射)、Heap(堆)、PriorityQueue(优先队列)、SegmentTree(线段树)、Trie(字典树)、UnionFind(并查集)、AVLTree(AVL 平衡树)、RedBlackTree(红黑平衡树)、HashTable(哈希表)
源代码有三个:ES6(单个单个的 class 类型的 js 文件) | JS + HTML(一个 js 配合一个 html)| JAVA (一个一个的工程)
全部源代码已上传 github, 点击我吧 ,光看文章能够掌握两成,动手敲代码、动脑思考、画图才可以掌握八成。
本文章适合 对数据结构想了解并且感兴趣的人群,文章风格一如既往如此,就觉得手机上看起来比较方便,这样显得比较有条理,整理这些笔记加源码,时间跨度也算将近半年时间了,希望对想学习数据结构的人或者正在学习数据结构的人群有帮助。
线性数据结构是把所有的数据排成一排
树结构本身是一个种天然的组织结构
树结构非常的高效
在计算机科学领域很多问题的处理
二分搜索树(Binary Search Tree)
平衡二叉树:AVL;红黑树,
算法需要使用一些特殊的操作的时候将数据组织成树结构
堆
以及 并查集
, 线段树、Trie(字典树、前缀树)
二叉树
class Node { E e; Node left; Node right; }
二叉树也叫多叉树,
在数据结构领域对应树结构来说
二叉树和链表一样具有天然递归的结构
二叉树不一定是“满”的
二分搜索树是一棵二叉树
二分搜索树的每一个节点的值
二分搜索树的每一棵子树也是二分搜索树
为了能够达到二分搜索树的性质
二分搜索树其实不是支持所有的类型
代码实现
public class MyBinarySearchTree<E extends Comparable<E>> { private class Node { public E e; public Node left, right; public Node (E e) { this.e = e; left = null; right = null; } } private Node root; private int size; public MyBinarySearchTree () { root = null; size = 0; } public int getSize() { return size; } public boolean isEmpty () { return size == 0; } }
如果二分搜索树的根节点为空的话
按照这样的规则,每来一个新元素从根节点开始,
如果遇到两个元素的值相同,那暂时先不去管,
二分搜索树添加元素的非递归写法,和链表很像
代码
public class MyBinarySearchTree<E extends Comparable<E>> { private class Node { public E e; public Node left, right; public Node (E e) { this.e = e; left = null; right = null; } } private Node root; private int size; public MyBinarySearchTree () { root = null; size = 0; } public int getSize() { return size; } public boolean isEmpty () { return size == 0; } // 向二分搜索树中添加一个元素 e public void add (E e) { if (root == null) { root = new Node(e); size ++; } else { add(root, e); } } // 向以node为根的二分搜索树种插入元素E,递归算法 private void add (Node node, E e) { // node 是对用户屏蔽的,用户不用知道二分搜索树中有怎样一个节点结构 // 如果出现相同的元素就不进行操作了 if (e.equals(node.e)) { return; } else if (e.compareTo(node.e) < 0 && node.left == null) { // 给左孩子赋值 node.left = new Node(e); size ++; return; } else if (e.compareTo(node.e) > 0 && node.right == null) { // 给右海子赋值 node.right = new Node(e); size ++; return; } // 这里是处理节点被占了,那就进入下一个层的二叉树中 if (e.compareTo(node.e) < 0) { // 去左子树 add(node.left, e); } else { // e.compareTo(node.e) > 0 // 去右子树 add(node.right, e); } } }
对于二分搜索的插入操作
改进添加操作
之前的算法
代码
public class MyBinarySearchTree<E extends Comparable<E>> { private class Node { public E e; public Node left, right; public Node (E e) { this.e = e; left = null; right = null; } } private Node root; private int size; public MyBinarySearchTree () { root = null; size = 0; } public int getSize() { return size; } public boolean isEmpty () { return size == 0; } // 向二分搜索树中添加一个元素 e // 改进:直接调用add public void add (E e) { root = add(root, e); } // 向以node为根的二分搜索树种插入元素E,递归算法 // 改进:返回插入的新节点后二分搜索树的根 private Node add (Node node, E e) { // 处理最基本的问题 if (node == null) { size ++; return new Node(e); } // 空的二叉树也是叉树。 if (e.compareTo(node.e) < 0) { // 将处理后的结果赋值给node的左子树 node.left = add(node.left, e); } else if (e.compareTo(node.e) > 0) { // 将处理后的结果赋值给node的右子树 node.right = add(node.right, e); } // 如果相同 就什么都不做 // 最后返回这个node return node; } // // 向二分搜索树中添加一个元素 e // public void add (E e) { // if (root == null) { // root = new Node(e); // size ++; // } else { // add(root, e); // } // } // // 向以node为根的二分搜索树种插入元素E,递归算法 // private void add (Node node, E e) { // // node 是对用户屏蔽的,用户不用知道二分搜索树中有怎样一个节点结构 // // // 如果出现相同的元素就不进行操作了 // if (e.equals(node.e)) { // return; // } else if (e.compareTo(node.e) < 0 && node.left == null) { // // 给左孩子赋值 // node.left = new Node(e); // return; // } else if (e.compareTo(node.e) > 0 && node.right == null) { // // 给右海子赋值 // node.right = new Node(e); // return; // } // // // 这里是处理节点被占了,那就进入下一个层的二叉树中 // if (e.compareTo(node.e) < 0) { // // 去左子树 // add(node.left, e); // } else { // e.compareTo(node.e) > 0 // // 去右子树 // add(node.right, e); // } // } }
虽然代码量更少了,但是也更难理解的了一些
查询操作非常的容易
和添加元素一样需要使用递归的进行实现
在数组和链表中有索引这个概念,
代码
public class MyBinarySearchTree<E extends Comparable<E>> { private class Node { public E e; public Node left, right; public Node (E e) { this.e = e; left = null; right = null; } } private Node root; private int size; public MyBinarySearchTree () { root = null; size = 0; } public int getSize() { return size; } public boolean isEmpty () { return size == 0; } // 向二分搜索树中添加一个元素 e // 改进:直接调用add public void add (E e) { root = add(root, e); } // 向以node为根的二分搜索树中插入元素E,递归算法 // 改进:返回插入的新节点后二分搜索树的根 private Node add (Node node, E e) { // 处理最基本的问题 if (node == null) { size ++; return new Node(e); } // 空的二叉树也是叉树。 if (e.compareTo(node.e) < 0) { // 将处理后的结果赋值给node的左子树 node.left = add(node.left, e); } else if (e.compareTo(node.e) > 0) { // 将处理后的结果赋值给node的右子树 node.right = add(node.right, e); } // 如果相同 就什么都不做 // 最后返回这个node return node; } // 查询二分搜索数中是否包含某个元素 public boolean contains (E e) { return contains(root, e); } // 向以node为根的二分搜索树 进行查找 递归算法 public boolean contains (Node node, E e) { // 解决最基本的问题 也就是遍历完所有节点都没有找到 if (node == null) { return false; } // 如果 e 小于当前节点的e 则向左子树进发 if (e.compareTo(node.e) < 0) { return contains(node.left, e); } else if (e.compareTo(node.e) > 0) { // 如果 e 大于当前节点的e 则向右子树进发 return contains(node.right, e); } else { // 如果e 等于 当前节点 e 则直接返回true return true; } } }
遍历操作就是把这个数据结构中所有的元素都访问一遍
访问数据结构中存储的所有元素是因为与业务相关,
在线性结构下,遍历是极其容易的
在树结构下遍历操作并没有那么难
对于遍历操作,两个子树都要顾及
// 遍历以node为根的二分搜索树 递归算法 function traverse(node) { if (node === null) { return; } // ... 要做的事情 // 访问该节点 两边都要顾及 // 访问该节点的时候就去做该做的事情, // 如 给所有学生加两分 traverse(node.left); traverse(node.right); } // 写法二 这种逻辑也是可以的 function traverse(node) { if (node !== null) { // ... 要做的事情 // 访问该节点 两边都要顾及 // 访问该节点的时候就去做该做的事情, // 如 给所有学生加两分 traverse(node.left); traverse(node.right); } }
(class: MyBinarySearchTree, class: Main)
MyBinarySearchTree
public class MyBinarySearchTree<E extends Comparable<E>> { private class Node { public E e; public Node left, right; public Node (E e) { this.e = e; left = null; right = null; } } private Node root; private int size; public MyBinarySearchTree () { root = null; size = 0; } public int getSize() { return size; } public boolean isEmpty () { return size == 0; } // 向二分搜索树中添加一个元素 e // 改进:直接调用add public void add (E e) { root = add(root, e); } // 向以node为根的二分搜索树中插入元素E,递归算法 // 改进:返回插入的新节点后二分搜索树的根 private Node add (Node node, E e) { // 处理最基本的问题 if (node == null) { size ++; return new Node(e); } // 空的二叉树也是叉树。 if (e.compareTo(node.e) < 0) { // 将处理后的结果赋值给node的左子树 node.left = add(node.left, e); } else if (e.compareTo(node.e) > 0) { // 将处理后的结果赋值给node的右子树 node.right = add(node.right, e); } // 如果相同 就什么都不做 // 最后返回这个node return node; } // 查询二分搜索数中是否包含某个元素 public boolean contains (E e) { return contains(root, e); } // 向以node为根的二分搜索树 进行查找 递归算法 public boolean contains (Node node, E e) { // 解决最基本的问题 也就是遍历完所有节点都没有找到 if (node == null) { return false; } // 如果 e 小于当前节点的e 则向左子树进发 if (e.compareTo(node.e) < 0) { return contains(node.left, e); } else if (e.compareTo(node.e) > 0) { // 如果 e 大于当前节点的e 则向右子树进发 return contains(node.right, e); } else { // 如果e 等于 当前节点 e 则直接返回true return true; } } // 二分搜索树的前序遍历 public void preOrder () { preOrder(root); } // 前序遍历以node为根的二分搜索树 递归算法 public void preOrder (Node node) { if (node == null) { return; } // 输出 System.out.println(node.e); preOrder(node.left); preOrder(node.right); // // 这种逻辑也是可以的 // if (node != null) { // // 输出 // System.out.println(node.e); // // preOrder(node.left); // preOrder(node.right); // } } }
Main
public class Main { public static void main(String[] args) { MyBinarySearchTree<Integer> mbst = new MyBinarySearchTree<Integer>(); int [] nums = {5, 3, 6, 8, 4, 2}; for (int i = 0; i < nums.length ; i++) { mbst.add(nums[i]); } ///////////////// // 5 // // / / // // 3 6 // // / / / // // 2 4 8 // ///////////////// mbst.preOrder(); } }
遍历输出二分搜索树
(class: MyBinarySearchTree, class: Main)
MyBinarySearchTree
public class MyBinarySearchTree<E extends Comparable<E>> { private class Node { public E e; public Node left, right; public Node (E e) { this.e = e; left = null; right = null; } } private Node root; private int size; public MyBinarySearchTree () { root = null; size = 0; } public int getSize() { return size; } public boolean isEmpty () { return size == 0; } // 向二分搜索树中添加一个元素 e // 改进:直接调用add public void add (E e) { root = add(root, e); } // 向以node为根的二分搜索树中插入元素E,递归算法 // 改进:返回插入的新节点后二分搜索树的根 private Node add (Node node, E e) { // 处理最基本的问题 if (node == null) { size ++; return new Node(e); } // 空的二叉树也是叉树。 if (e.compareTo(node.e) < 0) { // 将处理后的结果赋值给node的左子树 node.left = add(node.left, e); } else if (e.compareTo(node.e) > 0) { // 将处理后的结果赋值给node的右子树 node.right = add(node.right, e); } // 如果相同 就什么都不做 // 最后返回这个node return node; } // 查询二分搜索数中是否包含某个元素 public boolean contains (E e) { return contains(root, e); } // 向以node为根的二分搜索树 进行查找 递归算法 public boolean contains (Node node, E e) { // 解决最基本的问题 也就是遍历完所有节点都没有找到 if (node == null) { return false; } // 如果 e 小于当前节点的e 则向左子树进发 if (e.compareTo(node.e) < 0) { return contains(node.left, e); } else if (e.compareTo(node.e) > 0) { // 如果 e 大于当前节点的e 则向右子树进发 return contains(node.right, e); } else { // 如果e 等于 当前节点 e 则直接返回true return true; } } // 二分搜索树的前序遍历 public void preOrder () { preOrder(root); } // 前序遍历以node为根的二分搜索树 递归算法 public void preOrder (Node node) { if (node == null) { return; } // 输出 System.out.println(node.e); preOrder(node.left); preOrder(node.right); // // 这种逻辑也是可以的 // if (node != null) { // // 输出 // System.out.println(node.e); // // preOrder(node.left); // preOrder(node.right); // } } @Override public String toString () { StringBuilder sb = new StringBuilder(); generateBSTString(root, 0, sb); return sb.toString(); } // 生成以node为根节点,深度为depth的描述二叉树的字符串 private void generateBSTString (Node node, int depath, StringBuilder sb) { if (node == null) { sb.append(generateDepthString(depath) + "null/n"); return; } sb.append(generateDepthString(depath) + node.e + "/n"); generateBSTString(node.left, depath + 1, sb); generateBSTString(node.right, depath + 1, sb); } // 生成路径字符串 private String generateDepthString (int depth) { StringBuilder sb = new StringBuilder(); for (int i = 0; i < depth; i++) { sb.append("-- "); } return sb.toString(); } }
Main
public class Main { public static void main(String[] args) { MyBinarySearchTree<Integer> mbst = new MyBinarySearchTree<Integer>(); int [] nums = {5, 3, 6, 8, 4, 2}; for (int i = 0; i < nums.length ; i++) { mbst.add(nums[i]); } ///////////////// // 5 // // / / // // 3 6 // // / / / // // 2 4 8 // ///////////////// mbst.preOrder(); System.out.println(); // 输出 调试字符串 System.out.println(mbst.toString()); } }
前序遍历
前
function preOrder(node) { if (node == null) return; // ... 要做的事情 // 访问该节点 // 先一直往左,然后不断返回上一层 再向左、终止, // 最后整个操作循环往复,直到全部终止。 preOrder(node.left); preOrder(node.right); }
中序遍历
中
function inOrder(node) { if (node == null) return; inOrder(node.left); // ... 要做的事情 // 访问该节点 inOrder(node.right); }
中序遍历后输出的结果是排序后的结果。
后序遍历
后
function inOrder(node) { if (node == null) return; inOrder(node.left); inOrder(node.right); // ... 要做的事情 // 访问该节点 }
二分搜索树的前序遍历和后序遍历并不像中序遍历那样进行了排序
java
、 c#
这样的语言都有垃圾回收机制, c++
语言中需要手动的控制内存, 二分搜索树的前中后序遍历
(class: MyBinarySearchTree, class: Main)
MyBinarySearchTree
public class MyBinarySearchTree<E extends Comparable<E>> { private class Node { public E e; public Node left, right; public Node (E e) { this.e = e; left = null; right = null; } } private Node root; private int size; public MyBinarySearchTree () { root = null; size = 0; } public int getSize() { return size; } public boolean isEmpty () { return size == 0; } // 向二分搜索树中添加一个元素 e // 改进:直接调用add public void add (E e) { root = add(root, e); } // 向以node为根的二分搜索树中插入元素E,递归算法 // 改进:返回插入的新节点后二分搜索树的根 private Node add (Node node, E e) { // 处理最基本的问题 if (node == null) { size ++; return new Node(e); } // 空的二叉树也是叉树。 if (e.compareTo(node.e) < 0) { // 将处理后的结果赋值给node的左子树 node.left = add(node.left, e); } else if (e.compareTo(node.e) > 0) { // 将处理后的结果赋值给node的右子树 node.right = add(node.right, e); } // 如果相同 就什么都不做 // 最后返回这个node return node; } // 查询二分搜索数中是否包含某个元素 public boolean contains (E e) { return contains(root, e); } // 向以node为根的二分搜索树 进行查找 递归算法 private boolean contains (Node node, E e) { // 解决最基本的问题 也就是遍历完所有节点都没有找到 if (node == null) { return false; } // 如果 e 小于当前节点的e 则向左子树进发 if (e.compareTo(node.e) < 0) { return contains(node.left, e); } else if (e.compareTo(node.e) > 0) { // 如果 e 大于当前节点的e 则向右子树进发 return contains(node.right, e); } else { // 如果e 等于 当前节点 e 则直接返回true return true; } } // 二分搜索树的前序遍历 public void preOrder () { preOrder(root); } // 前序遍历以node为根的二分搜索树 递归算法 private void preOrder (Node node) { if (node == null) { return; } // 输出 System.out.println(node.e); preOrder(node.left); preOrder(node.right); // // 这种逻辑也是可以的 // if (node != null) { // // 输出 // System.out.println(node.e); // // preOrder(node.left); // preOrder(node.right); // } } // 二分搜索树的中序遍历 public void inOrder () { inOrder(root); } // 中序遍历以node为根的二分搜索树 递归算法 private void inOrder (Node node) { if (node == null) return; inOrder(node.left); System.out.println(node.e); inOrder(node.right); } // 二分搜索树的后序遍历 public void postOrder () { postOrder(root); } // 后续遍历以node为根的二分搜索树 递归算法 private void postOrder (Node node) { if (node == null) return; postOrder(node.left); postOrder(node.right); System.out.println(node.e); } @Override public String toString () { StringBuilder sb = new StringBuilder(); generateBSTString(root, 0, sb); return sb.toString(); } // 生成以node为根节点,深度为depth的描述二叉树的字符串 private void generateBSTString (Node node, int depath, StringBuilder sb) { if (node == null) { sb.append(generateDepthString(depath) + "null/n"); return; } sb.append(generateDepthString(depath) + node.e + "/n"); generateBSTString(node.left, depath + 1, sb); generateBSTString(node.right, depath + 1, sb); } // 生成路径字符串 private String generateDepthString (int depth) { StringBuilder sb = new StringBuilder(); for (int i = 0; i < depth; i++) { sb.append("-- "); } return sb.toString(); } }
Main
public class Main { public static void main(String[] args) { MyBinarySearchTree<Integer> mbst = new MyBinarySearchTree<Integer>(); int [] nums = {5, 3, 6, 8, 4, 2}; for (int i = 0; i < nums.length ; i++) { mbst.add(nums[i]); } ///////////////// // 5 // // / / // // 3 6 // // / / / // // 2 4 8 // ///////////////// // 前序遍历 mbst.preOrder(); // 5 3 2 4 6 8 System.out.println(); // 中序遍历 mbst.inOrder(); // 2 3 4 5 6 8 System.out.println(); // 后序遍历 mbst.postOrder(); // 2 4 3 8 6 5 System.out.println(); // // 输出 调试字符串 // System.out.println(mbst.toString()); } }
再看二分搜索树的遍历
对二分搜索树前中后这三种顺序的遍历
function traverse(node) { if (node === null) return; // 1. 第一个访问的机会 前 traverse(node.left); // 2. 第二个访问的机会 中 traverse(node.right); // 3. 第三个访问的机会 后 }
二叉树前中后序遍历访问节点的不同
前序遍历的递归写法
前
function preOrder(node) { if (node == null) return; // ... 要做的事情 // 访问该节点 // 先一直往左,然后不断返回上一层 再向左、终止, // 最后整个操作循环往复,直到全部终止。 preOrder(node.left); preOrder(node.right); }
前序遍历的非递归写法
栈
无论是非递归还是递归的写法,结果都是一致的
将递归算法转换为非递归算法
二分搜索树遍历的非递归实现比递归实现复杂很多
二分搜索树的中序遍历和后序遍历的非递归实现更复杂
对于前序遍历来说无论是递归写法还是非递归写法
(class: MyBinarySearchTree, class: Main)
MyBinarySearchTree
import java.util.Stack; public class MyBinarySearchTree<E extends Comparable<E>> { private class Node { public E e; public Node left, right; public Node (E e) { this.e = e; left = null; right = null; } } private Node root; private int size; public MyBinarySearchTree () { root = null; size = 0; } public int getSize() { return size; } public boolean isEmpty () { return size == 0; } // 向二分搜索树中添加一个元素 e // 改进:直接调用add public void add (E e) { root = add(root, e); } // 向以node为根的二分搜索树中插入元素E,递归算法 // 改进:返回插入的新节点后二分搜索树的根 private Node add (Node node, E e) { // 处理最基本的问题 if (node == null) { size ++; return new Node(e); } // 空的二叉树也是叉树。 if (e.compareTo(node.e) < 0) { // 将处理后的结果赋值给node的左子树 node.left = add(node.left, e); } else if (e.compareTo(node.e) > 0) { // 将处理后的结果赋值给node的右子树 node.right = add(node.right, e); } // 如果相同 就什么都不做 // 最后返回这个node return node; } // 查询二分搜索数中是否包含某个元素 public boolean contains (E e) { return contains(root, e); } // 向以node为根的二分搜索树 进行查找 递归算法 private boolean contains (Node node, E e) { // 解决最基本的问题 也就是遍历完所有节点都没有找到 if (node == null) { return false; } // 如果 e 小于当前节点的e 则向左子树进发 if (e.compareTo(node.e) < 0) { return contains(node.left, e); } else if (e.compareTo(node.e) > 0) { // 如果 e 大于当前节点的e 则向右子树进发 return contains(node.right, e); } else { // 如果e 等于 当前节点 e 则直接返回true return true; } } // 二分搜索树的前序遍历 public void preOrder () { preOrder(root); } // 前序遍历以node为根的二分搜索树 递归算法 private void preOrder (Node node) { if (node == null) { return; } // 输出 System.out.println(node.e); preOrder(node.left); preOrder(node.right); // // 这种逻辑也是可以的 // if (node != null) { // // 输出 // System.out.println(node.e); // // preOrder(node.left); // preOrder(node.right); // } } // 二分搜索树的前序遍历 非递归算法 public void preOrderNonRecursive () { Stack<Node> stack = new Stack<Node>(); stack.push(root); Node node = null; while (!stack.isEmpty()) { node = stack.pop(); // // 第一种写法 不符合要求也可以压入栈,但是不符合要求的在出栈后不处理它 // if (node != null) { // System.out.println(node.e); // stack.push(node.right); // stack.push(node.left); // } // // 第二种写法 不符合要求也可以压入栈,但是不符合要求的在出栈后不处理它 // if (node == null) continue; // // System.out.println(node.e); // stack.push(node.right); // stack.push(node.left); // 写法三 不符合要求就不压入栈 System.out.println(node.e); if (node.right != null) { stack.push(node.right); } if (node.left != null) { stack.push(node.left); } } } // 二分搜索树的中序遍历 public void inOrder () { inOrder(root); } // 中序遍历以node为根的二分搜索树 递归算法 private void inOrder (Node node) { if (node == null) return; inOrder(node.left); System.out.println(node.e); inOrder(node.right); } // 二分搜索树的中序遍历 非递归算法 public void inOrderNonRecursive () { } // 二分搜索树的后序遍历 public void postOrder () { postOrder(root); } // 后续遍历以node为根的二分搜索树 递归算法 private void postOrder (Node node) { if (node == null) return; postOrder(node.left); postOrder(node.right); System.out.println(node.e); } @Override public String toString () { StringBuilder sb = new StringBuilder(); generateBSTString(root, 0, sb); return sb.toString(); } // 生成以node为根节点,深度为depth的描述二叉树的字符串 private void generateBSTString (Node node, int depath, StringBuilder sb) { if (node == null) { sb.append(generateDepthString(depath) + "null/n"); return; } sb.append(generateDepthString(depath) + node.e + "/n"); generateBSTString(node.left, depath + 1, sb); generateBSTString(node.right, depath + 1, sb); } // 生成路径字符串 private String generateDepthString (int depth) { StringBuilder sb = new StringBuilder(); for (int i = 0; i < depth; i++) { sb.append("-- "); } return sb.toString(); } }
Main
public class Main { public static void main(String[] args) { MyBinarySearchTree<Integer> mbst = new MyBinarySearchTree<Integer>(); int [] nums = {5, 3, 6, 8, 4, 2}; for (int i = 0; i < nums.length ; i++) { mbst.add(nums[i]); } ///////////////// // 5 // // / / // // 3 6 // // / / / // // 2 4 8 // ///////////////// // 前序遍历 mbst.preOrder(); // 5 3 2 4 6 8 System.out.println(); // 中序遍历 mbst.inOrder(); // 2 3 4 5 6 8 System.out.println(); // 后序遍历 mbst.postOrder(); // 2 4 3 8 6 5 System.out.println(); // 前序遍历 非递归 mbst.preOrderNonRecursive(); // 5 3 2 4 6 8 System.out.println(); // // 输出 调试字符串 // System.out.println(mbst.toString()); } }
二分搜索树的 前序、中序、后序遍历
对于二分搜索树来说
先遍历第 0 层、再遍历第 1 层、再遍历下一层,
对于层序遍历的实现或者广度优先遍历的实现
先入队根节点,然后看队首是否有元素,
相对于深度优先遍历来说,广度优先遍历的优点
在图中也是有深度优先遍历和广度优先遍历的
(class: MyBinarySearchTree, class: Main)
MyBinarySearchTree
import java.util.LinkedList; import java.util.Queue; import java.util.Stack; public class MyBinarySearchTree<E extends Comparable<E>> { private class Node { public E e; public Node left, right; public Node (E e) { this.e = e; left = null; right = null; } } private Node root; private int size; public MyBinarySearchTree () { root = null; size = 0; } public int getSize() { return size; } public boolean isEmpty () { return size == 0; } // 向二分搜索树中添加一个元素 e // 改进:直接调用add public void add (E e) { root = add(root, e); } // 向以node为根的二分搜索树中插入元素E,递归算法 // 改进:返回插入的新节点后二分搜索树的根 private Node add (Node node, E e) { // 处理最基本的问题 if (node == null) { size ++; return new Node(e); } // 空的二叉树也是叉树。 if (e.compareTo(node.e) < 0) { // 将处理后的结果赋值给node的左子树 node.left = add(node.left, e); } else if (e.compareTo(node.e) > 0) { // 将处理后的结果赋值给node的右子树 node.right = add(node.right, e); } // 如果相同 就什么都不做 // 最后返回这个node return node; } // 查询二分搜索数中是否包含某个元素 public boolean contains (E e) { return contains(root, e); } // 向以node为根的二分搜索树 进行查找 递归算法 private boolean contains (Node node, E e) { // 解决最基本的问题 也就是遍历完所有节点都没有找到 if (node == null) { return false; } // 如果 e 小于当前节点的e 则向左子树进发 if (e.compareTo(node.e) < 0) { return contains(node.left, e); } else if (e.compareTo(node.e) > 0) { // 如果 e 大于当前节点的e 则向右子树进发 return contains(node.right, e); } else { // 如果e 等于 当前节点 e 则直接返回true return true; } } // 二分搜索树的前序遍历 public void preOrder () { preOrder(root); } // 前序遍历以node为根的二分搜索树 递归算法 private void preOrder (Node node) { if (node == null) { return; } // 输出 System.out.println(node.e); preOrder(node.left); preOrder(node.right); // // 这种逻辑也是可以的 // if (node != null) { // // 输出 // System.out.println(node.e); // // preOrder(node.left); // preOrder(node.right); // } } // 二分搜索树的前序遍历 非递归算法 public void preOrderNonRecursive () { Stack<Node> stack = new Stack<Node>(); stack.push(root); Node node = null; while (!stack.isEmpty()) { node = stack.pop(); // // 第一种写法 不符合要求也可以压入栈,但是不符合要求的在出栈后不处理它 // if (node != null) { // System.out.println(node.e); // stack.push(node.right); // stack.push(node.left); // } // // 第二种写法 不符合要求也可以压入栈,但是不符合要求的在出栈后不处理它 // if (node == null) continue; // // System.out.println(node.e); // stack.push(node.right); // stack.push(node.left); // 写法三 不符合要求就不压入栈 System.out.println(node.e); if (node.right != null) { stack.push(node.right); } if (node.left != null) { stack.push(node.left); } } } // 二分搜索树的中序遍历 public void inOrder () { inOrder(root); } // 中序遍历以node为根的二分搜索树 递归算法 private void inOrder (Node node) { if (node == null) return; inOrder(node.left); System.out.println(node.e); inOrder(node.right); } // 二分搜索树的中序遍历 非递归算法 public void inOrderNonRecursive () { } // 二分搜索树的后序遍历 public void postOrder () { postOrder(root); } // 后续遍历以node为根的二分搜索树 递归算法 private void postOrder (Node node) { if (node == null) return; postOrder(node.left); postOrder(node.right); System.out.println(node.e); } // 二分搜索树的层序遍历 public void levelOrder () { // java中的Queue是一个接口,但是它有链表和队列的实现, // 所以你可以new 一个子类链表类来进行进行使用,可以达到同样的效果 Queue<Node> queue = new LinkedList<Node>(); queue.add(root); while (!queue.isEmpty()) { Node node = queue.remove(); System.out.println(node.e); if (node.left != null) { queue.add(node.left); } if (node.right != null) { queue.add(node.right); } } } @Override public String toString () { StringBuilder sb = new StringBuilder(); generateBSTString(root, 0, sb); return sb.toString(); } // 生成以node为根节点,深度为depth的描述二叉树的字符串 private void generateBSTString (Node node, int depath, StringBuilder sb) { if (node == null) { sb.append(generateDepthString(depath) + "null/n"); return; } sb.append(generateDepthString(depath) + node.e + "/n"); generateBSTString(node.left, depath + 1, sb); generateBSTString(node.right, depath + 1, sb); } // 生成路径字符串 private String generateDepthString (int depth) { StringBuilder sb = new StringBuilder(); for (int i = 0; i < depth; i++) { sb.append("-- "); } return sb.toString(); } }
Main
public class Main { public static void main(String[] args) { MyBinarySearchTree<Integer> mbst = new MyBinarySearchTree<Integer>(); int [] nums = {5, 3, 6, 8, 4, 2}; for (int i = 0; i < nums.length ; i++) { mbst.add(nums[i]); } ///////////////// // 5 // // / / // // 3 6 // // / / / // // 2 4 8 // ///////////////// // // 前序遍历 // mbst.preOrder(); // 5 3 2 4 6 8 // System.out.println(); // // // 中序遍历 // mbst.inOrder(); // 2 3 4 5 6 8 // System.out.println(); // // // 后序遍历 // mbst.postOrder(); // 2 4 3 8 6 5 // System.out.println(); // // // 前序遍历 非递归 // mbst.preOrderNonRecursive(); // 5 3 2 4 6 8 // System.out.println(); mbst.levelOrder(); // 5 3 6 2 4 8 System.out.println(); // // 输出 调试字符串 // System.out.println(mbst.toString()); } }
很多时候学习知识
对于二分搜索树来说删除一个节点相对来说是比较复杂的
删除二分搜索树的最小值和最大值
找到二分搜索树中的最大值和最小值是非常容易的
删除最大元素节点
删除最小元素节点
(class: MyBinarySearchTree, class: Main)
MyBinarySearchTree
import java.util.LinkedList; import java.util.Queue; import java.util.Stack; public class MyBinarySearchTree<E extends Comparable<E>> { private class Node { public E e; public Node left, right; public Node (E e) { this.e = e; left = null; right = null; } } private Node root; private int size; public MyBinarySearchTree () { root = null; size = 0; } public int getSize() { return size; } public boolean isEmpty () { return size == 0; } // 向二分搜索树中添加一个元素 e // 改进:直接调用add public void add (E e) { root = add(root, e); } // 向以node为根的二分搜索树中插入元素E,递归算法 // 改进:返回插入的新节点后二分搜索树的根 private Node add (Node node, E e) { // 处理最基本的问题 if (node == null) { size ++; return new Node(e); } // 空的二叉树也是叉树。 if (e.compareTo(node.e) < 0) { // 将处理后的结果赋值给node的左子树 node.left = add(node.left, e); } else if (e.compareTo(node.e) > 0) { // 将处理后的结果赋值给node的右子树 node.right = add(node.right, e); } // 如果相同 就什么都不做 // 最后返回这个node return node; } // 查询二分搜索数中是否包含某个元素 public boolean contains (E e) { return contains(root, e); } // 向以node为根的二分搜索树 进行查找 递归算法 private boolean contains (Node node, E e) { // 解决最基本的问题 也就是遍历完所有节点都没有找到 if (node == null) { return false; } // 如果 e 小于当前节点的e 则向左子树进发 if (e.compareTo(node.e) < 0) { return contains(node.left, e); } else if (e.compareTo(node.e) > 0) { // 如果 e 大于当前节点的e 则向右子树进发 return contains(node.right, e); } else { // 如果e 等于 当前节点 e 则直接返回true return true; } } // 二分搜索树的前序遍历 public void preOrder () { preOrder(root); } // 前序遍历以node为根的二分搜索树 递归算法 private void preOrder (Node node) { if (node == null) { return; } // 输出 System.out.println(node.e); preOrder(node.left); preOrder(node.right); // // 这种逻辑也是可以的 // if (node != null) { // // 输出 // System.out.println(node.e); // // preOrder(node.left); // preOrder(node.right); // } } // 二分搜索树的前序遍历 非递归算法 public void preOrderNonRecursive () { Stack<Node> stack = new Stack<Node>(); stack.push(root); Node node = null; while (!stack.isEmpty()) { node = stack.pop(); // // 第一种写法 不符合要求也可以压入栈,但是不符合要求的在出栈后不处理它 // if (node != null) { // System.out.println(node.e); // stack.push(node.right); // stack.push(node.left); // } // // 第二种写法 不符合要求也可以压入栈,但是不符合要求的在出栈后不处理它 // if (node == null) continue; // // System.out.println(node.e); // stack.push(node.right); // stack.push(node.left); // 写法三 不符合要求就不压入栈 System.out.println(node.e); if (node.right != null) { stack.push(node.right); } if (node.left != null) { stack.push(node.left); } } } // 二分搜索树的中序遍历 public void inOrder () { inOrder(root); } // 中序遍历以node为根的二分搜索树 递归算法 private void inOrder (Node node) { if (node == null) return; inOrder(node.left); System.out.println(node.e); inOrder(node.right); } // 二分搜索树的中序遍历 非递归算法 public void inOrderNonRecursive () { } // 二分搜索树的后序遍历 public void postOrder () { postOrder(root); } // 后续遍历以node为根的二分搜索树 递归算法 private void postOrder (Node node) { if (node == null) return; postOrder(node.left); postOrder(node.right); System.out.println(node.e); } // 二分搜索树的层序遍历 public void levelOrder () { // java中的Queue是一个接口,但是它有链表和队列的实现, // 所以你可以new 一个子类链表类来进行进行使用,可以达到同样的效果 Queue<Node> queue = new LinkedList<Node>(); queue.add(root); while (!queue.isEmpty()) { Node node = queue.remove(); System.out.println(node.e); if (node.left != null) { queue.add(node.left); } if (node.right != null) { queue.add(node.right); } } } // 寻找二分搜索树的最小值元素 public E minimum () { if (size == 0) { throw new IllegalArgumentException("BST is empty."); } return minimum(root).e; } // 返回以node为根的二分搜索树的最小值所在的节点 private Node minimum (Node node) { // 向左走再也走不动了,就返回这个节点。 if (node.left == null) return node; return minimum(node.left); } // 从二分搜索树种删除最小值所在节点,返回这个最小值 public E removeMin () { E result = minimum(); // removeMin(root); root = removeMin(root); return result; } // 删除掉以node为根的二分搜索树中的最小节点 // 返回删除节点后新的二分搜索树的根 private Node removeMin (Node node) { // if (node.left == null) { // node = node.right; // size --; // return node; // } // // return removeMin(node.left); if (node.left == null) { Node rightNode = node.right; node.right = null; size --; return rightNode; } node.left = removeMin(node.left); return node; } // 寻找二分搜索树的最大值元素 public E maximum () { if (size == 0) { throw new IllegalArgumentException("BST is empty."); } return maximum(root).e; } // 返回以node为根的二分搜索树的最大值所在的节点 private Node maximum (Node node) { // 向右走再也走不动了,就返回这个节点。 if (node.right == null) return node; return maximum(node.right); } // 从二分搜索树种删除最大值所在节点,返回这个最大值 public E removeMax () { E result = maximum(); root = removeMax(root); return result; } // 删除掉以node为根的二分搜索树中的最大节点 // 返回删除节点后新的二分搜索树的根 private Node removeMax (Node node) { if (node.right == null) { Node leftNode = node.left; node.left = null; size --; return leftNode; } node.right = removeMax(node.right); return node; } @Override public String toString () { StringBuilder sb = new StringBuilder(); generateBSTString(root, 0, sb); return sb.toString(); } // 生成以node为根节点,深度为depth的描述二叉树的字符串 private void generateBSTString (Node node, int depath, StringBuilder sb) { if (node == null) { sb.append(generateDepthString(depath) + "null/n"); return; } sb.append(generateDepthString(depath) + node.e + "/n"); generateBSTString(node.left, depath + 1, sb); generateBSTString(node.right, depath + 1, sb); } // 生成路径字符串 private String generateDepthString (int depth) { StringBuilder sb = new StringBuilder(); for (int i = 0; i < depth; i++) { sb.append("-- "); } return sb.toString(); } }
Main
import java.util.ArrayList; import java.util.Random; public class Main { public static void main(String[] args) { MyBinarySearchTree<Integer> mbst = new MyBinarySearchTree<Integer>(); Random random = new Random(); int n = 100; for (int i = 0; i < n; i++) { mbst.add(random.nextInt(Integer.MAX_VALUE)); } // 动态数组 ArrayList<Integer> arrayList = new ArrayList<Integer>(); while (!mbst.isEmpty()) { arrayList.add(mbst.removeMin()); // arrayList.add(mbst.removeMax()); } // 数组中就是从小到大排序的 System.out.println(arrayList); // 验证一下 for (int i = 1; i < arrayList.size() ; i++) { // 如果前面的数大于后面的数就报异常 if (arrayList.get(i - 1) > arrayList.get(i)) { // 如果前面的数小于后面的数就报异常 // if (arrayList.get(i - 1) < arrayList.get(i)) { throw new IllegalArgumentException("error."); } } System.out.println("removeMin test completed."); // System.out.println("removeMax test completed."); } }
在二分搜索树种删除最大值最小值的逻辑
删除二分搜索树上任意节点会发生的情况
对于二分搜索树来说
(class: MyBinarySearchTree, class: Main)
MyBinarySearchTree
import java.util.LinkedList; import java.util.Queue; import java.util.Stack; public class MyBinarySearchTree<E extends Comparable<E>> { private class Node { public E e; public Node left, right; public Node (E e) { this.e = e; left = null; right = null; } } private Node root; private int size; public MyBinarySearchTree () { root = null; size = 0; } public int getSize() { return size; } public boolean isEmpty () { return size == 0; } // 向二分搜索树中添加一个元素 e // 改进:直接调用add public void add (E e) { root = add(root, e); } // 向以node为根的二分搜索树中插入元素E,递归算法 // 改进:返回插入的新节点后二分搜索树的根 private Node add (Node node, E e) { // 处理最基本的问题 if (node == null) { size ++; return new Node(e); } // 空的二叉树也是叉树。 if (e.compareTo(node.e) < 0) { // 将处理后的结果赋值给node的左子树 node.left = add(node.left, e); } else if (e.compareTo(node.e) > 0) { // 将处理后的结果赋值给node的右子树 node.right = add(node.right, e); } // 如果相同 就什么都不做 // 最后返回这个node return node; } // 查询二分搜索数中是否包含某个元素 public boolean contains (E e) { return contains(root, e); } // 向以node为根的二分搜索树 进行查找 递归算法 private boolean contains (Node node, E e) { // 解决最基本的问题 也就是遍历完所有节点都没有找到 if (node == null) { return false; } // 如果 e 小于当前节点的e 则向左子树进发 if (e.compareTo(node.e) < 0) { return contains(node.left, e); } else if (e.compareTo(node.e) > 0) { // 如果 e 大于当前节点的e 则向右子树进发 return contains(node.right, e); } else { // 如果e 等于 当前节点 e 则直接返回true return true; } } // 二分搜索树的前序遍历 public void preOrder () { preOrder(root); } // 前序遍历以node为根的二分搜索树 递归算法 private void preOrder (Node node) { if (node == null) { return; } // 输出 System.out.println(node.e); preOrder(node.left); preOrder(node.right); // // 这种逻辑也是可以的 // if (node != null) { // // 输出 // System.out.println(node.e); // // preOrder(node.left); // preOrder(node.right); // } } // 二分搜索树的前序遍历 非递归算法 public void preOrderNonRecursive () { Stack<Node> stack = new Stack<Node>(); stack.push(root); Node node = null; while (!stack.isEmpty()) { node = stack.pop(); // // 第一种写法 不符合要求也可以压入栈,但是不符合要求的在出栈后不处理它 // if (node != null) { // System.out.println(node.e); // stack.push(node.right); // stack.push(node.left); // } // // 第二种写法 不符合要求也可以压入栈,但是不符合要求的在出栈后不处理它 // if (node == null) continue; // // System.out.println(node.e); // stack.push(node.right); // stack.push(node.left); // 写法三 不符合要求就不压入栈 System.out.println(node.e); if (node.right != null) { stack.push(node.right); } if (node.left != null) { stack.push(node.left); } } } // 二分搜索树的中序遍历 public void inOrder () { inOrder(root); } // 中序遍历以node为根的二分搜索树 递归算法 private void inOrder (Node node) { if (node == null) return; inOrder(node.left); System.out.println(node.e); inOrder(node.right); } // 二分搜索树的中序遍历 非递归算法 public void inOrderNonRecursive () { } // 二分搜索树的后序遍历 public void postOrder () { postOrder(root); } // 后续遍历以node为根的二分搜索树 递归算法 private void postOrder (Node node) { if (node == null) return; postOrder(node.left); postOrder(node.right); System.out.println(node.e); } // 二分搜索树的层序遍历 public void levelOrder () { // java中的Queue是一个接口,但是它有链表和队列的实现, // 所以你可以new 一个子类链表类来进行进行使用,可以达到同样的效果 Queue<Node> queue = new LinkedList<Node>(); queue.add(root); while (!queue.isEmpty()) { Node node = queue.remove(); System.out.println(node.e); if (node.left != null) { queue.add(node.left); } if (node.right != null) { queue.add(node.right); } } } // 寻找二分搜索树的最小值元素 public E minimum () { if (size == 0) { throw new IllegalArgumentException("BST is empty."); } return minimum(root).e; } // 返回以node为根的二分搜索树的最小值所在的节点 private Node minimum (Node node) { // 向左走再也走不动了,就返回这个节点。 if (node.left == null) return node; return minimum(node.left); } // 从二分搜索树种删除最小值所在节点,返回这个最小值 public E removeMin () { E result = minimum(); // removeMin(root); root = removeMin(root); return result; } // 删除掉以node为根的二分搜索树中的最小节点 // 返回删除节点后新的二分搜索树的根 private Node removeMin (Node node) { // if (node.left == null) { // node = node.right; // size --; // return node; // } // // return removeMin(node.left); if (node.left == null) { Node rightNode = node.right; node.right = null; size --; return rightNode; } node.left = removeMin(node.left); return node; } // 寻找二分搜索树的最大值元素 public E maximum () { if (size == 0) { throw new IllegalArgumentException("BST is empty."); } return maximum(root).e; } // 返回以node为根的二分搜索树的最大值所在的节点 private Node maximum (Node node) { // 向右走再也走不动了,就返回这个节点。 if (node.right == null) return node; return maximum(node.right); } // 从二分搜索树种删除最大值所在节点,返回这个最大值 public E removeMax () { E result = maximum(); root = removeMax(root); return result; } // 删除掉以node为根的二分搜索树中的最大节点 // 返回删除节点后新的二分搜索树的根 private Node removeMax (Node node) { if (node.right == null) { Node leftNode = node.left; node.left = null; size --; return leftNode; } node.right = removeMax(node.right); return node; } // 从二分搜索树中删除元素e的节点 public void remove (E e) { root = remove(root, e); } // 删除掉以node为根的二分搜索树中值为e的节点 递归算法 // 返回删除节点后新的二分搜索树的根 private Node remove(Node node, E e) { if (node == null) return null; if (e.compareTo(node.e) < 0) { node.left = remove(node.left, e); return node; } else if (e.compareTo(node.e) > 0) { node.right = remove(node.right, e); return node; } else { // e == node.e // 待删除的节点左子树为空 if (node.left == null) { Node rightNode = node.right; node.right = null; size --; return rightNode; } // 待删除的节点右子树为空 if (node.right == null) { Node leftNode = node.left; node.left = null; size --; return leftNode; } // 待删除的节点左右子树都不为空的情况 // 找到比待删除节点大的最小节点,即待删除节点右子树的最小节点 // 用这个节点顶替待删除节点的位置 Node successor = minimum(node.right); successor.right = removeMin(node.right); // 在removeMin这个操作中维护了一次size --,但是并没有删除节点 // 所以这里要进行一次size ++操作 size ++; successor.left = node.left; // 让node这个节点与当前这个二分搜索树脱离关系 node.left = node.right = null; // 维护一下size size --; return successor; } } @Override public String toString () { StringBuilder sb = new StringBuilder(); generateBSTString(root, 0, sb); return sb.toString(); } // 生成以node为根节点,深度为depth的描述二叉树的字符串 private void generateBSTString (Node node, int depath, StringBuilder sb) { if (node == null) { sb.append(generateDepthString(depath) + "null/n"); return; } sb.append(generateDepthString(depath) + node.e + "/n"); generateBSTString(node.left, depath + 1, sb); generateBSTString(node.right, depath + 1, sb); } // 生成路径字符串 private String generateDepthString (int depth) { StringBuilder sb = new StringBuilder(); for (int i = 0; i < depth; i++) { sb.append("-- "); } return sb.toString(); } }
Main
import java.util.ArrayList; import java.util.Random; public class Main { public static void main(String[] args) { MyBinarySearchTree<Integer> mbst = new MyBinarySearchTree<Integer>(); // 动态数组 ArrayList<Integer> arrayList = new ArrayList<Integer>(); Random random = new Random(); int n = 10; for (int i = 0; i < n; i++) { int value = random.nextInt(Integer.MAX_VALUE); mbst.add(value); arrayList.add(value); } // 输出二分搜索树 System.out.println(mbst.getSize()); // 输出数组中内容 System.out.println(arrayList); for (int i = 0; i < arrayList.size(); i++) { mbst.remove(arrayList.get(i)); } // 输出二分搜索树 System.out.println(mbst.getSize()); System.out.println("remove test completed."); } }
可以非常方便的拿到二分搜索树中最大值和最小值,
也因为这个顺序性也可以对它进行 floor 和 ceil 的操作,
相应的二分搜索树还可以实现 rank 和 select 方法,
root.size
维护 depth 的二分搜索树
支持重复元素的二分搜索树
还可以通过维护每一个节点的 count 变量来实现重复元素的二分搜索树,
count++ count--
在二分搜索树中相应的变种其实大多是在 node 中维护一些数据
相关的习题可以去 leetcode 中找到,
https://leetcode-cn.com/tag/tree/
其它