数据结构的基本操作 14

遍历 + 访问，即增删查改。 数据结构种类很多，存在目的是在不同的应⽤场景，尽可能⾼效地增删改查。

分线性的（ for/while 迭代为代表）和非线性的（递归为代表），具体有以下几种框架：

0. 数组遍历框架，典型的线性迭代结构：

 void traverse(int[] arr) {
     for (int i = 0; i < arr.length; i++) {
     // 迭代访问 arr[i]
     }
 }

2. 链表遍历框架，兼具迭代和递归结构：

 /* 基本的单链表节点 */
 class ListNode {
     int val;


     ListNode next;
 }



 

 void traverse(ListNode head) {
     for (ListNode p = head; p != null; p = p.next) {
     // 迭代访问 p.val
     }
 }
 
 void traverse(ListNode head) {
     // 递归访问 head.val
     traverse(head.next);
 }

3. ⼆叉树遍历框架，典型的非线性递归遍历结构：

 /* 基本的⼆叉树节点 */
 class TreeNode {

     int val;


     TreeNode left, right;
 }



 

 void traverse(TreeNode root) {

     traverse(root.left);
     traverse(root.right);
 }

可以发现，⼆叉树的递归遍历⽅式和链表的递归遍历⽅式很相似。

4. ⼆叉树可以扩展为 N 叉树：

 /* 基本的 N 叉树节点 */
 class TreeNode {

     int val;


     TreeNode[] children;
 }




 void traverse(TreeNode root) {

     for (TreeNode child : root.children)
     traverse(child);
 }

N 叉树的遍历⼜可以扩展为图的遍历，因为图就是好几个 N 叉棵树的结合体。

图是可能出现环的？用个布尔数组 visited 做标记就可以。

所谓框架，就是套路。不管增删查改，这些代码都是永远无法脱离的结构，可以把这个结构作为大纲，根据具体问题在框架上添加代码。