數據結構之二叉樹

本文是數據結構和算法之美學習筆記

樹這種數據結構跟現實中的樹很像,裏面的每個元素叫做結點,用連線把相鄰的結點連接起來,相鄰結點之間的關係叫父子關係。

比如下圖中,A結點是B的父節點,B是A的子結點,B,C,D是兄弟結點,E沒有父節點稱為根節點,沒有子節點的結點是葉子結點,G,H,I,H,K,L都是葉子結點。

數據結構之二叉樹
數據結構之二叉樹

樹一般用三個概念可以描述,高度,深度,層

高度:結點到葉子結點的最長路徑(邊數)

深度:根結點到這個結點所經歷的邊的個數

層數:結點的深度加1

樹的高度:根結點的高度

數據結構之二叉樹
數據結構之二叉樹

高度是從下往上度量,就像數樓層。深度從上往下度量,就像往水下看,層數是跟深度類似,不過是以1為起點。

二叉樹

顧名思義,就是每個結點最多有兩個叉,也就是兩個葉子結點,左子節點和右子節點,左右子節點只要存在一個就行。

如果除了葉子結點外的每個結點都有左右兩個子節點,這種二叉樹叫“滿二叉樹”

如果葉子結點都在最底下兩層,最後一層的葉子結點都靠左排列,並且除了最後一層,其他的結點個數都要達到最大,這種二叉樹叫做“完全二叉樹”

如何存儲一個二叉樹?

可以使用基於指針的或者引用的二叉鏈式存儲法,或者基於數組的順序存儲法。

鏈式存儲法:

每個結點有三個字段,其中一個緩存數據,剩下的兩個分別是指向左右子節點的指針。我們只要找到根節點就能通過左右指針找到所有數據。

順序存儲法:

把根節點存儲在下標為i=1的位置,左子節點存儲在下標為2 i=2的位置,右子節點存儲在2 i+1=3的位置,以此類推。

對於順序存儲法來説,完全二叉樹更能節省內存。

二叉樹的遍歷

經典的方法有三種:前序遍歷,中序遍歷,後序遍歷。前中後表示的是結點本身打印的順序。

  • 前序遍歷是對於樹種的任意結點來説,先打印這個結點,然後在打印它的左子樹,最後打印它的右子樹
  • 中序遍歷是對於樹種任意結點來説,先打印它的左子樹,在打印它本身,最後打印它的右子樹
  • 後序遍歷是先對於樹種任意結點來説,先打印左子樹,在打印右子樹,最後打印結點本身。

其實二叉樹的前中後遍歷就是一個遞歸的過程。比如前序遍歷,就是先打印跟結點,然後遞歸打印左子樹,在遞歸打印右子樹。

遍歷方法:

void preOrder(Node* root) {
  if (root == null) return;
  System.out.print(root.data);
  preOrder(root->left);
  preOrder(root->right);
}

void inOrder(Node* root) {
  if (root == null) return;
  inOrder(root->left);
  System.out.print(root.data);
  inOrder(root->right);
}

void postOrder(Node* root) {
  if (root == null) return;
  postOrder(root->left);
  postOrder(root->right);
  System.out.print(root.data);
}

還有一種按層遍歷,這個需要用到隊列

public void levelOrder(BinaryTree tree) {
    // 利用隊列先入先出的特點來實現按層遍歷
    LinkedList<BinaryTree> linkedList = new LinkedList<>();
    // 記錄當前遍歷到哪個結點
    BinaryTree currentNode = tree;
    // 根節點入隊
    linkedList.add(currentNode);
    // 從隊列中彈出各結點數據,直到隊列為空,遍歷完畢
    while (linkedList.size()>0){
    // 彈出隊首元素(當前結點),打印其數據,並依次將其左右子節點入隊
      currentNode = linkedList.poll();
      System.out.print(currentNode.data+" -> ");
      if (currentNode.left!=null) {
        linkedList.add(currentNode.left);
      }
      if (currentNode.right!=null) {
        linkedList.add(currentNode.right);
      }
    }
  }

二叉樹最大的特點就是支持動態數據集合的快速插入、刪除、查找操作。

二叉查找樹(Binary Search Tree)

二叉查找樹也叫二叉搜索樹,是為了實現快速查找而生的,不過它不僅支持快速查找還支持快速插入刪除。

二叉查找樹規定:在樹中的任意一個節點,其左子樹的每個值都小於這個節點的值,右子樹的每個值都大於這個節點的值。

1.二叉查找樹的查找

先取根節點,如果它等於我們要查找的數據,那就返回,如果要查找的數據小於根節點的值,那就在左子樹中查找,反之就在右子樹中查找。

代碼:

public class BinarySearchTree {
  private Node tree;
  public Node find(int data) {
    Node p = tree;
    while (p != null) {
      if (data < p.data) p = p.left;
      else if (data > p.data) p = p.right;
      else return p;
    }
    return null;
  }

  public static class Node {
    private int data;
    private Node left;
    private Node right;

    public Node(int data) {
      this.data = data;
    }
  }
}

2.二叉查找樹的插入

新插入的數據一般都是在葉子節點,我們需要從根節點開始依次比較要插入的數據和節點的大小關係。如果要插入的數據比節點的數據大,並且節點的右子樹為空,就把數據插到右子節點的位置,如果不為空就在遞歸遍歷右子樹,直到找到插入的位置。如果要插入的數據比節點數值小並且節點的左子樹為空,就插入,不為空,遞歸遍歷左子樹直到找到插入位置。

代碼:

public void insert(int data) {
  if (tree == null) {
    tree = new Node(data);
    return;
  }
  Node p = tree;
  while (p != null) {
    if (data > p.data) {
      if (p.right == null) {
        p.right = new Node(data);
        return;
      }
      p = p.right;
    } else { // data < p.data
      if (p.left == null) {
        p.left = new Node(data);
        return;
      }
      p = p.left;
    }
  }
}

3.二叉查找樹的刪除

刪除操作比插入和查找操作麻煩一點

(1)如果要刪除的節點是葉子節點,我們只需更新父節點指向刪除節點的指針為null

(2)如果要刪除的節點只有一個子節點,我們只需要更新其父節點中指向要刪除節點的指針,讓它指向要刪除的節點的子節點就好了

(3)如果要刪除的節點有兩個子節點,我們需要找到這個節點的右子樹中的最小節點,或者這個節點的左子樹的最大節點,把它替換到要刪除的節點上。因為父節點的指針一定比所有左子樹的節點值大,比右子樹的節點的值

代碼:

public void delete(int data) {
  Node p = tree; // p 指向要刪除的節點,初始化指向根節點
  Node pp = null; // pp 記錄的是 p 的父節點
  while (p != null && p.data != data) {
    pp = p;
    if (data > p.data) p = p.right;
    else p = p.left;
  }
  if (p == null) return; // 沒有找到

  // 要刪除的節點有兩個子節點
  if (p.left != null && p.right != null) { // 查找右子樹中最小節點
    Node minP = p.right;
    Node minPP = p; // minPP 表示 minP 的父節點
    while (minP.left != null) {
      minPP = minP;
      minP = minP.left;
    }
    p.data = minP.data; // 將 minP 的數據替換到 p 中
    p = minP; // 下面就變成了刪除 minP 了
    pp = minPP;
  }

  // 刪除節點是葉子節點或者僅有一個子節點
  Node child; // p 的子節點
  if (p.left != null) child = p.left;
  else if (p.right != null) child = p.right;
  else child = null;

  if (pp == null) tree = child; // 刪除的是根節點
  else if (pp.left == p) pp.left = child;
  else pp.right = child;
}

中序遍歷二叉樹可以輸出有序的數據串行,並且非常高效。因此二叉查找樹也叫做二叉排序樹。

如果數據中有重複的數據怎麼辦?

(1)二叉查找樹中不僅會存儲一個數據,我們可以通過鏈表和支持動態擴容的數組,把相同的值存儲在同一個節點上。

(2)插入數據的時候,如果碰到一個節點的值與要插入的數據的值相同,就將這個要插入的數據放到這個節點的右子樹,也就是把它當成大於這個節點的值來處理。

當要查找數據的時候,遇到值相同的節點,不停止查找操作,而是繼續在右子樹中查找,直到遇到葉子節點停止。

刪除數據的時候,先找到每個要刪除的節點,然後按照前面的刪除方法依次刪除。