当前位置：首页 > news >正文

数据结构与算法笔记：树、链表、排序与队列实现

news 2026/9/26 8:27:11

数据结构与算法笔记：树、链表、排序与队列实现

数据结构与算法笔记：树、链表、排序与队列实现
- 🌲 二叉树（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);}