如何按顺序打印出二叉树? [英] How to print out a binary tree in order?

问题描述

我正在努力打印我编码的二叉树.这是一个小程序，您可以在其中输入不同的状态，然后在二叉树中按字母顺序对它们进行排序，然后再按字母顺序将它们打印出来.
我应该如何开始使用列表功能?我在互联网上读到，递归算法是最好的，但是我真的不知道如何在我的设置中做到这一点.

I'm struggling with the printing of a binary tree that I coded. It's a little program where you can type in different states and then it orders them alphabetically in the binary tree and afterwards it should print them out again, in alphabetic order.
How should I start with the listing function? I read in the internet that a recursive algorithm would be the best, but I don't really know how to do that with my setup.

#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

推荐答案

假设 node 是 Node * 类型的指针，表示树的某个节点.然后 inorder(Node *)定义如下:

Say that node is a pointer of type Node* representing some node of your tree. Then inorder(Node*) is defined as follows:

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
}

这篇关于如何按顺序打印出二叉树?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！