c++ - 如何按顺序打印出二叉树？

Question

我正在努力打印我编写的二叉树。这是一个小程序，您可以在其中输入不同的状态，然后在二叉树中按字母顺序对它们进行排序，然后它应该再次按字母顺序打印出来。
listing功能应该怎么入手？我在 Internet 上读到递归算法是最好的，但我真的不知道如何用我的设置做到这一点。

#include <iostream>
#include <stdlib.h>
#include <string>
using namespace std;


int insertInt()
{
  int x;
  cin>>x;
  while(cin.fail())
    {
      cout<<"Error! Please enter a valid integer: ";
      cin.clear();
      cin.ignore();
      cin>>x;
    }
  return x;
}//closes insertInt

struct node
{
  string info;
  node* right;
  node* left;
}; //closes node

class States
{
 private:
  node* start;

 public:
  void insert();
  void delete();
  void list();
  void search();
  States();
}; //closes States class

States::States()
{
  start = new node;
  start -> left = NULL;
  start -> right = NULL;
  start -> info = " ";
}

void States::insert()
{
  string state;
  char c;
  node *temp, *p, *s;
  p = start;
  s = start;
  temp = new node;
  temp ->info = state;

  cout<<"Please enter the state you want to add: ";
  cin>>state;

  if(s -> info == " ")
    {
      s -> info = state;
      cout<<"Added state "<<state<<"to the list.\n";
      cout<<"Ready to continue? (enter y)";
      cin>>c;
      return;
    }//close if
  else
    {
      while(true)
    {
      //moving pointer until next level is empty

      if(s->info > temp->info && s->left != NULL)
        {
          s = s->left;
          continue;
        }//close if

      if(s->info < temp->info && s->right != NULL)
        {
          s = s->right;
          continue;
        }//close if

      //inserting the new node

      if(s->info > temp->info && s-> left == NULL)
        {
          s -> left = temp;
          break;
        }//close if
      if(s->info < temp->info && s->right == NULL)
        {
          s->right = temp;
          break;
        }//cloese if

    }//close while loop
    }//close else

}//close insert function

void States::list()
{
  node *p, *s;
  p = start;
  s = start;

  if(start->info == " ")
    cout<<"Nothing to display!\n";

  if(s->left == NULL)
    cout<<"-"<<s->info<<endl;

}


void States::search()
{
  string state;
  cout<<"Please enter the state you're looking for: ";
  cin>>state;
  node *s, *temp;
  s = start;
  temp = new node;
  temp ->info = state;

  while(true)
    {
      if(s->info == state)
    {
      cout<<"Found your state!\n";
      break;
    }
      if(s->info > temp->info)
    {
      if(s->left == NULL)
        break;
      else
        s = s->left;
      continue;
    }//close if
      if(s->info < temp->info)
    {
      if(s->right == NULL)
        break;
      else
        s = s->right;
      continue;
    }//close if
    }//close while loop
}//close search function

int main()
{
  States s1;
  int c;
  int exit = 0;

  while(exit == 0)
    {
      cout<<"----------------------------------------------------------------------\n";
      cout<<"\t\tChoose one of the following options\n";
      cout<<"\t\t\t\t(1) Add a state\n";
      cout<<"\t\t\t\t(2) List states\n";
      cout<<"\t\t\t\t(3) Search for state\n";
      cout<<"\t\t\t\t(4) Delete state\n";
      cout<<"\t\t\t\t(5) Exit\n";
      cout<<"----------------------------------------------------------------------\n";
      c = insertInt();

      switch(c)
    {
    case 1:
      s1.insert();
      break;
    case 2:
      s1.list();
      break;
    case 3:
      s1.search();
      break;
    case 4:
      s1.delete();
      break;
    case 5:
      exit = 1;
      cout<<"Exiting...\n";
      break;
    default:
      cout<<"Error. Please enter a valid integer.\n";
    }//close switch
    }//closes while loop

}//closes main

Answer 1

假设 node 是一个 Node* 类型的指针，表示树的某个节点。那么inorder(Node*)定义如下:

void inorder(Node* node)
{
    if (!node) // end the recursion if node == nullptr
       return; 
    inorder(node->left);            // display the left subtree
    std::cout << node->info << " "; // display the current node
    inorder(node->right);           // display the right subtree
}