企业官网建设流程全解析

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

本文基于手写笔记整理，涵盖二叉树遍历、搜索、链表、栈、队列以及常见排序算法的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];}}

📊 排序算法总结

💡 补充说明：

• 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);}

✅ 总结

本笔记系统梳理了以下内容：

1. 二叉树基本操作：遍历与搜索
2. 单链表：增删查打印
3. 队列与栈：链式与数组实现
4. 经典排序算法：选择、归并
5. 复杂度分析：时间与空间对比

📝 建议结合代码调试运行，加深对递归、指针、内存管理的理解。

📌学习建议：

• 手写代码 → 理解逻辑 → 调试验证 → 优化改进
• 掌握基础后可拓展：BST、AVL、堆、哈希表等

👉 欢迎关注我，持续分享算法与数据结构干货！

本文由手写笔记整理而成，欢迎点赞收藏，一起进步！