Java中的数据结构函数

Java中的数据结构函数是指为了实现各种数据结构（如链表、栈、队列、树、图等）所编写的函数。这些函数在实现数据结构的基础上，可以让开发者更加高效地完成各种具体的编程任务。

链表函数

链表是一种非常基本的数据结构，其特点在于不需要连续的内存空间，数据元素之间通过指针来连接。Java中的链表函数主要包括节点的插入、删除、查找等操作。

插入函数：插入函数可以在链表任意位置插入新的数据元素。新插入的节点需要链接前面和后面的节点，并将前一个节点的next指向新插入的节点，新插入节点的next指向后一个节点。代码如下：

public void insertNode(Node head, Node newNode, int position) {
    if(position < 1 || position > listLength(head)+1) {
        System.out.println("Invalid position!");
        return;
    }
 
    if(position == 1) { 
        newNode.next = head;
        head = newNode;
    } else if(position == listLength(head)+1) { 
        Node temp = head;
        while(temp.next != null) {
            temp = temp.next;
        }
        newNode.next = null;
        temp.next = newNode;
    } else { 
        Node temp = head;
        for(int i=1; i<position-1; i++) {
            temp = temp.next;
        }
 
        Node nextTemp = temp.next;
        temp.next = newNode;
        newNode.next = nextTemp;
    }
}

删除函数：删除函数可以删除链表中的任意节点。删除节点需要将前面的节点的next指向后一个节点，将被删除节点的next设为null。代码如下：

public void deleteNode(Node head, int position) {
    if(position < 1 || position > listLength(head)) {
        System.out.println("Invalid position!");
        return;
    }
 
    if(position == 1) {
        Node temp = head;
        head = temp.next; 
        temp.next = null;
        return;
    }
 
    Node temp = head;
    for(int i=1; i<position-1; i++) {
        temp = temp.next;
    }
 
    Node toDelete = temp.next;
    temp.next = toDelete.next; 
    toDelete.next = null;
}

查找函数：查找函数用于查找节点上的数据元素。遍历链表，如果某个节点的值与给定的值相等，则返回该节点。代码如下：

public Node search(Node head, int value) {
    Node temp = head;
    while(temp != null) {
        if(temp.data == value) {
            return temp;
        }
        temp = temp.next;
    }
    return null;
}

栈函数

栈是一种LIFO（Last In First Out）的数据结构，类似于装药的筒。Java中的栈函数可以实现数据的压栈、出栈、查找等操作。

压栈函数：压栈函数将数据元素压入栈顶，并使得栈顶指向该元素。代码如下：

public void push(int value) {
    if(isFull()) { 
        System.out.println("Stack is overflow!");
        return;
    }
    top++;
    stackArray[top] = value;
}

出栈函数：出栈函数将栈顶的数据元素弹出，使得栈顶指向下一个元素。代码如下：

public int pop() {
    if(isEmpty()) { 
        System.out.println("Stack is underflow!");
        return -1;
    }
    int index = top;
    top--;
    return stackArray[index];
}

查找函数：查找函数用于查找栈中是否存在某个元素。从栈顶开始遍历，如果找到则返回true，否则返回false。代码如下：

public boolean search(int value) {
    for(int i=top; i>=0; i--) {
        if(stackArray[i] == value) return true;
    }
    return false;
}

队列函数

队列是一种FIFO（First In First Out）的数据结构，类似于排队吃饭。Java中的队列函数可以实现数据的入队、出队、查找等操作。

入队函数：入队函数将数据元素加入到队列尾部，并使得队尾指向该元素。代码如下：

public void enqueue(int value) {
    if(isFull()) { 
        System.out.println("Queue is overflow!");
        return;
    }
    rear++;
    queueArray[rear] = value;
}

出队函数：出队函数从队列头部弹出元素，并使得队头指向下一个元素。代码如下：

public int dequeue() {
    if(isEmpty()) { 
        System.out.println("Queue is underflow!");
        return -1;
    }
    int index = front;
    front++;
    return queueArray[index];
}

查找函数：查找函数用于查找队列中是否存在某个元素。从队头开始遍历，如果找到则返回true，否则返回false。代码如下：

public boolean search(int value) {
    for(int i=front; i<=rear; i++) {
        if(queueArray[i] == value) return true;
    }
    return false;
}

树函数

树是一种非常常用的数据结构，其特点在于能够以分层的形式来存储数据。Java中的树函数可以实现各种树的遍历、查找、删除等操作。

遍历函数：遍历函数用于遍历整个树结构，其表示方式一般有三种：前序遍历、中序遍历和后序遍历。前序遍历先遍历根节点，然后遍历左子节点和右子节点。中序遍历先遍历左子节点，然后遍历根节点和右子节点。后序遍历先遍历左子节点和右子节点，然后遍历根节点。代码如下：

public void preOrder(TreeNode root) {
    if(root != null) {
        System.out.print(root.val + " ");
        preOrder(root.left);
        preOrder(root.right);
    }
}
 
public void inOrder(TreeNode root) {
    if(root != null) {
        inOrder(root.left);
        System.out.print(root.val + " ");
        inOrder(root.right);
    }
}
 
public void postOrder(TreeNode root) {
    if(root != null) {
        postOrder(root.left);
        postOrder(root.right);
        System.out.print(root.val + " ");
    }
}

查找函数：查找函数用于查找树中是否存在某个元素。从根节点开始遍历，如果找到则返回true，否则返回false。代码如下：

public boolean search(TreeNode root, int value) {
    if(root == null) return false;
    if(root.val == value) return true;
    if(value < root.val) {
        return search(root.left, value);
    } else {
        return search(root.right, value);
    }
}

删除函数：删除函数用于删除一颗树中的某个节点。首先，需要找到该节点，然后判断其分支的情况，如果分支为空，则直接将该节点删除。如果分支只有一个节点，则用该节点来代替被删除节点。如果分支有两个节点，则需要找到被删除节点的直接后继节点，用后继节点来代替被删除节点。代码如下：

`java

public TreeNode delete(TreeNode root, int value) {

if(root == null) return null;

if(value < root.val) {

root.left = delete(root.left, value);

} else if(value > root.val) {

root.right = delete(root.right, value);

} else {

if(root.left == null) {

return root.right;

} else if(root.right == null) {

return root.left;

}

TreeNode successor = root.right;

while(successor.left != null) {

successor = successor.left;

}

root.val = successor.val;

root.right = delete(root.right, successor.val);

}