Java實現(xiàn)二叉樹的深度優(yōu)先遍歷和廣度優(yōu)先遍歷算法示例

更新時間：2018年04月19日 15:02:31 作者：Fantasy_Lin_

這篇文章主要介紹了Java實現(xiàn)二叉樹的深度優(yōu)先遍歷和廣度優(yōu)先遍歷算法,結(jié)合實例形式詳細分析了二叉樹的定義、深度優(yōu)先遍歷與廣度優(yōu)先遍歷算法原理與相關(guān)操作實現(xiàn)技巧,需要的朋友可以參考下

本文實例講述了Java實現(xiàn)二叉樹的深度優(yōu)先遍歷和廣度優(yōu)先遍歷算法。分享給大家供大家參考，具體如下：

1. 分析

二叉樹的深度優(yōu)先遍歷的非遞歸的通用做法是采用棧，廣度優(yōu)先遍歷的非遞歸的通用做法是采用隊列。

深度優(yōu)先遍歷：對每一個可能的分支路徑深入到不能再深入為止，而且每個結(jié)點只能訪問一次。要特別注意的是，二叉樹的深度優(yōu)先遍歷比較特殊，可以細分為先序遍歷、中序遍歷、后序遍歷。具體說明如下：

先序遍歷：對任一子樹，先訪問根，然后遍歷其左子樹，最后遍歷其右子樹。

中序遍歷：對任一子樹，先遍歷其左子樹，然后訪問根，最后遍歷其右子樹。

后序遍歷：對任一子樹，先遍歷其左子樹，然后遍歷其右子樹，最后訪問根。

廣度優(yōu)先遍歷：又叫層次遍歷，從上往下對每一層依次訪問，在每一層中，從左往右（也可以從右往左）訪問結(jié)點，訪問完一層就進入下一層，直到?jīng)]有結(jié)點可以訪問為止。

2. 舉例說明

對下圖所示的二叉排序樹進行遍歷，要求使用先序遍歷（遞歸、非遞歸）、中序遍歷（遞歸、非遞歸）、后序遍歷（遞歸、非遞歸）和廣度優(yōu)先遍歷。

① 參考代碼

package BinaryTreeTraverseTest;
import java.util.LinkedList;
import java.util.Queue;
/**
 * 二叉樹的深度優(yōu)先遍歷和廣度優(yōu)先遍歷
 * @author Fantasy
 * @version 1.0 2016/10/05 - 2016/10/07
 */
public class BinaryTreeTraverseTest {
  public static void main(String[] args) {
  BinarySortTree<Integer> tree = new BinarySortTree<Integer>();
    tree.insertNode(35);
    tree.insertNode(20);
    tree.insertNode(15);
    tree.insertNode(16);
    tree.insertNode(29);
    tree.insertNode(28);
    tree.insertNode(30);
    tree.insertNode(40);
    tree.insertNode(50);
    tree.insertNode(45);
    tree.insertNode(55);
    System.out.print("先序遍歷（遞歸）：");
    tree.preOrderTraverse(tree.getRoot());
    System.out.println();
    System.out.print("中序遍歷（遞歸）：");
    tree.inOrderTraverse(tree.getRoot());
    System.out.println();
    System.out.print("后序遍歷（遞歸）：");
    tree.postOrderTraverse(tree.getRoot());
    System.out.println();
    System.out.print("先序遍歷（非遞歸）：");
    tree.preOrderTraverseNoRecursion(tree.getRoot());
    System.out.println();
    System.out.print("中序遍歷（非遞歸）：");
    tree.inOrderTraverseNoRecursion(tree.getRoot());
    System.out.println();
    System.out.print("后序遍歷（非遞歸）：");
    tree.postOrderTraverseNoRecursion(tree.getRoot());
    System.out.println();
    System.out.print("廣度優(yōu)先遍歷：");
    tree.breadthFirstTraverse(tree.getRoot());
  }
}
/**
 * 結(jié)點
 */
class Node<E extends Comparable<E>> {
  E value;
  Node<E> left;
  Node<E> right;
  Node(E value) {
    this.value = value;
    left = null;
    right = null;
  }
}
/**
 * 使用一個先序序列構(gòu)建一棵二叉排序樹（又稱二叉查找樹）
 */
class BinarySortTree<E extends Comparable<E>> {
  private Node<E> root;
  BinarySortTree() {
    root = null;
  }
  public void insertNode(E value) {
    if (root == null) {
      root = new Node<E>(value);
      return;
    }
    Node<E> currentNode = root;
    while (true) {
      if (value.compareTo(currentNode.value) > 0) {
        if (currentNode.right == null) {
          currentNode.right = new Node<E>(value);
          break;
        }
        currentNode = currentNode.right;
      } else {
        if (currentNode.left == null) {
          currentNode.left = new Node<E>(value);
          break;
        }
        currentNode = currentNode.left;
      }
    }
  }
  public Node<E> getRoot(){
    return root;
  }
  /**
   * 先序遍歷二叉樹（遞歸）
   * @param node
   */
  public void preOrderTraverse(Node<E> node) {
    System.out.print(node.value + " ");
    if (node.left != null)
      preOrderTraverse(node.left);
    if (node.right != null)
      preOrderTraverse(node.right);
  }
  /**
   * 中序遍歷二叉樹（遞歸）
   * @param node
   */
  public void inOrderTraverse(Node<E> node) {
    if (node.left != null)
      inOrderTraverse(node.left);
    System.out.print(node.value + " ");
    if (node.right != null)
      inOrderTraverse(node.right);
  }
  /**
   * 后序遍歷二叉樹（遞歸）
   * @param node
   */
  public void postOrderTraverse(Node<E> node) {
    if (node.left != null)
      postOrderTraverse(node.left);
    if (node.right != null)
      postOrderTraverse(node.right);
    System.out.print(node.value + " ");
  }
  /**
   * 先序遍歷二叉樹（非遞歸）
   * @param root
   */
  public void preOrderTraverseNoRecursion(Node<E> root) {
    LinkedList<Node<E>> stack = new LinkedList<Node<E>>();
    Node<E> currentNode = null;
    stack.push(root);
    while (!stack.isEmpty()) {
      currentNode = stack.pop();
      System.out.print(currentNode.value + " ");
      if (currentNode.right != null)
        stack.push(currentNode.right);
      if (currentNode.left != null)
        stack.push(currentNode.left);
    }
  }
  /**
   * 中序遍歷二叉樹（非遞歸）
   * @param root
   */
  public void inOrderTraverseNoRecursion(Node<E> root) {
    LinkedList<Node<E>> stack = new LinkedList<Node<E>>();
    Node<E> currentNode = root;
    while (currentNode != null || !stack.isEmpty()) {
      // 一直循環(huán)到二叉排序樹最左端的葉子結(jié)點（currentNode是null）
      while (currentNode != null) {
        stack.push(currentNode);
        currentNode = currentNode.left;
      }
      currentNode = stack.pop();
      System.out.print(currentNode.value + " ");
      currentNode = currentNode.right;
    }
  }
  /**
   * 后序遍歷二叉樹（非遞歸）
   * @param root
   */
  public void postOrderTraverseNoRecursion(Node<E> root) {
    LinkedList<Node<E>> stack = new LinkedList<Node<E>>();
    Node<E> currentNode = root;
    Node<E> rightNode = null;
    while (currentNode != null || !stack.isEmpty()) {
      // 一直循環(huán)到二叉排序樹最左端的葉子結(jié)點（currentNode是null）
      while (currentNode != null) {
        stack.push(currentNode);
        currentNode = currentNode.left;
      }
      currentNode = stack.pop();
      // 當前結(jié)點沒有右結(jié)點或上一個結(jié)點（已經(jīng)輸出的結(jié)點）是當前結(jié)點的右結(jié)點，則輸出當前結(jié)點
      while (currentNode.right == null || currentNode.right == rightNode) {
        System.out.print(currentNode.value + " ");
        rightNode = currentNode;
        if (stack.isEmpty()) {
          return; //root以輸出，則遍歷結(jié)束
        }
        currentNode = stack.pop();
      }
      stack.push(currentNode); //還有右結(jié)點沒有遍歷
      currentNode = currentNode.right;
    }
  }
  /**
   * 廣度優(yōu)先遍歷二叉樹，又稱層次遍歷二叉樹
   * @param node
   */
  public void breadthFirstTraverse(Node<E> root) {
    Queue<Node<E>> queue = new LinkedList<Node<E>>();
    Node<E> currentNode = null;
    queue.offer(root);
    while (!queue.isEmpty()) {
      currentNode = queue.poll();
      System.out.print(currentNode.value + " ");
      if (currentNode.left != null)
        queue.offer(currentNode.left);
      if (currentNode.right != null)
        queue.offer(currentNode.right);
    }
  }
}

② 輸出結(jié)果

先序遍歷（遞歸）：35 20 15 16 29 28 30 40 50 45 55
中序遍歷（遞歸）：15 16 20 28 29 30 35 40 45 50 55
后序遍歷（遞歸）：16 15 28 30 29 20 45 55 50 40 35
先序遍歷（非遞歸）：35 20 15 16 29 28 30 40 50 45 55
中序遍歷（非遞歸）：15 16 20 28 29 30 35 40 45 50 55
后序遍歷（非遞歸）：16 15 28 30 29 20 45 55 50 40 35
廣度優(yōu)先遍歷：35 20 40 15 29 50 16 28 30 45 55

更多關(guān)于java算法相關(guān)內(nèi)容感興趣的讀者可查看本站專題：《Java數(shù)據(jù)結(jié)構(gòu)與算法教程》、《Java操作DOM節(jié)點技巧總結(jié)》、《Java文件與目錄操作技巧匯總》和《Java緩存操作技巧匯總》

希望本文所述對大家java程序設(shè)計有所幫助。

您可能感興趣的文章: