给定一棵二叉树，设计一个算法，该算法创建每个深度的所有节点的链表

Question

我已经尝试在 C++ 中实现相同的功能。我想我几乎得到了 it.However 我在从链表访问节点时遇到错误。

list<list<Node*> > Binary_Tree::level(Node* node)
{
list<Node*> current,parent;
list<list<Node*> > result;

list<Node*>::iterator itr;
if (node != NULL)
current.push_back(node);

while(current.size() > 0)
{
   result.push_back(current);
   parent = current;

   current.clear();
   itr = parent.begin();
   while(itr != parent.end())
   {
     if(itr->left != NULL) // I am getting an error here.error:    request for member ‘right’ in ‘* itr.std::_List_iterator<_Tp>::operator-><Node*>()’, which is of pointer type ‘Node*’ (maybe you meant to use ‘->’ ?
     current.push_back(itr->left);

     if(itr->right != NULL)
       current.push_back(itr->right);

        itr++;
   }

}

return 结果； }

Answer 1

以上问题的解决方法如下。我放完整的代码。

#include <iostream>
#include <list>

using namespace std;
struct Node{

Node *left;
Node *right;
int data;
Node(int d)
{
  left = NULL;
  right = NULL;
  data =d;
} 
};
class Binary_Tree{

Node *root;
list<list<Node*> > level(Node*);
public:
Binary_Tree()
{
   root = NULL;
} 

  void insert(int element);
  list<list<Node*> > level();

};
void Binary_Tree::insert(int ele)
{
 Node *node = new Node(ele); 
  if (root == NULL)
  {
    root = node;
    return;
  }
  Node* temp = root;
  while(temp != NULL)
  {
    if (ele > temp->data)
    {
      if(temp->right != NULL)
         temp = temp->right;
      else
      { 
        temp->right = node;
        return;
      }
    } 
   else
   {
      if(temp->left != NULL)
        temp = temp->left;
      else
       {
         temp->left = node;
         return;
       }
   }
  }  
}
list<list<Node*> > Binary_Tree::level()
{
   return level(root);
}
list<list<Node*> > Binary_Tree::level(Node* node)
{
   list<Node*> current,parent;
   list<list<Node*> > result;

   list<Node*>::iterator itr;
   if (node != NULL)
   current.push_back(node);

   while(current.size() > 0)
   {
    result.push_back(current);
    parent = current;

    current.clear();
    itr = parent.begin();
    while(itr != parent.end())
    {
     if((*itr)->left != NULL)
      current.push_back((*itr)->left);

     if((*itr)->right != NULL)
       current.push_back((*itr)->right);

        itr++;
   }

}
return result;
}

int main()
{
list<list<Node*> >l;
list<list<Node*> >::iterator itr;
list<Node*>::iterator itr1;

Binary_Tree bt;
bt.insert(3);
bt.insert(2);
bt.insert(4);
bt.insert(1);
bt.insert(5);
l=bt.level();

itr = l.begin();
while(itr != l.end())
{

 itr1 = (*itr).begin();
 while(itr1 != (*itr).end())
 {
     cout<<(*itr1)->data<<" ";
     itr1++; 
 }
 cout<<endl;
 itr++;

} 

return 0;
}

给定一棵二叉树，设计一个算法，该算法创建每个深度的所有节点的链表

Given a binary tree, design an algorithm which creates a linked list of all the nodes at each depth

c++

binary-tree

linked-list

levels