二叉树的遍历算法

二叉树的遍历算法

一、算法原理

二叉树遍历是指按照特定的顺序访问树中所有节点的过程，主要分为深度优先遍历（DFS）和广度优先遍历（BFS）。深度优先遍历包括前序遍历、中序遍历和后序遍历，广度优先遍历即层次遍历。

二、 深度优先遍历（DFS）

1.前序遍历（Preorder Traversal）

访问顺序：根节点—>左子树–>右子数
特点：第一个访问的总是根节点。适用于复制树的结构、序列化、或作为前缀表达式（波兰表达式）

递归实现：

//递归实现voidpreOrder(TreeNode*root){if(nullptr==root)return;cout<<root->val<<" ";//访问根节点preOrder(root->left);//遍历左子树preOrder(root->right);//遍历右子树}//迭代实现（使用栈）//迭代思路：使用栈。先将根节点入栈。当栈不为空时，弹出栈顶节点并访问，然后先将其右子节点入栈，//再将其左子节点入栈（栈是后进先出，以保证左子树先被处理）voidpreOrderStack(TreeNode*root){stack<TreeNode*>st;if(root)st.push(root);while(!st.empty()){TreeNode*node=st.top();st.pop();cout<<node->val<<" ";if(node->right)st.push(node->right);if(node->left)st.push(node->left);}}

2.中序遍历（Inorder Traversal）

访问顺序：左子树->根节点->右子树
特点：二叉搜索树进行中序遍历，会得到一个升序序列。这是BST独有的重要性质，常用于排序和范围查询。

递归实现

voidinorder(TreeNode*root){if(nullptr==root)return;inorder(root->left);//遍历左子树cout<<root->val<<" ";//访问根节点inorder(root->right);//遍历右子树}//迭代实现//迭代思路：使用栈。用一个curr指针从根节点开始，沿左子树一直走到最底，并将路径上的节点全部入栈。//然后弹出栈顶节点访问，并将curr指向该节点的右子节点，重复上述过程。voidinorderStack(TreeNode*root){stack<TreeNode*>st;TreeNode*curr=root;while(curr||!st.empty()){while(curr){st.push(curr);curr=curr->left;//左子树入栈}curr=st.top();st.pop();cout<<curr->val<<" ";curr=curr->right;//转向右子树}}

3.后序遍历（PostOrder Traversal）

访问顺序：左子树->右子树->根节点
特点：最后访问根节点。适用于先处理子节点再处理父节点的场景，如释放或删除树、计算目录大小、表达式求值（逆波兰表达式）

递归实现

//递归实现voidpostOrder(TreeNode*root){if(root==nullptr)return;postorder(root->left);// 遍历左子树postorder(root->right);// 遍历右子树cout<<root->val<<" ";// 访问根节点}//迭代实现//迭代思路：使用栈。可以模拟“根->右->左”的顺序进行遍历（类似于变种的前序遍历），然后将结果逆序，//即可得到“左->右->根”的后序结果。另一种经典方法是记录上一个访问的节点，以判断当前节点的右子树是否已被处理。voidpostOrderStack(TreeNode*root){stack<pair<TreeNode*,bool>>st;st.push({root,false});while(!st.empty()){auto[node,visited]=st.top();st.pop();if(node){if(visited){cout<<node->val<<" ";}else{st.push({node,true});st.push({node->right,false});st.push({node->left,false});}}}}}

三、广度优先遍历（BFS）

层次遍历（Level Order Traversal）

按层访问节点，使用队列实现

voidlevelOrder(TreeNode*root){queue<TreeNode*>q;if(root)q.push(root);while(!q.empty()){TreeNode*node=q.front();q.pop();cout<<node->val<<" ";if(node->left)q.push(node->left);if(node->right)q.push(node->root);}}

四、应用场景

• 前序遍历：复制树结构、表达式树的前缀表示
• 中序遍历：二叉搜索树的有序输出
• 后序遍历：释放数内存、表达式数的后缀计算
• 层次遍历：查找树的高度、层序构件二叉树

五、时间复杂度和空间复杂度

时间复杂度：O(n)(n为节点数)
空间复杂度：递归实现为：O(h)(h为树高)， 迭代实现方式 ：O(n)

六、调用示例

structTreeNode{intval;TreeNode*left;TreeNode*right;TreeNode(intv):val(v),left(nullptr),right(nullptr){}};TreeNode*buildTree(vector<int>&nums){if(nums.empty())returnnullptr;queue<TreeNode*>q;TreeNode*root=newTreeNode(nums[0]);q.push(root);inti=1;while(!q.empty()&&i<nums.size()){TreeNode*node=q.front();q.pop();//处理左子节点if(i<nums.size()){node->left=newTreeNode(nums[i]);q.push(node->left);}++i;//处理右子树节点if(i<nums.size()){node->right=newTreeNode(nums[i]);q.push(node->right);}++i;}returnroot;}voidfreeTree(TreeNode*root){if(nullptr==root)return;freeTree(root->left);freeTree(root->right);if(root){cout<<"free node:"<<root->val<<" ";deleteroot;root=nullptr;}}voidtree_seach_test(){//构造树vector<int>treeNode={1,2,3,4,5,6,7};TreeNode*root=buildTree(treeNode);//前序遍历算法cout<<"preOrder Start:";preOrder(root);cout<<endl;cout<<"preOrderStack Start:";preOrderStack(root);cout<<endl;//中序遍历算法cout<<"inOrder Start:";inOrder(root);cout<<endl;cout<<"inOrderStack Start:";inOrderStack(root);cout<<endl;//后序遍历算法cout<<"postOrder Start:";postOrder(root);cout<<endl;cout<<"postOrderStack Start:";postOrderStack(root);cout<<endl;//广度优先算法cout<<"BFS Start:";levelOrder(root);cout<<endl;//释放树空间freeTree(root);}intmain(){cout<<"Tree Search Start:"<<endl;tree_seach_test();cout<<endl;getchar();}