Ⅰ 求助:关于二叉树存入文件的问题
只要给每个节点按照它在二叉树中的位置给与其一个唯一的编号,那么只要记录每个节点的编号和相关信息,就能够记录一整棵二叉树 编号方式: 用n(x)表示节点x的编号 1、如果x是根节点,那么n(x)=1 2、如果x不是根节点,那么x有亲节点p;如果x是p的左子节点,那么n(x)=n(p)*2,否则n(x)=n(p)*2+1 在文件中记录格式: 节点总数 节点1编号 节点1信息 节点2编号 节点2信息 … 节点n编号 节点n信息 比如 3 3 100 1 200 2 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; }
Ⅱ 如何将下面的二叉树的程序运行结果前序遍历顺序输出到文件D:\\BiTree.txt。
//按顺序打印二叉树结果到文件中voidOutputInPreOrder(BiTree*T,FILE*fp){//同遍历,使用递归if(T){//输出节点数值fprintf(fp,"%d",T->data);OutputInPreOrder(T->lchild,fp);OutputInPreOrder(T->rchild,fp);}}voidmain(){//打开文件FILE*fp=fopen("D:\BiTree.txt","w");//输入二叉树内容BiTree*root=createBiTree();//按顺序打印二叉树结果到文件中OutputInPreOrder(root,fp);//关闭文件流fclose(fp);}
靠,我提交全部代码会提交失败~就把原来的main函数改成这两段,
另外,为了操作方便,
typedef int DataType;这个原来是char我改成了int,不过写文件的道理是一样的。
Ⅲ C++怎么把二叉树到文件中
可以把二叉树的前序遍历和中序遍历同时存入文件中,利用两种遍序的方式可以恢复出唯一的二叉树。
Ⅳ 从文件中数据创建二叉树
从文件中数据创建二叉树⒔�⒁桓龅チ幢恚�⒋悠聊幌允镜チ幢碓�亓斜怼� 2、从键盘输入一个数,查找在以上创建的单链表中是否存在该数;如果存在,显示它的位置;如果不存在,给出相应提示。 3、在上述的单链表中的指定位置插入指定的元素 4、删除上述单链表中指定位置的元素。 源程序:头文件 #includeiostream.h
Ⅳ 二叉搜索树的实现
前段时间正好写了~ 一个头文件搞定,声明和定义放一块了(我觉得模版类这样写的话更方便)/* * File: tree.h * Author: lenovo2010302580340 * * Created on 2011年6月3日, 下午7:12 */#ifndef TREE_H#defineTREE_H#include<iostream>using std::cout;using std::endl;template<typename T> class BinarySearchTree { public: BinarySearchTree():root(0){ } BinarySearchTree(const BinarySearchTree& rhs) { root = clone(rhs.root); } ~BinarySearchTree() { makeEmpty(); } const T& findMin() const { if(root) return (findMin(root))->element; throw 1; } const T& findMax() const { if(root) return (findMax(root))->element; throw 1.1; } bool contains( const T& x) const { return contains(x,root); } bool isEmpty() const { return (!root) ? true : false; }void makeEmpty() { makeEmpty(root); } void insert( const T& x) { insert(x, root); } void remove( const T& x) { remove(x, root); } const BinarySearchTree& operator=(const BinarySearchTree& rhs) { if(this!=&rhs) {makeEmpty(); root=clone(rhs.root); } return *this; } void printPost()const { printPost(root); } void printPre()const { printPre(root); } void printInorder()const { printInorder(root); } void draw() { draw(root,70); } void draw2() { draw2(root,1); } private: struct BinaryNode { T element; BinaryNode *left; BinaryNode *right; BinaryNode(const T& x, BinaryNode* lt, BinaryNode* rt) : element(x),left(lt),right(rt){} };BinaryNode *root;void insert(const T& x, BinaryNode*& t) const {// if(!t)t=new BinaryNode(x,0,0);// else if(x<t->element) insert(x,t->left);// else if(x>t->element) insert(x,t->right); if(!t){ t=new BinaryNode(x,0,0);return;} BinaryNode* cur(t),*pre; while(cur) { if(x<cur->element){pre=cur;cur=cur->left;} else if(x>cur->element){pre=cur;cur=cur->right;} else return; } if(x<pre->element){pre->left=new BinaryNode(x,0,0);return;} else if(x>pre->element){pre->right=new BinaryNode(x,0,0);return;} } // this is the recursive one: void remove(const T& x, BinaryNode*& t) const{ if(!t)return; if(x<t->element)remove(x,t->left); else if(x>t->element)remove(x,t->right); else// equal now: if(t->left&&t->right) { t->element=findMin(t->right)->element; remove(t->element,t->right); } else { BinaryNode* oldNode=t; if(t->left){t=t->left;delete oldNode;} else if(t->right){t=t->right;delete oldNode;} else {delete t;t=0;} } }/*// this is the loop one: void remove(T x, BinaryNode*& t) const { if(!t)return; BinaryNode* use=t,*pre(use); T i(use->element); while(1){ while(use) { if(x<use->element){pre=use;use=use->left;} else if(x>use->element){pre=use;use=use->right;} else break; } if(!use)break; // now equal if(use->left&&use->right) { BinaryNode* min=use->right; pre=use; while(min->left){pre=min;min=min->left;} i=use->element; use->element=min->element; x=use->element; use=min; } else { if(use->left) { if(x<i) pre->left=use->left; else if(x>i)pre->right=use->left; else throw 'x'; delete use; use=0; break; } else if(use->right){ if(x<i) pre->left=use->right; else if(x>i)pre->right=use->right; else throw 'x'; delete use; use=0; break; } else { if(pre->element>x) pre->left=0; else if(pre->element<x)pre->right=0; else throw 'x'; delete use; use=0; break;} } } }*/ BinaryNode* findMin(BinaryNode* t) const { if(t)while(t->left!=0)t=t->left; return t; } BinaryNode* findMax(BinaryNode* t) const { if(t)while(t->right!=0)t=t->right; return t; } bool contains(const T& x, BinaryNode * t) const { while(t) { if(x<t->element) t=t->left; else if(x>t->element)t=t->right; else return 1; } return 0; } void makeEmpty(BinaryNode*& t) { if( t !=0) { makeEmpty( (t->left) ); makeEmpty( (t->right) ); delete t; } t = 0; } BinaryNode* clone(BinaryNode* t) const { if(0 == t) { return 0; } return new BinaryNode(t->element, clone(t->left), clone(t->right)); } // BinaryNode* nleft=BinaryNode(t->element, clone(t->left), clone(t->right)); // BinaryNode* nright=BinaryNode(t->element, clone(t->left), clone(t->right)); // BinaryNode* node=BinaryNode(t->element, clone(t->left), clone(t->right));void printPost(BinaryNode* t)const { if(!t)return; printPost(t->left); printPost(t->right); cout<<t->element<<" "; } void printPre(BinaryNode* t)const { if(!t)return; cout<<t->element<<" "; printPre(t->left); printPre(t->right); } void printInorder(BinaryNode* t)const { if(!t)return; printInorder(t->left); cout<<t->element<<" "; printInorder(t->right); } void draw(BinaryNode* t,int x) { if(!t)return; x/=2; int i(x); while(i–)cout<<" "; cout<<t->element<<endl; draw(t->left,x); draw(t->right,x); } void draw2(BinaryNode* t,int x) { if(!t)return; x+=5; int i(x); while(i–)cout<<" "; cout<<t->element<<endl; draw2(t->left,x); draw2(t->right,x); } };#endif/* TREE_H */ Neatbeans和codeblock下都能编译通过,绝对没问题~
Ⅵ 二叉搜索树的基本操作
哈哈,居然有人来提问了,城院的
我刚奋斗了2小时做了下,你看看对不?
Test5.cpp:
#include<iostream.h>
#include<stdlib.h>
typedefdoubleElemType;
#defineMaxsize100
#include"BSTree.h"
voidmain()
{
inti,n;
ElemTypex;
ElemTypea[Maxsize];
BTreeNode*bst;
InitBSTree(bst);
cout<<"请输入你所要测试的二叉搜索树的结点的个数:";
cin>>n;
cout<<"请输入你要测试的二叉搜索树:"<<endl;
for(i=0;i<n;i++){
cin>>a[i];
}
CreateBSTree(bst,a,n);
cout<<"你输入的二叉搜索树的广义表形式为:";
PrintBSTree(bst);
cout<<endl;
cout<<"输入一个待插入结点的整数值:";
cin>>x;
Insert(bst,x);
cout<<"插入结点后的二叉搜索树的广义表形式为:";
PrintBSTree(bst);
cout<<endl;
cout<<"输入一个待删除结点的值:";
cin>>x;
if(Delete(bst,x))cout<<"删除元素"<<x<<"成功!"<<endl;
elsecout<<"删除元素"<<x<<"失败!"<<endl;
PrintBSTree(bst);
cout<<endl;
cout<<"该二叉搜索树中的最大值为:"<<MaxBSTree(bst)<<endl;
}
BSTree.h:
structBTreeNode{
ElemTypedata;
ElemTypecount;
BTreeNode*left;
BTreeNode*right;
};
voidInitBSTree(BTreeNode*&bst)//初始化二叉搜索树
{
bst=NULL;
}
voidPrintBSTree(BTreeNode*bst)//以广义表形式输出二叉搜索树
{
if(bst!=NULL){
cout<<bst->data;
cout<<'['<<bst->count<<']';
if(bst->left!=NULL||bst->right!=NULL){
cout<<'(';
PrintBSTree(bst->left);
if(bst->right!=NULL)
cout<<',';
PrintBSTree(bst->right);
cout<<')';
}
}
}
voidInsert(BTreeNode*&bst,ElemTypeitem)
{
BTreeNode*t=bst,*parent=NULL;
while(t!=NULL){
parent=t;
if(item<t->data)t=t->left;
elseif(item>t->data)t=t->right;
else{
t->count++;
break;
}
}
if((t==NULL)||item!=parent->data){
BTreeNode*p=newBTreeNode;
p->data=item;
p->count=1;
p->left=p->right=NULL;
if(parent==NULL)bst=p;
elseif(item<parent->data)parent->left=p;
elseparent->right=p;
}
}
voidCreateBSTree(BTreeNode*&bst,ElemTypea[],intn)//建立二叉搜索树(用非递归算法实现)
{
bst=NULL;
for(inti=0;i<n;i++)
Insert(bst,a[i]);
}
boolDelete(BTreeNode*&bst,ElemTypeitem)
{
BTreeNode*t=bst,*parent=NULL,*m,*n;
while((t!=NULL)&&(t->data!=item)){
if(item==t->data)break;
else{
if(item<t->data){
parent=t;
t=t->left;
}
else{
parent=t;
t=t->right;
}
}
}
if(t->count>1){
t->count–;
returntrue;
}
elseif(t==NULL){
cout<<"没有找到待删除结点!"<<endl;
returnfalse;
}
else{
if((t->left==NULL)&&(t->right==NULL)){
if(t==bst)
bst=NULL;
else{
if(t==parent->left)
parent->left=NULL;
else
parent->right=NULL;
}
}
elseif((t->left==NULL)||(t->right==NULL)){
if(t==bst){
if(t->left==NULL)
bst=t->right;
else
bst=t->left;
}
else{
if((t==parent->left)&&(t->left!=NULL))
parent->left=t->left;
elseif((t==parent->left)&&(t->right!=NULL))
parent->left=t->right;
elseif((t==parent->right)&&(t->left!=NULL))
parent->right=t->left;
elseif((t==parent->right)&&(t->right!=NULL))
parent->right=t->right;
}
}
else{
if((t->left!=NULL)&&(t->right!=NULL)){
m=t;
n=t->left;
while(n->right!=NULL){
m=n;
n=n->right;
}
t->data=n->data;
if(m==t)
t->left=n->left;
else
m->right=n->left;
t=n;
}
}
free(t);
returntrue;
}
}
ElemTypeMaxBSTree(BTreeNode*bst)//求二叉搜索树的最大结点值(用非递归算法实现)
{
ElemTypemax;
if(bst==NULL){
cout<<"该二叉搜索树为空!"<<endl;
exit(1);
}
max=bst->data;
while(bst!=NULL){
if(max<bst->data)
max=bst->data;
bst=bst->right;
}
returnmax;
}
你试试吧,应该对的,选我做答案哈~
Ⅶ 二叉搜索树
哈哈,居然有人来提问了,城院的 我刚奋斗了2小时做了下,你看看对不?Test5.cpp:#include <iostream.h>#include <stdlib.h>typedef double ElemType;#define Maxsize 100#include "BSTree.h"void main(){ int i,n; ElemType x; ElemType a[Maxsize]; BTreeNode *bst; InitBSTree(bst); cout<<"请输入你所要测试的二叉搜索树的结点的个数:"; cin>>n; cout<<"请输入你要测试的二叉搜索树:"<<endl; for(i=0;i<n;i++){ cin>>a[i]; } CreateBSTree(bst,a,n); cout<<"你输入的二叉搜索树的广义表形式为:"; PrintBSTree(bst); cout<<endl; cout<<"输入一个待插入结点的整数值:"; cin>>x; Insert(bst,x); cout<<"插入结点后的二叉搜索树的广义表形式为:"; PrintBSTree(bst); cout<<endl; cout<<"输入一个待删除结点的值:"; cin>>x; if(Delete(bst,x)) cout<<"删除元素"<<x<<"成功!"<<endl; else cout<<"删除元素"<<x<<"失败!"<<endl; PrintBSTree(bst); cout<<endl; cout<<"该二叉搜索树中的最大值为:"<<MaxBSTree(bst)<<endl;}BSTree.h:struct BTreeNode{ ElemType data; ElemType count; BTreeNode *left; BTreeNode *right;};void InitBSTree(BTreeNode *&bst) //初始化二叉搜索树{ bst=NULL; }void PrintBSTree(BTreeNode *bst) //以广义表形式输出二叉搜索树{ if(bst!=NULL){ cout<<bst->data; cout<<'['<<bst->count<<']'; if(bst->left!=NULL||bst->right!=NULL){ cout<<'('; PrintBSTree(bst->left); if(bst->right!=NULL) cout<<','; PrintBSTree(bst->right); cout<<')'; } }}void Insert (BTreeNode *&bst, ElemType item){ BTreeNode*t=bst,*parent=NULL; while(t!=NULL){ parent=t; if(item<t->data) t=t->left; else if(item>t->data) t=t->right; else{ t->count++; break; } } if((t==NULL)||item!=parent->data){ BTreeNode*p=new BTreeNode; p->data=item; p->count=1; p->left=p->right=NULL; if(parent==NULL) bst=p; else if(item<parent->data) parent->left=p; else parent->right=p; }}void CreateBSTree(BTreeNode *&bst, ElemType a[], int n) //建立二叉搜索树(用非递归算法实现){ bst=NULL; for(int i=0;i<n;i++) Insert(bst,a[i]); }bool Delete (BTreeNode *&bst , ElemType item){ BTreeNode *t=bst,*parent=NULL,*m,*n; while((t!=NULL)&&(t->data!=item)){ if(item==t->data) break; else{ if(item<t->data){ parent=t; t=t->left; } else{ parent=t; t=t->right; } } } if(t->count>1){ t->count–; return true; } else if(t==NULL){ cout<<"没有找到待删除结点!"<<endl; return false; } else{ if((t->left==NULL)&&(t->right==NULL)){ if(t==bst) bst=NULL; else{ if(t==parent->left) parent->left=NULL; else parent->right=NULL; } } else if((t->left==NULL)||(t->right==NULL)){ if(t==bst){ if(t->left==NULL) bst=t->right; else bst=t->left; } else{ if((t==parent->left)&&(t->left!=NULL)) parent->left=t->left; else if((t==parent->left)&&(t->right!=NULL)) parent->left=t->right; else if((t==parent->right)&&(t->left!=NULL)) parent->right=t->left; else if((t==parent->right)&&(t->right!=NULL)) parent->right=t->right; } } else{ if((t->left!=NULL)&&(t->right!=NULL)){ m=t; n=t->left; while(n->right!=NULL){ m=n; n=n->right; } t->data=n->data; if(m==t) t->left=n->left; else m->right=n->left; t=n; } } free(t); return true; }}ElemType MaxBSTree(BTreeNode *bst) //求二叉搜索树的最大结点值(用非递归算法实现){ ElemType max; if(bst==NULL){ cout<<"该二叉搜索树为空!"<<endl; exit(1); } max=bst->data; while(bst!=NULL){ if(max<bst->data) max=bst->data; bst=bst->right; } return max;}你试试吧,应该对的,选我做答案哈~
未经允许不得转载:山九号 » 二叉搜索树如何对应文件内容|求助:关于二叉树存入文件的问题