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

July 8, 2021 · 纯属折腾 · 64次阅读

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

  • 采用多种方式建树或森林(指定输入、读入文件等);
  • 实现各遍历算法;例如:如图2所示的森林,后序遍历森林的序列输出:KEFBGCHIJDALNM
  • 与二叉树的相互转换(如图2-图3所示);
    iShot2021-07-08 01.36.17.png
#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

除声明外inSoraSky博客(http://www.sorasky.in/)所有内容均为本人所原创,转载时请注明来源!

喝杯水

数据结构二叉树森林

最后编辑于19天前

添加新评论