java二叉樹(shù)的幾種遍歷遞歸與非遞歸實(shí)現(xiàn)代碼

更新時(shí)間：2020年12月04日 18:45:44 作者：zlp1992

這篇文章主要介紹了java二叉樹(shù)的幾種遍歷遞歸與非遞歸實(shí)現(xiàn)代碼,需要的朋友可以參考下

前序（先序）遍歷
中序遍歷
后續(xù)遍歷
層序遍歷

如圖二叉樹(shù)：

二叉樹(shù)結(jié)點(diǎn)結(jié)構(gòu)

public class TreeNode {
  int val;
  TreeNode left;
  TreeNode right;
  TreeNode(int x){
    val=x;
  }
  @Override
  public String toString(){
    return "val: "+val;
  }
}

訪問(wèn)函數(shù)

  public void visit(TreeNode node){
    System.out.print(node.val+" ");
  }

前序遍歷

對(duì)于圖中二叉樹(shù)而言其前序遍歷結(jié)果為：6 2 0 1 4 5 8 9
二叉樹(shù)的前序遍歷即先遍歷根結(jié)點(diǎn)再遍歷左結(jié)點(diǎn)最后遍歷右結(jié)點(diǎn)，使用遞歸如下：

  /**
   * 遞歸先序遍歷
   * */
  public void preOrderRecursion(TreeNode node){
    if(node==null) //如果結(jié)點(diǎn)為空則返回
      return;
    visit(node);//訪問(wèn)根節(jié)點(diǎn)
    preOrderRecursion(node.left);//訪問(wèn)左孩子
    preOrderRecursion(node.right);//訪問(wèn)右孩子
  }

非遞歸：

利用棧來(lái)實(shí)現(xiàn)二叉樹(shù)的先序非遞歸遍歷

  /**
   * 非遞歸先序遍歷二叉樹(shù)
   * */
  public List<Integer> preorderTraversal(TreeNode root) {
    List<Integer> resultList=new ArrayList<>();
    Stack<TreeNode> treeStack=new Stack<>();
    if(root==null) //如果為空樹(shù)則返回
      return resultList;
    treeStack.push(root);
    while(!treeStack.isEmpty()){
      TreeNode tempNode=treeStack.pop(); 
      if(tempNode!=null){
        resultList.add(tempNode.val);//訪問(wèn)根節(jié)點(diǎn)
        treeStack.push(tempNode.right); //入棧右孩子
        treeStack.push(tempNode.left);//入棧左孩子
      }
    }
    return resultList;
  }

更新：評(píng)論里有人說(shuō)不理解非遞歸的先序遍歷，其實(shí)你舉個(gè)例子，然后畫(huà)個(gè)圖就可以理解了，以上圖中的二叉樹(shù)為例，先將6入棧，此時(shí)List為空，Stack只有一個(gè)元素6，進(jìn)入while循環(huán)，彈出棧頂加入List，將6的右孩子和左孩子入棧，此時(shí)Stack從棧底到棧頂元素為8,2，List元素為6，由于棧不為空，進(jìn)入while循環(huán)，彈出棧頂2,將2加入List,同時(shí)將2的右孩子和左孩子分別入棧，此時(shí)Stack從棧底到棧頂?shù)脑貫?,4,0, List的元素為6,2，由于棧不為空再次進(jìn)入while循環(huán)…依次下去，彈出0加入List，入棧1,null，此時(shí)Stack從棧底到棧頂為8,4,1,null，List為6,2,0，彈出null為空繼續(xù)彈出1，如此下去就可以了…

中序遍歷

對(duì)于二叉樹(shù)的中序遍歷，即先訪問(wèn)左結(jié)點(diǎn)再訪問(wèn)根節(jié)點(diǎn)最后訪問(wèn)右結(jié)點(diǎn)

遞歸方法如下：

  /**
   * 遞歸中序遍歷
   * */
  public void preOrderRecursion(TreeNode node){
    if(node==null) //如果結(jié)點(diǎn)為空則返回
      return;
    preOrderRecursion(node.left);//訪問(wèn)左孩子
    visit(node);//訪問(wèn)根節(jié)點(diǎn)
    preOrderRecursion(node.right);//訪問(wèn)右孩子
  }

非遞歸：

在上圖中的二叉樹(shù)，其中序遍歷為：0 1 2 4 5 6 8 9
可以看到，二叉樹(shù)的中序遍歷如下：
先將根節(jié)點(diǎn)入棧，
一直往其左孩子走下去，將左孩子入棧，直到該結(jié)點(diǎn)沒(méi)有左孩子，則訪問(wèn)這個(gè)結(jié)點(diǎn)，如果這個(gè)結(jié)點(diǎn)有右孩子，則將其右孩子入棧，重復(fù)找左孩子的動(dòng)作，這里有個(gè)要判斷結(jié)點(diǎn)是不是已經(jīng)被訪問(wèn)的問(wèn)題。
非遞歸中序遍歷（效率有點(diǎn)低），使用map（用set貌似更合理）來(lái)判斷結(jié)點(diǎn)是否已經(jīng)被訪問(wèn)

  /**
   * 非遞歸中序遍歷
   * */
  public List<Integer> inorderTraversalNonCur(TreeNode root) {
    List<Integer> visitedList=new ArrayList<>();
    Map<TreeNode,Integer> visitedNodeMap=new HashMap<>();//保存已訪問(wèn)的節(jié)點(diǎn)
    Stack<TreeNode> toBeVisitedNodes=new Stack<>();//待訪問(wèn)的節(jié)點(diǎn)
    if(root==null)
      return visitedList;
    toBeVisitedNodes.push(root);
    while(!toBeVisitedNodes.isEmpty()){
      TreeNode tempNode=toBeVisitedNodes.peek(); //注意這里是peek而不是pop
      while(tempNode.left!=null){ //如果該節(jié)點(diǎn)的左節(jié)點(diǎn)還未被訪問(wèn)，則需先訪問(wèn)其左節(jié)點(diǎn)
        if(visitedNodeMap.get(tempNode.left)!=null) //該節(jié)點(diǎn)已經(jīng)被訪問(wèn)（不存在某個(gè)節(jié)點(diǎn)已被訪問(wèn)但其左節(jié)點(diǎn)還未被訪問(wèn)的情況）
          break;
        toBeVisitedNodes.push(tempNode.left);
        tempNode=tempNode.left;
      }
      tempNode=toBeVisitedNodes.pop();//訪問(wèn)節(jié)點(diǎn)
      visitedList.add(tempNode.val);
      visitedNodeMap.put(tempNode, 1);//將節(jié)點(diǎn)加入已訪問(wèn)map
      if(tempNode.right!=null) //將右結(jié)點(diǎn)入棧
        toBeVisitedNodes.push(tempNode.right);
    }
    return visitedList;
  }

Discuss中有人給出更簡(jiǎn)潔的方法

public List<Integer> inorderTraversal(TreeNode root) {
  List<Integer> list = new ArrayList<Integer>();

  Stack<TreeNode> stack = new Stack<TreeNode>();
  TreeNode cur = root;

  while(cur!=null || !stack.empty()){
    while(cur!=null){
      stack.add(cur);
      cur = cur.left;
    }
    cur = stack.pop();
    list.add(cur.val);
    cur = cur.right;
  }

  return list;
}

后序遍歷

遞歸代碼就不貼了

如果之前的非遞歸中序遍歷使用map的方法理解后，后序遍歷的話我們也可以使用一個(gè)map來(lái)保存那些已經(jīng)被訪問(wèn)的結(jié)點(diǎn)，后序遍歷即先訪問(wèn)左孩子再訪問(wèn)右孩子最后訪問(wèn)根結(jié)點(diǎn)。
非遞歸代碼：

  /**
   * 非遞歸后序遍歷
   * */
  public List<Integer> postOrderNonCur(TreeNode root){
    List<Integer> resultList=new ArrayList<>();
    if(root==null)
      return resultList;
    Map<TreeNode,Integer> visitedMap=new HashMap<>();
    Stack<TreeNode> toBeVisitedStack=new Stack<>();
    toBeVisitedStack.push(root);
    while(!toBeVisitedStack.isEmpty()){
      TreeNode tempNode=toBeVisitedStack.peek(); //注意這里是peek而不是pop
      if(tempNode.left==null && tempNode.right==null){ //如果沒(méi)有左右孩子則訪問(wèn)
        resultList.add(tempNode.val);
        visitedMap.put(tempNode, 1);
        toBeVisitedStack.pop();
        continue;
      }else if(!((tempNode.left!=null&&visitedMap.get(tempNode.left)==null )|| (tempNode.right!=null && visitedMap.get(tempNode.right)==null))){
        //如果節(jié)點(diǎn)的左右孩子均已被訪問(wèn)      
        resultList.add(tempNode.val);
        toBeVisitedStack.pop();
        visitedMap.put(tempNode, 1);
        continue;
      }
      if(tempNode.left!=null){
        while(tempNode.left!=null && visitedMap.get(tempNode.left)==null){//左孩子沒(méi)有被訪問(wèn)
          toBeVisitedStack.push(tempNode.left);
          tempNode=tempNode.left;
        }
      }
      if(tempNode.right!=null){
        if(visitedMap.get(tempNode.right)==null){//右孩子沒(méi)有被訪問(wèn)
          toBeVisitedStack.push(tempNode.right);
        }        
      }
    }
    return resultList;
  }

Discuss中有人給出了一個(gè)”巧“的方法，即先采用類似先序遍歷，先遍歷根結(jié)點(diǎn)再右孩子最后左孩子（先序是先根結(jié)點(diǎn)再左孩子最后右孩子），最后把遍歷的序列逆轉(zhuǎn)即得到了后序遍歷

public List<Integer> postorderTraversal(TreeNode root) {
  Deque<TreeNode> stack = new LinkedList<>();
  stack.push(root);
  List<Integer> ret = new ArrayList<>();
  while (!stack.isEmpty()) {
    TreeNode node = stack.pop();
    if (node != null) {
      ret.add(node.val);
      stack.push(node.left);
      stack.push(node.right);
    }
  }
  Collections.reverse(ret);
  return ret;
}

層序遍歷

層序遍歷也即寬度優(yōu)先搜索，一層一層搜索，非遞歸代碼如下：

  public List<List<Integer>> levelOrder(TreeNode root) {
    List<List<Integer>> resultList=new ArrayList<>();
    int levelNum=0;//記錄某層具有多少個(gè)節(jié)點(diǎn)
    Queue<TreeNode> treeQueue=new LinkedList<>();
    treeQueue.add(root);
    while(!treeQueue.isEmpty()){
      levelNum=treeQueue.size();
      List<Integer> levelList=new ArrayList<>();
      while(levelNum>0){
        TreeNode tempNode=treeQueue.poll();
        if(tempNode!=null){
          levelList.add(tempNode.val);
          treeQueue.add(tempNode.left); 
          treeQueue.add(tempNode.right);
        }
        levelNum--;
      }
      if(levelList.size()>0) 
        resultList.add(levelList);
    }
    return resultList;    
  }

到此這篇關(guān)于java二叉樹(shù)的幾種遍歷遞歸與非遞歸實(shí)現(xiàn)代碼的文章就介紹到這了,更多相關(guān)java二叉樹(shù)內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

您可能感興趣的文章: