二叉树、栈、队列、链表的Java代码实现
2024-10-21 06:03:04
这是我的学习总结。
如有文章存在谬误，欢迎指出，有其他意见或者建议，也欢迎留言
二叉树链表
前序遍历：先访问根节点，然后访问左子树、右子树
中序遍历：先访问左子树，然后访问根节点、右子树
后序遍历：先访问左子树、右子树，然后访问根节点
二叉树
/**
* 二叉树
*
* @author ChenSS 2016/11/10
* @version 1.0
*/
public class BinaryTree {
// 根节点数据
int data;
// 左子树
BinaryTree left;
// 右子树
BinaryTree right;
public BinaryTree(int data) {
this.data = data;
left = null;
right = null;
}
/**
* 插入新的节点，以根节点为准，大的放右边，小的放左边
*
* @param root
* 根节点
* @param data
* 数据
*/
public void insert(BinaryTree root, int data) {
if (data > root.data) {
if (root.right == null) {
root.right = new BinaryTree(data);
} else {
this.insert(root.right, data);
}
} else {
if (root.left == null) {
root.left = new BinaryTree(data);
} else {
this.insert(root.left, data);
}
}
}
}二叉树遍历：
/**
* 二叉树遍历
*
* @author ChenSS 2016/11/10
* @version 1.0
*/
public class BinaryTreePreorder {
/**
* 先根遍历，优先输出根节点的值，然后遍历左子树，左子树为空，就遍历右子树
* 假设左子树不为空，输出左子树的根节点，继续对左子树的左右子树相同判断
*/
public static void preOrder(BinaryTree root) {
if (root == null)
return;
System.out.print(root.data + "-");
preOrder(root.left);
preOrder(root.right);
}
/**
* 中根遍历
*/
public static void inOrder(BinaryTree root) {
if (root == null)
return;
inOrder(root.left);
System.out.print(root.data + "-");
inOrder(root.right);
}
/**
* 后根遍历
*/
public static void postOrder(BinaryTree root) {
if (root == null)
return;
postOrder(root.left);
postOrder(root.right);
System.out.print(root.data + "-");
}
public static void main(String[] str) {
int[] array = { 12, 76, 35, 22, 16, 48, 90, 46, 9, 40 };
BinaryTree root = new BinaryTree(array[0]);
for (int i = 1; i < array.length; i++) {
root.insert(root, array[i]); // 向二叉树中插入数据
}
System.out.println("先根遍历：");
preOrder(root);
System.out.println();
System.out.println("中根遍历：");
inOrder(root);
System.out.println();
System.out.println("后根遍历：");
postOrder(root);
}
}
生成的二叉树如上，先序遍历的输出情况为：
12-9-76-35-22-16-48-46-40-90
如图：
1. 第一个根节点是12，打印12.
2. 12有左子树和右子树，先遍历左子树，左子树根节点是9，打印9.
3. 9没有子树，所以会去判断12的右子树，右子树的根节点是76，打印76.
4. 76左右子树都有,先遍历左子树，左子树的根节点是35，打印35.
打印22……
打印16……
5. 35的左子树遍历完了，遍历右子树，打印48……
栈
栈（Stack）是限制仅在表的一端进行插入和删除运算的线性表，是一种后进先出（LILO）的线性表。
栈的链表实现
/**
* 链表栈
*
* @author ChenSS 2016/11/10
* @version 1.0
*/
public class LinkedStack implements AbsStack {
private int count;
private Node top;
@Override
public void push(Object element) {
Node node = new Node(element);
node.setNext(top);
top = node;
count++;
}
@Override
public Object pop() {
if (isEmpty())
throw new NullPointerException("stack is null");
Object result = top.getElement();
top = top.getNext();
count--;
return result;
}
@Override
public boolean isEmpty() {
return size() == 0;
}
@Override
public int size() {
return count;
}
@Override
public Object peek() {
Object result = top.getElement();
return result;
}
/**
* 链表，每一个对象拥有下一个对象的引用
*
* @author ChenSS
*
*/
private class Node {
// 链表元素
private Object element;
// 指向下一个元素的指针(引用)
private Node next;
public Node(Object element) {
this.element = element;
}
public void setNext(Node top) {
this.next = top;
}
public Node getNext() {
return next;
}
public Object getElement() {
return element;
}
}
public static void main(String[] args) {
LinkedStack stack = new LinkedStack();
// 压栈10次
for (int i = 0; i < 10; i++) {
stack.push(i);
}
// 出栈5次
System.out.println("连续执行5次出栈操作");
for (int i = 0; i < 5; i++) {
System.out.println(stack.pop());
}
System.out.println("栈是否为空： " + stack.isEmpty());
System.out.println("栈的大小为： " + stack.size());
System.out.println("栈顶元素为： " + stack.peek());
}
}栈的数组实现
/**
* 数组栈
*
* @author ChenSS 2016/11/10
* @version 1.0
*/
public class ArrayStack implements AbsStack {
// 初始化一部分空间
private Object[] objs = new Object[16];
private int size = 0;
public void clear() {
for (int i = 0; i < size; i++)
objs[size] = null;
size = 0;
}
@Override
public String toString() {
StringBuilder sb = new StringBuilder();
sb.append("ArrayStack: [");
for (int i = 0; i < size; i++) {
sb.append(objs[i].toString());
if (i != size - 1) {
sb.append(", ");
}
}
sb.append("]");
return sb.toString();
}
@Override
public void push(Object element) {
if (size >= objs.length) {
resize();
}
objs[size++] = element;
}
@Override
public Object pop() {
if (size == 0) {
return null;
}
return objs[--size];
}
@Override
public Object peek() {
return objs[size];
}
@Override
public boolean isEmpty() {
return size == 0;
}
@Override
public int size() {
return size;
}
/**
* 数组扩容，一次加5个
*/
private void resize() {
objs = Arrays.copyOf(objs, objs.length + 5);
}
public static void main(String[] args) {
ArrayStack stack = new ArrayStack();
// 压栈10次
for (int i = 0; i < 10; i++) {
stack.push(i);
}
// 出栈5次
System.out.println("连续执行5次出栈操作");
for (int i = 0; i < 5; i++) {
System.out.println(stack.pop());
}
System.out.println("栈是否为空： " + stack.isEmpty());
System.out.println("栈的大小为： " + stack.size());
System.out.println("栈顶元素为： " + stack.peek());
System.out.println("元素为： " + stack.toString());
}
}队列
队尾入列队头出，采用的是一种先进先出（LILO）的方式进行数据处理
/**
* 队列
*
* @author ChenSS 2016/11/10
* @version 1.0
*/
public class Queue {
// 队列长度，由构造函数初始化
private int maxSize;
// 队列
private long[] queArray;
// 队头
private int front;
// 队尾
private int rear;
// 元素的个数
private int size;
public Queue(int s) {
maxSize = s;
queArray = new long[maxSize];
front = 0;
rear = -1;
size = 0;
}
// 进队列
public void add(long j) {
// 处理循环
if (rear == maxSize - 1)
rear = -1;
// 队尾指针加1,把值j加入队尾
queArray[++rear] = j;
size++;
}
// 取得队列的队头元素。
public long take() {
// 取值和修改队头指针
long temp = queArray[front++];
// 处理循环
if (front == maxSize)
front = 0;
size--;
return temp;
}
// 取得队列的队头元素。该运算与 remove()不同，后者要修改队头元素指针。
public long peek() {
return queArray[front];
}
public boolean isEmpty() {
return (size == 0);
}
// 判队列是否已满。若已满返回一个真值，否则返回一个假值。
public boolean isFull() {
return (size == maxSize);
}
// 返回队列的长度
public int size() {
return size;
}
public static void main(String[] args) {
// 队列有5个元素
Queue theQueue = new Queue(5);
// 添加4个元素
theQueue.add(10);
theQueue.add(20);
theQueue.add(30);
theQueue.add(40);
// 移除3个元素
theQueue.take();
theQueue.take();
theQueue.take();
// 添加4个元素
theQueue.add(50);
theQueue.add(60);
theQueue.add(70);
theQueue.add(80);
// 遍历队列并移除所有元素
while (!theQueue.isEmpty()) {
long n = theQueue.take();
System.out.print(n);
System.out.print(" ");
}
}
}链表
单向链表
在表头插入一个新的链接点，每个元素有下一个元素的指针（索引），根据当前元素，可以获取下一个元素。
双端链表
与单向链表的不同之处在保存有对最后一个链接点的引用(last)，实现了在链尾也可以插入数据的功能
双向链表
在过去的学习中，我们使用到了迭代器，迭代器有个向后遍历的功能，而双向链表，就增加了一个功能：往回遍历。每一个元素有两个指针，一个指向前一个元素，一个指向后一个元素。（参考：LinkedList对象）
LinkedList底层代码（LinkedList的元素）：
每一个元素包含两个指针（引用），一个指向前面一个元素，一个指向后面一个元素，也就是说，我们只要能得到其中任何一个元素，就可以遍历整个链表。
private static class Node<E> {
E item;
Node<E> next;
Node<E> prev;
Node(Node<E> prev, E element, Node<E> next) {
this.item = element;
this.next = next;
this.prev = prev;
}
}LinkedList逆向遍历功能展示：
/**
* LinkedList测试
*
* @author ChenSS 2016/11/10
* @version 1.0
*/
public class BinaryTreePlus {
public static void main(String[] args) {
LinkedList<String> list=new LinkedList<>();
list.addFirst("AAA");
list.addLast("BBB");
ListIterator<String> iterator=list.listIterator(list.size());
while(iterator.hasPrevious()){
System.out.println(iterator.previous());
}
}
}LinkedList代码实现：
/**
* 双向链表
*
* @author ChenSS 2016/11/10
* @version 1.0
*/
public class DoubleLists<T> {
private DNode<T> header;
private int listSize;
public DoubleLists() {
header = new DNode<T>();
listSize = 0;
}
private static class DNode<T> {
T nodeValue;
DNode<T> prev;
DNode<T> next;
public DNode() { // for header
nodeValue = null;
prev = this; // left
next = this; // right
}
public DNode(T item) {
nodeValue = item;
prev = this;
next = this;
}
}
public boolean isEmpty() {
return (header.prev == header || header.next == header);
}
public int size() {
return listSize;
}
private DNode<T> addBefore(DNode<T> curr, T item) {
DNode<T> newNode, prevNode;
newNode = new DNode<T>(item);
prevNode = curr.prev;
newNode.prev = prevNode;
newNode.next = curr;
prevNode.next = newNode;
curr.prev = newNode;
return newNode;
}
public boolean add(T item) {
addBefore(header, item);
listSize++;
return true;
}
public void addFirst(T item) {
addBefore(header.next, item);
listSize++;
}
public void addLast(T item) {
addBefore(header, item);
listSize++;
}
private void remove(DNode<T> curr) {
if (curr.next == curr)
return;
DNode<T> prevNode = curr.prev, nextNode = curr.next;
prevNode.next = nextNode;
nextNode.prev = prevNode;
}
public boolean remove(Object o) {
for (DNode<T> p = header.next; p != header; p = p.next) {
if (o.equals(p.nodeValue)) {
remove(p);
listSize--;
return true;
}
}
return false;
}
public void printList() {
for (DNode<T> p = header.next; p != header; p = p.next)
System.out.println(p.nodeValue);
}
private class MyIterator implements Iterator<T> {
public DNode<T> nextNode = header.next;
public DNode<T> lastReturned = header;
public boolean hasNext() {
return nextNode != header;
}
public T next() {
if (nextNode == header)
throw new NoSuchElementException("");
lastReturned = nextNode;
nextNode = nextNode.next;
return lastReturned.nodeValue;
}
public void remove() {
if (lastReturned == header)
throw new IllegalStateException("");
DoubleLists.this.remove(lastReturned);
lastReturned = header;
listSize--;
}
}
private class MyListIterator extends MyIterator implements ListIterator<T> {
private int nextIndex;
MyListIterator(int index) {
if (index < 0 || index > listSize)
throw new IndexOutOfBoundsException("");
if (index < (listSize >> 1)) {
nextNode = header.next;
for (nextIndex = 0; nextIndex < index; nextIndex++)
nextNode = nextNode.next;
} else {
nextNode = header;
for (nextIndex = listSize; nextIndex > index; nextIndex--)
nextNode = nextNode.prev;
}
}
public boolean hasPrevious() {
return nextIndex != 0;
// return nextNode.prev != header;
}
public T previous() {
if (nextIndex == 0)
throw new NoSuchElementException("no");
lastReturned = nextNode = nextNode.prev;
nextIndex--;
return lastReturned.nodeValue;
}
public void remove() {
if (lastReturned == header)
throw new IllegalStateException("");
DoubleLists.this.remove(lastReturned);
nextIndex--;
listSize--;
if (lastReturned == nextNode)
nextNode = nextNode.next;
lastReturned = header;
}
public void add(T item) {
DoubleLists.this.addBefore(nextNode, item);
nextIndex++;
listSize++;
lastReturned = header;
}
public void set(T item) {
if (lastReturned == header)
throw new IllegalStateException();
lastReturned.nodeValue = item;
}
public int nextIndex() {
return nextIndex;
}
public int previousIndex() {
return nextIndex - 1;
}
}
public Iterator<T> iterator() {
return new MyIterator();
}
public ListIterator<T> listIterator(int index) {
return new MyListIterator(index);
}
public static void main(String[] args) {
DoubleLists<String> t = new DoubleLists<String>();
t.add("A");
t.add("B");
t.remove("B");
t.addFirst("AA");
t.addLast("BB");
t.add("C");
t.add("D");
ListIterator<String> it = t.listIterator(t.size());
while (it.hasPrevious()) {
//指向位置前面的元素
System.out.println(it.previous());
}
}
}4种常见的排序
/**
* 排序算法
*
* @author ChenSS 2016/11/10
* @version 1.0
*/
public class SortUtil {
/**
* 选择排序,采用记角标的方式，记住数组中最小的那个数的角标，然后与开始的元素交换位置
*/
public static void selectSort(int[] a) {
int index;
int temp;
for (int i = 0; i < a.length - 1; i++) {
index = i;
for (int j = i + 1; j < a.length; j++) {
if (a[index] > a[j])
index = j;
}
if (index != i) {
temp = a[index];
a[index] = a[i];
a[i] = temp;
}
}
}
/**
* 快速排序，以一个数为基准（通常选第一个数），大数置于右边，小数置于左边，
* 此后以相同的算法对左边和右边这两组数进行排序，以此类推，
* 直至整个数组从小到大排列
*/
public static void quickSort(int[] a, int left, int right) {
if (left >= right)
return;
int temp = a[left];
int low = left;
int high = right;
while (low < high) {
while (low < high && a[high] >= temp)
high--;
a[low] = a[high];
while (low < high && a[low] <= temp)
low++;
a[high] = a[low];
}
a[low] = temp;
quickSort(a, left, low - 1);
quickSort(a, low + 1, right);
}
/**
* 冒泡排序
*/
public static void bubbleSort(int[] a) {
int temp;
for (int i = 0; i < a.length; i++) {
for (int j = 0; j < a.length - i - 1; j++) {
if (a[j] > a[j + 1]) {
temp = a[j];
a[j] = a[j + 1];
a[j + 1] = temp;
}
}
}
}
/**
* 插入排序，和选择排序类似，遍历取出最小的那个数，然后插入到第一个元素的位置，其它元素全部后移
*/
public static void insertSort(int a[]) {
for (int i = 1; i < a.length; i++) {
int key = a[i];
int index = i;
while (index > 0 && a[index - 1] > key) {
a[index] = a[index - 1];
index--;
}
a[index] = key;
}
}
/**
* 测试方法
*/
public static void print(int a[]) {
for (int i = 0; i < a.length; i++) {
System.out.print(a[i] + " ");
}
System.out.println();
}
public static void main(String[] args) {
int[] arr = { 7, 6, 5, 4, 2, 3, 9, 90, 4, 50 };
insertSort(arr);
print(arr);
}
}最新文章
- oracle触发器详解
- gitlab配置邮件通知功能操作记录
- 【USACO 2.3.5】控制公司
- 【用PS3手柄在安卓设备上玩游戏系列】谈安卓游戏对手柄的支持
- 【转】关于ios10中ATS的问题
- Struts2自定义拦截器Interceptor以及拦截器登录实例
- Jquery实现选项卡效果
- javaApplication中如何使用log4j
- 笔记11 在XML中声明切面（2）
- duilib 新增数据迁移界面
- Linux上的10个Touch命令实例
- k8s初始化搭建方法
- 经典中的品味：第一章 C++的Hello，World！
- ECO开放平台对接文档说明
- [leetcode]Minimum Window Substring @ Python
- appium 后台运行shell脚本
- Charles 从入门到精通 --转
- 要学习的UML图
- 基于Django的乐观锁与悲观锁解决订单并发问题的一点浅见
- @RestController和@Controller的差异
热门文章
- JS中apply和call的区别和用法
- Hibernate逆向代码问题
- Java常用类（一）之Object类详解
- Django(一)
- GoldenGate 复制进程报错"OGG-01296 Error mapping"，丢弃文件报错“Mapping problem with delete record (target format)”，且实际条目存在
- LINUX 笔记-free命令
- 对象转字典 iOS
- LeetCode 26. Remove Duplicates from Sorted Array （从有序序列里移除重复项）
- macOs升级到10.13.1Beta || JAVA升级到最新版之后PhpStorm菜单栏问题
- IIS下自定义错误页面配置的两种方式（亲测可行）--IIS服务器