創建/輸出二叉樹（非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）

回答

相關問題