我创建了二叉搜索树。我的函数可以添加、删除和查找带有数字的节点。所有这些功能都运行良好。你能帮我两个功能吗:1( 打印BST2( 计算BST的深度?
我不知道如何以快速简便的方式做到这一点。深度 i 在添加新节点期间计算,但我只想拥有用于执行此操作的功能。
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()
{
}
}
};
计算深度和打印都可以使用树遍历来完成。此外,树遍历具有O(n)
的时间复杂度(n
是树中的节点数(。
PS:要计算树深度,您可以使用三种遍历方法之一。
- 在每个递归调用中增加深度变量
- 之后减少它并
- 保存总最大值(在减少之前(
这个练习是每个程序员都必须做的事情,学习递归。这也可以通过迭代来完成,但这需要构建您的堆栈
对于递归,必须创建一个函数,该函数调用自身以"计算"结果。
你必须思考,如何从较小的结果中"计算"最终结果。
让我们看一下深度计算。
这是在一棵树上。这是由节点构造的。
那么我们如何在节点上计算一些东西以获得最终结果呢?
每个节点的高度比 (左子树和右子树(的最大高度大 1。如果没有子树,我们只会说它的高度为零。
顺便说一句:永远不要在一开始就寻找快速和简单的东西。第一步始终是:让它工作。