二叉查找樹

二叉查找樹是二叉樹中最常用的一種類型，也叫二叉搜索樹。

二叉查找樹要求，在樹中的任意一個(gè)節(jié)點(diǎn)，其左子的每個(gè)節(jié)點(diǎn)的值，都要小于這個(gè)節(jié)點(diǎn)的值，而右子樹節(jié)點(diǎn)的值都大于這個(gè)節(jié)點(diǎn)的值。

二叉查找樹

二叉查找樹的查找操作

1. 對(duì)比當(dāng)前節(jié)點(diǎn)（首個(gè)是根節(jié)點(diǎn)），相等則返回。
2. 大于則從右子樹查找
3. 小于則從左子樹查找
4. 直到葉子節(jié)點(diǎn)，如果不存在，則返回空，存在則返回。

查找

代碼實(shí)現(xiàn)：

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 class Node
    {
        public int data;
        public Node left;
        public Node right;
        public Node(int data)
        {
            this.data = data;
        }
    }
}

二叉查找樹的插入操作

插入操作有點(diǎn)類似查找操作。

1. 如果要插入的數(shù)據(jù)比當(dāng)前節(jié)點(diǎn)的數(shù)據(jù)大，并且節(jié)點(diǎn)的右子樹為空，則新數(shù)據(jù)直接插入右子節(jié)點(diǎn)的位置
2. 如果不為空，再遞歸遍歷右子樹，查找插入位置
3. 同理，插入的數(shù)據(jù)比當(dāng)前節(jié)點(diǎn)的數(shù)據(jù)要小，并且節(jié)點(diǎn)的左子樹為空，則插入左子節(jié)點(diǎn)的位置。
4. 如果不為空，再遞歸遍歷左子樹，查找插入位置。

插入

代碼實(shí)現(xiàn)：

public void Insert(int data)
{
    if (tree == null)
    {
        tree = new Node(data);
        return;
    }
    
    Insert(tree, data);
}
 
private void Insert(Node node, int data)
{
    if (data > node.data)
    {
        if (node.right == null)
            node.right = new Node(data);
        else
            Insert(node.right, data);
    }
    else if (data < node.data)
    {
        if (node.left == null)
            node.left = new Node(data);
        else
            Insert(node.left, data);
    }
}

二叉查找樹的刪除操作

相比二叉查找樹的查找和插入操作，刪除操作要復(fù)雜不少，有三種情況：

1. 情況一：刪除節(jié)點(diǎn)沒(méi)有沒(méi)有子節(jié)點(diǎn)，父節(jié)點(diǎn)的左節(jié)點(diǎn)（或右節(jié)點(diǎn)）設(shè)置為null。
2. 情況二：刪除節(jié)點(diǎn)只有一個(gè)子節(jié)點(diǎn)，父節(jié)點(diǎn)的左節(jié)點(diǎn)（或右節(jié)點(diǎn)）直接連接此葉子節(jié)點(diǎn)。
3. 情況三：刪除節(jié)點(diǎn)有兩個(gè)子節(jié)點(diǎn)，則查找刪除節(jié)點(diǎn)的右子樹的最小節(jié)點(diǎn)，替換到刪除節(jié)點(diǎn)的位置，然后再刪除掉這個(gè)最小節(jié)點(diǎn)。

刪除

代碼實(shí)現(xiàn)：

public void Delete(int data)
{
    Node p = tree;
    Node pp = null;
    while (p != null)
    {
        if (data < p.data)
        {
            pp = p;
            p = p.left;
        }
        else if (data > p.data)
        {
            pp = p;
            p = p.right;
        }
        else
        {
            break;
        }
    }

    if (p == null) return;

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


    // 刪除的是結(jié)點(diǎn)是葉子結(jié)點(diǎn)或僅有一個(gè)結(jié)點(diǎn)
    Node child;
    if (p.left != null) child = p.left;
    else if (p.right != null) child = p.right;
    else child = null;

    if (pp == null) tree = null;  // 如果pp=null，表示樹只有一個(gè)結(jié)點(diǎn)
    else if (pp.left == p) pp.left = child;
    else pp.right = child;
}

二叉查找樹的其他操作

除了插入、刪除、查找操作之外，二叉查找樹還可以支持快速查找最大節(jié)點(diǎn)和最早小節(jié)點(diǎn)、前驅(qū)節(jié)點(diǎn)和后繼節(jié)點(diǎn)。

另外還有一個(gè)重要的特性，就是中序遍歷二叉查找樹，可以輸出有序的數(shù)據(jù)序列，時(shí)間復(fù)雜度是O(n)。因此，二叉查找樹也叫作二叉排序樹。

二叉查找樹的時(shí)間復(fù)雜度分析

image

最壞情況，二叉查找樹退化成鏈表，時(shí)間復(fù)雜度為O(n)。

最好情況，二叉查找樹是完全二叉樹（或滿二叉樹），時(shí)間復(fù)雜度為O(height)。而完全二叉樹的高度是log2(n)，即時(shí)間復(fù)雜度是O(logn)。

課后思考

今天我講了二叉樹高度的理論分析方法，給出了粗略的數(shù)量級(jí)。如何通過(guò)編程，求出一棵給 定二叉樹的確切高度呢？

使用廣度遍歷，通過(guò)兩個(gè)隊(duì)列，一個(gè)記錄廣度遍歷的順序，一個(gè)記錄廣度遍歷的節(jié)點(diǎn)的高度。遍歷過(guò)程中，找到最大的高度。

代碼實(shí)現(xiàn)：

public int GetHeight()
{
    if (tree == null) return 0;

    // 廣度遍歷，通過(guò)兩個(gè)隊(duì)列，queueN記錄廣度遍歷的順序，queueH記錄queueN相對(duì)應(yīng)節(jié)點(diǎn)的高度
    Queue<Node> queueN = new Queue<Node>();
    Queue<int> queueH = new Queue<int>();

    queueN.Enqueue(tree);
    queueH.Enqueue(1);

    int maxHeight = 1;

    while (queueN.Count > 0)
    {
        Node p = queueN.Dequeue();

        int height = queueH.Dequeue();

        if (maxHeight < height) maxHeight = height;

        if (p.left != null) { queueN.Enqueue(p.left); queueH.Enqueue(height + 1); }
        if (p.right != null) { queueN.Enqueue(p.right); queueH.Enqueue(height + 1); }
    }

    return maxHeight;
}