溫馨提示×

您好，登錄后才能下訂單哦！

密碼登錄×
登錄注冊(cè)×
其他方式登錄
點(diǎn)擊 登錄注冊(cè) 即表示同意《億速云用戶服務(wù)條款》

利用java如何實(shí)現(xiàn)遍歷二叉樹

發(fā)布時(shí)間：2020-11-18 15:20:53 來源：億速云 閱讀：124 作者：Leah 欄目：編程語言

這篇文章給大家介紹利用java如何實(shí)現(xiàn)遍歷二叉樹，內(nèi)容非常詳細(xì)，感興趣的小伙伴們可以參考借鑒，希望對(duì)大家能有所幫助。

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

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

需要一個(gè)隊(duì)列，隊(duì)列里面放節(jié)點(diǎn)（從根節(jié)點(diǎn)開始），然后依次進(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ù)按照之字形打印二叉樹，即第一行按照從左到右的順序打印，第二層按照從右至左的順序打印，第三行按照從左到右的順序打印，其他行以此類推。

解析：之字形打印二叉樹，不要將所有層放入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）從上到下按層打印二叉樹，同一層結(jié)點(diǎn)從左至右輸出。每一層輸出一行。

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

思路：因?yàn)槲覀円磳哟蛴。孕枰O(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í)也就是說明把一層已經(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;

 }

}

關(guān)于利用java如何實(shí)現(xiàn)遍歷二叉樹就分享到這里了，希望以上內(nèi)容可以對(duì)大家有一定的幫助，可以學(xué)到更多知識(shí)。如果覺得文章不錯(cuò)，可以把它分享出去讓更多的人看到。

向AI問一下細(xì)節(jié)

免責(zé)聲明：本站發(fā)布的內(nèi)容（圖片、視頻和文字）以原創(chuàng)、轉(zhuǎn)載和分享為主，文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng)，如果涉及侵權(quán)請(qǐng)聯(lián)系站長(zhǎng)郵箱：is@yisu.com進(jìn)行舉報(bào)，并提供相關(guān)證據(jù)，一經(jīng)查實(shí)，將立刻刪除涉嫌侵權(quán)內(nèi)容。

AI
助
手