需要帮助搜索二叉树

Question

trav.h
#include <map>
#include <iostream>
class Tree
{
Tree *left;
Tree *right;
int node;
static std::map<int, Tree *> allNodes;
public:
Tree(int n, Tree *l = 0, Tree *r = 0) : left(l), right(r), node(n)
{
allNodes[n] = this;
}
int GetNode() { return node; }
void Insert(Tree *newnode)
{
if (newnode->node == this->node)
{
}
// skip dup
else if (newnode->node < this->node)
{
left = newnode;
cout << "left" << left->node << endl;
}
else if (newnode->node > this->node)
{
right = newnode;
cout << "right" << right->node << endl;
}
}
int Find(int node)
{
if (node == this->node){}
// skip dup
else if (node < this->node)
{
return left->node;
}
else if (node > this->node)
{
return right->node;
}
}
// print does an inorder search
void Print(Tree *root)
{
if (root == nullptr)
{
return;
}
Print(root->left);
cout << root->node << endl;
Print(root->right);
}
};
trav.cpp
#include <iostream>
#include <string>
#include <vector>
using namespace std;
#include "trav.h"
std::map<int, Tree *> Tree::allNodes;
// trav print
// trav find X
int main(int argc, char *argv[])
{
if (argc < 2)
return 0;
string cmd(argv[1]);
// READ IN THE INTEGERS
vector<int> ids;
int input;
while (cin >> input)
{
ids.push_back(input);
}
// MAKE NODES FROM THE INTEGERS
vector<Tree *> nodes;
for (int id : ids)
{
nodes.push_back(new Tree(id));
}
if (ids.size() == 0)
return -1;
// PUT NODES INTO A TREE USING Insert
Tree *theTree = nodes[0];
if (theTree == nullptr)
return -1;
for (auto n : nodes)
{
theTree->Insert(n);
}
// PRINT TREE
if (cmd == "print")
theTree->Print(theTree);
else if (cmd == "find")
{
string cmd2 = argv[2];
int num = stoi(cmd2);
int result = theTree-> Find(num);
if(result!=0)
cout<<num<<endl;
else
cout<<"-1"<<endl;
}
return 0;
}

创建Find((时遇到问题

1. 对树进行有序遍历并打印遍历结果
2. 在树中找到一个值，如果找到就打印出来

当argv[1]＝＝"0"时触发第一个动作；打印"；。如果是，请执行有序遍历并打印每个树节点，每行输出一个节点。有序遍历意味着遍历左子树(如果存在(，然后打印当前节点，然后遍历右子树(如果有(。

当argv[1]＝＝"0"时触发第二动作；查找"；。如果是，请在树中搜索argv[2](需要转换为int的字符串(。如果找到，打印int。如果没有找到，打印-1。输出格式应为一行：

Answer 1

有一些错误。

Insert((方法只在left或right上添加新节点。如果这些指针仍然为NULL，这是可以的。否则你应该递归到它们中。没有对Insert()的递归调用。

Find()方法也有一个问题，在启用警告的情况下(g++ -Wall ....(，已经发现该问题：如果node值与查询匹配，它将不执行任何操作。没有返回值，所以它将返回一些未定义的值。此处未命中return 0;。

Answer 2

我对Insert和Find方法做了一些更改：

void Insert(Tree *newnode)
{
// skip dup
if (newnode->node == this->node)
{
}
else if (newnode->node < this->node)
{
if(left != nullptr)
{
left -> Insert(newnode);
}
else 
{
left = newnode;
}
}
else if (newnode->node > this->node)
{
if(right != nullptr)
{
right -> Insert(newnode);
}
else
{
right = newnode;
}
}
}
// 1 if found,
// 0 if not found
int Find(int node)
{
if (node == this->node)
{
return 1;
}
else if (node < this->node)
{
if(left == nullptr)
{
return 0;
}
return left->Find(node);
}
else
{
if(right == nullptr)
{
return 0;
}
return right->Find(node);
}
}

Insert检查当前节点是否已经有left或right，如果已经，则向左或向右插入，否则设置为向左或向右。对Find进行了类似的检查。希望这能有所帮助。