二叉查找樹詳解及C++實現

注：資料主要參考算法導論

二叉樹常被用作二叉查找樹和二叉堆。二叉查找樹是一種很特殊的二叉樹，弄懂了二叉查找樹，再研究二叉樹也就很容易了。

二叉排序樹（Binary Sort Tree）又稱二叉查找樹。它或者是一棵空樹；或者是具有下列性質的二叉樹： （1）若左子樹不空，則左子樹上所有結點的值均小於它的根結點的值；（2）若右子樹不空，則右子樹上所有結點的值均大於它的根結點的值； （3）左、右子樹也分別為二叉排序樹

無論是樹還是圖，我們經常需要遍歷所有的結點。對於二叉樹，一般都使用先序遍歷、中序遍歷和後序遍歷這三種方式。由於二叉查找樹的特性，先序跟後序沒有太多的意義。

INORDER-TREE-WALK (x)

If x NIL

then INORDER-TREE-WALK (left[x])
print key[x]
INORDER-TREE-WALK (right[x])

如果我們自己不想使用遞歸調用，可以自己實現一個棧，用循環來實現遍歷以提高效率。這種非遞歸調用的實現在以後的深度優先遍歷和廣度優先遍歷中詳細說明。

在樹中查找一個給定的關鍵字（k），可以用以下方式。通過傳遞樹根指針和關鍵字key，TREE-SEARCH返回指向包含關鍵字k的結點或返回NULL。

TREE-SEARCH(x, k)

If x = NIL or k = key[x]

then return x

If k < key[x]

then return TREE-SEARCH(left[x], k)

else return TREE-SEARCH(right[x], k)

用循環代替遞歸，大多數情況下效率要高一些。

同樣由於二叉查找樹的特性，我們很容易知道，要找出最小的值一頂是順著根結點，沿著各結點左孩子不斷搜索下去，直到最後一個。而最大值則是沿著右孩子一直搜索下去。

另外，二叉查找樹中很重要的兩個功能是插入和刪除結點。這裡假設所有結點的關鍵值都不相等。

插入功能實現簡單一些，只需要從根開始不斷去對比當前值和需要插入值的大小，來確定插入值的位置應該在哪裡。

如果要將新值v插入樹中，插入參數是結點Z， key[Z] = V

TREE-INSERT(T, Z)

y <- NIL

x <- root[T]

while x≠NIL

do y <- x

If key[z] <key[x]

then x <- left[x]

else x<-right[x]

p[z] <- y

if y = NIL

then root[T] <- z //空樹

else if key[z] < key[y]

then left[y] <- z

else right[y]<- z

刪除給定結點z會麻煩一些。有三種情況需要考慮。

1. 需要刪除的結點沒有左孩子和右孩子，即該結點為葉子結點
2. 需要刪除的結點只有左右孩子之一
3. 需要刪除的結點有左孩子和右孩子

對於情況1，可以直接刪除該結點。對於情況2，同樣可以直接刪除該結點，然後將它的孩子代替他的位置即可。需要注意的是情況3，因為左右孩子都存在，因為用誰來代替它的位置呢？

我們選用需要刪除結點的後繼結點y來代替它的位置。頂替z位置的結點關鍵值必須跟z最接近，那麼只有從結點z的前驅結點跟後繼結點中選擇。前驅結點是它的父節點，無法代替它的位置。所以只能選擇後繼結點，選用後繼結點的另一個原因是因為後繼結點y沒有左孩子。處理起來也很方便。

# P[z]是結點z的父親結點。如果未在結點中定義指向父親結點的指針，可用臨時指針保存

TREE-DELETE(T, Z)

If left[z] = NIL or right[z] = NIL

then y <- z

else y <- TREE-SUCCESSOR(z) //找到z的後繼結點

If left[y] ≠ NIL //判斷結點z是否有孩子，有則用x保存

then x <- left[y]

else x<- right[y]

If x ≠ NIL

then p[x] <- p[y] //如果x不是空，即y有孩子，將x的父親指針修改

If p[y] = NIL

then root[T] <- x //要刪除的結點是根

else if y = left[p[y]] //將父親指針值修改，作用是刪除該結點

then left[p[y]] <- x

else right[p[y]] <- x

If y ≠ z //情況3，用y的key值替換z的key值

then key[z] <- key[y]

Copy y’s satellite data into z

return y

上述過程首先刪除一個結點，如果是情況3，刪除的是後繼結點，需要用後繼結點的值去覆蓋真正需要刪除的結點的值。

頭文件 binaryTree.h:

#ifndef __BINARYTREE_H__ #define __BINARYTREE_H__ namespace binarytree { template<typename Element> class CTreeNode { public: Element key; CTreeNode<Element> *lchild; CTreeNode<Element> *rchild; CTreeNode(Element value):key(value),lchild(NULL), rchild(NULL){}; ~CTreeNode(){lchild = NULL; rchild = NULL;}; }; template <typename Element> class CBinaryTree { public: CBinaryTree(); ~CBinaryTree(); bool treeEmpty(); //樹是否為空 bool insertElement(Element value); //插入元素 void inorderTree(CTreeNode<Element> *root); //中序遍歷 CTreeNode<Element> * minValue(CTreeNode<Element> * root); //返回最小值結點 CTreeNode<Element> * maxValue(CTreeNode<Element> * root); //返回最大值結點 CTreeNode<Element> * search( Element value); //查找元素 bool deleteValue(Element value); //刪除元素 CTreeNode<Element> * parent(CTreeNode<Element> * child); //查找父結點 CTreeNode<Element> * postNode(CTreeNode<Element> * node); //後繼結點 public: CTreeNode<Element> *root; }; } #endif

實現文件 binaryTree.cpp

#include "binaryTree.h"

using namespace binarytree;

template<typename Element>
CBinaryTree<Element>::CBinaryTree()
{
    root = NULL;
}

template<typename Element>
CBinaryTree<Element>::~CBinaryTree()
{
    root = NULL;
}

template<typename Element>
bool CBinaryTree<Element>::treeEmpty()
{
    return root == NULL;
}

template<typename Element>
bool CBinaryTree<Element>::insertElement(Element value)
{
    CTreeNode<Element> *p = root;
    CTreeNode<Element> *q = NULL;
    while ( p != NULL )
    {
        q = p;
        if ( value < p->key )
            p = p->lchild;
        else 
            p = p->rchild;
    }
    if ( q == NULL )
    {
        root = new CTreeNode<Element>(value);
        return true;
    }
    else if ( value < q->key )
    {
        q->lchild = new CTreeNode<Element>(value);
        return true;
    }
    else
    {    
        q->rchild = new CTreeNode<Element>(value);
        return true;
    }
    return false;
}    

template<typename Element>
void CBinaryTree<Element>::inorderTree(CTreeNode<Element> *root)
{
    if ( root != NULL )
    {
        inorderTree(root->lchild);
        cout<<root->key<<endl;
        inorderTree(root->rchild);
    }
}

template<typename Element>
CTreeNode<Element> * CBinaryTree<Element>::search(Element value)
{
    CTreeNode<Element> *p = root;
    while ( p != NULL && p->key != value)
    {
        if ( value < p->key )
            p = p->lchild;
        else
            p = p->rchild;
    }
    return p;
}


template<typename Element>
CTreeNode<Element> * CBinaryTree<Element>::parent(CTreeNode<Element> * child)
{
    CTreeNode<Element> *p = root;
    CTreeNode<Element> *q = NULL;
    while ( p != NULL && p->key != child->key )
    {
        q = p;
        if( p->key > child->key )
        {
            p = p->lchild;
        }
        else
        {
            p = p->rchild;
        }
    }
    return q;
}

template<typename Element>
CTreeNode<Element> * CBinaryTree<Element>::minValue(CTreeNode<Element> * root)
{
    CTreeNode<Element> *p = root;
    while ( p->lchild != NULL)
    {
        p = p->lchild;
    }
    return p;
}

template<typename Element>
CTreeNode<Element> * CBinaryTree<Element>::maxValue(CTreeNode<Element> * root)
{
    CTreeNode<Element> *p = root;
    while ( p->rchild != NULL)
    {
        p = p->rchild;
    }
    return p;
}

template<typename Element>
CTreeNode<Element> * CBinaryTree<Element>::postNode(CTreeNode<Element> * node)
{
    if( node->rchild != NULL )
        return minValue(node->rchild);
    CTreeNode<Element> *p = node;
    CTreeNode<Element> *par = parent(p);
    while ( par != NULL && par->rchild == p )
    {
        p = par;
        par = parent(p);
    }
    return par;
}

template<typename Element>
bool CBinaryTree<Element>::deleteValue(Element Value)
{
    CTreeNode<Element> * p = search(Value);
    CTreeNode<Element> * q = NULL;
    CTreeNode<Element> * s = NULL;
    if ( p->lchild == NULL || p->rchild == NULL )
    {
        q = p;
    }
    else
        q = postNode(p);

    s = parent(q);
    if ( q->lchild != NULL )
    {
        if ( s != NULL && s->lchild == q )
            s->lchild = q->lchild;
        else if ( s != NULL && s->rchild == q )
            s->rchild = q->lchild;
    }
    else
    {
        if ( s != NULL && s->lchild == q )
            s->lchild = q->rchild;
        else if ( s != NULL && s->rchild == q )
            s->rchild = q->rchild;
    }

    if ( s == NULL )
        root->key = q->key;

    if ( q != p )
        p->key = q->key;

    delete q;
    return true;
} 

主函數

#include <iostream>
#include "binaryTree.h"
#include "binaryTree.cpp"
using namespace binarytree;
using namespace std;

int main()
{
    CBinaryTree<int> m_bTree;
    
    m_bTree.insertElement(15);
    m_bTree.insertElement(5);
    m_bTree.insertElement(3);
    m_bTree.insertElement(12);
    m_bTree.insertElement(13);
    m_bTree.insertElement(10);
    m_bTree.insertElement(6);
    m_bTree.insertElement(7);
    m_bTree.insertElement(16);
    m_bTree.insertElement(20);
    m_bTree.insertElement(18);
    m_bTree.insertElement(23);
    m_bTree.deleteValue(5);
    
    m_bTree.inorderTree(m_bTree.root);
    system("pause");
    return 1;
}