深度与广度优先遍历：二叉树的访问策略

"二叉树遍历是一种在二叉树数据结构中系统访问所有节点的方法。每个节点只被访问一次，但不指定特定的访问顺序。遍历方式主要有两种：广度优先遍历（Breadth-first Traversal）和深度优先遍历（Depth-first Traversal）。其中，深度优先遍历又分为前序遍历、中序遍历和后序遍历。 1. 广度优先遍历（Breadth-first Traversal）： 这种遍历方式从最低层的节点开始，按水平方向逐层向右访问每个节点。代码实现通常使用队列（Queue）来辅助完成，首先将根节点入队，然后每次出队一个节点并访问，再将其左右子节点（如果存在）入队。 ```cpp void BST::breadthFirst() { Queue<BSTNode> q; BSTNode* p = root; if (p != 0) { q.enqueue(p); while (!q.empty()) { p = q.dequeue(); visit(p); if (p->left != 0) q.enqueue(p->left); if (p->right != 0) q.enqueue(p->right); } } } ``` 2. 深度优先遍历（Depth-first Traversal）： 深度优先遍历会尽可能深地进入子树，然后再回溯。有三种主要的深度优先遍历方式： - 前序遍历（Preorder Traversal）：先访问根节点，然后访问左子树，最后访问右子树。代码实现为递归结构。 ```cpp void BST::preorder(BSTNode* p) { if (p != 0) { visit(p); preorder(p->left); preorder(p->right); } } ``` - 中序遍历（Inorder Traversal）：先访问左子树，然后访问根节点，最后访问右子树。 ```cpp void BST::inorder(BSTNode* p) { if (p != 0) { inorder(p->left); visit(p); inorder(p->right); } } ``` - 后序遍历（Postorder Traversal）：先访问左子树，然后访问右子树，最后访问根节点。 ```cpp void BST::postorder(BSTNode* p) { if (p != 0) { postorder(p->left); postorder(p->right); visit(p); } } ``` 在实际应用中，二叉树遍历广泛用于数据结构的搜索、复制、打印以及算法的实现，如查找最大值或最小值，构建树的镜像等。此外，Morris遍历是一种不使用额外空间的深度优先遍历方法，通过改变二叉树的链接结构进行遍历，也是二叉树遍历的一个重要补充。"