二叉树的遍历算法

二叉树的遍历算法一、算法原理二叉树遍历是指按照特定的顺序访问树中所有节点的过程主要分为深度优先遍历DFS和广度优先遍历BFS。深度优先遍历包括前序遍历、中序遍历和后序遍历广度优先遍历即层次遍历。二、 深度优先遍历DFS1.前序遍历Preorder Traversal访问顺序根节点—左子树–右子数特点第一个访问的总是根节点。适用于复制树的结构、序列化、或作为前缀表达式波兰表达式递归实现//递归实现voidpreOrder(TreeNode*root){if(nullptrroot)return;coutroot-val ;//访问根节点preOrder(root-left);//遍历左子树preOrder(root-right);//遍历右子树}//迭代实现使用栈//迭代思路使用栈。先将根节点入栈。当栈不为空时弹出栈顶节点并访问然后先将其右子节点入栈//再将其左子节点入栈栈是后进先出以保证左子树先被处理voidpreOrderStack(TreeNode*root){stackTreeNode*st;if(root)st.push(root);while(!st.empty()){TreeNode*nodest.top();st.pop();coutnode-val ;if(node-right)st.push(node-right);if(node-left)st.push(node-left);}}2.中序遍历Inorder Traversal访问顺序左子树-根节点-右子树特点二叉搜索树进行中序遍历会得到一个升序序列。这是BST独有的重要性质常用于排序和范围查询。递归实现voidinorder(TreeNode*root){if(nullptrroot)return;inorder(root-left);//遍历左子树coutroot-val ;//访问根节点inorder(root-right);//遍历右子树}//迭代实现//迭代思路使用栈。用一个curr指针从根节点开始沿左子树一直走到最底并将路径上的节点全部入栈。//然后弹出栈顶节点访问并将curr指向该节点的右子节点重复上述过程。voidinorderStack(TreeNode*root){stackTreeNode*st;TreeNode*currroot;while(curr||!st.empty()){while(curr){st.push(curr);currcurr-left;//左子树入栈}currst.top();st.pop();coutcurr-val ;currcurr-right;//转向右子树}}3.后序遍历PostOrder Traversal访问顺序左子树-右子树-根节点特点最后访问根节点。适用于先处理子节点再处理父节点的场景如释放或删除树、计算目录大小、表达式求值逆波兰表达式递归实现//递归实现voidpostOrder(TreeNode*root){if(rootnullptr)return;postorder(root-left);// 遍历左子树postorder(root-right);// 遍历右子树coutroot-val ;// 访问根节点}//迭代实现//迭代思路使用栈。可以模拟“根-右-左”的顺序进行遍历类似于变种的前序遍历然后将结果逆序//即可得到“左-右-根”的后序结果。另一种经典方法是记录上一个访问的节点以判断当前节点的右子树是否已被处理。voidpostOrderStack(TreeNode*root){stackpairTreeNode*,boolst;st.push({root,false});while(!st.empty()){auto[node,visited]st.top();st.pop();if(node){if(visited){coutnode-val ;}else{st.push({node,true});st.push({node-right,false});st.push({node-left,false});}}}}}三、广度优先遍历BFS层次遍历Level Order Traversal按层访问节点使用队列实现voidlevelOrder(TreeNode*root){queueTreeNode*q;if(root)q.push(root);while(!q.empty()){TreeNode*nodeq.front();q.pop();coutnode-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(vectorintnums){if(nums.empty())returnnullptr;queueTreeNode*q;TreeNode*rootnewTreeNode(nums[0]);q.push(root);inti1;while(!q.empty()inums.size()){TreeNode*nodeq.front();q.pop();//处理左子节点if(inums.size()){node-leftnewTreeNode(nums[i]);q.push(node-left);}i;//处理右子树节点if(inums.size()){node-rightnewTreeNode(nums[i]);q.push(node-right);}i;}returnroot;}voidfreeTree(TreeNode*root){if(nullptrroot)return;freeTree(root-left);freeTree(root-right);if(root){coutfree node:root-val ;deleteroot;rootnullptr;}}voidtree_seach_test(){//构造树vectorinttreeNode{1,2,3,4,5,6,7};TreeNode*rootbuildTree(treeNode);//前序遍历算法coutpreOrder Start:;preOrder(root);coutendl;coutpreOrderStack Start:;preOrderStack(root);coutendl;//中序遍历算法coutinOrder Start:;inOrder(root);coutendl;coutinOrderStack Start:;inOrderStack(root);coutendl;//后序遍历算法coutpostOrder Start:;postOrder(root);coutendl;coutpostOrderStack Start:;postOrderStack(root);coutendl;//广度优先算法coutBFS Start:;levelOrder(root);coutendl;//释放树空间freeTree(root);}intmain(){coutTree Search Start:endl;tree_seach_test();coutendl;getchar();}