一藕甩、二叉查找樹

前面一章分析了二分查找這種算法施敢。

要支持高效的插入操作，我們需要鏈?zhǔn)降臄?shù)據(jù)結(jié)構(gòu)狭莱，但是鏈表不能二分查找僵娃，因?yàn)橹虚g值需要從鏈表頭部開始尋找。為了將二分查找的效率和鏈表的靈活性結(jié)合起來(lái)腋妙，需要一種新的數(shù)據(jù)結(jié)構(gòu)默怨。
這種數(shù)據(jù)結(jié)構(gòu)就是二叉樹查找，它能夠?qū)㈡湵聿迦氲撵`活性和有序數(shù)組查找的高效性結(jié)合起來(lái)的符號(hào)表實(shí)現(xiàn)骤素。

要實(shí)現(xiàn)二叉樹匙睹，首先樹的結(jié)構(gòu)需要了解清楚，一般一個(gè)樹可以分為兩個(gè)部分：

樹根 ---> 樹節(jié)點(diǎn)

樹節(jié)點(diǎn)中又存儲(chǔ)著幾個(gè)部分：

存儲(chǔ)的Key值 -- 存儲(chǔ)的value值 -- 節(jié)點(diǎn)左孩子 -- 節(jié)點(diǎn)右孩子

// header.h
#ifndef JUNZALGHEADER_H_
#define JUNZALGHEADER_H_
#include <iostream>
#include <queue>
template<class T>
struct TreeNode
{
    T key;
    int data;
    TreeNode* leftChild = nullptr;
    TreeNode* rightChild = nullptr;
};

template<class T>
class BinaryTree
{
protected:
    TreeNode<T> * root;
public:
    BinaryTree();
//  BinaryTree(T k, int d, int n);
    void SetTreeRoot(const TreeNode<T> * r);
    void SetTreeNnum(int n);
    TreeNode<T>* getRoot() { return root; }

    // Ergodic
    void midOrder();
    void midOrder_ac(TreeNode<T> * currentNode);

    void preOrder();
    void preOrder_ac(TreeNode<T> * currentNode);

    void postOrder();
    void postOrder_ac(TreeNode<T> * currentNode);

    void layerOrder();

    void Show(TreeNode<T> * currentNode) const;
    // insert
    bool treeInsert(TreeNode<T> * currentNode);

    // find
    int treeFind(TreeNode<T> * currentNode);
};
#endif // !JUNZALGHEADER_H_

template<class T>
BinaryTree<T>::BinaryTree()
{
    root = NULL;
}

template<class T>
void BinaryTree<T>::SetTreeRoot(const TreeNode<T> * r)
{
    root = r;
    if (num == 0)
        num += 1;
    else
        num = 1;
}

template<class T>
void BinaryTree<T>::SetTreeNnum(int n)
{
    num = n;
}

template<class T>
void BinaryTree<T>::Show(TreeNode<T> * currentNode) const
{
    std::cout << currentNode->key;
}

template<class T>
void BinaryTree<T>::midOrder()
{
    midOrder_ac(root);
}

template<class T>
void BinaryTree<T>::midOrder_ac(TreeNode<T> * currentNode)
{
    if (currentNode)
    {
        midOrder_ac(currentNode->leftChild);
        Show(currentNode);
        midOrder_ac(currentNode->rightChild);
    }
    else
    {
        return;
    }
}

template<class T>
void BinaryTree<T>::preOrder()
{
    preOrder_ac(root);
}

template<class T>
void BinaryTree<T>::preOrder_ac(TreeNode<T> * currentNode)
{
    if (currentNode)
    {
        Show(currentNode);
        preOrder_ac(currentNode->leftChild);
        preOrder_ac(currentNode->rightChild);
    }
    else
        return;
}

template<class T>
void BinaryTree<T>::postOrder()
{
    postOrder_ac(root);
}

template<class T>
void BinaryTree<T>::postOrder_ac(TreeNode<T>* currentNode)
{
    if (currentNode)
    {
        postOrder_ac(currentNode->leftChild);
        postOrder_ac(currentNode->rightChild);
        Show(currentNode);
    }
    else
        return;
}

template<class T>
void BinaryTree<T>::layerOrder()
{
    std::queue<TreeNode<T>*> q;
    TreeNode<T> *currentNode = root;
    while (currentNode)
    {
        Show(currentNode);
        if(currentNode->leftChild)
            q.push(currentNode->leftChild);
        if(currentNode->rightChild)
            q.push(currentNode->rightChild);
        if (q.empty()) break;
        currentNode = q.front();
        q.pop();
    }
}

template<class T>
bool BinaryTree<T>::treeInsert(TreeNode<T> *currentNode)
{
    if (root == NULL)
    {
        root = currentNode;
        return true;
    }
    else
    {
        TreeNode<T> * NowNode = root;
        while (NowNode)
        {
            if (currentNode->key < NowNode->key)
            {
                if (NowNode->leftChild)
                {
                    NowNode = NowNode->leftChild;
                }
                    
                else
                {
                    NowNode->leftChild = currentNode;
                    break;
                }
            }
            else if (currentNode->key > NowNode->key)
            {
                if (NowNode->rightChild)
                    NowNode = NowNode->rightChild;
                else
                {
                    NowNode->rightChild = currentNode;
                    break;
                }
            }
            else
            {
                NowNode->data = currentNode->data;
                break;
            }
        }
        return true;
    }
}

template<class T>
int BinaryTree<T>::treeFind(TreeNode<T> *currentNode)
{

    if (root == NULL)
    {
        return -1;
    }
    else
    {
        TreeNode<T> *NowNode = root;
        while (NowNode)
        {
            if (currentNode->key == NowNode->key)
            {
                NowNode->data = currentNode->data;
                return NowNode->data;
            }
            else if (currentNode->key > NowNode->key)
                NowNode = NowNode->rightChild;
            else if (currentNode->key < NowNode->key)
                NowNode = NowNode->leftChild;
        }
        return NowNode->data;
    }
}

// main.cpp
#include<iostream>
#include "JunzAlgHeader.h"
using namespace std;
const int NUM = 7;
int main()
{
    BinaryTree<char> tree;
    TreeNode<char> temp[NUM];
    for (int i = 0; i < NUM; i++)
    {
        cout << "Add the treenode: \n";
        cout << "Key: (char)";
        cin >> (temp[i].key);
        cout << "Value:(int)";
        cin >> (temp[i].data);
        // tree insert
        tree.treeInsert(&temp[i]);
    }

    cout << "Middle Order Ergodic: \n";
    tree.midOrder();
    cout << endl;
    cout << "Layer Order Ergodic: \n";
    tree.layerOrder();
    cout << endl;

    cout << "Tree find:\n";
    TreeNode<char> temp1;
    temp1.data = 4;
    temp1.key = 'A';
    cout << tree.treeFind(&temp1) << endl;
    TreeNode<char> temp2;
    temp2.data = 2;
    temp2.key = 'A';
    cout << tree.treeFind(&temp2) <<endl;
    system("pause");
    return 0;
}

編寫這個(gè)程序是遇到一個(gè)問題：就是使用常規(guī)的頭文件聲明類及方法济竹、.cpp文件定義類方法痕檬、main函數(shù)執(zhí)行功能這個(gè)套路是行不通的，程序會(huì)報(bào)Linker Tools Error LNK2019的錯(cuò)誤送浊。
原因：采用的是特殊的模板類進(jìn)行代碼的編寫梦谜。

編譯器處理模板類時(shí)，如有一些模板類以及函數(shù)袭景，則會(huì)進(jìn)行如下操作唁桩。
1、模板函數(shù)和類在編譯時(shí)期間并未生成具體的二進(jìn)制代碼耸棒， 在main函數(shù)中也沒有嵌入這個(gè)類或函數(shù)的代碼朵夏，只是包含了一句 call +類名/函數(shù)名
2、編譯階段榆纽，在main函數(shù)中發(fā)現(xiàn)了模板類和的引用仰猖，但是main.obj

有序性相關(guān)方法和刪除操作

1捏肢、首先，我們可以獲取樹的最大鍵和最小鍵饥侵。

其思路非常簡(jiǎn)單鸵赫，最小鍵即處于樹最左邊的鍵，最大鍵即處于樹最右邊的鍵躏升。獲取最小鍵與最大鍵的方法我們可以采用遞歸來(lái)實(shí)現(xiàn)辩棒。

 // ac
    TreeNode<T> * Min_ac(TreeNode<T> *currentNode);
    TreeNode<T> * Max_ac(TreeNode<T> *currentNode);
// min & max find
    T & Min();
    T & Max();

// definition
//private Min methods
template<class T>
TreeNode<T>* BinaryTree<T>::Min_ac(TreeNode<T> * currentNode)
{
    if (currentNode->leftChild == NULL)
        return currentNode;
    return Min_ac(currentNode->leftChild);
}
//private Max methods
template<class T>
TreeNode<T>* BinaryTree<T>::Max_ac(TreeNode<T> * currentNode)
{
    if (currentNode->rightChild == NULL)
        return currentNode;
    return Max_ac(currentNode->rightChild);
}

// public Min
template<class T>
T & BinaryTree<T>::Min()
{
    return (Min_ac(root)->key);
}

//public Max
template<class T>
T & BinaryTree<T>::Max()
{
    return (Max_ac(root)->key);
}

2、向上取整和向下取整

在向下取整中膨疏，若需要判斷的鍵Key到達(dá)某個(gè)節(jié)點(diǎn)時(shí)一睁，它需要尋找該節(jié)點(diǎn)的左子樹，因?yàn)樾∮诘扔趉ey的鍵值就在該節(jié)點(diǎn)的左子樹中佃却。只有當(dāng)右子樹存在比Key小的鍵值時(shí)者吁，最大的小于等于鍵值的鍵才會(huì)出現(xiàn)在右子樹中。因此饲帅，利用這個(gè)思路复凳，可以寫出floor向下取整函數(shù)。當(dāng)然灶泵，向上取整就是把上述思路的左右對(duì)調(diào)一下育八。

// ac
    TreeNode<T> * floor_ac(TreeNode<T> *currentNode, T k);
    TreeNode<T> * ceiling_ac(TreeNode<T> *currentNode, T k);
    T floor(T k);
    T ceiling(T k);
//
// private floor method
template<class T>
TreeNode<T> * BinaryTree<T>::floor_ac(TreeNode<T> * currentNode, T k)
{
    if (currentNode == NULL)
        return NULL;
    if (k < currentNode->key)
        return floor_ac(currentNode->leftChild, k);
    if (k == currentNode->key)
        return currentNode;
    TreeNode<T> * temp;
    temp = floor_ac(currentNode->rightChild, k);
    if (temp != NULL)
        return temp;
    else
        return currentNode;
}

// private ceiling method
template<class T>
TreeNode<T> * BinaryTree<T>::ceiling_ac(TreeNode<T> *currentNode, T k)
{
    if (currentNode == NULL)
        return NULL;
    if (k > currentNode->key)
        return ceiling_ac(currentNode->rightChild, k);
    if (k == currentNode->key)
        return currentNode;
    TreeNode<T> *temp;
    temp = ceiling_ac(currentNode->leftChild, k);
    if (temp != NULL)
        return temp;
    else
        return currentNode;
}

// public floor methods
template<class T>
T BinaryTree<T>::floor(T k)
{
    TreeNode<T> * Node = floor_ac(root, k);
    if (Node == NULL)
        return NULL;
    return Node->key;
}

//public ceiling methods
template<class T>
T BinaryTree<T>::ceiling(T k)
{
    TreeNode<T>* Node = ceiling_ac(root, k);
    if (Node == NULL)
        return NULL;
    return Node->key;
}

3、選擇操作

選擇操作是將排名為r的節(jié)點(diǎn)的key值輸出赦邻。具體思路是：
①?gòu)母?jié)點(diǎn)開始髓棋，計(jì)算其左子樹的結(jié)點(diǎn)數(shù)。
②如果左子樹的結(jié)點(diǎn)數(shù)小于r惶洲，則繼續(xù)往左子樹尋找排名為r的結(jié)點(diǎn)仲锄。
③如果左子樹的結(jié)點(diǎn)數(shù)大于r，則向其右子樹中尋找排名為r-左子樹結(jié)點(diǎn)數(shù)-1的結(jié)點(diǎn)
④如果左子樹的結(jié)點(diǎn)數(shù)等于r湃鹊，則返回其左子樹的根結(jié)點(diǎn)儒喊。
⑤遞歸1~4過(guò)程，直至找到相應(yīng)結(jié)點(diǎn)币呵。

// private select method
template<class T>
TreeNode<T> * BinaryTree<T>::select_ac(TreeNode<T> *currentNode, int k)
{
    if (currentNode == NULL)
        return NULL;
    int size_leftChild = size(currentNode->leftChild);
    if (size_leftChild > k)
        return select_ac(currentNode->leftChild, k);
    else if (size_leftChild < k)
        return select_ac(currentNode->rightChild, k - size_leftChild - 1);
    else
        return currentNode;
}

//public select method
template<class T>
T BinaryTree<T>::select(int k)
{
    return select_ac(root, k)->key;
}

4怀愧、排名操作

排名操作其實(shí)是選擇操作的逆過(guò)程。即它是通過(guò)查找結(jié)點(diǎn)中的key值余赢，計(jì)算該結(jié)點(diǎn)有r個(gè)比它的key值小的結(jié)點(diǎn)芯义，從而得出排名r。 具體思路是：
①對(duì)比需要查找的key值與當(dāng)前根結(jié)點(diǎn)的key值妻柒。
②如果查找key值小于根結(jié)點(diǎn)key值扛拨，則繼續(xù)在根結(jié)點(diǎn)的左子樹尋找。
③如果查找的key值大于根結(jié)點(diǎn)的key值举塔，則將排名更新至1+當(dāng)前根節(jié)點(diǎn)左子樹的結(jié)點(diǎn)數(shù)绑警，再在右子樹尋找求泰。
④如果查找的key值等于根結(jié)點(diǎn)的key值，則排名即為其左子樹的結(jié)點(diǎn)數(shù)计盒。
⑤遞歸1~4過(guò)程渴频，直至找到相應(yīng)結(jié)點(diǎn)，返回排名北启。

// private rank method
template<class T>
int BinaryTree<T>::rank_ac(TreeNode<T> *currentNode, T ke)
{
    int size_temp = size(currentNode->leftChild);
    if (ke == currentNode->key)
        return size_temp;
    else if (ke < currentNode->key)
        return rank_ac(currentNode->leftChild, ke);
    else
        return 1 + size_temp + rank_ac(currentNode->rightChild, ke);

}

template<class T>
int BinaryTree<T>::rank(T ke)
{
    return rank_ac(root, ke);
}

5卜朗、刪除最大鍵和刪除最小鍵

刪除最小（大）鍵首先需要找到最泄敬濉（大）鍵场钉。所用的思路與上述的Min()和Max()函數(shù)類似。
尋找到最行柑巍（大）鍵后逛万，需要對(duì)其進(jìn)行刪處，并將它的右子樹連接到最屑缒啤（大）鍵的父結(jié)點(diǎn)中泣港。

// private delete min method
template<class T>
TreeNode<T> * BinaryTree<T>::deleteMin_ac(TreeNode<T> * currentNode)
{
    if (currentNode->leftChild == NULL)
        return currentNode->rightChild;
    currentNode->leftChild = deleteMin_ac(currentNode->leftChild);
    return currentNode;
}

// public delete min
template<class T>
bool BinaryTree<T>::deleteMin()
{
    if (root)
    {
        root = deleteMin_ac(root);
        return true;
    }
    else
    {
        return false;
    }
}

// private delete max method
template<class T>
TreeNode<T> * BinaryTree<T>::deleteMax_ac(TreeNode<T> * currentNode)
{
    if (currentNode->rightChild == NULL)
        return currentNode->rightChild;
    currentNode->rightChild = deleteMax_ac(currentNode->rightChild);
    return currentNode;
}

// public delete max
template<class T>
bool BinaryTree<T>::deleteMax()
{
    if (root)
    {
        root = deleteMax_ac(root);
        return true;
    }
    else
        return false;
}

小記：尋找與刪除最性葜场（大）結(jié)點(diǎn)的思路是比較容易的价匠，唯一的難題在于如何將最小（大）結(jié)點(diǎn)的右子樹連接到最星好俊（大）結(jié)點(diǎn)的父結(jié)點(diǎn)上踩窖，保持樹的有序性。

currentNode->leftChild = deleteMin_ac(currentNode->leftChild);

這個(gè)句式巧妙地解決了這個(gè)難題晨横，（以刪除最小葉結(jié)點(diǎn)為例）通過(guò)每一層的遞歸洋腮，將遞歸的結(jié)果付給當(dāng)前遍歷結(jié)點(diǎn)的左指針。在未找到最小值前手形，deleteMin_ac()函數(shù)當(dāng)前層會(huì)返回該葉結(jié)點(diǎn)的原左子結(jié)點(diǎn)啥供，保護(hù)了未被操作的子結(jié)點(diǎn)。當(dāng)尋找到最小值時(shí)库糠，deleteMin_ac()函數(shù)返回最小葉結(jié)點(diǎn)的右子結(jié)點(diǎn)伙狐，返回上層之后自然能夠?qū)⒆钚∪~節(jié)點(diǎn)的父結(jié)點(diǎn)與最小葉結(jié)點(diǎn)的右子結(jié)點(diǎn)相連。此時(shí)瞬欧，最小葉結(jié)點(diǎn)輸入失連狀態(tài)贷屎，被系統(tǒng)自動(dòng)回收。
（刪除最大葉結(jié)點(diǎn)的原理也如此）

6艘虎、刪除樹中的某個(gè)結(jié)點(diǎn)

刪除樹中的某個(gè)結(jié)點(diǎn)是樹中最難的操作唉侄，根據(jù)理解，刪除樹中結(jié)點(diǎn)需要分為4個(gè)步驟：
①尋找需要?jiǎng)h除的節(jié)點(diǎn)野建。
②找到需要?jiǎng)h除的節(jié)點(diǎn)的位置后属划，查找其右子樹的最小葉節(jié)點(diǎn)t恬叹。
③t的右指針指向需要?jiǎng)h除的節(jié)點(diǎn)的右子樹根節(jié)點(diǎn)，t的左指針指向需要?jiǎng)h除的節(jié)點(diǎn)的左指針榴嗅。
④將需要?jiǎng)h除的節(jié)點(diǎn)的父結(jié)點(diǎn)左/右指針指向t妄呕。

// private delete node assisted method
template<class T>
TreeNode<T> * BinaryTree<T>::delete_as(TreeNode<T> * currentNode, T ke)
{
    if (currentNode == NULL)
        return NULL;
    if (ke < currentNode->key)
        currentNode->leftChild = delete_as(currentNode->leftChild, ke);
    else if (ke > currentNode->key)
        currentNode->rightChild = delete_as(currentNode->rightChild, ke);
    else
    {
        if (currentNode->leftChild == NULL)
            return currentNode->rightChild;
        if (currentNode->rightChild == NULL)
            return currentNode->leftChild;
        TreeNode<T> *t = currentNode;
        currentNode = Min_ac(t->rightChild);
        currentNode->rightChild = deleteMin_ac(t->rightChild);
        currentNode->leftChild = t->leftChild;
    }
    return currentNode;
}

// public deleteNode
template<class T>
bool BinaryTree<T>::deleteNode(T ke)
{
    if (root)
    {
        delete_as(root, ke);
        return true;
    }

    else
        return false;
    
}

小記：編寫刪除方法的思路十分清晰。但是有一點(diǎn)困擾了我很久嗽测，思路③中左指針和右指針的分配是有順序的绪励。從程序上看，如果

// code1
currentNode->rightChild = deleteMin_ac(t->rightChild);
currentNode->leftChild = t->leftChild;

調(diào)換順序?yàn)?/p>

// code2
currentNode->leftChild = t->leftChild;
currentNode->rightChild = deleteMin_ac(t->rightChild);

那么唠粥，在樹圖疏魏。。晤愧。中大莫，code2會(huì)丟失結(jié)點(diǎn)A，導(dǎo)致遍歷程序無(wú)休止的運(yùn)行官份。其原因是本身結(jié)點(diǎn)H的左孩結(jié)點(diǎn)為NULL只厘，在上述程序中，為了刪除結(jié)點(diǎn)E舅巷，需要把結(jié)點(diǎn)A的父結(jié)點(diǎn)修改為結(jié)點(diǎn)H羔味。code2執(zhí)行第一行時(shí)是沒有問題的，但執(zhí)行第二行時(shí)钠右，因?yàn)镠的左子結(jié)點(diǎn)已經(jīng)賦為結(jié)點(diǎn)A赋元，則deleteMin_ac函數(shù)旨在尋找最小結(jié)點(diǎn)，因此需要尋找E的右子樹的最左的子結(jié)點(diǎn)飒房。在原來(lái)的樹中搁凸，E的右子樹的最小結(jié)點(diǎn)為H，而執(zhí)行了code2第一行的操作后狠毯，E的右子樹的最小結(jié)點(diǎn)變?yōu)锳护糖，因此刪除A后，將C接到H的左指針處嚼松。H的右指針接到結(jié)點(diǎn)R嫡良，造成整個(gè)程序的混亂。因此惜颇，將code2代碼改為code1皆刺，才能實(shí)現(xiàn)正確刪除結(jié)點(diǎn)的功能。

7凌摄、范圍查找

范圍查找是輸入一個(gè)區(qū)間羡蛾，如[F,T]。遍歷整個(gè)樹锨亏，找到落入該范圍的節(jié)點(diǎn)痴怨。因此忙干，范圍查找與層序遍歷有一些類似，相類似的地方有兩點(diǎn)：①兩者同樣需要遍歷整個(gè)樹浪藻，②遍歷整個(gè)樹都需要引入隊(duì)列的思想捐迫。范圍查找的具體步驟為：
（1）遍歷整個(gè)樹
（2）尋找隊(duì)列中落入?yún)^(qū)間的葉結(jié)點(diǎn)
（3）將這些落入?yún)^(qū)間的葉結(jié)點(diǎn)以隊(duì)列(類似與層序)的形式輸出

// public search method
template <class T>
void BinaryTree<T>::keys_ac(std::queue<TreeNode<T>*> &q, T lo, T hi)
{
    if (root == NULL)
        return;
    std::queue<TreeNode<T>*> temp_saver;
    TreeNode<T>* ptNode = root;
    while (ptNode)
    {
        if (ptNode->key >= lo && ptNode->key <= hi)
            q.push(ptNode);
        if (ptNode->leftChild)
            temp_saver.push(ptNode->leftChild);
        if (ptNode->rightChild)
            temp_saver.push(ptNode->rightChild);
        if (temp_saver.empty()) break;
        ptNode = temp_saver.front();
        temp_saver.pop();
    }
}

小記：范圍查找需要采用兩個(gè)隊(duì)列進(jìn)行實(shí)現(xiàn)，其中一個(gè)隊(duì)列用于遍歷整個(gè)樹(temp_saver)爱葵，另一個(gè)隊(duì)列用于存儲(chǔ)落入?yún)^(qū)間的葉結(jié)點(diǎn)(q)施戴。采用函數(shù)引用隊(duì)列q (queue & q)，便于修改隊(duì)列q的內(nèi)容萌丈。在函數(shù)調(diào)用之后輸出隊(duì)列q即能夠找到落入?yún)^(qū)間的葉結(jié)點(diǎn)赞哗。