VC、C++保存二叉树在文件中然后读出来

2019-11-06 06:12:43

字体：大中小

来源：转载

供稿：网友

只要给每个节点按照它在二叉树中的位置给与其一个唯一的编号，那么只要记录每个节点的编号和相关信息，就能够记录一整棵二叉树编号方式:用n(x)表示节点x的编号1、如果x是根节点，那么n(x)=12、如果x不是根节点，那么x有亲节点p;如果x是p的左子节点，那么n(x)=n(p)*2，否则n(x)=n(p)*2+1在文件中记录格式:节点总数节点1编号节点1信息节点2编号节点2信息...节点n编号节点n信息比如33 1001 2002 1这样就记录了一个有3个节点的二叉树，其中根节点信息为200，左子节点信息为1，右子节点信息为100读取时，对于每一个编号i，从i的二进制次高位开始，逐位判断，就可以得到i所表示的节点的位置比如i=5，它的二进制是101，除掉最高位是01那么它就是根节点的左子节点(0)的右子节点(1)C++代码如下#include <iostream>#include <fstream>#include <string>using namespace std;class Binary_Tree{PRivate: struct Node { int data; Node *parent,*left,*right; Node() { parent=left=right=0; data=-1; } }; Node *root; int size; void Clear(Node*); void Clear();//清空原先二叉树的信息 void Save(Node*,int,ofstream&);public: Binary_Tree(); bool Load(string);//从指定文件中读取二叉树 bool Save(string);//将二叉树保存于指定文件};void Menu_Display();Binary_Tree T;int main(){ int i; do { Menu_Display(); cin>>i; if (i==1) { string s; cout<<"请输入文件名"<<endl; cin>>s; if (T.Load(s)) cout<<"读取成功"<<endl; else cout<<"读取失败，文件不存在或格式错误"<<endl; } else if (i==2) { string s; cout<<"请输入文件名"<<endl; cin>>s; if (T.Save(s)) cout<<"保存成功"<<endl; else cout<<"保存失败"<<endl; } cout<<endl; }while (i); return 0;}Binary_Tree::Binary_Tree(){ root=0; size=0;}bool Binary_Tree::Load(string filename){ ifstream fin(filename.c_str()); int n; Node *p; int i,j; int count; Clear(); if (fin.fail()) return false; if (!(fin>>n)) return false; count=0; size=n; for (i=0;i<n;i++) { int id,data; if (!(fin>>id>>data) || id<=0) { Clear(); fin.close(); return false; } if (root==0) { root=new Node; count++; } p=root; for (j=30;j>=0;j--) if (id & (1<<j)) break; while (j--) { if (!(id & (1<<j))) { if (p->left==0) { p->left=new Node; p->left->parent=p; count++; } p=p->left; } else { if (p->right==0) { p->right=new Node; p->right->parent=p; count++; } p=p->right; } } p->data=data; p=0; } fin.close(); if (count>n) { Clear(); return false; } return true;}bool Binary_Tree::Save(string filename){ ofstream fout(filename.c_str()); if (fout.fail()) return false; fout<<size<<endl; if (root) Save(root,1,fout); fout.close(); return true;}void Binary_Tree::Save(Node *p,int id,ofstream &fout){ fout<<id<<' '<<p->data<<endl; if (p->left) Save(p->left,id*2,fout); if (p->right) Save(p->right,id*2+1,fout);}void Binary_Tree::Clear(){ if (root!=0) Clear(root); root=0; size=0;}void Binary_Tree::Clear(Node *p){ if (p->left) Clear(p->left); if (p->right) Clear(p->right); delete p;}void Menu_Display(){ cout<<"----------------------------------------------------"<<endl; cout<<"请输入指令"<<endl; cout<<"输入1 从指定文件读读二叉树"<<endl; cout<<"输入2 将二叉树存入指定文件"<<endl; cout<<"输入0 退出程序"<<endl;}

上一篇：c++之stl 二叉树

下一篇：提高C++程序运行效率的10个简单方法