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

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

公司主營業(yè)務(wù)：做網(wǎng)站、成都網(wǎng)站制作、移動網(wǎng)站開發(fā)等業(yè)務(wù)。幫助企業(yè)客戶真正實現(xiàn)互聯(lián)網(wǎng)宣傳，提高企業(yè)的競爭能力。創(chuàng)新互聯(lián)是一支青春激揚、勤奮敬業(yè)、活力青春激揚、勤奮敬業(yè)、活力澎湃、和諧高效的團隊。公司秉承以“開放、自由、嚴謹、自律”為核心的企業(yè)文化，感謝他們對我們的高要求，感謝他們從不同領(lǐng)域給我們帶來的挑戰(zhàn)，讓我們激情的團隊有機會用頭腦與智慧不斷的給客戶帶來驚喜。創(chuàng)新互聯(lián)推出綏棱免費做網(wǎng)站回饋大家。

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

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

需要一個隊列，隊列里面放節(jié)點（從根節(jié)點開始），然后依次進行打印。

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）請實現(xiàn)一個函數(shù)按照之字形打印二叉樹，即第一行按照從左到右的順序打印，第二層按照從右至左的順序打印，第三行按照從左到右的順序打印，其他行以此類推。

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

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); //將元素插入指定位置（頭部），也就相當于倒序了
    }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é)點從左至右輸出。每一層輸出一行。

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

思路：因為我們要按層打印，所以需要設(shè)置標志量。

其次：我們需要三個集合：

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

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

第三個集合用于存放節(jié)點。

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é)點

  // 檢查是否為空
  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é)點
   {
    queue.add(treeNode.left);// 將左節(jié)點加入linkedList中
    start++; // 標志進入下一行
   }
   if (treeNode.right != null)
   {
    queue.add(treeNode.right);
    start++; // 標志進入下一行
   }

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

   }

  }

  return result;

 }

}

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

本文名稱：利用java如何實現(xiàn)遍歷二叉樹
文章URL：http://muchs.cn/article30/gppgpo.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供云服務(wù)器、定制開發(fā)、建站公司、虛擬主機、Google、標簽優(yōu)化

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請盡快告知，我們將會在第一時間刪除。文章觀點不代表本網(wǎng)站立場，如需處理請聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時需注明來源： 創(chuàng)新互聯(lián)

成都app開發(fā)公司