1、递归遍历
// 先序遍历(递归实现)------------------------------------------------------------- /* 1. Visit the node. 1. Call itself to traverse the node’s left subtree. 3. Call itself to traverse the node’s right subtree. 4. base case: there is no node */ private void preOrder(Node localRoot){ if(localRoot != null) { visit(localRoot); // System.out.print(localRoot.iData + " "); preOrder(localRoot.leftChild); preOrder(localRoot.rightChild); } }// 中序遍历(递归实现)------------------------------------------------------------- private void inOrder(Node localRoot){ if(localRoot != null) { inOrder(localRoot.leftChild); visit(localRoot); //System.out.print(localRoot.iData + " "); inOrder(localRoot.rightChild); } }// 后序遍历(递归实现)------------------------------------------------------------- private void postOrder(Node localRoot){ if(localRoot != null) { postOrder(localRoot.leftChild); postOrder(localRoot.rightChild); visit(localRoot); //System.out.print(localRoot.iData + " "); } }// -------------------------------------------------------------
2、非递归遍历
/*总体思想是:因为递归的本质是用栈实现的,所以写出非递归的形式要用到栈。入栈的顺序与访问的顺序相反,如中序遍历访问顺序是left,current,right,所以入栈的顺序相反是right,current,leftsteo0:初始化当前节点currentstep1:初始化栈step3:出栈,并访问Note:中序遍历和后序遍历需要先判断bPushed为true时访问)step2:入栈循环结束条件是:栈为空*///算法框架 pushNode是入栈的方式public void templet(Node root){ //special case if(root==null) return; //inital current node Node current=root; //initial stack Stack s=new Stack(); pushNode(current,s); //loop: base case is stack is empty while( !s.empty() ){ //pop current=s.pop(); //visit or push }//end while }//end templet()// 先序遍历-深度优先搜索(递归实现)-------------------------------------------------------------//current left right //step1:pop current node //step2:visit current node //step3:push current's right child //step4:push current's left child //step5: loop step1-step5privete void pushPreOrderNode(Node current, Stack s){ if(current==null) return ; if(!s.empty()){ leftChild=current.leftChild; rightChild=curret.rightChild; if(rightChild!=null) //push rightChild s.push(rightChild); if(leftChild!=null) //push leftChild s.push(leftChild): visit(current); //current always first visit in preOrder }//end if }//end pushPreOrderNode()public void preOrder(Node root){ //special case if(root==null) return ; //inintial current node Node current=root; //inintial stack Stack s=new Stack(); pushPreOrderNode(current,s); //base case:stack is empty while( !s.empty() ){ //pop current=s.pop(); //push pushPreOrderNode(current,s); }//end while}//end preOrder() // 中序遍历(非递归实现)-------------------------------------------------------------/*left current right*/public void inOrder( Node root){ //special case if(root==null) return; Node current=root; //initial stack Stack s=new Stack(); pushInOrderNode(current,s); //pop and visit while( !s.empty() ){ current=s.pop(); if(current.bPushed) visit(current); else pushInOrderNode(current,s); }//end while}//end postOrder()private void pushInOrderNode(Node current,Stack s){ if(current==null) return; if(!s.empty()){ leftChild=current.leftChild; rightChild=curret.rightChild; if(rightChild!=null){ //push rightChild s.push(rightChild); rightChild.bPushed=false; }//end if s.push(current); //push current if(leftChild!=null){ //push leftChild s.push(leftChild); rightChild.bPushed=false; }//end if //set flag, ture present current's left and right has both pushed current.bPushed=true; }//end if }//end if}//end pushInOrderNode()// -------------------------------------------------------------// 后序遍历(递归实现)-------------------------------------------------------------/*left right currentstep1:初始化栈按照step2初始化栈step2:入栈入栈顺序:current,right,left如果current的中左右节点都入栈了,将current标识为true;将入栈的左右节点标识初始化为falsestep3:出栈出栈节点设置为current,如果current标识为ture,访问之;如果为false,做step2步骤step4:重复step2&step3*/public void postOrder( Node root){ //special case if(root==null) return; Node current=root; //initial stack Stack s=new Stack(); pushPostOrderNode(current,s); //pop and visit while( !s.empty() ){ current=s.pop(); if(current.bPushed) visit(current); else pushPostOrderNode(current,s); }//end while}//end postOrder()// 左右子树尚未入栈,则依次将 根节点,右节点,左节点 入栈private void pushPostOrderNode(Node current, Stack s){ if(current==null) return; if(!s.empty()){ leftChild=current.leftChild; rightChild=curret.rightChild; s.push(current); //push current if(rightChild!=null){ //push rightChild s.push(rightChild); rightChild.bPushed=false; }//end if if(leftChild!=null){ //push leftChild s.push(leftChild); rightChild.bPushed=false; }//end if //set flag, ture present current's left and right has both pushed current.bPushed=true; }//end if }//end if }//end pushPostOrderNode()
3 深度优先搜索和层次遍历(广度优先搜索)
// -------------------------------------------------------------/*二叉树的广度深度优先搜索即先序遍历,用栈实现(非递归实现)*/// -------------------------------------------------------------/*层次搜索,即广度优先搜索step1:specail caseroot==null;step2:initial currentcurrent=root;step3:initial queuestep4:remove node in queue, and visit the current nodestep5:add node in queuestep6:loop step4 and step5base case: queue is empty*/public void gfs(Noode root){ //step1:specail case if(root==null) return ; //step2:initial current Node current=root; //step3:initial queue Queue q=new Queue(); q.add(current); //step6:loop step4 and step5 //base case: queue is empty while( !q.empty() ){ //step4:remove node in queue current=q.remove(); visit(current); Node leftChild=current.leftChild; Node rightChild=curret.rightChild; //step5:add node in queue if(leftChild!=null) q.add(leftChild); if(rightChild!=null) q.add(rightChild); }//end while }//gfs()