二叉查找树全面详细介绍

我不是女神ヾ 2023-02-21 09:15 20阅读 0赞

## 一、前言 ##

重新梳理整理归纳二叉搜索树。主要参考《C++数据结构与算法》。

## 二、定义 ##

二叉排序树（Binary Sort Tree），又称二叉查找树（Binary Search Tree），亦称二叉搜索树。是数据结构中的一类。在一般情况下，查询效率比链表结构要高。

二叉排序树定义，一棵空树，或者是具有下列性质的二叉树：

1.  若左子树不空，则左子树上所有结点的值均小于它的根结点的值；
2.  若右子树不空，则右子树上所有结点的值均大于它的根结点的值；
3.  左、右子树也分别为二叉排序树；
4.  没有键值相等的结点。

## 三、二叉搜索树接口操作说明 ##

二叉搜索树的基本操作有：搜索（查找）、遍历、插入、删除。

### 3.1 搜索 ###

在树中定位一个元素的算法相当直观，《4.2 搜索（查找）》实现了该算法。对于每个节点，算法将要定位的值与当前所指节点中存储的值进行比较。如果该值小于存储值，则转向左子树；如果该值大于存储的值，则转向右子树。如果二者相同，很明显查找过程可以结束了。如果没有其他可以查找的节点，该查找过程也终止，这表示该值不在该树中。

搜索实现方法可以分为：递归搜索、非递归搜索《4.2 搜索（查找）》实现了该算法。

### 3.2 遍历 ###

树的遍历是当且仅当访问树中每个节点一次的过程。遍历可以解释为把所有的节点放在一条线上,或者将树线性化。

遍历的定义只指定了个条件：每个节点仪访问一次，没有指定这些节点的访问顺序。因此，节点有多少种排列方式，就有多少种遍历方法。对于有n个节点的树，共有n!个不同的遍历方式。然而，大多数遍历方式是混乱的，很难从中找到规律，因此实现这样的遍历缺乏普遍性。对于每个n，必须实现一套独立的遍历程序，其中只有很少的几个可以用于不同数量的数据。在如此多的遍历方法中，大多数方法明显没有什么用处，这里仅介绍两类方法，即深度优先遍历与广度优先遍历。

遍历可以分为：深度优先遍历(DFS)和广度优先遍历(BFS)。

**3.2.1 深度优先遍历(DFS)**

深度优先遍历将尽可能地向左(或向右)进行，在遇到第一个转折点时，向左(或向右)一步，然后,再尽可能地向左(或向右)发展。这一过程，一直重复，直至访问了所有的节点为止。然而，这一定义并没有清楚地指明什么时候访问节点：在沿着树向下进行之前还是在折返之后？深度优先遍历有许多变种。

这种类型的遍历中，有3个有趣的任务：

*  v——访问节点
 *  L——遍历左子树
 *  R——遍历右子树

如果这些任务在每个节点上都以相同的顺序执行，就形成了有序遍历。这3种任务自身共有3!=6种排序方式，因此，总共有6种有序深度优先遍历：VLR，LVR，LRV，VRL，RVL，RLV。

遍历方式看起来还是有些多，如果规定访问总是从左向右移动，则上面的遍历方式可以缩减为3种。这三种遍历方式的标准名称为：

*  VLR——前序树遍历
 *  LVR——中字树遍历
 *  LVR——后序树遍

深度优先遍历(DFS)按照遍历顺序可以分为：前序遍历、中序遍历、后序遍历

深度优先遍历(DFS)按照实现方法可以分为：递归遍历实现、非递归遍历实现、Morris遍历实现。

深度优先遍历接口有9(3\*3)个。

备注：递归遍历实现、非递归遍历实现、Morris遍历实：详细讲解：[https://blog.csdn.net/nie2314550441/article/details/107073598][https_blog.csdn.net_nie2314550441_article_details_107073598]

**3.2.2 广度优先遍历(BFS)**

用**队列实现**。《4.5 插入》实现了插入节点算法的代码。

广度优先遍历从最低层(或者最高层)开始，向下(或向上)逐层访问每个节点，在每一层次上，从左到右(或从右到左)访问每个节点。这样就有4种访问方式，其中的种访问方式(从上到下、从左到右的广度优先遍历方式)。

当使用队列时，这种遍历方式的实现相当直接。假设从上到下、从左到右进行广度优先遍历。在访问了一个节点后，它的子节点(如果有的话)就放到队列的末尾，然后访问队列头部的节点。对于层次为n的节点，它的子节点位于第n+1层，如果将该节点的所有子节点都放到队列的末尾，那么，这些节点将在第n层的所有节点都访问后再访问。这样，算法就满足了“第n层的所有节点都必须在第n+1层的节点之前访问”的条件。实现过程见——4.4 广度优先遍历。

### 3.3 插入 ###

要插入键值为el的新节点，必须找到树中的一个终端节点，并将新节点与该节点连接。要找到这样一个终端节点，可以使用与查找树相同的技术：在扫描树的过程中，比较键值el与当前检查的节点的键值。如果el小于该键值，就测试当前节点的左子节点，否则，就测试当前节点的右子节点。如果要测试的p的子节点为空，就停止扫描，新节点将成为p的子节点。图6-12显示了这一过程。

插入实现方法可以分为：非递归实现、递归实现。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25pZTIzMTQ1NTA0NDE_size_16_color_FFFFFF_t_70][]

###  ###

### 3.4 删除 ###

删除节点有两种方案：查找合并删除、查找复制删除。

执行删除操作的复杂度取决于要删除的节点在树中的位置。删除有两个子树的节点比删除叶节点困难得多，删除算法的复杂度与被删除节点的子节点数目成正比。从二叉查找树中删除节点有三种情况：

(1)要删除的节点是一个叶节点，该节点没有子节点。这种情况最容易处理。其父节点的相应指针设置为空，该节点通过delete操作被删除，如图6-14所示。

![20200629223857207.png][]

(2)要删除的节点有一个子节点，这种情况也不复杂。父节点中指向该节点的指针重新设置为指向被删除节点的子节点。这样，被删除节点的子节点提升一个层次，其后的所有后裔节点根据家族关系依次提升一个层次。例如，要删除图6-15中包含20的节点，可以将其父节点15的右指针指向其唯的子节点16。

![20200629223945363.png][]

(3)要删除的节点有两个子节点。在这种情况中，无法一步完成删除操作，因为父节点的右指针或左指针不能同时指向被删除节点的两个子节点。本节讨论解决这一问题的两种不同方案。

**3.4.1 查找合并删除**

查找合并删除：查找到删除节点P，将P节点删除，然后将左节点L、右节点R进行合并，最后将P父节点（如果有的话）指向L节点。

1）需要删除的节点，有左右孩子节点，下图中删除节点是点P，灰色节点表示该节点可以有可以没有。P节点可以有父节点，可以没有，如果有父节点，可以是父节点的左节点也可以是右节点，对结果没有影响。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25pZTIzMTQ1NTA0NDE_size_16_color_FFFFFF_t_70 1][]

2）P节点删除之后剩下：P节点父节点（如果有的话）、左节点L、右节点R。查找合并删除：查找到P节，将P节点删除，然后将P节点父节点（如果有的话）、左节点L、右节点R进行合并，准确来说是将左节点L、右节点R进行合并。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25pZTIzMTQ1NTA0NDE_size_16_color_FFFFFF_t_70 2][]

3）找到P节点右节点中最大节点，并将R节点接在最大节点右节点上，P父节点（如果有的话）指向L节点。

P节点的右节点中最大节点查找方法，一直查找L节点的右节点，直到最后一个没有右节点的节点D即为P节点中最大的节点，D节点的右节点指向R节点，合并完成，例如下图：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25pZTIzMTQ1NTA0NDE_size_16_color_FFFFFF_t_70 3][]

**3.4.2 查找复制删除**

查找复制删除：查找一个可以替换P节点位置的节点，将该节点元素复制到P节点中，并将该节点删除。能替换P节点位置的节点有两个，一个是P节点左节点中元素最大的节点，另一个是P节点右节点中元素最小的节点，这里用到的是P节点左节点中元素最大的节点。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25pZTIzMTQ1NTA0NDE_size_16_color_FFFFFF_t_70 4][]

2）查找P节点左节点中最大的节点D

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25pZTIzMTQ1NTA0NDE_size_16_color_FFFFFF_t_70 5][]

3) 将D节点元素复制到P节点中，D节点的父节点Pre指向D节点左节点，删除D节点。需要说明一下，如果Pre和P是同一个节点，则Pre左节点指向T节点，如果Pre和P不是同一个节点，则Pre右节点指向T节点。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25pZTIzMTQ1NTA0NDE_size_16_color_FFFFFF_t_70 6][]

## 四、二叉搜索树接口C++实现(代码说明) ##

### 4.1 基本定义 ###

为了方便使用对栈和队列一些接口进行了重写。

template<class T>
    class Stack: public stack<T> 
    {
    public:
        T pop() 
        {
            T tmp = stack<T>::top();
            stack<T>::pop();
            return tmp;
        }
    };
    
    template<class T>
    class Queue: public queue<T> 
    {
    public:
        T dequeue() 
        {
            T tmp = queue<T>::front();
            queue<T>::pop();
            return tmp;
        }
    
        void enqueue(const T& m_el) 
        {
            queue<T>::push(m_el);
        }
    };
    
    template<class T>
    class BSTNode 
    {
    public:
        BSTNode()
        {
            m_el = 0;
            m_left = nullptr;
            m_right = nullptr;
        }
    
        BSTNode(const T& e, BSTNode<T>* l = nullptr, BSTNode<T> * r = nullptr)
        {
            m_el = e; 
            m_left = l; 
            m_right = r;
        }
    
        T m_el;
        BSTNode<T>* m_left;
        BSTNode<T>* m_right;
    };

###  ###

### 4.2 搜索（查找） ###

递归实现和非递归实现，很容易理解直接看代码即可。

// 搜索，递归实现
    template<class T>
    T* BST<T>::recursiveSearch(BSTNode<T>* p, const T& m_el) const 
    {
        if (p != 0)
        {
            if (m_el == p->m_el)
                return &p->m_el;
            else if (m_el < p->m_el)
                return recursiveSearch(p->m_left, m_el);
            else 
                return recursiveSearch(p->m_right, m_el);
        }
        else
            return 0;
    }
    
    // 搜索，非递归实现
    template<class T>
    T* BST<T>::search(BSTNode<T>* p, const T& m_el) const 
    {
        while (p != 0)
        {
            if (m_el == p->m_el)
                return &p->m_el;
            else if (m_el < p->m_el)
                p = p->m_left;
            else 
                p = p->m_right;
        }
    
        return 0;
    }

###  ###

### 4.3 深度优先遍历 ###

**4.3.1 递归实现：前序遍历、中序遍历、后序遍历**

递归实现的，前序遍历、中序遍历、后序遍历直接看代码即可。

// 前序遍历，递归实现
    template<class T>
    void BST<T>::preorder(BSTNode<T>* p)
    {
    	if (p != 0)
    	{
            visit(p);
            preorder(p->m_left);
            preorder(p->m_right);
    	}
    }
    
    // 中序遍历，递归实现
    template<class T>
    void BST<T>::inorder(BSTNode<T>* p) 
    {
        if (p != 0) 
        {
            inorder(p->m_left);
            visit(p);
            inorder(p->m_right);
        }
    }
    
    // 后序遍历，递归实现
    template<class T>
    void BST<T>::postorder(BSTNode<T>* p) 
    {
        if (p != 0) 
        {
            postorder(p->m_left);
            postorder(p->m_right);
            visit(p);
        }
    }

**4.3.2 非递归实现：前序遍历、中序遍历、后序遍历**

// 前序遍历，非递归栈实现
    template<class T>
    void BST<T>::iterativePreorder() 
    {
        Stack<BSTNode<T>*> travStack;
        BSTNode<T>* p = root;
        if (p != 0) 
        {
            travStack.push(p);
            while (!travStack.empty())
            {
                p = travStack.pop();
                visit(p);
                if (p->m_right != 0)
                    travStack.push(p->m_right);
    
                if (p->m_left != 0)            
                    travStack.push(p->m_left); 
            }
        }
    }
    
    // 中序遍历，非递归栈实现
    template<class T>
    void BST<T>::iterativeInorder() 
    {
        Stack<BSTNode<T>*> travStack;
        BSTNode<T>* p = root;
        while (p != nullptr) 
        {
            while (p != nullptr)
            {                 
                if (p->m_right)                
                    travStack.push(p->m_right); 
    
                travStack.push(p);
                p = p->m_left;
            }
    
            p = travStack.pop();             
            while (!travStack.empty() && p->m_right == nullptr)
            { 
                visit(p);                                
                p = travStack.pop();
            }
    
            visit(p);                       
            if (!travStack.empty())          
                p = travStack.pop();
            else 
                p = nullptr;
        }
    }
    
    // 后序遍历，非递归栈实现
    template<class T>
    void BST<T>::iterativePostorder() 
    {
        Stack<BSTNode<T>*> travStack;
        BSTNode<T>* p = root, * q = root;
        while (p != nullptr) 
        {
            for (; p->m_left != nullptr; p = p->m_left)
                travStack.push(p);
    
            while (p->m_right == nullptr || p->m_right == q)
            {
                visit(p);
                q = p;
                if (travStack.empty())
                    return;
    
                p = travStack.pop();
            }
            travStack.push(p);
            p = p->m_right;
        }
    }

**4.3.3 Morris遍历：前序遍历、中序遍历、后序遍历**

// 前序遍历，非递归Morris遍历算法实现
    template<class T>
    void BST<T>::MorrisPreorder() 
    {
        BSTNode<T>* p = root, * tmp;
        while (p != nullptr) 
        {
            if (p->m_left == nullptr)
            {
                visit(p);
                p = p->m_right;
            }
            else 
            {
                tmp = p->m_left;
                while (tmp->m_right != nullptr && tmp->m_right != p)
                    tmp = tmp->m_right;   
    
                if (tmp->m_right == nullptr)
                {  
                    visit(p);         
                    tmp->m_right = p;    
                    p = p->m_left;        
                }
                else 
                {                   
                    tmp->m_right = nullptr;    
                    p = p->m_right;       
                }                        
            }
        }
    }
    
    // 中序遍历，非递归Morris遍历算法实现
    template<class T>
    void BST<T>::MorrisInorder() 
    {
        BSTNode<T>* p = root, * tmp;
        while (p != 0)
        {
            if (p->m_left == 0) 
            {
                visit(p);
                p = p->m_right;
            }
            else 
            {
                tmp = p->m_left;
                while (tmp->m_right != 0 &&
                    tmp->m_right != p)  
                    tmp = tmp->m_right;   
                if (tmp->m_right == 0) 
                {   
                    tmp->m_right = p;    
                    p = p->m_left;       
                }
                else 
                {                   
                    visit(p);      
                    tmp->m_right = 0;    
                    p = p->m_right;      
                }                      
            }
        }
    }
    
    // 后序遍历，非递归Morris遍历算法实现
    template<class T>
    void BST<T>::MorrisPostorder() 
    {
        BSTNode<T>* p = new BSTNode<T>(), * tmp, * q, * r, * s;
        p->m_left = root;
        while (p != 0)
        {
            if (p->m_left == 0)
                p = p->m_right;
            else
            {
                tmp = p->m_left;
                while (tmp->m_right != 0 && tmp->m_right != p)  
                    tmp = tmp->m_right;   
    
                if (tmp->m_right == 0) 
                {   
                    tmp->m_right = p;     
                    p = p->m_left;        
                }
                else
                {             
                    for (q = p->m_left, r = q->m_right, s = r->m_right;
                        r != p; q = r, r = s, s = s->m_right)
                        r->m_right = q;
    
                    for (s = q->m_right; q != p->m_left;
                        q->m_right = r, r = q, q = s, s = s->m_right)
                        visit(q);
    
                    visit(p->m_left);    
                    tmp->m_right = 0;     
                    p = p->m_right;      
                }                   
            }
        }
    }

###  ###

### 4.4 广度优先遍历 ###

// 广度优先遍历：从上到下，从左到右
    template<class T>
    void BST<T>::breadthFirst() 
    {
        Queue<BSTNode<T>*> queue;
        BSTNode<T>* p = root;
        if (p != 0) 
        {
            queue.enqueue(p);
            while (!queue.empty()) 
            {
                p = queue.dequeue();
                visit(p);
                if (p->m_left != 0)
                    queue.enqueue(p->m_left);
                if (p->m_right != 0)
                    queue.enqueue(p->m_right);
            }
        }
    }

###  ###

### 4.5 插入 ###

非递归实现和递归实现

// 插入插入一个元素，非递归实现
    template<class T>
    bool BST<T>::insert(const T& m_el) 
    {
        BSTNode<T>* p = root, * prev = 0;
        while (p != 0) 
        {  
            prev = p;
            if (m_el < p->m_el)
                p = p->m_left;
            else if (m_el > p->m_el)
                p = p->m_right;
            else
            {
                cout << "BST<T>::insert 插入相同的数据，插入失败" << endl;
                return false;
            }
        }
    
        if (root == 0)    
            root = new BSTNode<T>(m_el);
        else if (m_el < prev->m_el)
            prev->m_left = new BSTNode<T>(m_el);
        else 
            prev->m_right = new BSTNode<T>(m_el);
    
    	return true;
    }
    
    // 插入插入一个元素，递归实现
    template<class T>
    bool BST<T>::recursiveInsert(BSTNode<T>*& p, const T& m_el) 
    {
        if (p == 0)
            p = new BSTNode<T>(m_el);
        else if (m_el < p->m_el)
            recursiveInsert(p->m_left, m_el);
        else if (m_el > p->m_el)
            recursiveInsert(p->m_right, m_el);
        else
        {
            cout << "BST<T>::recursiveInsert 插入相同的数据，插入失败" << endl;
            return false;
        }
        
        return true; 
    }

### 4.6 删除 ###

查找复制删除和查找归并删除

// 查找复制删除
    template<class T>
    void BST<T>::findAndDeleteByCopying(const T& m_el) 
    {
        BSTNode<T>* p = root, * prev = 0;
        while (p != 0 && p->m_el != m_el) 
        {
            prev = p;
            if (m_el < p->m_el)
                p = p->m_left;
            else 
                p = p->m_right;
        }
    
        if (p != 0 && p->m_el == m_el)
        {
            if (p == root)
                deleteByCopying(root);
            else if (prev->m_left == p)
                deleteByCopying(prev->m_left);
            else
                deleteByCopying(prev->m_right);
    	}
        else if (root != 0)
            cout << "m_el " << m_el << " is not in the tree\n";
        else 
            cout << "the tree is empty\n";
    }
    
    // 查找复制删除
    template<class T>
    void BST<T>::deleteByCopying(BSTNode<T>*& node) 
    {
        if (node == nullptr)
            return;
    	
        BSTNode<T>* previous, * tmp = node;
        if (node->m_right == nullptr)                  // node 没有右节点
            node = node->m_left;
        else if (node->m_left == nullptr)              // node 没有左节点
            node = node->m_right;
        else 
        {
            tmp = node->m_left;							// node 有左、右节点
            previous = node;                   
            while (tmp->m_right != nullptr)
            {         
                previous = tmp;
                tmp = tmp->m_right;
            }
    
            node->m_el = tmp->m_el;                
            if (previous == node)
                previous->m_left = tmp->m_left;
            else 
                previous->m_right = tmp->m_left;   
        }
    
        delete tmp;                            
    }
    
    // 查找合并删除
    template<class T>
    void BST<T>::findAndDeleteByMerging(const T& m_el) 
    {
        BSTNode<T>* p = root, * prev = 0;
        while (p != 0 && p->m_el != m_el)
        {
            prev = p;
            if (m_el < p->m_el)
                p = p->m_left;
            else 
                p = p->m_right;
        }
    
    	if (p != 0 && p->m_el == m_el)
    	{
            if (p == root)
                deleteByMerging(root);
            else if (prev->m_left == p)
                deleteByMerging(prev->m_left);
            else
                deleteByMerging(prev->m_right);
    	}
        else if (root != 0)
            cout << "m_el " << m_el << " is not in the tree\n";
        else cout << "the tree is empty\n";
    }
    
    // 查找合并删除
    template<class T>
    void BST<T>::deleteByMerging(BSTNode<T>*& node) 
    {
        if (node == nullptr)
            return;
    
        BSTNode<T>* tmp = node;
        if (node->m_right == nullptr)           // node 没有右节点
            node = node->m_left;     
        else if (node->m_left == nullptr)       // node 没有左节点
            node = node->m_right;    
        else 
        {                      
            tmp = node->m_left;      
            while (tmp->m_right != nullptr)
                tmp = tmp->m_right;
    
            tmp->m_right = node->m_right;           															
            tmp = node;							
            node = node->m_left;					
        }
    
        delete tmp;								
    }

## 五、完整代码 ##

// 通用二叉查找树的实现
    #pragma once
    #include <queue>
    #include <stack>
    #include <iostream>
    using namespace std;
    
    template<class T>
    class Stack: public stack<T> 
    {
    public:
        T pop() 
        {
            T tmp = stack<T>::top();
            stack<T>::pop();
            return tmp;
        }
    };
    
    template<class T>
    class Queue: public queue<T> 
    {
    public:
        T dequeue() 
        {
            T tmp = queue<T>::front();
            queue<T>::pop();
            return tmp;
        }
    
        void enqueue(const T& m_el) 
        {
            queue<T>::push(m_el);
        }
    };
    
    template<class T>
    class BSTNode 
    {
    public:
    	BSTNode()
    	{
            m_el = 0;
            m_left = nullptr;
            m_right = nullptr;
    	}
    
        BSTNode(const T& e, BSTNode<T>* l = nullptr, BSTNode<T> * r = nullptr)
        {
            m_el = e; 
            m_left = l; 
            m_right = r;
        }
    
    	T m_el;
    	BSTNode<T>* m_left;
    	BSTNode<T>* m_right;
    };
    
    template<class T>
    class BST 
    {
    public:
        BST()  { root = 0; }
        ~BST() { clear();  }
    
        void clear() 
        {
            clear(root);
            root = 0;
        }
    
    	// 搜索，递归实现
    	T* recursiveSearch(const T& m_el) const { return recursiveSearch(root, m_el); }
        // 搜索，非递归实现
        T* search(const T& m_el) const { return search(root, m_el); }
    
        // 前序遍历，递归实现
        void preorder()  { preorder(root); }
        // 中序遍历，递归实现
        void inorder()  { inorder(root); }
        // 后续遍历，递归实现
        void postorder()  { postorder(root); }
        // 前序遍历，非递归栈实现
        void iterativePreorder();
        // 中序遍历，非递归栈实现
        void iterativeInorder();
        // 后序遍历，非递归栈实现
        void iterativePostorder();
        // 前序遍历，非递归Morris遍历算法实现
        void MorrisPreorder();
        // 中序遍历，非递归Morris遍历算法实现
        void MorrisInorder();
        // 后序遍历，非递归Morris遍历算法实现
        void MorrisPostorder();
    
        // 广度优先遍历：从上到下，从左到右
        void breadthFirst();
    
        // 插入插入一个元素，非递归实现
        bool insert(const T&);
        // 插入插入一个元素，递归实现
        bool recursiveInsert(const T& m_el) { recursiveInsert(root, m_el); }
    
        // 查找合并删除
        void findAndDeleteByMerging(const T&);
        // 查找复制删除
        void findAndDeleteByCopying(const T&);
    
    protected:
        BSTNode<T>* root;
        void clear(BSTNode<T>*);
        // 插入插入一个元素，递归实现
        bool recursiveInsert(BSTNode<T>*&, const T&);
        // 搜索（查找），非递归实现
        T* search(BSTNode<T>*, const T&) const;
        // 搜索（查找），递归实现
        T* recursiveSearch(BSTNode<T>*, const T&) const;
        // 前序遍历，递归实现
        void preorder(BSTNode<T>*);
        // 中序遍历，递归实现
        void inorder(BSTNode<T>*);
        // 后序遍历，递归实现
        void postorder(BSTNode<T>*);
        // 复制删除
        void deleteByCopying(BSTNode<T>*&);
        // 合并删除
        void deleteByMerging(BSTNode<T>*&);
        // 访问节点
        virtual void visit(BSTNode<T>* p) { cout << p->m_el << ' '; }
    };
    
    template<class T>
    void BST<T>::clear(BSTNode<T>* p) 
    {
        if (p != 0) 
        {
            clear(p->m_left);
            clear(p->m_right);
            delete p;
        }
    }
    
    // 搜索（查找），递归实现
    template<class T>
    T* BST<T>::recursiveSearch(BSTNode<T>* p, const T& m_el) const 
    {
        if (p != 0)
        {
            if (m_el == p->m_el)
                return &p->m_el;
            else if (m_el < p->m_el)
                return recursiveSearch(p->m_left, m_el);
            else 
                return recursiveSearch(p->m_right, m_el);
        }
        else
            return 0;
    }
    
    // 搜索（查找），非递归实现
    template<class T>
    T* BST<T>::search(BSTNode<T>* p, const T& m_el) const 
    {
        while (p != 0)
        {
            if (m_el == p->m_el)
                return &p->m_el;
            else if (m_el < p->m_el)
                p = p->m_left;
            else 
                p = p->m_right;
        }
    
        return 0;
    }
    
    // 前序遍历，递归实现
    template<class T>
    void BST<T>::preorder(BSTNode<T>* p)
    {
    	if (p != 0)
    	{
            visit(p);
            preorder(p->m_left);
            preorder(p->m_right);
    	}
    }
    
    // 中序遍历，递归实现
    template<class T>
    void BST<T>::inorder(BSTNode<T>* p) 
    {
        if (p != 0) 
        {
            inorder(p->m_left);
            visit(p);
            inorder(p->m_right);
        }
    }
    
    // 后序遍历，递归实现
    template<class T>
    void BST<T>::postorder(BSTNode<T>* p) 
    {
        if (p != 0) 
        {
            postorder(p->m_left);
            postorder(p->m_right);
            visit(p);
        }
    }
    
    // 前序遍历，非递归栈实现
    template<class T>
    void BST<T>::iterativePreorder() 
    {
        Stack<BSTNode<T>*> travStack;
        BSTNode<T>* p = root;
        if (p != 0) 
        {
            travStack.push(p);
            while (!travStack.empty())
            {
                p = travStack.pop();
                visit(p);
                if (p->m_right != 0)
                    travStack.push(p->m_right);
    
                if (p->m_left != 0)            
                    travStack.push(p->m_left); 
            }
        }
    }
    
    // 中序遍历，非递归栈实现
    template<class T>
    void BST<T>::iterativeInorder() 
    {
        Stack<BSTNode<T>*> travStack;
        BSTNode<T>* p = root;
        while (p != nullptr) 
        {
            while (p != nullptr)
            {                 
                if (p->m_right)                
                    travStack.push(p->m_right); 
    
                travStack.push(p);
                p = p->m_left;
            }
    
            p = travStack.pop();             
            while (!travStack.empty() && p->m_right == nullptr)
            { 
                visit(p);                                
                p = travStack.pop();
            }
    
            visit(p);                       
            if (!travStack.empty())          
                p = travStack.pop();
            else 
                p = nullptr;
        }
    }
    
    // 后序遍历，非递归栈实现
    template<class T>
    void BST<T>::iterativePostorder() 
    {
        Stack<BSTNode<T>*> travStack;
        BSTNode<T>* p = root, * q = root;
        while (p != nullptr) 
        {
            for (; p->m_left != nullptr; p = p->m_left)
                travStack.push(p);
    
            while (p->m_right == nullptr || p->m_right == q)
            {
                visit(p);
                q = p;
                if (travStack.empty())
                    return;
    
                p = travStack.pop();
            }
            travStack.push(p);
            p = p->m_right;
        }
    }
    
    // 前序遍历，非递归Morris遍历算法实现
    template<class T>
    void BST<T>::MorrisPreorder() 
    {
        BSTNode<T>* p = root, * tmp;
        while (p != nullptr) 
        {
            if (p->m_left == nullptr)
            {
                visit(p);
                p = p->m_right;
            }
            else 
            {
                tmp = p->m_left;
                while (tmp->m_right != nullptr && tmp->m_right != p)
                    tmp = tmp->m_right;   
    
                if (tmp->m_right == nullptr)
                {  
                    visit(p);         
                    tmp->m_right = p;    
                    p = p->m_left;        
                }
                else 
                {                   
                    tmp->m_right = nullptr;    
                    p = p->m_right;       
                }                        
            }
        }
    }
    
    // 中序遍历，非递归Morris遍历算法实现
    template<class T>
    void BST<T>::MorrisInorder() 
    {
        BSTNode<T>* p = root, * tmp;
        while (p != 0)
        {
            if (p->m_left == 0) 
            {
                visit(p);
                p = p->m_right;
            }
            else 
            {
                tmp = p->m_left;
                while (tmp->m_right != 0 && tmp->m_right != p)  
                    tmp = tmp->m_right;   
                    
                if (tmp->m_right == 0) 
                {   
                    tmp->m_right = p;    
                    p = p->m_left;       
                }
                else 
                {                   
                    visit(p);      
                    tmp->m_right = 0;    
                    p = p->m_right;      
                }                      
            }
        }
    }
    
    // 后序遍历，非递归Morris遍历算法实现
    template<class T>
    void BST<T>::MorrisPostorder() 
    {
        BSTNode<T>* p = new BSTNode<T>(), * tmp, * q, * r, * s;
        p->m_left = root;
        while (p != 0)
        {
            if (p->m_left == 0)
                p = p->m_right;
            else
            {
                tmp = p->m_left;
                while (tmp->m_right != 0 && tmp->m_right != p)  
                    tmp = tmp->m_right;   
    
                if (tmp->m_right == 0) 
                {   
                    tmp->m_right = p;     
                    p = p->m_left;        
                }
                else
                {             
                    for (q = p->m_left, r = q->m_right, s = r->m_right;
                        r != p; q = r, r = s, s = s->m_right)
                        r->m_right = q;
    
                    for (s = q->m_right; q != p->m_left;
                        q->m_right = r, r = q, q = s, s = s->m_right)
                        visit(q);
    
                    visit(p->m_left);    
                    tmp->m_right = 0;     
                    p = p->m_right;      
                }                   
            }
        }
    }
    
    // 广度优先遍历：从上到下，从左到右
    template<class T>
    void BST<T>::breadthFirst() 
    {
        Queue<BSTNode<T>*> queue;
        BSTNode<T>* p = root;
        if (p != 0) 
        {
            queue.enqueue(p);
            while (!queue.empty()) 
            {
                p = queue.dequeue();
                visit(p);
                if (p->m_left != 0)
                    queue.enqueue(p->m_left);
                if (p->m_right != 0)
                    queue.enqueue(p->m_right);
            }
        }
    }
    
    // 插入插入一个元素，非递归实现
    template<class T>
    bool BST<T>::insert(const T& m_el) 
    {
        BSTNode<T>* p = root, * prev = 0;
        while (p != 0) 
        {  
            prev = p;
            if (m_el < p->m_el)
                p = p->m_left;
            else if (m_el > p->m_el)
                p = p->m_right;
            else
            {
                cout << "BST<T>::insert 插入相同的数据，插入失败" << endl;
                return false;
            }
        }
    
        if (root == 0)    
            root = new BSTNode<T>(m_el);
        else if (m_el < prev->m_el)
            prev->m_left = new BSTNode<T>(m_el);
        else 
            prev->m_right = new BSTNode<T>(m_el);
    
    	return true;
    }
    
    // 插入插入一个元素，递归实现
    template<class T>
    bool BST<T>::recursiveInsert(BSTNode<T>*& p, const T& m_el) 
    {
        if (p == 0)
            p = new BSTNode<T>(m_el);
        else if (m_el < p->m_el)
            recursiveInsert(p->m_left, m_el);
        else if (m_el > p->m_el)
            recursiveInsert(p->m_right, m_el);
    	else
        {
            cout << "BST<T>::recursiveInsert 插入相同的数据，插入失败" << endl;
            return false;
        }
        
    	return true; 
    }
    
    
    // 查找合并删除
    template<class T>
    void BST<T>::findAndDeleteByMerging(const T& m_el)
    {
        BSTNode<T>* p = root, * prev = 0;
        while (p != 0 && p->m_el != m_el)
        {
            prev = p;
            if (m_el < p->m_el)
                p = p->m_left;
            else
                p = p->m_right;
        }
    
        if (p != 0 && p->m_el == m_el)
        {
            if (p == root)
                deleteByMerging(root);
            else if (prev->m_left == p)
                deleteByMerging(prev->m_left);
            else
                deleteByMerging(prev->m_right);
        }
        else if (root != 0)
            cout << "m_el " << m_el << " is not in the tree\n";
        else 
            cout << "the tree is empty\n";
    }
    
    // 查找合并删除
    template<class T>
    void BST<T>::deleteByMerging(BSTNode<T>*& node)
    {
        if (node == nullptr)
            return;
    
        BSTNode<T>* tmp = node;
        if (node->m_right == nullptr)           // node 没有右节点
            node = node->m_left;
        else if (node->m_left == nullptr)       // node 没有左节点
            node = node->m_right;
        else
        {
            tmp = node->m_left;
            while (tmp->m_right != nullptr)
                tmp = tmp->m_right;
    
            tmp->m_right = node->m_right;
            tmp = node;
            node = node->m_left;
        }
    
        delete tmp;
    }
    
    // 查找复制删除
    template<class T>
    void BST<T>::findAndDeleteByCopying(const T& m_el) 
    {
        BSTNode<T>* p = root, * prev = 0;
        while (p != 0 && p->m_el != m_el) 
        {
            prev = p;
            if (m_el < p->m_el)
                p = p->m_left;
            else 
                p = p->m_right;
        }
    
        if (p != 0 && p->m_el == m_el)
        {
            if (p == root)
                deleteByCopying(root);
            else if (prev->m_left == p)
                deleteByCopying(prev->m_left);
            else
                deleteByCopying(prev->m_right);
    	}
        else if (root != 0)
            cout << "m_el " << m_el << " is not in the tree\n";
        else 
            cout << "the tree is empty\n";
    }
    
    // 查找复制删除
    template<class T>
    void BST<T>::deleteByCopying(BSTNode<T>*& node) 
    {
        if (node == nullptr)
            return;
    	
        BSTNode<T>* previous, * tmp = node;
        if (node->m_right == nullptr)                  // node 没有右节点
            node = node->m_left;
        else if (node->m_left == nullptr)              // node 没有左节点
            node = node->m_right;
        else 
        {
            tmp = node->m_left;							// node 有左、右节点
            previous = node;                   
            while (tmp->m_right != nullptr)
            {         
                previous = tmp;
                tmp = tmp->m_right;
            }
    
            node->m_el = tmp->m_el;                
            if (previous == node)
                previous->m_left = tmp->m_left;
            else 
                previous->m_right = tmp->m_left;   
        }
    
        delete tmp;                            
    }

[https_blog.csdn.net_nie2314550441_article_details_107073598]: https://blog.csdn.net/nie2314550441/article/details/107073598
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25pZTIzMTQ1NTA0NDE_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/2020062922380185.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25pZTIzMTQ1NTA0NDE=,size_16,color_FFFFFF,t_70
[20200629223857207.png]: https://img-blog.csdnimg.cn/20200629223857207.png
[20200629223945363.png]: https://img-blog.csdnimg.cn/20200629223945363.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25pZTIzMTQ1NTA0NDE_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/2020062922402766.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25pZTIzMTQ1NTA0NDE=,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25pZTIzMTQ1NTA0NDE_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/20200629224101202.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25pZTIzMTQ1NTA0NDE=,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25pZTIzMTQ1NTA0NDE_size_16_color_FFFFFF_t_70 3]: https://img-blog.csdnimg.cn/2020062922413162.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25pZTIzMTQ1NTA0NDE=,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25pZTIzMTQ1NTA0NDE_size_16_color_FFFFFF_t_70 4]: https://img-blog.csdnimg.cn/20200629224212148.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25pZTIzMTQ1NTA0NDE=,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25pZTIzMTQ1NTA0NDE_size_16_color_FFFFFF_t_70 5]: https://img-blog.csdnimg.cn/2020062922423527.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25pZTIzMTQ1NTA0NDE=,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25pZTIzMTQ1NTA0NDE_size_16_color_FFFFFF_t_70 6]: https://img-blog.csdnimg.cn/20200629224306302.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25pZTIzMTQ1NTA0NDE=,size_16,color_FFFFFF,t_70