一、二叉查找树

前面一章分析了二分查找这种算法。

要支持高效的插入操作，我们需要链式的数据结构，但是链表不能二分查找，因为中间值需要从链表头部开始寻找。为了将二分查找的效率和链表的灵活性结合起来，需要一种新的数据结构。
这种数据结构就是二叉树查找，它能够将链表插入的灵活性和有序数组查找的高效性结合起来的符号表实现。

要实现二叉树，首先树的结构需要了解清楚，一般一个树可以分为两个部分：

树根 ---> 树节点

树节点中又存储着几个部分：

存储的Key值 -- 存储的value值 -- 节点左孩子 -- 节点右孩子

// 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;
}

编写这个程序是遇到一个问题：就是使用常规的头文件声明类及方法、.cpp文件定义类方法、main函数执行功能这个套路是行不通的，程序会报Linker Tools Error LNK2019的错误。
原因：采用的是特殊的模板类进行代码的编写。

编译器处理模板类时，如有一些模板类以及函数，则会进行如下操作。
1、模板函数和类在编译时期间并未生成具体的二进制代码， 在main函数中也没有嵌入这个类或函数的代码，只是包含了一句 call +类名/函数名
2、编译阶段，在main函数中发现了模板类和的引用，但是main.obj

有序性相关方法和删除操作

1、首先，我们可以获取树的最大键和最小键。

其思路非常简单，最小键即处于树最左边的键，最大键即处于树最右边的键。获取最小键与最大键的方法我们可以采用递归来实现。

 // 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到达某个节点时，它需要寻找该节点的左子树，因为小于等于key的键值就在该节点的左子树中。只有当右子树存在比Key小的键值时，最大的小于等于键值的键才会出现在右子树中。因此，利用这个思路，可以写出floor向下取整函数。当然，向上取整就是把上述思路的左右对调一下。

// 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的节点的key值输出。具体思路是：
①从根节点开始，计算其左子树的结点数。
②如果左子树的结点数小于r，则继续往左子树寻找排名为r的结点。
③如果左子树的结点数大于r，则向其右子树中寻找排名为r-左子树结点数-1的结点
④如果左子树的结点数等于r，则返回其左子树的根结点。
⑤递归1~4过程，直至找到相应结点。

// 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、排名操作

排名操作其实是选择操作的逆过程。即它是通过查找结点中的key值，计算该结点有r个比它的key值小的结点，从而得出排名r。 具体思路是：
①对比需要查找的key值与当前根结点的key值。
②如果查找key值小于根结点key值，则继续在根结点的左子树寻找。
③如果查找的key值大于根结点的key值，则将排名更新至1+当前根节点左子树的结点数，再在右子树寻找。
④如果查找的key值等于根结点的key值，则排名即为其左子树的结点数。
⑤递归1~4过程，直至找到相应结点，返回排名。

// 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()函数类似。
寻找到最小（大）键后，需要对其进行删处，并将它的右子树连接到最小（大）键的父结点中。

// 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;
}

小记：寻找与删除最小（大）结点的思路是比较容易的，唯一的难题在于如何将最小（大）结点的右子树连接到最小（大）结点的父结点上，保持树的有序性。

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

这个句式巧妙地解决了这个难题，（以删除最小叶结点为例）通过每一层的递归，将递归的结果付给当前遍历结点的左指针。在未找到最小值前，deleteMin_ac()函数当前层会返回该叶结点的原左子结点，保护了未被操作的子结点。当寻找到最小值时，deleteMin_ac()函数返回最小叶结点的右子结点，返回上层之后自然能够将最小叶节点的父结点与最小叶结点的右子结点相连。此时，最小叶结点输入失连状态，被系统自动回收。
（删除最大叶结点的原理也如此）

6、删除树中的某个结点

删除树中的某个结点是树中最难的操作，根据理解，删除树中结点需要分为4个步骤：
①寻找需要删除的节点。
②找到需要删除的节点的位置后，查找其右子树的最小叶节点t。
③t的右指针指向需要删除的节点的右子树根节点，t的左指针指向需要删除的节点的左指针。
④将需要删除的节点的父结点左/右指针指向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;
    
}

小记：编写删除方法的思路十分清晰。但是有一点困扰了我很久，思路③中左指针和右指针的分配是有顺序的。从程序上看，如果

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

调换顺序为

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

那么，在树图。。。中，code2会丢失结点A，导致遍历程序无休止的运行。其原因是本身结点H的左孩结点为NULL，在上述程序中，为了删除结点E，需要把结点A的父结点修改为结点H。code2执行第一行时是没有问题的，但执行第二行时，因为H的左子结点已经赋为结点A，则deleteMin_ac函数旨在寻找最小结点，因此需要寻找E的右子树的最左的子结点。在原来的树中，E的右子树的最小结点为H，而执行了code2第一行的操作后，E的右子树的最小结点变为A，因此删除A后，将C接到H的左指针处。H的右指针接到结点R，造成整个程序的混乱。因此，将code2代码改为code1，才能实现正确删除结点的功能。

7、范围查找

范围查找是输入一个区间，如[F,T]。遍历整个树，找到落入该范围的节点。因此，范围查找与层序遍历有一些类似，相类似的地方有两点：①两者同样需要遍历整个树，②遍历整个树都需要引入队列的思想。范围查找的具体步骤为：
（1）遍历整个树
（2）寻找队列中落入区间的叶结点
（3）将这些落入区间的叶结点以队列(类似与层序)的形式输出

// 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();
    }
}

小记：范围查找需要采用两个队列进行实现，其中一个队列用于遍历整个树(temp_saver)，另一个队列用于存储落入区间的叶结点(q)。采用函数引用队列q (queue & q)，便于修改队列q的内容。在函数调用之后输出队列q即能够找到落入区间的叶结点。