C++实现二叉搜索树

#pragma once
#include "stdio.h";
#include "Queue.h"
//二叉搜索树（链表式）

namespace SF 
{
    template<class T>
    struct BinaryTreeNode
    {
        T data;
        BinaryTreeNode<T> *left;
        BinaryTreeNode<T> *right;

        BinaryTreeNode()
        {
            this->left = nullptr;
            this->right = nullptr;
        }
    };


    template<class T>
    class BinaryTree
    {
    public:
        BinaryTree();
        ~BinaryTree();
        void Release() { ReleaseTree(root); };
        void PreOrder() { PreOrderTraverse(root); };
        void InOrder() { InOrderTraverse(root); };
        void PostOrder() { PostOrderTraverse(root); };
        void SequenceOrder();
        void Size() { return this->count; };
        void Insert(T val);
        BinaryTreeNode<T> *Find(T val);
        void Delete(T val);
    private:
        int count;
        BinaryTreeNode<T> *root;
        void PreOrderTraverse(BinaryTreeNode<T> *node);
        void InOrderTraverse(BinaryTreeNode<T> *node);
        void PostOrderTraverse(BinaryTreeNode<T> *node);
        void ReleaseTree(BinaryTreeNode<T> *node);
        BinaryTreeNode<T> *InsertNode(BinaryTreeNode<T> *node, T val);
        BinaryTreeNode<T> *DeleteNode(BinaryTreeNode<T>* node, T val);
        BinaryTreeNode<T> *FindMin(BinaryTreeNode<T> *node); //找最小的
    };

    template<class T>
    BinaryTree<T>::BinaryTree()
    {
        this->count = 0;
        this->root = new BinaryTreeNode<T>();
    }

    template<class T>
    BinaryTree<T>::~BinaryTree()
    {
        this->Release();
    }

    template<class T>
    void BinaryTree<T>::PreOrderTraverse(BinaryTreeNode<T> *node)
    {
        if (node)
        {
            printf("%i\n", node->data);
            PreOrderTraverse(node->left);
            PreOrderTraverse(node->right);
        }
    }

    template<class T>
    void BinaryTree<T>::InOrderTraverse(BinaryTreeNode<T> *node)
    {
        if (node)
        {
            InOrderTraverse(node->left);
            printf("%i\n", node->data);
            InOrderTraverse(node->right);
        }
    }

    template<class T>
    void BinaryTree<T>::PostOrderTraverse(BinaryTreeNode<T> *node)
    {
        if (node)
        {
            PostOrderTraverse(node->left);
            PostOrderTraverse(node->right);
            printf("%i/n", node->data);
        }
    }

    template<class T>
    void BinaryTree<T>::SequenceOrder() 
    {
        BinaryTreeNode<T> *node;
        Queue<BinaryTreeNode<T>> queue;
        queue.Enqueue(*root);
        while (queue.IsEmtpy())
        {
            node = &(queue.Dequeue()->data);
            printf("%i\n", node->data);
            if (node->left) queue.Enqueue(*node->left);
            if (node->right) queue.Enqueue(*node->right);
        }
    }

    template<class T>
    void BinaryTree<T>::ReleaseTree(BinaryTreeNode<T> *node)
    {
        if (node)
        {
            ReleaseTree(node->left);
            ReleaseTree(node->right);
            delete node;
        }
    }

    template<class T>
    void BinaryTree<T>::Insert(T val)
    {
        if (this->count==0) 
        {
            root->data = val;
        }
        else
        {
            InsertNode(root, val);
        }
        this->count++;
    }

    template<class T>
    BinaryTreeNode<T>* BinaryTree<T>::InsertNode(BinaryTreeNode<T> *node, T val)
    {
        if (node)
        {
            if ( val > node->data)
            {
                node->right = InsertNode(node->right, val);
            }
            else
            {
                node->left = InsertNode(node->left, val);
            }
        }
        else
        {
            node = new BinaryTreeNode<T>();
            node->data = val;
            node->left = node->right = nullptr;
        }
        return node;
    }


    template<class T>
    BinaryTreeNode<T>* BinaryTree<T>::Find(T val)
    {
        BinaryTreeNode<T> *node = root;
        while (node)
        {
            if (val > node->data) 
            {
                node = node->right;
            }
            else if(val < node->data)
            {
                node = node->left;
            }
            else
            {
                return node;
            }
        }
        return nullptr;
    }

    template<class T>
    void BinaryTree<T>::Delete(T val)
    {
        //1.叶节点直接删除
        //2.节点只有一个儿子
        //3.节点有两个儿子
        //需要先找到节点
        DeleteNode(root, val);
    }

    template<class T>
    BinaryTreeNode<T>* BinaryTree<T>::DeleteNode(BinaryTreeNode<T> *node, T val)
    {
        if (!node) 
        {
            printf("要删除的元素不存在");
        }
        else if (val > node->data)
        {
            node->right = DeleteNode(node->right, val);  //花式删除
        }
        else if (val < node->data) 
        {
            node->left = DeleteNode(node->left, val);
        }
        else
        {
            //找到需要删除的节点了
            BinaryTreeNode<T> *tmp;
            if (node->left && node->right)  //左右儿子都存在
            {
                tmp = FindMin(node->right); //从右子树中找一个最小的出来
                node->data = tmp->data;  //数据替换 
                node->right = DeleteNode(node->right, node->data);  //然后去干掉那个右子树中最小的节点
            }
            else 
            {
                tmp = node;
                if (!node->left)  //只有一个右节点  直接给中间这个删除，然后接上指针关系即可
                {
                    node = node->right;
                }
                else if (!node->right) //右子树 不存在 或者没有子节点
                {
                    node = node->left;
                }
                delete tmp;
            }
        }
        return node;
    }

    template<class T>
    BinaryTreeNode<T>* BinaryTree<T>::FindMin(BinaryTreeNode<T> *node) 
    {
        BinaryTreeNode<T> *temp = node;
        while (temp->left)
        {
            temp = temp->left;
        }
        return temp;
    }

}