二叉树遍历算法（递归的、非递归的中序、前序、后序遍历和层次遍历以及求二叉树的宽度和深度）.pdf-资料库

linux_lihuafeng-9130105-4744302543377753759.pdf-第1页.png

第1页 / 共26页

linux_lihuafeng-9130105-4744302543377753759.pdf-第2页.png

第2页 / 共26页

linux_lihuafeng-9130105-4744302543377753759.pdf-第3页.png

第3页 / 共26页

linux_lihuafeng-9130105-4744302543377753759.pdf-第4页.png

第4页 / 共26页

linux_lihuafeng-9130105-4744302543377753759.pdf-第5页.png

第5页 / 共26页

linux_lihuafeng-9130105-4744302543377753759.pdf-第6页.png

第6页 / 共26页

linux_lihuafeng-9130105-4744302543377753759.pdf-第7页.png

第7页 / 共26页

linux_lihuafeng-9130105-4744302543377753759.pdf-第8页.png

第8页 / 共26页

二叉树的遍历前序遍历递归算法：代码如下：publicvoidpreOrderTraver(Noderoot){if(root!=null){visit(root);preOrderTraver(root.getLeft());preOrderTraver(root.getRight());}}二叉树的前序遍历的规则是依次访问根-》左子树-》右子树。并且左子树、右子树均是一棵二叉树。对于一棵最小的子树来说，它的结构有如下四种情况：1）根2）根3）根4）根/\/\叶子叶子叶子叶子注意：不存在无根的子树根据二叉树的前序遍历的规则，我们能够发现前序遍历的过程是可以抽象成依次访问根-》左子树-》右子树的，并且对于每一棵子树我们采用相同的遍历规则，只是当前的根有所不同而已。现在，我们考虑一下遍历终止的条件：当我们将二叉树中所有结点都遍历过了之后，这时我们遍历结束。当然，这也可以等价于我们访问过了二叉树的根节点和所有子树的根节点。这个条件在我们编程时，更容易实现。当根为null时，说明该棵子树已经遍历完成1、当二叉树为空树时，显然无需遍历。2、当二叉树不为空树时，等价于该二叉树有根节点。对于前序遍历来说，我们先要访问根节点，然后访问左子树，然后右子树。因为二叉树的子树也是二叉树，当我们遍历左右子树时，只需要把子树当成二叉树一样遍历就好（重复上面的1、2过程），不同的是，此时的根为子树的根。我们能够发现当没有根可以遍历时，我们就遍历完了整棵二叉树。中序遍历和后序遍历是相同的道理。中序遍历递归算法：代码如下：publicvoidinOrderTraver(Noderoot){if(root!=null){preOrderTraver(root.getLeft());visit(root);

preOrderTraver(root.getRight());}}后序遍历递归算法：代码如下：publicvoidpostOrderTraver(Noderoot){if(root!=null){preOrderTraver(root.getLeft());preOrderTraver(root.getRight());visit(root);}}非递归遍历二叉树前序遍历非递归法（用栈）：/***非递归法求先序遍历序列*法1*思路：*1、如果二叉树为空树，则结束遍历；*2、如果二叉树不为空树，将根节点入栈*当栈不为空时*3、弹出栈顶节点并访问*4、如果栈顶节点有右子树，将右子树根入栈*5、如果栈顶元素有左子树，将左子树根入栈*6、重复3、4、5过程，直到栈为空*@paramroot*/publicvoiditerativePreOrderTraver(Noderoot){Stacknodes=newStack();if(root!=null){//当二叉树不为空（即二叉树有根节点）时//将根节点入栈nodes.push(root);while(!nodes.empty()){//当栈不为空时，//弹出栈顶元素root=nodes.pop();//访问根节点visit(root);//如果二叉树有右子树，将右子树根节点压入栈中if(root.getRight()!=null){nodes.push(root.getRight());}//如果二叉树有左子树，将左子树跟阶段压入栈中

if(root.getLeft()!=null){nodes.push(root.getLeft());}}}}/***非递归法求先序遍历序列*法2*思路：*当栈不为空或节点不为空时*1、将当前节点的根入栈并访问*2、将当前节点的左子树根设为当前节点*3、重复1、2，直到当前节点无左孩子*如果栈不空*4、将栈顶节点弹出*5、如果栈顶节点有右子树，将栈顶节点的右子树根设为当前节点*6、重复1、2、3、4、5过程，直到栈为空。*@paramroot*/publicvoiditerativePreOrderTraver2(Noderoot){Stacknodes=newStack();Nodenode=root;while(node!=null||!nodes.empty()){//将左节点压入栈中while(node!=null){visit(node);nodes.push(node);node=node.getLeft();}//将栈中深度最大节点的右子树根压入栈中，将该右子树按照上面方法将该右子树根的左节点遍历后压入栈中if(!nodes.empty()){node=nodes.pop();node=node.getRight();}}}中序遍历非递归法（用栈）：/***非递归法求中序遍历序列*法1*思路：*1、将当前节点（可看成某棵子树或二叉树的根）的右子树根压入栈中，再将当前节点

压入栈中*2、将当前节点的左子树根设为当前节点*3、重复1、2，直到当前节点没有左孩子为止*4、将栈顶节点出栈，当栈不为空（没有遍历完二叉树）且弹出节点没有右子树时，弹出节点并遍历，重复4；*5、如果栈不为空，将当前节点的右子树根设为当前节点*6、重复1、2、3、4、5过程直到当前节点为空（按照这种压栈弹栈方法，遍历完整个二叉树的条件为最后一棵被遍历的子树没有右孩子）*@paramroot*/publicstaticvoiditerativeInOrderTraver(Noderoot){Stacknodes=newStack();Nodenode=root;//由于压栈过程是先压右子树，再压根节点，所以当栈为空时，遍历过二叉树所有节点while(node!=null){//压栈过程while(node!=null){if(node.getRight()!=null)nodes.push(node.getRight());nodes.push(node);node=node.getLeft();}//弹栈过程node=nodes.pop();visit(node);//分两种情况//1、栈不空且当前节点无右子树while(!nodes.empty()&&node.getRight()==null){//返回上一层node=nodes.pop();//访问当前节点visit(node);}//2、栈不空且当前节点无右子树if(!nodes.empty()){//弹出右节点，把右节点当根，重复下面过程/*while(node!=null){if(node.getRight()!=null)nodes.push(node.getRight());nodes.push(node);node=node.getLeft();}node=nodes.pop();

visit(node);while(!nodes.empty()&&node.getRight()==null){//返回上一层node=nodes.pop();visit(node);}*/node=nodes.pop();}else{//结束遍历node=null;}}}/***非递归法求中序遍历序列*法2*思路：*1、将当前节点的左侧节点依次放入栈中，直到最左侧节点（无左孩子）*2、将最左侧节点（实际上为未访问过的最左侧节点，因为访问过的节点都会出栈）出栈，并访问*3、将最左侧节点的右子树根节点定为当前节点*4、重复1、2、3过程直到栈为空（即遍历完整棵二叉树）*@paramroot*/publicstaticvoiditerativeInOrderTraver2(Noderoot){Stacknodes=newStack();Nodenode=root;//二叉树无根节点（此时栈为空且当前节点为空）//遍历结束时（//二叉树无根节点（此时栈为空且当前节点为空）while(node!=null||!nodes.empty()){//遍历结束的条件是：//1）二叉树不为空树时，运行后，栈为空，当前节点为空（此时，正是遍历完整棵二叉树的时候）//2）二叉树为空树//将以当前节点为根节点的子树左侧节点压入栈中while(node!=null){nodes.push(node);node=node.getLeft();}//弹出左侧最深节点，将当前节点设为当前节点的右孩子，将右孩子视为下一次循环的根节点

if(!nodes.empty()){node=nodes.pop();visit(node);node=node.getRight();}}}后序遍历非递归法（用栈）：后序遍历的非递归实现是三种遍历方式中最难的一种。因为在后序遍历中，要保证左孩子和右孩子都已被访问并且左孩子在右孩子前访问才能访问根结点，这就为流程的控制带来了难题。下面介绍两种思路。第一种思路：对于任一结点P，将其入栈，然后沿其左子树一直往下搜索，直到搜索到没有左孩子的结点，此时该结点出现在栈顶，但是此时不能将其出栈并访问，因为其右孩子还为被访问。所以接下来按照相同的规则对其右子树进行相同的处理，当访问完其右孩子时，该结点又出现在栈顶，此时可以将其出栈并访问。这样就保证了正确的访问顺序。可以看出，在这个过程中，每个结点都两次出现在栈顶，只有在第二次出现在栈顶时，才能访问它。因此需要多设置一个变量标识该结点是否是第一次出现在栈顶。第二种思路：要保证根结点在左孩子和右孩子访问之后才能访问，因此对于任一结点P，先将其入栈。如果P不存在左孩子和右孩子，则可以直接访问它；或者P存在左孩子或者右孩子，但是其左孩子和右孩子都已被访问过了，则同样可以直接访问该结点。若非上述两种情况，则将P的右孩子和左孩子依次入栈，这样就保证了每次取栈顶元素的时候，左孩子在右孩子前面被访问，左孩子和右孩子都在根结点前面被访问。/**非递归实现后序遍历*/protectedstaticvoiditerativePostorder(Nodep){Nodeq=p;Stackstack=newStack();while(p!=null){//左子树入栈for(;p.getLeft()!=null;p=p.getLeft())stack.push(p);//当前节点无右子或右子已经输出while(p!=null&&(p.getRight()==null||p.getRight()==q)){visit(p);q=p;//记录上一个已输出节点

if(stack.empty())return;p=stack.pop();}//处理右子stack.push(p);p=p.getRight();}}/**非递归实现后序遍历双栈法*/protectedstaticvoiditerativePostorder2(Nodep){Stacklstack=newStack();Stackrstack=newStack();Nodenode=p,right;do{while(node!=null){right=node.getRight();lstack.push(node);rstack.push(right);node=node.getLeft();}node=lstack.pop();right=rstack.pop();if(right==null){visit(node);}else{lstack.push(node);rstack.push(null);}node=right;}while(lstack.size()>0||rstack.size()>0);}/**非递归实现后序遍历单栈法*/protectedstaticvoiditerativePostorder3(Nodep){Stackstack=newStack();Nodenode=p,prev=p;while(node!=null||stack.size()>0){while(node!=null){stack.push(node);node=node.getLeft();}if(stack.size()>0){

Nodetemp=stack.peek().getRight();if(temp==null||temp==prev){node=stack.pop();visit(node);prev=node;node=null;}else{node=temp;}}}}/**非递归实现后序遍历4双栈法*/protectedstaticvoiditerativePostorder4(Nodep){Stackstack=newStack();Stacktemp=newStack();Nodenode=p;while(node!=null||stack.size()>0){while(node!=null){temp.push(node);stack.push(node);node=node.getRight();}if(stack.size()>0){node=stack.pop();node=node.getLeft();}}while(temp.size()>0){node=temp.pop();visit(node);}}层次遍历（用队列）：/***层次遍历二叉树*@paramroot*/publicstaticvoidlevelTraver(Noderoot){Nodenode=root;

资料库

二叉树遍历算法（递归的、非递归的中序、前序、后序遍历和层次遍历以及求二叉树的宽度和深度）.pdf

相关推荐

课程资源

热门标签

最新资料