數據結構與算法-基礎（七）完全二叉樹

2021 年 9 月 30 日
筆記
數據結構與算法

完全二叉樹判斷（判斷）

完全二叉樹的葉子節點只會出現最後兩層，且最後一層的葉子節點都靠左對齊。根據定義來看，度為 1 的節點只會在左子樹，度為 1 的節點要麼是 1 個，要麼是 0 個。

完全二叉樹屬於二叉樹，即每個節點的度最大為 2。

度：節點擁有 n 棵子樹，就是度為 n。

判斷完全二叉樹之前，需要先編寫是否是葉子節點的判斷，當節點的左右子節點都是 null 時，這個節點就是葉子節點

/**
 * 是否是葉子節點
 * 
 * 通過判斷是否 left 和 right 是否都為 null
 * 
 * @return
 */
public Boolean isLeaf() {
  return left == null && right == null;
}

下面是判斷是否是完全二叉樹的代碼：

/**
 * 是否是完整二叉樹
 * @return
 */
public boolean isComplete() {
  if (root == null) return false;
  Queue<Node<E>> queue = new LinkedList<>();
  queue.offer(root);

  // 是否是葉子節點標識，初始為 false
  boolean leaf = false;
  while (!queue.isEmpty()) {
    Node<E> node = queue.poll();
    // 上一個節點是葉子節點，當前節點不是葉子節點，返回 false
    if (leaf && !node.isLeaf()) return false;
    if (node.left != null) {
      queue.offer(node.left);
    } else if (node.right != null) {
      // 左子節點為 null，右子節點不為 null，返回 false
      return false;
    }

    if (node.right != null) {
      queue.offer(node.right);
    } else { // 後面遍歷的節點都必須是葉子節點
      leaf = true;
    }
  }
  return true;
}

樹的高度

接上節二叉樹基礎，這裡來詳細梳理一下樹的高度，先明確定義：

樹的高度：所有節點高度中的最大值
節點高度：從當前節點到最遠葉子節點的路徑上的節點總數。

遞歸求樹的高度

樹的高度就是根節點的高度，每一個節點的高度是它的左右子節點中最大的高度加上當前節點的高度（+1）。

所以求樹的高度，就是就根節點的高度。

/**
 * 樹的高度（遞歸）
 * @return
 */
public int height2() {
  // 求根節點的高度
  return height(root);
}

注意：凡是遞歸都要有結束遞歸的條件，這裡設置的條件是節點為 null。

// 求節點的高度（遞歸方法）
private int height(Node<E> node) {
  if (node == null) return 0;
  return 1 + Math.max(height(node.left), height(node.right));
}

非遞歸求樹的高度

這裡也可以用非遞歸的方式求樹的高度。主要的邏輯就是遍歷每一層的節點，當前層的節點都遍歷完時，樹的高度就增加 1，直到遍歷完所有的節點。這裡使用棧來處理遍歷節點。

需要注意的是，首先從根節點開始遍歷，根節點遍歷完的高度為 1。leverSide 記錄每一次遍歷節點，並遞減，當leverSide 為 0 時，高度就增加 1，並通過 queue.size() 來獲取下一層的節點數量。

/**
 * 樹的高度
 * @return
 */
public int height() {
  if (root == null) return 0;
  // 樹的高度
  int height = 0;
  // 每一層元素數量
  int leverSide = 1;
  Queue<Node<E>> queue = new LinkedList<>();
  queue.offer(root);
  while (!queue.isEmpty()) {
    Node<E> node = queue.poll();
    leverSide --;

    if (node.left != null) {
      queue.offer(node.left);
    }

    if (node.right != null) {
      queue.offer(node.right);
    }

    if (leverSide == 0) {
      height ++;
      // 下一層節點的數量
      leverSide = queue.size();
    }
  }
  return height;
}

Tags: 數據結構與算法