c++ - 从文件重建二叉树

Question

下面的信息是在一个文件中给出的，你必须在C++中创建一个函数来重建二叉树..

node   leftchild  rtchild

1       2   4
2       $   5
5       6   7
6       $   $
7       $   $
4       $     8
8       $   $

$- 空

谁能提出一些重建二叉树的想法...？？？

我做了:-

void rebuild_btree(node *tree) 
{
    ifstream fin("data.txt");
    string a;

    if (!fin)
        cout << "\nError in opening file.." << endl;
    else
        cout << "\nFile is successfully opened.." << endl;

    while (!fin.eof()) 
    {
        fin >> a;
        tree = insert(tree, a);
    }
    fin.close();
}

node* insert(node *root, string &dat)
{
    if(dat != "$")
    { 
       if(root == NULL)
       {
          root = new node;
          strcpy(root->data, dat);
          root->left = root->right = NULL;
       }
       else if (root->left == NULL)
            root->left = insert(root->left, dat);
       else
            root->right = insert(root->right, dat);
       return root;
    }
    return root;
}

这行不通..我认为有一些我没有得到的错误...如果你能捕获然后建议我....

Answer 1

问题一:

不要这样做:(这是错误的)。 EOF 标志在您尝试读取超过 EOF 之前不会设置，而最后一次成功读取读取到(但不是超过)EOF。所以你进入循环的次数比要求的多。

while (!fin.eof()) 
{
    fin >> a;
    tree = insert(tree, a);
}

应该这样写:这是有效的，因为运算符>>返回对流的引用。当在 bool 上下文中使用流时(如 while 的条件)，它会转换为可转换为 bool 的对象，如果未设置任何错误标志，则该对象的值为 true。因此，如果读取成功，则进入循环，否则不进入循环。

while (fin >> a) 
{
    tree = insert(tree, a);
}

问题2:

这显然不能编译，因为 String 不是标准类型。
类型是字符串(小写的 s)，它在 std::命名空间中。所以请使用 std::string。

如果这是您定义的类型，那么我们需要知道它是什么来理解这一行是如何工作的:

fin >> a;

问题3:

如果传递的字符串是“$”，则函数 insert() 不会返回值。 C++ 函数必须始终返回一个值(除非返回类型为 void)。否则就是“未定义的行为”。

问题4:

Insert() 显然行不通。

• 您不要尝试区分三种不同的输入类型:
  可以是“整数索引”、“$”或“,”。
• 您没有将输入位置关联到树的结构。

问题5:

您应该为二叉树考虑一种不同的输入格式。这特别难以解析和重新构建，因为它需要两次传递。您需要第一遍才能读取所有节点。然后你需要第二遍来重新构建树结构。

这显然是作业!

提示:

一次读取一行并正确解析该行:

std::string  line;
std::getline(fin, line);

一次性解析整行并构建一个对象来表示节点。不幸的是，您可以构建真实节点，因为这种输入格式需要两次传递。

struct TmpNode { int value; std::string left; std::string right; }  tmp;
std::istringstream data(line);

data >> tmp.value >> tmp.left >> tmp.right;

因为您需要一个两阶段构建 1) 阅读 2) 构建树。您需要存储 TmpNode 对象，直到您拥有所有对象并可以构建树。

std::map<int,TmpNode>  nodes;
nodes[boost::lexical_cast<int>(tmp.value)] = tmp;

一旦您将所有 TmpNode 存储在 map 中。您现在可以轻松地遍历 map 并构建您的树。

node* buildTree(std::string const& nodeID)
{
    if (nodeID == "$") { return NULL;}

    TmpNode& n = nodes[boost::lexical_cast<int>(nodeID)];
    return new node(nodeID, buildTree(n.left), buildTree(n.right));
}