C++ 二叉搜索树打印和深度计算

Question

我已经创建了二叉搜索树。我的函数可以添加、删除和查找带有数字的节点。所有这些功能都运行良好。你能帮我实现两个功能吗:1) 打印 BST2) 计算BST的深度？

我不知道如何快速简便地完成此操作。我在添加新节点期间计算深度，但我只想拥有这样做的功能。

class Node{
    public:
shared_ptr<Node> right;
shared_ptr<Node> left;
int number;
Node(int number)
{
    this->number=number;
    right=nullptr;
    left=nullptr;
}
~Node()
{
    cout<<"Deleted"<<" "<<number<<endl;
}
};
class BT
{
    public:
    shared_ptr<Node> root;
    int deep;
    BT(int num)
    {
      deep=0;
      root=make_shared<Node>(num);
    }

    void add_number(int num)
    {
        shared_ptr<Node> new_num=make_shared<Node>(num);
        shared_ptr<Node> tmp=root;
        int tmp_deep=0;
        while(tmp!=nullptr)
        {
            tmp_deep++;

            if(tmp->number>num)
            {
            if (tmp->left==nullptr)
            {
                tmp->left=new_num;
                break;
            }

            else
             tmp=tmp->left;
            }

            else if (tmp->number<num)
            {
                if (tmp->right==nullptr)
                 {
                tmp->right=new_num;
                break;
            }
            else
               tmp=tmp->right;
            }


        }
        tmp.reset();
        if (tmp_deep>deep)
            deep=tmp_deep;

    }

    shared_ptr<Node> find_node(int num)
    {
        shared_ptr<Node> tmp=root;

        while (tmp!=nullptr && tmp->number!=num)
        {
           if (tmp->number>num)
            tmp=tmp->left;
            else if (tmp->number<num)
                tmp=tmp->right;

        }

        if (tmp==nullptr)
        {
            cout<<"Not found";
            return nullptr;
        }
        else
            return tmp;

    }

    void delete_ (int num)
    {
        shared_ptr<Node> tmp=root;
        shared_ptr<Node> previous=root;


          while (tmp!=nullptr && tmp->number!=num)
        {
           if (tmp->number>num)
           {
               previous=tmp;
                tmp=tmp->left;

           }

            else if (tmp->number<num)
            {
                previous=tmp;
                tmp=tmp->right;
            }


        }

        if (tmp==nullptr)
        {
            cout<<"Not found";
        }
        else
        {

            if(tmp->left==nullptr && tmp->right==nullptr)
            {

                if (previous->number>tmp->number)
                previous->left=nullptr;
                else
                previous->right=nullptr;


                tmp.reset();
            }
            else if (tmp->left==nullptr && tmp->right!=nullptr)
            {
                if(tmp->right!=nullptr)
                {
                 previous->right=tmp->right;
                }
                else
                    previous->right=tmp->left;
                tmp.reset();
            }
            else if (tmp->left!=nullptr && tmp->right==nullptr)
            {
                if(tmp->right!=nullptr)
                {
                 previous->left=tmp->right;
                }
                else
                    previous->left=tmp->left;
                tmp.reset();
            }
            else if (tmp->left!=nullptr && tmp->right!=nullptr)
            {

                shared_ptr<Node> tmp_left=tmp->right;
                shared_ptr<Node> prev_left=tmp->right;
               while (tmp_left->left!=nullptr)
               {

                        //prev_left=tmp_left;
                        tmp_left=tmp_left->left;


                }
                if (tmp->number<previous->number)
                    previous->left=tmp_left;
                else
                    previous->right=tmp_left;

            prev_left->left=tmp_left->right;
            tmp_left->left=tmp->left;
            tmp_left->right=tmp->right;
            tmp.reset();

            }




        }

        void show_bt()
        {

        }
        void calc_depth()
        {

        }

    }




};

Answer 1

计算深度和打印都可以使用tree traversal来完成.此外，树遍历具有O(n)时间复杂度(n是树中的节点数)。

PS:为了计算树的深度，您可以使用三个 traversal methods 之一.

1. 在每次递归调用中增加深度变量
2. 然后减少它
3. 保存总最大值(在减少之前)