数据结构与算法笔记：树、链表、排序与队列实现
目录
- 数据结构与算法笔记：树、链表、排序与队列实现
- 🌲 二叉树（Binary Tree）
- TreeNode 类定义
- 二叉树前序遍历（递归）
- 二叉树搜索（查找目标值节点）
- 🔗 单链表（Linked List）
- ListNode 节点类
- LinkedList 类实现
- 🔄 队列（Queue） - 链式实现
- QueueNode 节点类
- LinkedQueue 类实现
- 11111栈（Stack） - 数组实现1111
- ArrayStack 类实现（补充完整版）
- 📊 排序算法总结
- 🔁 排序算法实现
- 选择排序（Selection Sort）
- 归并排序（Merge Sort）
- ✅ 总结
本文基于手写笔记整理，涵盖二叉树遍历、搜索、链表、栈、队列以及常见排序算法的Java实现。适合初学者快速掌握核心数据结构和算法逻辑。
🌲 二叉树（Binary Tree）
TreeNode 类定义
classTreeNode{intval;TreeNodeleft;TreeNoderight;publicTreeNode(intval){this.val=val;}}二叉树前序遍历（递归）
publicstaticvoidorder(TreeNodenode){if(node==null)return;order(node.left);System.out.print(node.val+" ");order(node.right);}⚠️ 注意：此处为中序遍历，代码顺序应为
left -> root -> right。若需前序则应为root -> left -> right。
二叉树搜索（查找目标值节点）
publicstaticTreeNodesearch(TreeNodenode,inttarget){if(node==null)returnnull;if(node.val==target)returnnode;TreeNodeleft=search(node.left,target);if(left!=null)returnleft;returnsearch(node.right,target);}🔗 单链表（Linked List）
ListNode 节点类
classListNode{intval;ListNodenext;publicListNode(intval){this.val=val;}}LinkedList 类实现
publicclassLinkedList{privateListNodehead;publicvoidaddFirst(intval){ListNodenewNode=newListNode(val);newNode.next=head;head=newNode;}publicvoidprint(){ListNodecur=head;while(cur!=null){System.out.print(cur.val+" ");cur=cur.next;}System.out.println();}}🔄 队列（Queue） - 链式实现
QueueNode 节点类
classQueueNode{intval;QueueNodenext;publicQueueNode(intval){this.val=val;this.next=null;}}LinkedQueue 类实现
publicclassLinkedQueue{privateQueueNodefront;privateQueueNoderear;publicLinkedQueue(){this.front=null;this.rear=null;}publicbooleanisEmpty(){returnfront==null;}publicvoidenqueue(intval){QueueNodenewNode=newQueueNode(val);if(isEmpty()){front=rear=newNode;}else{rear.next=newNode;rear=newNode;}}publicintdequeue(){if(isEmpty()){System.out.println("队列空");return-1;}intval=front.val;front=front.next;if(front==null){rear=null;}returnval;}}11111栈（Stack） - 数组实现1111
ArrayStack 类实现（补充完整版）
publicclassArrayStack{privateint[]data;privateinttop;privateintcapacity;publicArrayStack(intsize){this.capacity=size;this.data=newint[capacity];this.top=-1;}publicbooleanisEmpty(){returntop==-1;}publicvoidpush(intval){if(top>=capacity-1){System.out.println("栈满");return;}data[++top]=val;}publicintpop(){if(isEmpty()){System.out.println("栈空");return-1;}returndata[top--];}publicintpeek(){if(isEmpty()){System.out.println("栈空");return-1;}returndata[top];}}📊 排序算法总结
| 算法 | 时间复杂度 | 空间复杂度 | 特点 |
|---|---|---|---|
| 快排 | O(n log n) | O(log n) | 原地排序，不稳定 |
| 直接插入 | O(n²) | O(1) | 稳定，小规模高效 |
| 选择排序 | O(n²) | O(1) | 不稳定，交换次数少 |
| 归并排序 | O(n log n) | O(n) | 稳定，适合链表 |
| 冒泡排序 | O(n²) | O(1) | 稳定，效率低 |
💡 补充说明：
- n个结点的完全二叉树：有
n+1个空指针域- 第k层最多：2^(k-1) 个结点
- 叶子结点数：≤ 总结点数 / 2
- 度为2的结点数= 叶子结点数 - 1
- 满二叉树：所有层都填满
- 完全二叉树：除最后一层外，其余层全满
🔁 排序算法实现
选择排序（Selection Sort）
publicvoidselectionSort(int[]arr){for(inti=0;i<arr.length-1;i++){intminIndex=i;for(intj=i+1;j<arr.length;j++){if(arr[j]<arr[minIndex]){minIndex=j;}}swap(arr,i,minIndex);}}privatevoidswap(int[]arr,inti,intj){inttemp=arr[i];arr[i]=arr[j];arr[j]=temp;}归并排序（Merge Sort）
publicvoidmergeSort(int[]arr,intleft,intright){if(left>=right)return;intmid=(left+right)/2;mergeSort(arr,left,mid);mergeSort(arr,mid+1,right);merge(arr,left,mid,right);}privatevoidmerge(int[]arr,intl,intm,intr){int[]temp=newint[r-l+1];inti=l,j=m+1,k=0;while(i<=m&&j<=r){temp[k++]=arr[i]<=arr[j]?arr[i++]:arr[j++];}while(i<=m)temp[k++]=arr[i++];while(j<=r)temp[k++]=arr[j++];System.arraycopy(temp,0,arr,l,temp.length);}✅ 总结
本笔记系统梳理了以下内容：
- 二叉树基本操作：遍历与搜索
- 单链表：增删查打印
- 队列与栈：链式与数组实现
- 经典排序算法：选择、归并
- 复杂度分析：时间与空间对比
📝 建议结合代码调试运行，加深对递归、指针、内存管理的理解。
📌学习建议：
- 手写代码 → 理解逻辑 → 调试验证 → 优化改进
- 掌握基础后可拓展：BST、AVL、堆、哈希表等
👉 欢迎关注我，持续分享算法与数据结构干货！
本文由手写笔记整理而成，欢迎点赞收藏，一起进步！
