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

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

• 采用多种方式建树或森林（指定输入、读入文件等）；

• 实现各遍历算法；例如：如图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