VC、C++保存二叉樹在文件中然后讀出來

2019-11-06 06:12:43

字體：大中小

供稿：網(wǎng)友

只要給每個節(jié)點按照它在二叉樹中的位置給與其一個唯一的編號，那么只要記錄每個節(jié)點的編號和相關(guān)信息，就能夠記錄一整棵二叉樹編號方式:用n(x)表示節(jié)點x的編號1、如果x是根節(jié)點，那么n(x)=12、如果x不是根節(jié)點，那么x有親節(jié)點p;如果x是p的左子節(jié)點，那么n(x)=n(p)*2，否則n(x)=n(p)*2+1在文件中記錄格式:節(jié)點總數(shù)節(jié)點1編號節(jié)點1信息節(jié)點2編號節(jié)點2信息...節(jié)點n編號節(jié)點n信息比如33 1001 2002 1這樣就記錄了一個有3個節(jié)點的二叉樹，其中根節(jié)點信息為200，左子節(jié)點信息為1，右子節(jié)點信息為100讀取時，對于每一個編號i，從i的二進制次高位開始，逐位判斷，就可以得到i所表示的節(jié)點的位置比如i=5，它的二進制是101，除掉最高位是01那么它就是根節(jié)點的左子節(jié)點(0)的右子節(jié)點(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個簡單方法