数据结构 二叉树和森林的小系统

Author Avatar
Sora 7月 08, 2021

数据结构虐我千百遍 我待数据结构如初恋
声明:发表在博客的所有数据结构作业源码均为本人独立编写。
题目:设计一个树和森林的小系统,包含以下功能,并可采用菜单方式来选择相应功能:

  • 采用多种方式建树或森林(指定输入、读入文件等);

  • 实现各遍历算法;例如:如图2所示的森林,后序遍历森林的序列输出:KEFBGCHIJDALNM

  • 与二叉树的相互转换(如图2-图3所示);

    #include <iostream>
    #include <fstream>
    using namespace std;
    struct Node{
      char data;
      Node *child, *brother;
      Node(): data('\0'), child(NULL), brother(NULL){};
      Node(char data_): data(data_), child(NULL), brother(NULL){};
    };
    Node *root = new Node(' ');
    void initialize(Node *father, fstream *file){
      int child_count;
      if(file) *file >> child_count;
      else cin >> child_count;
      if(child_count == 0) return;
      char data;
      if(file) *file >> data;
      else cin >> data;
      father->child = new Node(data);
      initialize(father->child, file);
      Node *p = father->child;
      for(int i = 1; i < child_count; i++){
          if(file) *file >> data;
          else cin >> data;
          p->brother = new Node(data);
          initialize(p->brother, file);
          p = p->brother;
      }
    }
    void goThrough(Node *head){
      if(head && head->child){
          Node *p = head->child;
          while(p){
              goThrough(p);
              cout << p->data;
              p = p->brother;
          }
      }
    }
    struct BNode{
      char data;
      BNode *lchild, *rchild;
      BNode(): data('\0'), lchild(NULL), rchild(NULL){};
      BNode(char data_): data(data_), lchild(NULL), rchild(NULL){};
    };
    BNode *broot;
    void convert(Node *thead, BNode *bhead){
      if(thead){
          if(thead->child) bhead->lchild = new BNode(thead->child->data);
          if(thead->brother) bhead->rchild = new BNode(thead->brother->data);
          convert(thead->child, bhead->lchild);
          convert(thead->brother, bhead->rchild);
      }
    }
    void frontGoThrough(BNode *head){
      if(head){
          cout << head->data;
          if(head->lchild) frontGoThrough(head->lchild);
          if(head->rchild) frontGoThrough(head->rchild);
      }
    }
    int main(){
      int method;
      cout << "请选择建立方法:1.输入;2.文件:";
      cin >> method;
      // method = 2;
      switch (method){
          case 1:
              cout << "请输入要建立的树:" << endl;
              initialize(root, NULL);
              break;
          case 2:{
              fstream f;
              f.open("./tree.txt", ios::in);
              if(!f.is_open()){
                  cout << "文件打开失败!" << endl;
                  exit(0);
              }
              initialize(root, &f);
              break;
          }
          default:
              cout << "输入错误,即将退出!" << endl;
              exit(0);
      }
      root = root->child;
      cout << "建立成功!" << endl;
      cout << "森林后序遍历:";
      goThrough(root);
      broot = new BNode(root->data);
      convert(root, broot);
      cout << endl << "转换为二叉树后的前序遍历:";
      frontGoThrough(broot);
      return 0;
    }
    

    示例数据:3 A 3 B 2 E 1 K 0 F 0 C 1 G 0 D 3 H 0 I 0 J 0 L 0 M 1 N 0