一分钟建站,海南网站制做的公司,培训课程安排,wordpress编辑页面模板下载本节课在线学习视频#xff08;网盘地址#xff0c;保存后即可免费观看#xff09;#xff1a;
https://pan.quark.cn/s/e4f2ff1e1895
链表和树是数据结构中两种非常重要和常见的结构。链表是一种线性数据结构#xff0c;适用于需要频繁插入和删除操作的场景网盘地址保存后即可免费观看
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树的旋转操作这里补充一下综合操作。
案例6AVL树的插入和删除操作
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树的插入、查找和删除操作。通过这些代码案例可以帮助你更好地理解和应用链表和树结构。在实际开发中选择合适的数据结构和操作方法可以显著提升代码的效率和可维护性。希望这些示例和注意事项能帮助你更好地掌握链表和树结构的操作方法。
