数据结构篇：链表和树结构的操作方法

2024-06-16 07:20
文章标签 链表 数据结构 操作方法 树结构

本文主要是介绍数据结构篇：链表和树结构的操作方法，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

本节课在线学习视频（网盘地址，保存后即可免费观看）：

​​https://pan.quark.cn/s/e4f2ff1e1895​​

链表和树是数据结构中两种非常重要和常见的结构。链表是一种线性数据结构，适用于需要频繁插入和删除操作的场景；而树是一种非线性数据结构，适用于表示层级关系的数据。本文将详细介绍链表和树结构的基本操作方法，并通过多个代码案例展示其具体实现。

1. 链表

链表是由一系列节点组成的线性数据结构，每个节点包含数据部分和指向下一个节点的指针。链表主要有单链表、双链表和循环链表三种类型。

1.1 单链表

单链表中的每个节点只包含一个指向下一个节点的指针。

案例1：单链表的基本操作
class ListNode {int val;ListNode next;ListNode(int val) {this.val = val;}
}public class SinglyLinkedList {private ListNode head;// 插入节点到链表头public void insertAtHead(int val) {ListNode newNode = new ListNode(val);newNode.next = head;head = newNode;}// 删除链表头节点public void deleteHead() {if (head != null) {head = head.next;}}// 打印链表public void printList() {ListNode current = head;while (current != null) {System.out.print(current.val + " -> ");current = current.next;}System.out.println("null");}public static void main(String[] args) {SinglyLinkedList list = new SinglyLinkedList();list.insertAtHead(10);list.insertAtHead(20);list.insertAtHead(30);System.out.println("Initial list:");list.printList();list.deleteHead();System.out.println("After deleting head:");list.printList();}
}

在这个例子中，我们实现了单链表的插入和删除操作，并打印链表的内容。

1.2 双链表

双链表中的每个节点包含两个指针，分别指向前一个节点和下一个节点。

案例2：双链表的基本操作
class DoublyListNode {int val;DoublyListNode prev;DoublyListNode next;DoublyListNode(int val) {this.val = val;}
}public class DoublyLinkedList {private DoublyListNode head;// 插入节点到链表头public void insertAtHead(int val) {DoublyListNode newNode = new DoublyListNode(val);newNode.next = head;if (head != null) {head.prev = newNode;}head = newNode;}// 删除链表头节点public void deleteHead() {if (head != null) {head = head.next;if (head != null) {head.prev = null;}}}// 打印链表public void printList() {DoublyListNode current = head;while (current != null) {System.out.print(current.val + " <-> ");current = current.next;}System.out.println("null");}public static void main(String[] args) {DoublyLinkedList list = new DoublyLinkedList();list.insertAtHead(10);list.insertAtHead(20);list.insertAtHead(30);System.out.println("Initial list:");list.printList();list.deleteHead();System.out.println("After deleting head:");list.printList();}
}

在这个例子中，我们实现了双链表的插入和删除操作，并打印链表的内容。

1.3 循环链表

循环链表中的最后一个节点指向链表中的第一个节点，从而形成一个环。

案例3：循环单链表的基本操作
class CircularListNode {int val;CircularListNode next;CircularListNode(int val) {this.val = val;}
}public class CircularLinkedList {private CircularListNode head;// 插入节点到链表头public void insertAtHead(int val) {CircularListNode newNode = new CircularListNode(val);if (head == null) {head = newNode;head.next = head;} else {CircularListNode temp = head;while (temp.next != head) {temp = temp.next;}temp.next = newNode;newNode.next = head;head = newNode;}}// 打印链表public void printList() {if (head == null) return;CircularListNode temp = head;do {System.out.print(temp.val + " -> ");temp = temp.next;} while (temp != head);System.out.println("(head)");}public static void main(String[] args) {CircularLinkedList list = new CircularLinkedList();list.insertAtHead(10);list.insertAtHead(20);list.insertAtHead(30);System.out.println("Circular Linked List:");list.printList();}
}

在这个例子中，我们实现了循环单链表的插入和打印操作。

2. 树结构

树是一种层级数据结构，由节点和边组成。树的每个节点可以有零个或多个子节点，但每个节点只有一个父节点（根节点除外）。常见的树有二叉树、二叉搜索树和AVL树等。

2.1 二叉树

二叉树中的每个节点最多有两个子节点，分别称为左子节点和右子节点。

案例4：二叉树的基本操作
class TreeNode {int val;TreeNode left;TreeNode right;TreeNode(int val) {this.val = val;}
}public class BinaryTree {// 插入节点public TreeNode insert(TreeNode root, int val) {if (root == null) {return new TreeNode(val);}if (val < root.val) {root.left = insert(root.left, val);} else {root.right = insert(root.right, val);}return root;}// 前序遍历public void preOrderTraversal(TreeNode root) {if (root != null) {System.out.print(root.val + " ");preOrderTraversal(root.left);preOrderTraversal(root.right);}}// 中序遍历public void inOrderTraversal(TreeNode root) {if (root != null) {inOrderTraversal(root.left);System.out.print(root.val + " ");inOrderTraversal(root.right);}}// 后序遍历public void postOrderTraversal(TreeNode root) {if (root != null) {postOrderTraversal(root.left);postOrderTraversal(root.right);System.out.print(root.val + " ");}}public static void main(String[] args) {BinaryTree tree = new BinaryTree();TreeNode root = null;int[] values = {30, 20, 40, 10, 25, 35, 50};for (int val : values) {root = tree.insert(root, val);}System.out.print("Pre-order traversal: ");tree.preOrderTraversal(root);System.out.println();System.out.print("In-order traversal: ");tree.inOrderTraversal(root);System.out.println();System.out.print("Post-order traversal: ");tree.postOrderTraversal(root);System.out.println();}
}

在这个例子中，我们实现了二叉树的插入操作，以及前序遍历、中序遍历和后序遍历。

2.2 二叉搜索树

二叉搜索树（BST）是一种特殊的二叉树，满足以下性质：对于树中的每个节点，其左子树中的所有节点的值都小于该节点的值，右子树中的所有节点的值都大于该节点的值。

案例5：二叉搜索树的查找和删除操作
public class BinarySearchTree {// 查找节点public TreeNode search(TreeNode root, int val) {if (root == null || root.val == val) {return root;}if (val < root.val) {return search(root.left, val);}return search(root.right, val);}// 删除节点public TreeNode delete(TreeNode root, int val) {if (root == null) return null;if (val < root.val) {root.left = delete(root.left, val);} else if (val > root.val) {root.right = delete(root.right, val);} else {if (root.left == null) return root.right;if (root.right == null) return root.left;TreeNode minNode = findMin(root.right);root.val = minNode.val;root.right = delete(root.right, minNode.val);}return root;}// 查找最小节点private TreeNode findMin(TreeNode node) {while (node.left != null) {node = node.left;}return node;}public static void main(String[] args) {BinarySearchTree bst = new BinarySearchTree();TreeNode root = null;int[] values = {50, 30, 70, 20, 40, 60, 80};for (int val : values) {root = bst.insert(root, val);}System.out.println("BST created.");System.out.print("In-order traversal before deletion: ");bst.inOrderTraversal(root);System.out.println();root = bst.delete(root, 20);System.out.print("In-order traversal after deleting 20: ");bst.inOrderTraversal(root);System.out.println();root = bst.delete(root, 30);System.out.print("In-order traversal after deleting 30: ");bst.inOrderTraversal(root);System.out.println();root = bst.delete(root, 50);System.out.print("In-order traversal after deleting 50: ");bst.inOrderTraversal(root);System.out.println();}
}

在这个例子中，我们实现了二叉搜索树的查找和删除操作，并展示了删除节点后的中序遍历结果。

2.3 AVL树

AVL树是平衡二叉搜索树的一种，通过旋转操作保持树的平衡。我们在前面的博客中已经详细介绍了AVL树的旋转操作，这里补充一下综合操作。

案例6：AVL树的插入和删除操作
public class AVLTree {private int height(TreeNode node) {if (node == null) return 0;return node.height;}private int balanceFactor(TreeNode node) {if (node == null) return 0;return height(node.left) - height(node.right);}private TreeNode rightRotate(TreeNode y) {TreeNode x = y.left;TreeNode T2 = x.right;x.right = y;y.left = T2;y.height = Math.max(height(y.left), height(y.right)) + 1;x.height = Math.max(height(x.left), height(x.right)) + 1;return x;}private TreeNode leftRotate(TreeNode x) {TreeNode y = x.right;TreeNode T2 = y.left;y.left = x;x.right = T2;x.height = Math.max(height(x.left), height(x.right)) + 1;y.height = Math.max(height(y.left), height(y.right)) + 1;return y;}private TreeNode insert(TreeNode node, int val) {if (node == null) return new TreeNode(val);if (val < node.val) node.left = insert(node.left, val);else if (val > node.val) node.right = insert(node.right, val);else return node;node.height = 1 + Math.max(height(node.left), height(node.right));int balance = balanceFactor(node);if (balance > 1 && val < node.left.val) return rightRotate(node);if (balance < -1 && val > node.right.val) return leftRotate(node);if (balance > 1 && val > node.left.val) {node.left = leftRotate(node.left);return rightRotate(node);}if (balance < -1 && val < node.right.val) {node.right = rightRotate(node.right);return leftRotate(node);}return node;}private TreeNode delete(TreeNode root, int val) {if (root == null) return root;if (val < root.val) root.left = delete(root.left, val);else if (val > root.val) root.right = delete(root.right, val);else {if ((root.left == null) || (root.right == null)) {TreeNode temp = null;if (temp == root.left) temp = root.right;else temp = root.left;if (temp == null) {temp = root;root = null;} else root = temp;} else {TreeNode temp = findMin(root.right);root.val = temp.val;root.right = delete(root.right, temp.val);}}if (root == null) return root;root.height = Math.max(height(root.left), height(root.right)) + 1;int balance = balanceFactor(root);if (balance > 1 && balanceFactor(root.left) >= 0) return rightRotate(root);if (balance > 1 && balanceFactor(root.left) < 0) {root.left = leftRotate(root.left);return rightRotate(root);}if (balance < -1 && balanceFactor(root.right) <= 0) return leftRotate(root);if (balance < -1 && balanceFactor(root.right) > 0) {root.right = rightRotate(root.right);return leftRotate(root);}return root;}private TreeNode findMin(TreeNode node) {while (node.left != null) node = node.left;return node;}public void inOrderTraversal(TreeNode root) {if (root != null) {inOrderTraversal(root.left);System.out.print(root.val + " ");inOrderTraversal(root.right);}}public static void main(String[] args) {AVLTree avl = new AVLTree();TreeNode root = null;int[] values = {10, 20, 30, 40, 50, 25};for (int val : values) {root = avl.insert(root, val);}System.out.print("In-order traversal before deletion: ");avl.inOrderTraversal(root);System.out.println();root = avl.delete(root, 10);System.out.print("In-order traversal after deleting 10: ");avl.inOrderTraversal(root);System.out.println();root = avl.delete(root, 30);System.out.print("In-order traversal after deleting 30: ");avl.inOrderTraversal(root);System.out.println();root = avl.delete(root, 50);System.out.print("In-order traversal after deleting 50: ");avl.inOrderTraversal(root);System.out.println();}
}

在这个例子中，我们实现了AVL树的插入和删除操作，并展示了删除节点后的中序遍历结果。

3. 注意事项

  • 在链表操作中，注意处理空链表和单节点链表的特殊情况。
  • 在树操作中，确保在插入或删除节点后正确调整节点的高度，并进行必要的旋转操作以保持树的平衡。
  • 对于大规模数据，链表和树的操作可能需要考虑空间和时间复杂度，以提高性能。

结语

本文详细介绍了链表和树结构的基本操作方法，包括单链表、双链表、循环链表的插入和删除操作，以及二叉树、二叉搜索树和AVL树的插入、查找和删除操作。通过这些代码案例，可以帮助你更好地理解和应用链表和树结构。在实际开发中，选择合适的数据结构和操作方法，可以显著提升代码的效率和可维护性。希望这些示例和注意事项能帮助你更好地掌握链表和树结构的操作方法。

这篇关于数据结构篇：链表和树结构的操作方法的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/1065807。

相关文章

【数据结构】——原来排序算法搞懂这些就行，轻松拿捏

【数据结构】——原来排序算法搞懂这些就行，轻松拿捏

前言：快速排序的实现最重要的是找基准值，下面让我们来了解如何实现找基准值 基准值的注释：在快排的过程中，每一次我们要取一个元素作为枢纽值，以这个数字来将序列划分为两部分。 在此我们采用三数取中法，也就是取左端、中间、右端三个数，然后进行排序，将中间数作为枢纽值。 快速排序实现主框架： //快速排序 void QuickSort(int* arr, int left, int rig
阅读更多...
csu1329(双向链表)

csu1329(双向链表)

题意：给n个盒子，编号为1到n，四个操作：1、将x盒子移到y的左边；2、将x盒子移到y的右边；3、交换x和y盒子的位置；4、将所有的盒子反过来放。 思路分析：用双向链表解决。每个操作的时间复杂度为O(1)，用数组来模拟链表，下面的代码是参考刘老师的标程写的。 代码如下： #include<iostream>#include<algorithm>#include<stdio.h>#
阅读更多...
6.1.数据结构-c/c++堆详解下篇（堆排序，TopK问题）

6.1.数据结构-c/c++堆详解下篇（堆排序，TopK问题）

上篇：6.1.数据结构-c/c++模拟实现堆上篇（向下，上调整算法，建堆，增删数据）-CSDN博客 本章重点 1.使用堆来完成堆排序 2.使用堆解决TopK问题 目录 一.堆排序 1.1 思路 1.2 代码 1.3 简单测试 二.TopK问题 2.1 思路(求最小)： 2.2 C语言代码（手写堆） 2.3 C++代码（使用优先级队列 priority_queue）
阅读更多...
深入手撕链表

深入手撕链表

链表 分类概念单链表增尾插头插插入 删尾删头删删除 查完整实现带头不带头 双向链表初始化增尾插头插插入 删查完整代码 数组 分类 #mermaid-svg-qKD178fTiiaYeKjl {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-
阅读更多...
建立升序链表

建立升序链表

题目1181：遍历链表 时间限制：1 秒 内存限制：32 兆 特殊判题：否 提交：2744 解决：1186 题目描述： 建立一个升序链表并遍历输出。 输入： 输入的每个案例中第一行包括1个整数：n(1<=n<=1000)，接下来的一行包括n个整数。 输出： 可能有多组测试数据，对于每组数据， 将n个整数建立升序链表，之后遍历链表并输出。 样例输
阅读更多...
《数据结构（C语言版）第二版》第八章-排序（8.3-交换排序、8.4-选择排序）

《数据结构（C语言版）第二版》第八章-排序（8.3-交换排序、8.4-选择排序）

8.3 交换排序 8.3.1 冒泡排序 【算法特点】 (1) 稳定排序。 (2) 可用于链式存储结构。 (3) 移动记录次数较多，算法平均时间性能比直接插入排序差。当初始记录无序，n较大时， 此算法不宜采用。 #include <stdio.h>#include <stdlib.h>#define MAXSIZE 26typedef int KeyType;typedef char In
阅读更多...
【每日一题】LeetCode 2181.合并零之间的节点（链表、模拟）

【每日一题】LeetCode 2181.合并零之间的节点（链表、模拟）

【每日一题】LeetCode 2181.合并零之间的节点（链表、模拟） 题目描述 给定一个链表，链表中的每个节点代表一个整数。链表中的整数由 0 分隔开，表示不同的区间。链表的开始和结束节点的值都为 0。任务是将每两个相邻的 0 之间的所有节点合并成一个节点，新节点的值为原区间内所有节点值的和。合并后，需要移除所有的 0，并返回修改后的链表头节点。 思路分析 初始化：创建一个虚拟头节点
阅读更多...
学习记录：js算法（二十八）：删除排序链表中的重复元素、删除排序链表中的重复元素II

学习记录：js算法（二十八）：删除排序链表中的重复元素、删除排序链表中的重复元素II

文章目录 删除排序链表中的重复元素我的思路解法一：循环解法二：递归 网上思路 删除排序链表中的重复元素 II我的思路网上思路 总结 删除排序链表中的重复元素 给定一个已排序的链表的头 head ， 删除所有重复的元素，使每个元素只出现一次 。返回 已排序的链表 。 图一 图二 示例 1：（图一）输入：head = [1,1,2]输出：[1,2]示例 2：（图
阅读更多...
【408数据结构】散列 （哈希）知识点集合复习考点题目

【408数据结构】散列 （哈希）知识点集合复习考点题目

苏泽  “弃工从研”的路上很孤独，于是我记下了些许笔记相伴，希望能够帮助到大家    知识点 1. 散列查找 散列查找是一种高效的查找方法，它通过散列函数将关键字映射到数组的一个位置，从而实现快速查找。这种方法的时间复杂度平均为(
阅读更多...
浙大数据结构：树的定义与操作

浙大数据结构：树的定义与操作

四种遍历 #include<iostream>#include<queue>using namespace std;typedef struct treenode *BinTree;typedef BinTree position;typedef int ElementType;struct treenode{ElementType data;BinTree left;BinTre
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2