程式師世界 >> 編程語言 >> .NET網頁編程 >> C# >> C#入門知識 >> 數據結構-二叉樹和二叉查找樹

數據結構-二叉樹和二叉查找樹

編輯：C#入門知識

數據結構-二叉樹和二叉查找樹

先按樹-二叉樹-二叉查找樹的順序解釋會比較清楚。

一，樹

樹（Tree）是n（n≥0）個結點的有限集。在任意一棵非空樹中：

（1）有且僅有一個特定的被稱為根（Root）的結點；

（2）當n>1時，其余結點可分為m（m>0）個互不相交的有限集T1，T2，…，Tm，其中每一個集合本身又是一棵樹，並且稱為根的子樹（SubTree）。

結點的度（Degree）：結點擁有的子樹數稱為結點的度（Degree）。度為0的結點稱為葉子（Leaf）或終端結點。度不為0的結點稱為非終端結點或分支結點。
樹的度：是樹內各結點的度的最大值。
孩子和雙親：結點的子樹的根稱為該結點的孩子（Child），相應地，該結點稱為孩子的雙親（Parent）。
結點的層次（Level）：是從根結點開始計算起，根為第一層，根的孩子為第二層，依次類推。樹中結點的最大層次稱為樹的深度（Depth）或高度。

如果將樹中結點的各子樹看成從左至右是有次序的（即不能互換），則稱該樹為有序樹，否則稱為無序樹。

二，二叉樹

二叉樹（Binary Tree）的特點是每個結點至多具有兩棵子樹（即在二叉樹中不存在度大於2的結點），並且子樹之間有左右之分。

二叉樹的性質：
（1）、在二叉樹的第i層上至多有2i-1個結點（i≥1）。
（2）、深度為k的二叉樹至多有2k-1個結點（k≥1）。
（3）、對任何一棵二叉樹，如果其終端結點數為n0，度為2的結點數為n2，則n0=n2+1。

有很多關於樹的術語，在這裡不做過多的文字解釋，不想畫圖了。下面我找了圖來說明，圖參考來自http://blog.csdn.net/u012152619/article/details/42059325，通過它可以直觀地理解樹的路徑、根、父節點、子節點、葉節點、子樹、層等概念

三，二叉查找樹（左<中<右）

我們從一種特殊的、使用很廣泛的二叉樹入手：二叉查找樹。

二叉查找樹的性質：

（1）、若它的左子樹不為空，則左子樹上所有結點的值均小於它的根結點的值；
（2）、若它的右子樹不為空，則右子樹上所有結點的值均大於它的根結點的值；
（3）、它的左、右子樹也分別為二叉查找樹。
用一句話概括,二叉查找樹的特點是，一個節點的左子節點的關鍵字值小於這個節點，右子節點的關鍵字值大於或等於這個父節點。

二叉查找樹的基本操作是查找，插入，刪除，遍歷，下面一一介紹：

1，查找（search）

我們已經知道，二叉搜索樹的特點是左子節點小於父節點，右子節點大於或等於父節點。查找某個節點時，先從根節點入手，如果該元素值小於根節點，則轉向左子節點，否則轉向右子節點，以此類推，直到找到該節點，或者到最後一個葉子節點依然沒有找到，則證明樹中沒有該節點

代碼是：

  /** 查找元素，返回true */
  public boolean search(E e) {
    TreeNode current = root; // 從根元素開始

    while (current != null) {
      if (e.compareTo(current.element) < 0) {//如果比當前元素值小，就指向當前元素的左子樹
        current = current.left;
      }
      else if (e.compareTo(current.element) > 0) {//如果比當前元素值大，就指向當前元素的右子樹
        current = current.right;
      }
      else // element等於 current.element
        return true; //發現元素，返回true
    }

    return false;
  }

2，插入（insert）

插入一個新節點首先要確定插入的位置，關鍵思路是確定新節點父節點所在的位置。

代碼：

/** 插入元素，成功返回true */
  public boolean insert(E e) {
    if (root == null)
      root = createNewNode(e); // 如果是樹空則創造一個跟節點
    else {
      // 標記當前父節點位置
      TreeNode parent = null;
      TreeNode current = root;
      while (current != null)
        if (e.compareTo(current.element) < 0) {
          parent = current;
          current = current.left;
        }
        else if (e.compareTo(current.element) > 0) {
          parent = current;
          current = current.right;
        }
        else
          return false; // 有重復節點，不能被插入

      // 創建一個新節點掛在父節點下
       if (e.compareTo(parent.element) < 0)
        parent.left = createNewNode(e);
       else
        parent.right = createNewNode(e);
    }

    size++;
    return true; // 插入成功
  }

3，刪除（delete）
刪除BST中的一個節點是最麻煩的操作，總結一下大概下面兩種方法：

Case 1：刪除點沒有左孩子，這是只需要將該節點的父節點和當前節點的有孩子相連即可

Case2：刪除點有左孩子.這種情況下先找到當前節點的左子樹的最右節點，因為一個節點的左子樹的最右節點也比右子樹的最左節點小，把最右節點復制給刪除點，然後刪除最右節點

代碼：

 /** 刪除節點，刪除成功返回true，不在樹中返回false*/
  public boolean delete(E e) {
    // 標記被刪除的節點和該節點的父節點位置
    TreeNode parent = null; 
    TreeNode current = root;
    while (current != null) {
      if (e.compareTo(current.element) < 0) {
        parent = current;
        current = current.left;
      }
      else if (e.compareTo(current.element) > 0) {
        parent = current;
        current = current.right;
      }
      else
        break; // 元素在這個樹中
    }

    if (current == null)
      return false; // 元素不在樹中

    
    if (current.left == null) { // 第一種情況：元素沒有左子樹，把當前節點的右子樹直接掛在其父節點的右子樹上
      // 把當前節點的右子樹直接掛在其父節點的右子樹上
      if (parent == null) {
        root = current.right;
      }
      else {
        if (e.compareTo(parent.element) < 0)
          parent.left = current.right;
        else
          parent.right = current.right;
      }
    }
    else {  // 第二種情況：元素有左子樹，先找到當前節點的左子樹的最右節點
     
      //標記當前節點的左子樹的父節點和最右節點
      TreeNode parentOfRightMost = current;
      TreeNode rightMost = current.left;
      
      //一直向右，找到最右端的節點，因為一個節點的左子樹的最右節點也比右子樹的最左節點小
      while (rightMost.right != null) {
        parentOfRightMost = rightMost;
        rightMost = rightMost.right; // 一直向右
      }
   /*
    * 以上代碼的目的是要找到刪除節點的左子樹最右節點 ，因為一個節點的左子樹的最右節點也比右子樹的最左節點小*/
      
      
      // 找到最右節點後，放到當前要刪除的位置
      current.element = rightMost.element;

      // 消除最右節點
      if (parentOfRightMost.right == rightMost)
        parentOfRightMost.right = rightMost.left;//把最右節點的左子樹掛在其父節點的右子樹上
      else
        // 具體情況: parentOfRightMost == current
        parentOfRightMost.left = rightMost.left;     
    }

    size--;
    return true; // 刪除成功
  }

下面介紹一下二叉樹的構成：

Tree.java

package com.hust.cn;
public interface Tree> {
  //查找元素 
  public boolean search(E e);
  //插入元素
  public boolean insert(E e);
  //刪除元素
  public boolean delete(E e);

  
  //中序遍歷
  public void inorder();
  //後序遍歷
  public void postorder();
  //前序遍歷
  public void preorder();

  
  //返回大小
  public int getSize();
  //判空
  public boolean isEmpty();
  //返回樹的迭代器
  public java.util.Iterator iterator();
}

AbstractTree.java

package com.hust.cn;
public abstract class AbstractTree>
    implements Tree {
	//中序遍歷
  public void inorder() {
  }

  //後序遍歷
  public void postorder() {
  }

  //前序遍歷
  public void preorder() {
  }

  //判空
  public boolean isEmpty() {
    return getSize() == 0;
  }

  //返回樹的迭代器
  public java.util.Iterator iterator() {
    return null;
  }
}

BinaryTree.java

package com.hust.cn;
public class BinaryTree>
    extends AbstractTree {
  protected TreeNode root;//節點類，是內部類
  protected int size = 0;

  /** 構造函數 */
  public BinaryTree() {
  }

  /** 對象數組創建一個二叉查找樹 */
  public BinaryTree(E[] objects) {
    for (int i = 0; i < objects.length; i++)
      insert(objects[i]);
  }

  /** 查找元素，返回true */
  public boolean search(E e) {
    TreeNode current = root; // 從根元素開始

    while (current != null) {
      if (e.compareTo(current.element) < 0) {//如果比當前元素值小，就指向當前元素的左子樹
        current = current.left;
      }
      else if (e.compareTo(current.element) > 0) {//如果比當前元素值大，就指向當前元素的右子樹
        current = current.right;
      }
      else // element等於 current.element
        return true; //發現元素，返回true
    }

    return false;
  }

  /** 插入元素，成功返回true */
  public boolean insert(E e) {
    if (root == null)
      root = createNewNode(e); // 如果是樹空則創造一個跟節點
    else {
      // 標記當前父節點位置
      TreeNode parent = null;
      TreeNode current = root;
      while (current != null)
        if (e.compareTo(current.element) < 0) {
          parent = current;
          current = current.left;
        }
        else if (e.compareTo(current.element) > 0) {
          parent = current;
          current = current.right;
        }
        else
          return false; // 有重復節點，不能被插入

      // 創建一個新節點掛在父節點下
       if (e.compareTo(parent.element) < 0)
        parent.left = createNewNode(e);
       else
        parent.right = createNewNode(e);
    }

    size++;
    return true; // 插入成功
  }
  /*創建一個新節點*/
  protected TreeNode createNewNode(E e) {
    return new TreeNode(e);
  }

  /** 中序遍歷*/
  public void inorder() {
    inorder(root);
  }

  /** 從根節點中序遍歷 ，遞歸方法*/
  protected void inorder(TreeNode root) {
    if (root == null) return;
    inorder(root.left);
    System.out.print(root.element + " ");
    inorder(root.right);
  }

  /**後序遍歷 */
  public void postorder() {
    postorder(root);
  }

  /**從根節點後序遍歷，遞歸方法 */
  protected void postorder(TreeNode root) {
    if (root == null) return;
    postorder(root.left);
    postorder(root.right);
    System.out.print(root.element + " ");
  }

  /**前序遍歷 */
  public void preorder() {
    preorder(root);
  }

  /** 從根節點前序遍歷，遞歸方法 */
  protected void preorder(TreeNode root) {
    if (root == null) return;
    System.out.print(root.element + " ");
    preorder(root.left);
    preorder(root.right);
  }

  /** 返回樹的大小 */
  public int getSize() {
    return size;
  }

  /** 返回根節點 */
  public TreeNode getRoot() {
    return root;
  }

  /** 返回從根節點到一個具體元素的路徑 */
  public java.util.ArrayList> path(E e) {
    java.util.ArrayList> list =
      new java.util.ArrayList>();//用數組存放路徑上的元素
    TreeNode current = root; // 從根節點開始

    while (current != null) {
      list.add(current); // 添加當前元素到數組裡
      if (e.compareTo(current.element) < 0) {
        current = current.left;
      }
      else if (e.compareTo(current.element) > 0) {
        current = current.right;
      }
      else
        break;
    }

    return list; // 返回節點數組
  }

  /** 刪除節點，刪除成功返回true，不在樹中返回false*/
  public boolean delete(E e) {
    // 標記被刪除的節點和該節點的父節點位置
    TreeNode parent = null; 
    TreeNode current = root;
    while (current != null) {
      if (e.compareTo(current.element) < 0) {
        parent = current;
        current = current.left;
      }
      else if (e.compareTo(current.element) > 0) {
        parent = current;
        current = current.right;
      }
      else
        break; // 元素在這個樹中
    }

    if (current == null)
      return false; // 元素不在樹中

    
    if (current.left == null) { // 第一種情況：元素沒有左子樹，把當前節點的右子樹直接掛在其父節點的右子樹上
      // 把當前節點的右子樹直接掛在其父節點的右子樹上
      if (parent == null) {
        root = current.right;
      }
      else {
        if (e.compareTo(parent.element) < 0)
          parent.left = current.right;
        else
          parent.right = current.right;
      }
    }
    else {  // 第二種情況：元素有左子樹，先找到當前節點的左子樹的最右節點
     
      //標記當前節點的左子樹的父節點和最右節點
      TreeNode parentOfRightMost = current;
      TreeNode rightMost = current.left;
      
      //一直向右，找到最右端的節點，因為一個節點的左子樹的最右節點也比右子樹的最左節點小
      while (rightMost.right != null) {
        parentOfRightMost = rightMost;
        rightMost = rightMost.right; // 一直向右
      }
   /*
    * 以上代碼的目的是要找到刪除節點的左子樹最右節點 ，因為一個節點的左子樹的最右節點也比右子樹的最左節點小*/
      
      
      // 找到最右節點後，放到當前要刪除的位置
      current.element = rightMost.element;

      // 消除最右節點
      if (parentOfRightMost.right == rightMost)
        parentOfRightMost.right = rightMost.left;//把最右節點的左子樹掛在其父節點的右子樹上
      else
        // 具體情況: parentOfRightMost == current
        parentOfRightMost.left = rightMost.left;     
    }

    size--;
    return true; // 刪除成功
  }

  /** 獲得中序迭代器 */
  public java.util.Iterator iterator() {
    return inorderIterator();
  }

  /**  創建一個迭代器類*/
  public java.util.Iterator inorderIterator() {
    return new InorderIterator();
  }

  // 中序迭代器類，內部類
  class InorderIterator implements java.util.Iterator {
    // 存儲元素的數組
    private java.util.ArrayList list =
      new java.util.ArrayList();
    private int current = 0; //數組中當前元素的位置

    public InorderIterator() {
      inorder(); // 中序遍歷二叉樹
    }

    /** 從根部中序遍歷*/
    private void inorder() {
      inorder(root);
    }

    /** 中序遍歷子樹 */
    private void inorder(TreeNode root) {
      if (root == null)return;
      inorder(root.left);
      list.add(root.element);
      inorder(root.right);
    }

    /** 遍歷下一個元素*/
    public boolean hasNext() {
      if (current < list.size())
        return true;

      return false;
    }

    /** 獲得當前元素，並把指針指向另一個元素 */
    public Object next() {
      return list.get(current++);
    }

    /** 移出當前元素 */
    public void remove() {
      delete(list.get(current)); //刪除當前元素
      list.clear(); //清理數組
      inorder(); //重新中序遍歷數組
    }
  }

  /** 清楚樹的所有元素 */
  public void clear() {
    root = null;
    size = 0;
  }
  
  

  /** 內部類，樹的節點類 */
  public static class TreeNode> {
    E element;
    TreeNode left;
    TreeNode right;

    public TreeNode(E e) {
      element = e;
    }
  }

}

TestBinaryTree.java

package com.hust.cn;
public class TestBinaryTree {
  public static void main(String[] args) {
    // 創建一個二叉查找樹
    BinaryTree tree = new BinaryTree();
    tree.insert("George");
    tree.insert("Michael");
    tree.insert("Tom");
    tree.insert("Adam");
    tree.insert("Jones");
    tree.insert("Peter");
    tree.insert("Daniel");

    // 遍歷樹
    System.out.println("Inorder (sorted): ");
    tree.inorder();
    System.out.println("\nPostorder: ");
    tree.postorder();
    System.out.println("\nPreorder: ");
    tree.preorder();
    System.out.println("\nThe number of nodes is " + tree.getSize());

    // 查找一個元素
    System.out.println("\nIs Peter in the tree? " + 
      tree.search("Peter"));

    // 從root到peter的一條路徑
    System.out.println("\nA path from the root to Peter is: ");
    java.util.ArrayList>  path 
      = tree.path("Peter");
    for (int i = 0; path != null && i < path.size(); i++)
      System.out.print(path.get(i).element + " ");
    
    //利用數組構建一個二叉查找樹，並中序遍歷
    Integer[] numbers = {2, 4, 3, 1, 8, 5, 6, 7};
    BinaryTree intTree = new BinaryTree(numbers);
    System.out.println("\nInorder (sorted): ");
    intTree.inorder();
  }
}

測試結果：