快捷導(dǎo)航

詳解java實(shí)現(xiàn)遍歷二叉樹(shù)的三種情況

更新時(shí)間：2017年04月27日 09:57:30 作者：linkinparkzlz

這篇文章主要介紹了java實(shí)現(xiàn)遍歷二叉樹(shù)的三種情況,小編覺(jué)得挺不錯(cuò)的，現(xiàn)在分享給大家，也給大家做個(gè)參考。一起跟隨小編過(guò)來(lái)看看吧

遍歷二叉樹(shù)，從上往下遍歷。但是同層節(jié)點(diǎn)可以從左向右遍歷，也可以從右向左遍歷（也就是之字型遍歷），其中，都需要隊(duì)列進(jìn)行實(shí)現(xiàn)。只是按照之字型稍微麻煩一些。

（1）從上往下打印出二叉樹(shù)的每個(gè)節(jié)點(diǎn)，同層節(jié)點(diǎn)從左至右打印。

需要一個(gè)隊(duì)列，隊(duì)列里面放節(jié)點(diǎn)（從根節(jié)點(diǎn)開(kāi)始），然后依次進(jìn)行打印。

import java.util.ArrayList;
import java.util.Queue;
import java.util.LinkedList;
class TreeNode{
 int val = 0;
 TreeNode left = null;
 TreeNode right = null;

 public TreeNode(int val){
  this.val = val;
 }
}

public class Solution {
  public ArrayList<Integer> PrintFromTopToBottom(TreeNode root) {
   ArrayList<Integer> list = new ArrayList<Integer>();
   if(root == null) 
    return list;
   Queue<TreeNode> queue = new LinkedList<TreeNode>();

   queue.add(root);
   while(!queue.isEmpty()){
    TreeNode t = queue.poll();
    list.add(t.val);
    if(t.left != null) queue.add(t.left);
    if(t.right != null) queue.add(t.right);
   }
   return list;
  }
}

（2）請(qǐng)實(shí)現(xiàn)一個(gè)函數(shù)按照之字形打印二叉樹(shù)，即第一行按照從左到右的順序打印，第二層按照從右至左的順序打印，第三行按照從左到右的順序打印，其他行以此類(lèi)推。

解析：之字形打印二叉樹(shù)，不要將所有層放入ArrayList中后再將偶數(shù)層進(jìn)行reverse()，這樣可以實(shí)現(xiàn)，但是數(shù)據(jù)量大的時(shí)候效率太低。

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
 class TreeNode {
 int val = 0;
 TreeNode left = null;
 TreeNode right = null;

 public TreeNode(int val) {
  this.val = val;

 }

}

public class Solution {
 public ArrayList<ArrayList<Integer> > Print(TreeNode pRoot) {
  ArrayList<ArrayList<Integer>> result=new ArrayList<ArrayList<Integer>>();
  if(pRoot==null){
   return result;
  }

  Queue<TreeNode> queue = new LinkedList<TreeNode>();
  int rows=1;
  queue.add(pRoot);
  while(!queue.isEmpty()){
   ArrayList<Integer> list=new ArrayList();
   int size=queue.size();
   for(int i=0;i<size;i++){
    TreeNode t=queue.poll();
    if(rows%2==0){
     list.add(0,t.val); //將元素插入指定位置（頭部），也就相當(dāng)于倒序了
    }else{
     list.add(t.val); //將元素插入尾部
    }
    if(t.left!=null){
     queue.offer(t.left);
    }
    if(t.right!=null){
     queue.offer(t.right);
    }
   }
   result.add(list);
   rows++;
  }
  return result;

 }

}

（3）從上到下按層打印二叉樹(shù)，同一層結(jié)點(diǎn)從左至右輸出。每一層輸出一行。

這道題就是典型的二叉樹(shù)層次遍歷。

思路：因?yàn)槲覀円磳哟蛴?，所以需要設(shè)置標(biāo)志量。

其次：我們需要三個(gè)集合：

第一個(gè)集合用于存放結(jié)果集

第二個(gè)集合用于臨時(shí)存放每一層的結(jié)果，等到一層結(jié)束之后，再將其加入到最終結(jié)果集中。注意，每一次使用完這個(gè)集合之后，需要將其清空，以便下一次存放。

第三個(gè)集合用于存放節(jié)點(diǎn)。

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.*;

class TreeNode
{
 int val = 0;
 TreeNode left = null;
 TreeNode right = null;

 public TreeNode(int val)
 {
  this.val = val;

 }

}

public class Solution
{
 ArrayList<ArrayList<Integer>> Print(TreeNode pRoot)
 {

  ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();

  ArrayList<Integer> arrayList = new ArrayList<Integer>();

  Queue<TreeNode> queue = new LinkedList<TreeNode>(); // 存放節(jié)點(diǎn)

  // 檢查是否為空
  if (pRoot == null)
   return result;

  queue.add(pRoot);

  int start = 0;
  int end = 1; // 第一行

  while (!queue.isEmpty())
  {
   TreeNode treeNode = queue.poll();
   end--;
   arrayList.add(treeNode.val);

   if (treeNode.left != null) // 如果有左節(jié)點(diǎn)
   {
    queue.add(treeNode.left);// 將左節(jié)點(diǎn)加入linkedList中
    start++; // 標(biāo)志進(jìn)入下一行
   }
   if (treeNode.right != null)
   {
    queue.add(treeNode.right);
    start++; // 標(biāo)志進(jìn)入下一行
   }

   if (end == 0)
   { // 此時(shí)也就是說(shuō)明把一層已經(jīng)打印完了，應(yīng)該將其加入結(jié)果集中
    result.add(new ArrayList<Integer>(arrayList)); // 加入結(jié)果集中
    arrayList.clear();// 必須將臨時(shí)存放結(jié)果的集合清空，以便進(jìn)行下一次存放
    end = start; // 恢復(fù)原狀
    start = 0;

   }

  }

  return result;

 }

}

以上就是本文的全部?jī)?nèi)容，希望對(duì)大家的學(xué)習(xí)有所幫助，也希望大家多多支持腳本之家。

您可能感興趣的文章: