创建/输出二叉树（非BST）

我的代码（如下）工作，除非所需的密钥不在列表中（所以如果一个节点没有对其父节点的引用）。它忽略了节点，只是在没有它们的情况下制作一棵树。我该如何解决它？我一直在考虑只要所有密钥都处于重新循环状态，并继续相应地添加和删除。创建/输出二叉树（非BST）

#include <iostream> 
#include <string> 
#include <sstream> 
#include <memory> 
#include <map> 

struct Foo { 
    int data{0}; 
    int left{-1}; 
    int right{-1}; 
}; 

std::istream& operator>>(std::istream& in, Foo& ff) { 
    in >> ff.data >> ff.left >> ff.right; 
    return in; 
} 

struct Del { 
    template <class T> 
    void operator()(T* p) { 
    std::cout << "[deleted #" << (p ? p->data : 0) << "]\n"; 
    delete p; 
    } 
}; 

struct Bar { 
    int data{0}; 
    std::unique_ptr<Bar, Del> lef; 
    std::unique_ptr<Bar, Del> rig; 
}; 

void print(const std::unique_ptr<Bar, Del>& node) { 
    if (node) { 
    std::cout << ' ' << node->data; 
    print(node->lef); 

    print(node->rig); 
    } 
} 

int main() { 
    std::string input = 
     "101 1 3 102 2 8 104 6 7 103 -1 5 109 -1 -1 106 4 -1 107 -1 -1 108 -1 " 
     "-1 105 -1 -1"; 

    std::istringstream IN(input); 

    std::map<int, std::pair<Bar*, bool>> mlist; 
    std::unique_ptr<Bar, Del> root; 
    int row = 0; 
    Foo entry; 
    while (IN >> entry) { 
    if (0 == row) { 
     root.reset(new Bar); 
     Bar* node = root.get(); 
     node->data = entry.data; 
     std::cout << row << " [created #" << entry.data << ']'; 
     if (0 <= entry.left) 
     mlist.emplace(entry.left, std::make_pair(node, true)); 
     if (0 <= entry.right) 
     mlist.emplace(entry.right, std::make_pair(node, false)); 

    } else { 
     auto it = mlist.find(row); 
     if (mlist.end() != it) { 
     if (it->second.second) { 
      it->second.first->lef.reset(new Bar); 
      Bar* node = it->second.first->lef.get(); 
      node->data = entry.data; 
      std::cout << row << " [created #" << entry.data << ']'; 
      if (0 <= entry.left) 
      mlist.emplace(entry.left, std::make_pair(node, true)); 
      if (0 <= entry.right) 
      mlist.emplace(entry.right, std::make_pair(node, false)); 

      mlist.erase(it); 
     } else { 
      it->second.first->rig.reset(new Bar); 
      Bar* node = it->second.first->rig.get(); 
      node->data = entry.data; 
      std::cout << row << " [created #" << entry.data << ']'; 
      if (0 <= entry.left) 
      mlist.emplace(entry.left, std::make_pair(node, true)); 
      if (0 <= entry.right) 
      mlist.emplace(entry.right, std::make_pair(node, false)); 

      mlist.erase(it); 
     } 
     // mlist.erase(it); 
     } 
    } 
    std::cout << " list size " << mlist.size() << '\n'; 
    ++row; 
    } 
    std::cout << "final list size " << mlist.size() << "\n\n"; 
    print(root); 
    std::cout << "\n\n"; 
    std::cout << "Lets see whats left in the list:"; 

    return 0; 
}

来源

2016-11-09 P.T

那么，你的二叉树和二叉搜索树有什么区别？我的理解是，在二叉树中，每个节点可能有两个不必排序的子树。 –

是的，这只是一棵二叉树。它根本没有排序，但它确实遵循最大两个节点。 –

'root - > Left'似乎不是有效的。你的意思是'root - > Left'（使用' - >'运算符而不是'-'运算符和'>'运算符）？为什么不发布[最小，完整和可验证示例]（http://stackoverflow.com/help/mcve）？ – MikeCAT

其实，我只是使用了一个节点的向量，它的工作完美。对不起所有的困惑！

来源

2016-11-10 23:02:33

创建/输出二叉树（非BST）

回答

相关问题