头歌JAVA数据结构答案

头歌JAVA数据结构答案

一、Java数据结构-循环链表的设计与实现

第1关 单循环链表的实现—链表的添加、遍历

package step1;
/**
 * Created by sykus on 2018/1/15.
 */
public class MyCircleLinkedList {
    private Node head;//头结点, 不存数据
    private Node tail;//尾结点, 指向链表的最后一个节点
    private int size;
    public MyCircleLinkedList() {
        head = new Node(Integer.MIN_VALUE, null);
        head.next = head;
        tail = head;
        size = 0;
    }
    /**
     * 添加到链表尾部
     *
     * @param item
     */
    public void add(int item) {
        /********** Begin *********/
        Node node = new Node(item, tail.next);
        tail.next = node;
        tail = node;
        ++size;
        /********** End *********/
    }
    /**
     * 遍历链表并输出元素
     */
    public void output() {
        /********** Begin *********/
        Node p = head;
        while (p.next != head) {
            p = p.next;
            System.out.println(p.item);
        }
        /********** End *********/
    }
    public boolean isEmpty() {
        return head.next == head;
    }
    public int size() {
        return size;
    }
    //结点内部类
    private static class Node {
        int item;
        Node next;
        Node(int item, Node next) {
            this.item = item;
            this.next = next;
        }
    }
}

第2关 单循环链表的实现—链表的删除

package step2;
/**
 * Created by sykus on 2018/1/15.
 */
public class MyCircleLinkedList {
    private Node head;//头结点, 不存数据
    private Node tail;//尾结点, 指向链表的最后一个节点
    private int size;
    public MyCircleLinkedList() {
        head = new Node(Integer.MIN_VALUE, null);
        head.next = head;
        tail = head;
        size = 0;
    }
    /**
     * 添加到链表尾部
     *
     * @param item
     */
    public void add(int item) {
        Node node = new Node(item, tail.next);
        tail.next = node;
        tail = node;
        ++size;
    }
    /**
     * 遍历链表并输出元素
     */
    public void output() {
        Node p = head;
        while (p.next != head) {
            p = p.next;
            System.out.println(p.item);
        }
    }
    /**
     * 删除从头结点开始的第index个结点
     * index从0开始
     *
     * @param index
     * @return
     */
    public int remove(int index) {
        checkPosIndex(index);
        /********** Begin *********/
        Node f = head;
        while ((index--) > 0) {
            f = f.next;
        }
        Node del = f.next;
        if (del == tail) {//要删除的是尾结点
            tail = f;//使tail依然指向末尾结点
        }
        f.next = del.next;
        del.next = null;
        int oldVal = del.item;
        del = null;
        --size;
        return oldVal;
        /********** End *********/
    }
    public boolean isEmpty() {
        return head.next == head;
    }
    public int size() {
        return size;
    }
    private void checkPosIndex(int index) {
        if (index < 0 || index >= size) {
            throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size);
        }
    }
    //结点内部类
    private static class Node {
        int item;
        Node next;
        Node(int item, Node next) {
            this.item = item;
            this.next = next;
        }
    }
}

第3关 双向循环链表的实现—链表的插入

package step3;
/**
 * Created by sykus on 2018/1/15.
 */
public class MyDoubleLinkedList {
    private Node head;//头结点
    private Node tail;//指向链表的尾结点
    private int size;
    public MyDoubleLinkedList() {
        head = new Node(null, Integer.MIN_VALUE, null);
        head.next = head.prev = head;
        tail = head;
        size = 0;
    }
    /**
     * 添加元素到表尾
     *
     * @param item
     */
    public void add(int item) {
        /********** Begin *********/
        Node newNode = new Node(null, item, null);
        tail.next = newNode;
        newNode.prev = tail;
        newNode.next = head;
        head.prev = newNode;
        tail = newNode;
        ++size;
        /********** End *********/
    }
    /**
     * 打印双向链表
     *
     * @param flag true从左向右顺序打印, false从右向左顺序打印
     */
    public void printList(boolean flag) {
        Node f = head;
        if (flag) {//向右
            while (f.next != head) {
                f = f.next;
                System.out.print(f.item + " ");
            }
        } else {//向左
            while (f.prev != head) {
                f = f.prev;
                System.out.print(f.item + " ");
            }
        }
    }
    public int size() {
        return size;
    }
    //结点内部类
    private static class Node {
        int item;
        Node next;//直接后继引用
        Node prev;//直接前驱引用
        Node(Node prev, int item, Node next) {
            this.prev = prev;
            this.item = item;
            this.next = next;
        }
    }
}

第4关：双向循环链表的实现—链表的删除

package step4;
/**
 * Created by sykus on 2018/1/15.
 */
public class MyDoubleLinkedList {
    private Node head;//头结点
    private Node tail;//指向链表的尾结点
    private int size;
    public MyDoubleLinkedList() {
        head = new Node(null, Integer.MIN_VALUE, null);
        head.next = head.prev = head;
        tail = head;
        size = 0;
    }
    /**
     * 添加元素到表尾
     *
     * @param item
     */
    public void add(int item) {
        Node newNode = new Node(null, item, null);
        tail.next = newNode;
        newNode.prev = tail;
        newNode.next = head;
        head.prev = newNode;
        tail = newNode;
        ++size;
    }
    /**
     * 删除指定位置index出的结点，并返回其值
     *
     * @param index
     * @return
     */
    public int remove(int index) {
        checkPosIndex(index);//
        /********** Begin *********/
        Node p = head.next;
        while ((index--) > 0) {
            p = p.next;
        }
        if (p == tail) {
            tail = p.prev;
        }
        p.prev.next = p.next;
        p.next.prev = p.prev;
        int val = p.item;
        p = null;
        --size;
        return val;
        /********** End *********/
    }
    /**
     * 打印双向链表
     *
     * @param flag true从左向右顺序打印, false从右向左顺序打印
     */
    public void printList(boolean flag) {
        Node f = head;
        if (flag) {//向右
            while (f.next != head) {
                f = f.next;
                System.out.print(f.item + " ");
            }
        } else {//向左
            while (f.prev != head) {
                f = f.prev;
                System.out.print(f.item + " ");
            }
        }
    }
    public int size() {
        return size;
    }
    private void checkPosIndex(int index) {
        if (index < 0 || index >= size) {
            throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size);
        }
    }
    //结点内部类
    private static class Node {
        int item;
        Node next;//直接后继引用
        Node prev;//直接前驱引用
        Node(Node prev, int item, Node next) {
            this.prev = prev;
            this.item = item;
            this.next = next;
        }
    }
}

二、Java数据结构-线性表的设计与实现

第1关：顺序表的实现之增删功能

package step1;
/**
 * Created by zengpeng on 2017/12/25.
 */
public class MyArrayList {
    private int[] elements;//元素
    private int size;//List中当前的元素个数
    public MyArrayList() {
        this(1);//List默认大小为1
    }
    /**
     * 按指定大小capacity构造List
     *
     * @param capacity List初始化时的大小
     */
    public MyArrayList(int capacity) {
        elements = new int[capacity];
        size = 0;
    }
    /**
     * 返回List中元素的个数
     *
     * @return
     */
    public int size() {
        return size;
    }
    /**
     * 添加一个元素到末尾
     *
     * @param item
     */
    public void Add(int item) {
        int len = elements.length;
        if (size == len - 1) {
            resize(2 * len);
        }
        /********** Begin *********/
        elements[size++] = item;
        /********** End *********/
    }
    /**
     * 添加一个元素到指定位置index
     *
     * @param index
     * @param item
     */
    public void Add(int index, int item) {
        validateRangeForAdd(index);
        int len = elements.length;
        if (size == len - 1) {
            resize(2 * len);
        }
        /********** Begin *********/
        for (int i = size; i > index; i--) {
            elements[i] = elements[i - 1];
        }
        elements[index] = item;
        size++;
        /********** End *********/
    }
    /**
     * 删除指定位置index的元素,并返回被删除的元素
     *
     * @param index
     * @return
     */
    public int remove(int index) {
        validateRange(index);
        /********** Begin *********/
        int oldVal=elements[index];
        for (int i = index; i < size - 1; i++) {
            elements[i] = elements[i + 1];
        }
        --size;
        return oldVal;
        /********** End *********/
    }
    /**
     * 校验索引范围
     *
     * @param index
     */
    private void validateRange(int index) {
        if (index >= size || index < 0) {
            throw new ArrayIndexOutOfBoundsException("索引越界了哦！Index: " + index + ", Size: " + size);
        }
    }
    /**
     * 校验索引范围
     *
     * @param index
     */
    private void validateRangeForAdd(int index) {
        if (index > size || index < 0)
            throw new IndexOutOfBoundsException("索引越界了哦！Index: " + index + ", Size: " + size);
    }
    /**
     * 动态扩展数组大小
     *
     * @param capacity
     */
    private void resize(int capacity) {
        assert capacity > size;
        int[] tmp = new int[capacity];
        for (int i = 0; i < size; i++) {
            tmp[i] = elements[i];
        }
        elements = tmp;
    }
}

第2关： 顺序表的实现之查询功能

package step2;
/**
 * Created by zengpeng on 2017/12/25.
 */
public class MyArrayList {
    private int[] elements;//元素
    private int size;//List中当前的元素个数
    public MyArrayList() {
        this(1);//List默认大小为1
    }
    /**
     * 按指定大小capacity构造List
     *
     * @param capacity List初始化时的大小
     */
    public MyArrayList(int capacity) {
        elements = new int[capacity];
        size = 0;
    }
    /**
     * 返回List中元素的个数
     *
     * @return
     */
    public int size() {
        return size;
    }
    /**
     * 添加一个元素到末尾
     *
     * @param item
     */
    public void Add(int item) {
        int len = elements.length;
        if (size == len - 1) {
            resize(2 * len);
        }
        elements[size++] = item;
    }
    /**
     * 添加一个元素到指定位置index
     *
     * @param index
     * @param item
     */
    public void Add(int index, int item) {
        validateRangeForAdd(index);
        int len = elements.length;
        if (size == len - 1) {
            resize(2 * len);
        }
        for (int i = size; i > index; i--) {
            elements[i] = elements[i - 1];
        }
        elements[index] = item;
        size++;
    }
    /**
     * 删除指定位置index的元素,并返回被删除的元素
     *
     * @param index
     * @return 被删除的元素
     */
    public int remove(int index) {
        validateRange(index);
        int oldVal = elements[index];
        for (int i = index; i < size - 1; i++) {
            elements[i] = elements[i + 1];
        }
        --size;
        return oldVal;
    }
    /**
     * 返回表中下标为index的元素
     * @param index 下标
     * @return
     */
    public int get(int index) {
        validateRange(index);
        /********** Begin *********/
        return elements[index];
        /********** End *********/
    }
    /**
     * 校验索引范围
     *
     * @param index
     */
    private void validateRange(int index) {
        if (index >= size || index < 0) {
            throw new ArrayIndexOutOfBoundsException("索引越界了哦！Index: " + index + ", Size: " + size);
        }
    }
    /**
     * 校验索引范围
     *
     * @param index
     */
    private void validateRangeForAdd(int index) {
        if (index > size || index < 0)
            throw new IndexOutOfBoundsException("索引越界了哦！Index: " + index + ", Size: " + size);
    }
    /**
     * 动态扩展数组大小
     *
     * @param capacity
     */
    private void resize(int capacity) {
        assert capacity > size;
        int[] tmp = new int[capacity];
        for (int i = 0; i < size; i++) {
            tmp[i] = elements[i];
        }
        elements = tmp;
    }
}

第3关：单链表的实现之增删功能

package step3;
/**
 * Created by zengpeng on 2017/12/25.
 */
public class MyLinkedList {
    private Node first;//头结点，不存数据
    private Node last;//指向链表的最后一个节点
    private int size;
    public MyLinkedList() {
        size = 0;
        first = new Node(0, null);
        last = null;
    }
    /**
     * 添加到链表尾部
     *
     * @param item
     */
    public void add(int item) {
        /********** Begin *********/
        final Node l = last;
        final Node node = new Node(item, null);
        last = node;
        if (first.next == null) {//首次添加
            first.next = node;
        } else {
            l.next = node;
        }
        ++size;
        /********** End *********/
    }
    /**
     * 添加数据item到指定位置index
     * index从0开始
     * @param index
     * @param item
     */
    public void add(int index, int item) {
        checkPosIndex(index);
        /********** Begin *********/
        int n = index;
        Node l = first;
        while ((n--) > 0) {
            l = l.next;
        }
        final Node node = new Node(item, null);
        if (null == first.next) {//首次添加
            last = node;
        }
        node.next = l.next;
        l.next = node;
        ++size;
        /********** End *********/
    }
    /**
     * 删除指定位置index处的元素并返回, index从0开始
     * @param index
     * @return
     */
    public int remove(int index) {
        checkPosIndex(index);
        /********** Begin *********/
        Node f = first;
        while ((index--) > 0) {
            f = f.next;
        }
        Node del = f.next;
        if (del == last) {//删除最后一个元素
            last = f;
        }
        f.next = del.next;
        del.next = null;
        int oldVal = del.item;
        del = null;
        --size;
        return oldVal;
        /********** End *********/
    }
    public int size() {
        return size;
    }
    private void checkPosIndex(int index) {
        if (index < 0 || index > size) {
            throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size);
        }
    }
    //结点内部类
    private static class Node {
        int item;
        Node next;
        Node(int item, Node next) {
            this.item = item;
            this.next = next;
        }
    }
}

第4关：单链表的实现之查询功能

package step4;
/**
 * Created by zengpeng on 2017/12/25.
 */
public class MyLinkedList {
    private Node first;//头结点，不存数据
    private Node last;//指向链表的最后一个节点
    private int size;
    public MyLinkedList() {
        size = 0;
        first = new Node(0, null);
        last = null;
    }
    /**
     * 添加到链表尾部
     *
     * @param item
     */
    public void add(int item) {
        final Node l = last;
        final Node node = new Node(item, null);
        last = node;
        if (first.next == null) {//首次添加
            first.next = node;
        } else {
            l.next = node;
        }
        ++size;
    }
    /**
     * 添加数据item到指定位置index
     * index从0开始
     * @param index
     * @param item
     */
    public void add(int index, int item) {
        checkPosIndex(index);
        int n = index;
        Node l = first;
        while ((n--) > 0) {
            l = l.next;
        }
        final Node node = new Node(item, null);
        if (null == first.next) {//首次添加
            last = node;
        }
        node.next = l.next;
        l.next = node;
        ++size;
    }
    /**
     * 删除指定位置index处的元素并返回, index从0开始
     * @param index
     * @return
     */
    public int remove(int index) {
        checkPosIndex(index);
        Node f = first;
        while ((index--) > 0) {
            f = f.next;
        }
        Node del = f.next;
        if (del == last) {//删除最后一个元素
            last = f;
        }
        f.next = del.next;
        del.next = null;
        int oldVal = del.item;
        del = null;
        --size;
        return oldVal;
    }
    /**
     * 获取链表中第index个元素
     * @param index
     * @return
     */
    public int get(int index) {
        checkPosIndex(index);
        /********** Begin *********/
        Node f = first.next;
        while ((index--) > 0) {
            f = f.next;
        }
        int val = f.item;
        return val;
        /********** End *********/
    }
    public int size() {
        return size;
    }
    private void checkPosIndex(int index) {
        if (index < 0 || index > size) {
            throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size);
        }
    }
    //结点内部类
    private static class Node {
        int item;
        Node next;
        Node(int item, Node next) {
            this.item = item;
            this.next = next;
        }
    }
    }

三、Java 数据结构之栈、队列

第1关：实现基于数组的栈

package step1;
import java.util.NoSuchElementException;
/**
 * Created by sykus on 2018/1/26.
 */
public class MyStack<T> {
    private T[] S;
    private int top;//栈顶元素下标，初始为-1
    public MyStack() {
        this(1);
    }
    public MyStack(int capacity) {
        S = (T[]) new Object[capacity];
        top = -1;
    }
    /**
     * 入栈操作，把item压入栈中
     *
     * @param item
     */
    public void push(T item) {
        int len = S.length;
        if (top == len - 1) {
            resize(2 * len);
        }
        /********** Begin *********/
        S[++top] = item;
        /********** End *********/
    }
    /**
     * 返回栈顶元素并从栈中移除
     *
     * @return
     */
    public T pop() {
        if (isEmpty()) {
            throw new NoSuchElementException("栈为空！");
        }
        /********** Begin *********/
        T val = S[top--];
        return val;
        /********** End *********/
    }
    /**
     * 判断栈是否为空
     *
     * @return
     */
    public boolean isEmpty() {
        if (top < 0)
            return true;
        else
            return false;
    }
    /**
     * 动态扩展数组大小
     *
     * @param capacity
     */
    private void resize(int capacity) {
        assert capacity > top;
        T[] tmp = (T[]) new Object[capacity];
        for (int i = 0; i <= top; i++) {
            tmp[i] = S[i];
        }
        S = tmp;
    }
}

第2关：实现基于链表的栈

package step2;
import java.util.NoSuchElementException;
/**
 * Created by sykus on 2017/12/29.
 */
public class MyStack<E> {
    private Node<E> head;//头结点
    private Node<E> top;//栈顶
    private int size;//栈中元素个数
    public MyStack() {
        head = new Node<E>();
        head.next = null;
        top = null;//栈顶初始化为null
        size = 0;
    }
    /**
     * 把item压入栈中
     *
     * @param item
     */
    public void push(E item) {
        /********** Begin *********/
        Node<E> newNode = new Node<E>();
        newNode.item = item;
        newNode.next = head.next;
        head.next = newNode;
        top = newNode;
        ++size;
        /********** End *********/
    }
    /**
     * 返回它栈顶元素并删除
     */
    public E pop() {
        if (isEmpty())
            throw new NoSuchElementException("栈为空！");
        /********** Begin *********/
        Node<E> node = top;
        top = top.next;
        head.next = top;
        node.next = null;
        --size;
        return node.item;
        /********** End *********/
    }
    /**
     * 返回栈中元素个数
     *
     * @return
     */
    public int size() {
        return size;
    }
    /**
     * 判断一个栈是否为空
     *
     * @return
     */
    public boolean isEmpty() {
        return (null == head);
    }
    //链表结点内部类
    private static class Node<E> {
        private E item;
        private Node<E> next;
    }
}

第3关：基于数组的队列

package step3;
/**
 * Created by zengpeng on 2018/1/30.
 */
public class MyQueue<T> {
    private T[] Q;
    private int head;
    private int tail;
    private int size;
    public MyQueue() {
        this(1);
    }
    public MyQueue(int capacity) {
        Q = (T[]) new Object[capacity];
        size = 0;
        head = tail = 0;
    }
    /**
     * 入队操作
     *
     * @param item
     */
    public void enqueue(T item) {
        /********** Begin *********/
        Q[tail] = item;
        tail = (tail + 1) % Q.length;
        ++size;
        /********** End *********/
    }
    /**
     * 出队操作
     *
     * @return
     */
    public T dequeue() {
        /********** Begin *********/
        T val = Q[head];
        head = (head + 1) % Q.length;
        --size;
        return val;
        /********** End *********/
    }
    /**
     * 判断队列是否为空
     * @return
     */
    public boolean isEmpty() {
        return (head == tail) && (size < Q.length);
    }
    public int size() {
        return size;
    }
}

第4关：基于链表的队列

package step4;
import java.util.NoSuchElementException;
/**
 * Created by sykus on 2017/12/29.
 */
public class MyQueue<T> {
    private Node<T> head;// 头结点，不存数据
    private Node<T> front;//指向队头结点
    private Node<T> tail;//指向队尾结点
    private int size;
    public MyQueue() {
        head = new Node<T>();
        front = tail = null;
        size = 0;
    }
    /**
     * 入队
     *
     * @param item
     */
    public void enqueue(T item) {
        /********** Begin *********/
        Node<T> oldTail = tail;
        Node<T> newNode = new Node<T>();
        newNode.item = item;
        newNode.next = null;
        if (null == front) {//空队列
            head.next = newNode;
            front = newNode;
        } else {
            oldTail.next = newNode;
        }
        tail = newNode;
        ++size;
        /********** End *********/
    }
    /**
     * 出队
     *
     * @return
     */
    public T dequeue() {
        if (isEmpty())
            throw new NoSuchElementException("队列为空！");
        /********** Begin *********/
        T val = front.item;
        head.next = front.next;
        front.next = null;
        front = head.next;//此时队头为后继结点
        --size;
        if (null == head.next) {//出队的是队列中的最后一个元素
            front = tail = null;
        }
        return val;
        /********** End *********/
    }
    /**
     * 返回队列中元素数量
     *
     * @return
     */
    public int size() {
        return size;
    }
    /**
     * 判断一个队列是否为空
     *
     * @return
     */
    public boolean isEmpty() {
        return (front == null);
    }
    /**
     * 链表结点内部类
     */
    private static class Node<E> {
        private E item;
        private Node<E> next;
    }
}

四、Java 数据结构之二叉搜索树

第1关：二叉搜索树的介绍与构建

package step1;
/**
 * Created by zengpeng on 2018/3/3.
 */
public class BSTree {
    private TreeNode root;//根结点
    public BSTree() {
        root = null;
    }
    /**
     * 向树root中插入key
     *
     * @param key 要插入的值
     */
    public void insert(int key) {
        /********** Begin *********/
        TreeNode x = root;
        TreeNode p = null;//始终指向x的父结点
        while (x != null) {
            p = x;
            if (key < x.item) {
                x = x.leftChild;
            } else {
                x = x.rightChild;
            }
        }
        if (null == p) {//空树
            root = new TreeNode(key);
        } else if (key < p.item) {
            p.leftChild = new TreeNode(key);
        } else {
            p.rightChild = new TreeNode(key);
        }
        /********** End *********/
    }
    /**
     * 前序遍历
     */
    public void preOrder() {
        preOrder(root);
    }
    /**
     * 中序遍历
     */
    public void inOrder() {
        inOrder(root);
    }
    /**
     * 后序遍历
     */
    public void postOrder(){
        postOrder(root);
    }
    private void preOrder(TreeNode node) {
        if (node != null) {
            System.out.print(node.item + " ");
            preOrder(node.leftChild);
            preOrder(node.rightChild);
        }
    }
    private void inOrder(TreeNode node) {
        if (node != null) {
            inOrder(node.leftChild);
            System.out.print(node.item + " ");
            inOrder(node.rightChild);
        }
    }
    private void postOrder(TreeNode node) {
        if (node != null) {
            postOrder(node.leftChild);
            postOrder(node.rightChild);
            System.out.print(node.item + " ");
        }
    }
    public static class TreeNode {
        private TreeNode leftChild;
        private TreeNode rightChild;
        private int item;
        public TreeNode(int item) {
            this(null, null, item);
        }
        public TreeNode(TreeNode leftChild, TreeNode rightChild, int item) {
            this.leftChild = leftChild;
            this.rightChild = rightChild;
            this.item = item;
        }
    }
}

第2关：二叉搜索树的删除

package step2;
/**
 * Created by zengpeng on 2018/3/14.
 */
public class BSTree {
    private TreeNode root;//根结点
    public BSTree() {
        root = null;
    }
    /**
     * 向树root中插入a
     *
     * @param key 要插入的值
     */
    public void insert(int key) {
        TreeNode x = root;
        TreeNode p = null;//始终指向x的父结点
        while (x != null) {
            p = x;
            if (key < x.item) {
                x = x.leftChild;
            } else {
                x = x.rightChild;
            }
        }
        if (null == p) {//空树
            root = new TreeNode(key);
        } else if (key < p.item) {
            p.leftChild = new TreeNode(key);
        } else {
            p.rightChild = new TreeNode(key);
        }
    }
    /**
     * 在树root中删除结点key
     *
     * @param key
     * @return
     */
    public void delete(int key) {
        root = delete(root, key);
    }
    private TreeNode delete(TreeNode x, int key) {
        /********** Begin *********/
        if (x == null) {
            return null;
        }
        if (key < x.item) {
            x.leftChild = delete(x.leftChild, key);
        } else if (key > x.item) {
            x.rightChild = delete(x.rightChild, key);
        } else {
            if (x.leftChild == null) return x.rightChild;
            if (x.rightChild == null) return x.leftChild;
            TreeNode t = x;
            x = min(t.rightChild);
            x.rightChild = deleteMin(t.rightChild);
            x.leftChild = t.leftChild;
        }
        return x;
        /********** End *********/
    }
    /**
     * 删除树x中的最小结点
     *
     * @param x
     * @return
     */
    private TreeNode deleteMin(TreeNode x) {
        if (x.leftChild == null) return x.rightChild;
        x.leftChild = deleteMin(x.leftChild);
        return x;
    }
    /**
     * 查找树x中的最小结点
     *
     * @param x
     * @return
     */
    private TreeNode min(TreeNode x) {
        TreeNode p = x;
        while (p.leftChild != null) {
            p = p.leftChild;
        }
        return p;
    }
    public void preOrder() {
        preOrder(root);
    }
    private void preOrder(TreeNode node) {
        if (node != null) {
            System.out.print(node.item + " ");
            preOrder(node.leftChild);
            preOrder(node.rightChild);
        }
    }
    public void inOrder() {
        inOrder(root);
    }
    private void inOrder(TreeNode node) {
        if (node != null) {
            inOrder(node.leftChild);
            System.out.print(node.item + " ");
            inOrder(node.rightChild);
        }
    }
    public void postOrder() {
        postOrder(root);
    }
    private void postOrder(TreeNode node) {
        if (node != null) {
            postOrder(node.leftChild);
            postOrder(node.rightChild);
            System.out.print(node.item + " ");
        }
    }
    public static class TreeNode {
        private TreeNode leftChild;
        private TreeNode rightChild;
        private int item;
        public TreeNode(int item) {
            this(null, null, item);
        }
        public TreeNode(TreeNode leftChild, TreeNode rightChild, int item) {
            this.leftChild = leftChild;
            this.rightChild = rightChild;
            this.item = item;
        }
    }
}

第3关：二叉搜索树的查找

package step3;
/**
 * Created by zengpeng on 2018/3/14.
 */
public class BSTree {
    private TreeNode root;//根结点
    public BSTree() {
        root = null;
    }
    /**
     * 向树root中插入a
     *
     * @param key    要插入的值
     */
    public void insert(int key) {
        TreeNode x = root;
        TreeNode p = null;//始终指向x的父结点
        while (x != null) {
            p = x;
            if (key < x.item) {
                x = x.leftChild;
            } else {
                x = x.rightChild;
            }
        }
        if (null == p) {//空树
            root = new TreeNode(key);
        } else if (key < p.item) {
            p.leftChild = new TreeNode(key);
        } else {
            p.rightChild = new TreeNode(key);
        }
    }
    /**
     * 判断树root中是否包含key，包含则返回true，不包含返回false
     *
     * @param key
     * @return
     */
    public boolean search(int key) {
        /********** Begin *********/
        TreeNode p = root;
        while (p != null && key != p.item) {
            if (key < p.item) {
                p = p.leftChild;
            } else {
                p = p.rightChild;
            }
        }
        if (p == null) {
            return false;
        } else {
            return true;
        }
        /********** End *********/
    }
    /**
     * 在树root中删除结点key
     *
     * @param key
     * @return
     */
    public void delete(int key) {
        root = delete(root, key);
    }
    private TreeNode delete(TreeNode x, int key) {
        if (x == null) {
            return null;
        }
        if (key < x.item) {
            x.leftChild = delete(x.leftChild, key);
        } else if (key > x.item) {
            x.rightChild = delete(x.rightChild, key);
        } else {
            if (x.leftChild == null) return x.rightChild;
            if (x.rightChild == null) return x.leftChild;
            TreeNode t = x;
            x = min(t.rightChild);
            x.rightChild = deleteMin(t.rightChild);
            x.leftChild = t.leftChild;
        }
        return x;
    }
    /**
     * 删除树x中的最小结点
     * @param x
     * @return
     */
    private TreeNode deleteMin(TreeNode x) {
        if (x.leftChild == null) return x.rightChild;
        x.leftChild = deleteMin(x.leftChild);
        return x;
    }
    /**
     * 查找树x中的最小结点
     *
     * @param x
     * @return
     */
    private TreeNode min(TreeNode x) {
        TreeNode p = x;
        while (p.leftChild != null) {
            p = p.leftChild;
        }
        return p;
    }
    public void preOrder() {
        preOrder(root);
    }
    public void inOrder() {
        inOrder(root);
    }
    public void postOrder() {
        postOrder(root);
    }
    private void preOrder(TreeNode node) {
        if (node != null) {
            System.out.print(node.item + " ");
            preOrder(node.leftChild);
            preOrder(node.rightChild);
        }
    }
    private void inOrder(TreeNode node) {
        if (node != null) {
            inOrder(node.leftChild);
            System.out.print(node.item + " ");
            inOrder(node.rightChild);
        }
    }
    private void postOrder(TreeNode node) {
        if (node != null) {
            postOrder(node.leftChild);
            postOrder(node.rightChild);
            System.out.print(node.item + " ");
        }
    }
    public static class TreeNode {
        private TreeNode leftChild;
        private TreeNode rightChild;
        private int item;
        public TreeNode(int item) {
            this(null, null, item);
        }
        public TreeNode(TreeNode leftChild, TreeNode rightChild, int item) {
            this.leftChild = leftChild;
            this.rightChild = rightChild;
            this.item = item;
        }
    }
}

五、Java 数据结构之二叉树
第1关：二叉树的实现之前序遍历

package step1;
/**
 * Created by zengpeng on 2018/2/9.
 */
public class BinaryTree {
    private TreeNode root;//根节点
    public BinaryTree() {
        root = null;
    }
    public void preOrder(TreeNode root) {
        /********** Begin *********/
        if (root == null) {
            return;
        }
        System.out.println(root.item);
        preOrder(root.leftChild);
        preOrder(root.rightChild);
        /********** End *********/
    }
    /**
     * 以数组arr从左至右构建二叉树
     *
     * @param arr
     * @param n
     * @return
     */
    public TreeNode createTree(int arr[]) {
        TreeNode tmp[] = new TreeNode[arr.length + 1];
        for (int k = 1; k <= arr.length; k++) {
            TreeNode node = new TreeNode(arr[k - 1]);
            tmp[k] = node;
            if (k == 1) {
                root = node;
            } else {
                int j = k / 2;
                if (k % 2 == 0) {
                    tmp[j].leftChild = node;
                } else {
                    tmp[j].rightChild = node;
                }
            }
        }
        return root;
    }
    public static class TreeNode {
        private TreeNode leftChild;
        private TreeNode rightChild;
        private int item;
        public TreeNode(int item) {
            this(null, null, item);
        }
        public TreeNode(TreeNode leftChild, TreeNode rightChild, int item) {
            this.leftChild = leftChild;
            this.rightChild = rightChild;
            this.item = item;
        }
    }
}

第2关：二叉树的实现之中序遍历

package step2;
/**
 * Created by zengpeng on 2018/2/12.
 */
public class BinaryTree {
    private TreeNode root;//根节点
    public BinaryTree() {
        root = null;
    }
    public void inOrder(TreeNode root) {
        /********** Begin *********/
        if (root == null) {
            return;
        }
        inOrder(root.leftChild);
        System.out.println(root.item);
        inOrder(root.rightChild);
        /********** End *********/
    }
    /**
     * 根据二叉树的性质，以数组arr从左至右构建一颗满二叉树
     *
     * @param arr
     * @param n
     * @return
     */
    public TreeNode createTree(int arr[]) {
        TreeNode tmp[] = new TreeNode[arr.length + 1];
        for (int k = 1; k <= arr.length; k++) {
            TreeNode node = new TreeNode(arr[k - 1]);
            tmp[k] = node;
            if (k == 1) {
                root = node;
            } else {
                int j = k / 2;
                if (k % 2 == 0) {
                    tmp[j].leftChild = node;
                } else {
                    tmp[j].rightChild = node;
                }
            }
        }
        return root;
    }
    public static class TreeNode {
        private TreeNode leftChild;
        private TreeNode rightChild;
        private int item;
        public TreeNode(int item) {
            this(null, null, item);
        }
        public TreeNode(TreeNode leftChild, TreeNode rightChild, int item) {
            this.leftChild = leftChild;
            this.rightChild = rightChild;
            this.item = item;
        }
    }
}

第3关 二叉树的实现之后序遍历

package step3;
/**
 * Created by zengpeng on 2018/2/12.
 */
public class BinaryTree {
    private TreeNode root;//根节点
    public BinaryTree() {
        root = null;
    }
    public void postOrder(TreeNode root) {
        /********** Begin *********/
        if (root == null) {
            return;
        }
        postOrder(root.leftChild);
        postOrder(root.rightChild);
        System.out.println(root.item);
        /********** End *********/
    }
    /**
     * 根据二叉树的性质，以数组arr从左至右构建一颗满二叉树
     *
     * @param arr
     * @param n
     * @return
     */
    public TreeNode createTree(int arr[]) {
        TreeNode tmp[] = new TreeNode[arr.length + 1];
        for (int k = 1; k <= arr.length; k++) {
            TreeNode node = new TreeNode(arr[k - 1]);
            tmp[k] = node;
            if (k == 1) {
                root = node;
            } else {
                int j = k / 2;
                if (k % 2 == 0) {
                    tmp[j].leftChild = node;
                } else {
                    tmp[j].rightChild = node;
                }
            }
        }
        return root;
    }
    public static class TreeNode {
        private TreeNode leftChild;
        private TreeNode rightChild;
        private int item;
        public TreeNode(int item) {
            this(null, null, item);
        }
        public TreeNode(TreeNode leftChild, TreeNode rightChild, int item) {
            this.leftChild = leftChild;
            this.rightChild = rightChild;
            this.item = item;
        }
    }
}

六、Java 数据结构之排序

第1关：选择排序

package step1;
/**
 * Created by sykus on 2018/3/20.
 */
public class SelectionSort {
    /**
     * 选择排序
     *
     * @param arr
     */
    public static void sort(int arr[]) {
        /********** Begin *********/
        for (int i = 0; i < arr.length-1; i++) {
            for (int j = i + 1; j < arr.length; j++) {
                if (arr[j] < arr[i]) {
                    int tmp = arr[i];
                    arr[i] = arr[j];
                    arr[j] = tmp;
                }
            }
            print(arr);
        }
        /********** End *********/
    }
    private static void print(int arr[]) {
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + " ");
        }
        System.out.println();
    }
}

第2关 插入排序

package step2;
/**
 * Created by sykus on 2018/3/20.
 */
public class InsertionSort {
    public static void sort(int arr[]) {
        /********** Begin *********/
        for (int i = 1; i < arr.length; i++) {
            int j = i;
            int tmp = arr[j];
            while (j > 0 && tmp < arr[j - 1]) {
                arr[j] = arr[j - 1];
                j--;
            }
            arr[j] = tmp;
            print(arr);
        }
        /********** End *********/
    }
    private static void print(int arr[]) {
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + " ");
        }
        System.out.println();
    }
}

第3关 归并排序

package step3;
/**
 * Created by sykus on 2018/3/20.
 */
public class MergeSort {
    /**
     * lo, hi都是指下标
     */
    public static void sort(int arr[], int lo, int hi) {
        if (lo < hi) {
            int mid = (lo + hi) / 2;
            sort(arr, lo, mid);
            sort(arr, mid + 1, hi);
            merge(arr, lo, mid, hi);
            print(arr);
        }
    }
    private static void merge(int arr[], int p, int q, int r) {
        /********** Begin *********/
        int n1 = q - p + 1;
        int n2 = r - q;
        int L[] = new int[n1 + 1];
        int R[] = new int[n2 + 1];
        for (int i = 0; i < n1; i++) {
            L[i] = arr[p + i];
        }
        for (int j = 0; j < n2; j++) {
            R[j] = arr[q + j + 1];
        }
        L[n1] = Integer.MAX_VALUE;
        R[n2] = Integer.MAX_VALUE;
        int i = 0, j = 0;
        for (int k = p; k <= r; k++) {
            if (L[i] <= R[j]) {
                arr[k] = L[i];
                i++;
            } else {
                arr[k] = R[j];
                j++;
            }
        }
        /********** End *********/
    }
    private static void print(int arr[]) {
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + " ");
        }
        System.out.println();
    }
}

第4关 快速排序

package step4;
/**
 * Created by sykus on 2018/3/20.
 */
public class QuickSort {
    public void sort(int arr[], int low, int high) {
        /********** Begin *********/
        int i = low;
        int j = high + 1;
        int povit = arr[low];
        while (i < j) {
            while (j > low && arr[--j] >= povit) ;
            while (i < high && arr[++i] <= povit) ;
            if (i>=j)break;
            int temp = arr[j];
            arr[j] = arr[i];
            arr[i] = temp;
            print(arr);
        }
        int temp = arr[j];
        arr[j] = arr[low];
        arr[low] = temp;
        print(arr);
        if (i > low) sort(arr, low, j - 1);
        if (j < high) sort(arr, j + 1, high);
        /********** End *********/
    }
    private static void print(int arr[]) {
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + " ");
        }
        System.out.println();
    }
}

第5关 堆排序

package step5;
/**
 * Created by sykus on 2018/3/20.
 */
public class HeapSort {
    public static void sort(int arr[]) {
        /********** Begin *********/
        int n = arr.length;
        for (int k = n / 2; k >= 1; k--) {
            int l = k;
            while (2 * l <= n) {
                int j = 2 * l;
                if (j < n && arr[j - 1] < arr[j + 1 - 1]) j++;
                if (arr[l - 1] > arr[j - 1]) break;
                int tmp = arr[l - 1];
                arr[l - 1] = arr[j - 1];
                arr[j - 1] = tmp;
                l = j;
            }
        }
        while (n > 1) {
            int tmp = arr[0];
            arr[0] = arr[n - 1];
            arr[n - 1] = tmp;
            int k = 1;
            n--;
            while (2 * k <= n) {
                int j = 2 * k;
                if (j < n && arr[j - 1] < arr[j]) j++;
                if (arr[k - 1] > arr[j - 1]) break;
                tmp = arr[k - 1];
                arr[k - 1] = arr[j - 1];
                arr[j - 1] = tmp;
                k = j;
            }
            print(arr);
        }
        /********** End *********/
    }
    private static void print(int[] arr) {
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + " ");
        }
        System.out.println();
    }
}

七、Java 数据结构之图

第1关 图的表示

package step1;
import java.util.ArrayList;
public class Graph {
    private int V;//顶点数
    private int E;//边数
    private ArrayList<Integer>[] adj;//邻接表
    public Graph(int v) {
        if (v < 0) throw new IllegalArgumentException("Number of vertices must be nonnegative");
        V = v;
        E = 0;
        adj = new ArrayList[V + 1];
        for (int i = 0; i <= this.V; i++) {
            adj[i] = new ArrayList<Integer>();
        }
    }
    public void addEdge(int v, int w) {
        /********** Begin *********/
        adj[v].add(w);
        adj[w].add(v);
        E++;
        /********** End *********/
    }
    public String toString() {
        StringBuilder s = new StringBuilder();
        s.append(V + " 个顶点, " + E + " 条边\n");
        for (int v = 1; v <= V; v++) {
            s.append(v + ": ");
            for (int w : adj[v]) {
                s.append(w + " ");
            }
            s.append("\n");
        }
        return s.toString();
    }
}

第2关 深度优先搜索

package step2;
import java.util.ArrayList;
public class DFSGraph {
    private boolean[] marked;
    private int V;//顶点数
    private int E;//边数
    private ArrayList<Integer>[] adj;//邻接表
    public DFSGraph(int v) {
        if (v < 0) throw new IllegalArgumentException("Number of vertices must be nonnegative");
        V = v;
        E = 0;
        adj = new ArrayList[V + 1];
        marked = new boolean[V + 1];
        for (int i = 0; i <= this.V; i++) {
            adj[i] = new ArrayList<Integer>();
        }
    }
    public void addEdge(int v, int w) {
        adj[v].add(w);
        adj[w].add(v);
        E++;
    }
    public void DFS(int v) {
        /********** Begin *********/
        marked[v] = true;
        System.out.print(v + " ");
        for (int w : adj[v]) {
            if (!marked[w]) {
                DFS(w);
            }
        }
        /********** End *********/
    }
    public String toString() {
        StringBuilder s = new StringBuilder();
        s.append(V + " 个顶点, " + E + " 条边\n");
        for (int v = 1; v <= V; v++) {
            s.append(v + ": ");
            for (int w : adj[v]) {
                s.append(w + " ");
            }
            s.append("\n");
        }
        return s.toString();
    }
}

第3关 广度优先搜索

package step3;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
public class BFSGraph {
    private int V;//顶点数
    private int E;//边数
    private boolean[] marked;
    private ArrayList<Integer>[] adj;//邻接表
    public BFSGraph(int v) {
        if (v < 0) throw new IllegalArgumentException("Number of vertices must be nonnegative");
        V = v;
        E = 0;
        adj = new ArrayList[V + 1];
        marked = new boolean[V + 1];
        for (int i = 0; i <= this.V; i++) {
            adj[i] = new ArrayList<Integer>();
        }
    }
    public void addEdge(int v, int w) {
        adj[v].add(w);
        adj[w].add(v);
        E++;
    }
    public void BFS(int s) {
        /********** Begin *********/
        Queue<Integer> que = new LinkedList<>();
        que.offer(s);
        marked[s] = true;
        while (!que.isEmpty()) {
            int v = que.poll();
            System.out.print(v + " ");
            for (int w : adj[v]) {
                if (!marked[w]) {
                    que.offer(w);
                    marked[w] = true;
                }
            }
        }
        /********** End *********/
    }
    public String toString() {
        StringBuilder s = new StringBuilder();
        s.append(V + " 个顶点, " + E + " 条边\n");
        for (int v = 1; v <= V; v++) {
            s.append(v + ": ");
            for (int w : adj[v]) {
                s.append(w + " ");
            }
            s.append("\n");
        }
        return s.toString();
    }
}

第4关 单源最短路径

package step4;
import java.util.*;
public class ShortestPath {
    private int V;//顶点数
    private int E;//边数
    private int[] dist;
    private ArrayList<Integer>[] adj;//邻接表
    private int[][] weight;//权重
    public ShortestPath(int v, int e) {
        V = v;
        E = e;
        dist = new int[V + 1];
        adj = new ArrayList[V + 1];
        weight = new int[V + 1][V + 1];
        for (int i = 0; i <= this.V; i++) {
            adj[i] = new ArrayList<Integer>();
        }
    }
    public void addEdge(int u, int v, int w) {
        adj[u].add(v);
        adj[v].add(u);
        weight[u][v] = weight[v][u] = w;
    }
    public int[] Paths(int source) {
        /********** Begin *********/
        Queue<Integer> Q = new LinkedList<Integer>();
        dist[source] = 0;
        for (int i = 1; i <= V; i++) {
            if (i != source) {
                dist[i] = Integer.MAX_VALUE;
            }
            Q.offer(i);
        }
        while (!Q.isEmpty()) {
            int minV = Integer.MAX_VALUE;
            int v = source;
            for (int i = 0; i < Q.size(); i++) {
                int index = ((LinkedList<Integer>) Q).get(i);
                if (dist[index] < minV) {
                    minV = dist[index];
                    v = index;
                }
            }
            Q.poll();
            Q.remove(v);
            for (int u : adj[v]) {
                int alt = dist[v] + weight[v][u];
                if (alt < dist[u]) {
                    dist[u] = alt;
                }
            }
        }
        return dist;
        /********** End *********/
    }
    /**
     * 打印源点到所有顶点的距离，INF为无穷大
     *
     * @param dist
     */
    public void print(int[] dist) {
        for (int i = 1; i <= V; i++) {
            if (dist[i] == Integer.MAX_VALUE) {
                System.out.print("INF ");
            } else {
                System.out.print(dist[i] + " ");
            }
        }
    }
}

最后的图的代码来只班级内同学的支持！！文章来源地址https://www.toymoban.com/news/detail-719074.html

到了这里，关于头歌JAVA数据结构答案的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！