二叉树实现代码

迷南。 2022-09-30 10:51 147阅读 0赞

### 头文件 ###

#### binarytree.h ####

#ifndef BINARYTREE_H
    #define BINARYTREE_H
    
    #include <functional>
    
    template<typename T>
    class BinaryTree
    {
    struct node_
    {
        T value;
        node_* left;
        node_* right;
        node_* parent;
    };
    
    typedef std::function<void(struct node_*)> handler;
    
    //typedef struct _node Node;
    
    public:
        BinaryTree();
        void insert(const T&);
        bool isExist(const T&);
        void erase(const T&);
        void traverse();
    private:
        struct node_* _root;
    
    private:
        void do_traverse(struct node_* root, const handler&);
        void print(struct node_* node);
        void find(const T&, struct node_*& node);
        void findMin(struct node_*, struct node_*& node);
        bool findParent(const T&, struct node_*& node);
    };
    
    #endif // BINARYTREE_H

####     ####

### 源文件 ###

#### binarytree.cpp ####

#include "binarytree.h"
    #include <iostream>
    
    template<typename T>
    BinaryTree<T>::BinaryTree()
        :_root(nullptr)
    {
    
    }
    
    template<typename T>
    void BinaryTree<T>::insert(const T& value)
    {
        if (_root == nullptr)
        {
            struct node_* node = new struct node_;
            node->left = nullptr;
            node->right = nullptr;
            node->parent = nullptr;
            node->value = value;
            _root = node;
            return;
        }
        ///
        bool notExist = true;
        struct node_* target = _root;
        int dir = 0;
        while(target != nullptr)
        {
            if (target->value < value)
            {
                if (target->right == nullptr)
                {
                    dir = 2;
                    break;
                }
                else
                {
                    target = target->right;
                }
            }
            else if (target->value == value)
            {
                notExist = false;
                break;
            }
            else
            {
                if (target->left == nullptr)
                {
                    dir = 1;
                    break;
                }
                else
                {
                    target = target->left;
                }
            }
        }
    
        if (notExist)
        {
            struct node_* node = new struct node_;
            node->left = nullptr;
            node->right = nullptr;
            node->value = value;
            node->parent = target;
            if (dir == 1)
            {
                target->left = node;
            }
            else if (dir == 2)
            {
                target->right = node;
            }
        }
    }
    
    template<typename T>
    bool BinaryTree<T>::isExist(const T& value)
    {
        struct node_* target = nullptr;
        find(value, target);
        if (target != nullptr)
        {
            return true;
        }
        return false;
    }
    
    template<typename T>
    void BinaryTree<T>::erase(const T& value)
    {
        struct node_* parent = nullptr;
        bool flag = findParent(value, parent);
        if (!flag)
        {
            return;
        }
        if (parent == nullptr)
        {
            //if value exist, than the node is root.
            //left and right are both not nullptr
            struct node_* minNode = nullptr;
            findMin(_root->right, minNode);
            //minNode->left must be nullptr
            minNode->left = _root->left;
            minNode->right = _root->right;
            minNode->parent->left = nullptr;
            delete _root;
            _root = minNode;
            return;
        }
    
        struct node_* target = nullptr;
        if (parent->value < value)
        {
            target = parent->right;
        }
        else
        {
            target = parent->left;
        }
        if (target->left == nullptr && target->right == nullptr)
        {
            delete target;
            if (parent->value < value)
            {
                parent->right = nullptr;
            }
            else
            {
                parent->left = nullptr;
            }
        }
        else if (target->left == nullptr)
        {
            if (parent->value < value)
            {
                parent->right = target->right;
            }
            else
            {
                parent->left = target->right;
            }
            delete target;
        }
        else if (target->right == nullptr)
        {
            if (parent->value < value)
            {
                parent->right = target->left;
            }
            else
            {
                parent->left = target->left;
            }
            delete target;
        }
        else
        {
            //left and right are both not nullptr
            struct node_* minNode = nullptr;
            findMin(target->right, minNode);
            //minNode->left must be nullptr
            minNode->left = target->left;
            if (parent->value < value)
            {
                parent->right = minNode;
            }
            else
            {
                parent->left = minNode;
            }
            delete target;
        }
    }
    
    template<typename T>
    void BinaryTree<T>::traverse()
    {
        do_traverse(_root, std::bind(&BinaryTree<T>::print, this, std::placeholders::_1));
    }
    
    template<typename T>
    void BinaryTree<T>::print(struct node_* node)
    {
        if (node != nullptr)
        {
            std::cout << node->value << std::endl;
        }
    }
    
    template<typename T>
    void BinaryTree<T>::find(const T& value, struct node_*& rnode)
    {
        struct node_* target = _root;
        while(target != nullptr)
        {
            if (target->value == value)
            {
                rnode = target;
                return;
            }
            if (target->value < value)
            {
                target = target->right;
            }
            else
            {
                target = target->left;
            }
        }
        rnode = nullptr;
    }
    
    template<typename T>
    bool BinaryTree<T>::findParent(const T& value, struct node_*& rnode)
    {
        if (_root != nullptr && _root->value == value)
        {
            rnode = nullptr;
            return true;
        }
        //
        struct node_* target = _root;
        while(target != nullptr)
        {
            if (target->value < value)
            {
                if (target->right != nullptr && target->right->value == value)
                {
                    rnode = target;
                    return true;
                }
                target = target->right;
            }
            else
            {
                if (target->left != nullptr && target->left->value == value)
                {
                    rnode = target;
                    return true;
                }
                target = target->left;
            }
        }
        rnode = nullptr;
        return false;
    }
    
    template<typename T>
    void BinaryTree<T>::findMin(struct node_* node, struct node_*& rnode)
    {
        while(true)
        {
            if (node->left == nullptr)
            {
                rnode = node;
                return;
            }
            node = node->left;
        }
    }
    
    template<typename T>
    void BinaryTree<T>::do_traverse(struct node_* root, const handler& handler)
    {
        if (root != nullptr)
        {
            handler(root);
            do_traverse(root->left, handler);
            do_traverse(root->right, handler);
        }
    }

### 测试代码 ###

#include <QCoreApplication>
    #include "binarytree.h"
    #include "binarytree.cpp"
    
    int main(int argc, char *argv[])
    {
        QCoreApplication a(argc, argv);
    
        BinaryTree<int> itree;
        itree.insert(20);
        itree.insert(13);
        itree.insert(28);
        itree.insert(7);
        itree.insert(14);
        itree.insert(23);
        itree.insert(29);
        itree.insert(5);
        itree.insert(8);
        itree.insert(15);
        itree.insert(30);
    
        itree.traverse();
        itree.erase(20);
        std::cout << std::endl;
        itree.traverse();
    
        return a.exec();
    }