实现简单文件树

如何实现cmd 里的 “dir” 和“cd..”命令呢，当我们在cmd 里面输入dir时，cmd会显示出当前目录的子文件；当我们输入 “cd.."时，cmd会返回当前目录的根目录，这要怎么实现呢？这时，我们会很容易想到树，看代码把：

struct Treefile{
	string Name;
	struct Treefile* child;
	struct Treefile* parent;
	struct Treefile* next; 
};

定义一个string 来存放文件的名字，三个指针：child 指向第一个儿子节点，另一个next 指向兄弟节点，一个parent 指向父亲节点。为什么要定义一个指向父亲的指针呢？因为这样方便指针回退，这是为 cd 命令服务，当你想要返回包含当前目录的根目录时，通过这个指针，就可以获取根目录。用容器vector<string> vs来顺序存放各个根文件名字，比如，你访问 "A\B\C\D"文件，则A,B,C,D依次push入容器。

把一个节点设为孩子的函数为：

void BeChild(struct Treefile* tParent,struct Treefile* tChild){
	//struct Treefile* pt=tParent->child;
	if(!tParent->child){
	    tParent->child=tChild;		
        tChild->parent=tParent;
	}
	else{
		tChild->next=tParent->child;
		tParent->child=tChild;
		tChild->parent=tParent;		
	}    
}

输出一个目录下的所有文件的函数为：

void OutputTree(struct Treefile* tParent){
    struct Treefile* pt=tParent->child;
    while(pt){
    	cout<<pt->Name<<' ';
    	pt=pt->next;
    }
}

然后，这里有一个问题，如何从一棵树的根，搜索到我们需要的目录，即搜索到特定路径，把路径里的所有节点都存起来，这里也用容器vector 来存，定义vecotor<Treefile*> vt 来存入节点指针。

查找路径的函数为：

void FindTree(vector<string>& vs,vector<Treefile*>&vt,Treefile *t,int len,int pos){
    if(len==0 )
    	return;
   	if(vs[pos]!=t->Name){
   		if(t->next==NULL)
           return;
        else{
       	   FindTree(vs,vt,t->next,len,pos);
       }
    }
    if(vs[pos]==t->Name){
    	vt.push_back(t);
    	FindTree(vs,vt,t->child,len-1,pos+1);
    }
}

这个函数递归查找，直到查找到文件，或查找失败，在查找的同时，把节点指针存入vecotor<Treefile*> vt 。

/*
   该树用于存储文件的名字，没有儿子的节点可能是 文件夹 或者 文件，
   存储路径时可以用一个vector来存储各个文件夹，例如“C:AABBCC”，
   可以用vector把AA、BB、CC按序存储，如果要返回，则调用vector的pop
   操作，要进入一个文件夹，则调用vector的push操作，把文件夹的名字
   存入vector。
   2013-11-25 22：04 by JackWoo

   以下代码建立如下图的文件树：

                  A
				 / 
				B   C
			       / 
			      D   E
                     / 
			        F   G

*/
#include "stdafx.h"
#include<iostream>
#include<string>
#include<vector>

using namespace std;
/*
   child 用于存储一个儿子节点，parent用于存储父亲节点
   next用于存储儿子节点的兄弟
*/
struct Treefile{
	string Name;
	struct Treefile* child;
	struct Treefile* parent;
	struct Treefile* next; 
};

void BeChild(struct Treefile* tParent,struct Treefile* tChild){
	//struct Treefile* pt=tParent->child;
	if(!tParent->child){
	    tParent->child=tChild;		
        tChild->parent=tParent;
	}
	else{
		tChild->next=tParent->child;
		tParent->child=tChild;
		tChild->parent=tParent;		
	}    
}
void OutputTree(struct Treefile* tParent){
    struct Treefile* pt=tParent->child;
    while(pt){
    	cout<<pt->Name<<' ';
    	pt=pt->next;
    }
}
void DeleteNode(struct Treefile* tTree){
	//struct Treefile* pt=tTree->parent;
	if(tTree->parent->child==tTree){
		tTree->parent->child=tTree->next;
		delete tTree;
	}
	else{
		struct Treefile* pt=tTree->parent->child;
		while(pt&&pt->next!=tTree){
			pt=pt->next;
		}
		if(pt==NULL){
			return;
		}
		else{
			pt->next=tTree->next;
			delete tTree;
		}
	}
}
void FindTree(vector<string>& vs,vector<Treefile*>&vt,Treefile *t,int len,int pos){
	//vs存了路径中包含的文件名，vt用来存入的树中与vs包含的文件名相同的节点指针
	//len 表示vs中的个数，pos表示从vs中的第几个节点开始查找（从0开始）
    if(len==0 )
    	return;
   	if(vs[pos]!=t->Name){
   		if(t->next==NULL)
           return;
        else{
       	   FindTree(vs,vt,t->next,len,pos);
       }
    }
    if(vs[pos]==t->Name){
    	vt.push_back(t);
    	FindTree(vs,vt,t->child,len-1,pos+1);
    }
}

int _tmain(int argc, _TCHAR* argv[])
{
	system("title TreeFile");
	vector<string> vs;//用于存放根文件名字，即目录中涉及到的所有文件名
	vector<Treefile*> vt;
	struct Treefile* A=new Treefile;
	struct Treefile* B=new Treefile;
	struct Treefile* C=new Treefile;
	struct Treefile* D=new Treefile;
	struct Treefile* E=new Treefile;
	struct Treefile* F=new Treefile;
	struct Treefile* G=new Treefile;
	string sA="A",sB="B",sC="C",sD="D",sE="E",sF="F",sG="G";
	//定义各个节点的名字
	
	A->Name=sA;
	B->Name=sB;
	C->Name=sC;
	D->Name=sD;
	E->Name=sE;
	F->Name=sF;
	G->Name=sG;
	//构造树
	BeChild(A,B);
	BeChild(A,C);
	BeChild(B,D);
	BeChild(B,E);
	BeChild(E,F);
	BeChild(E,G);
	//把目录涉及到的文件名字顺序存入容器：存入A,B,E,G
	vs.push_back(sA);
	vs.push_back(sB);
	vs.push_back(sE);
	vs.push_back(sG);
	//验证代码
	FindTree(vs,vt,A,4,0);
	cout<<"vt's size is "<<vt.size()<<endl;
	for(int i=0;i<vt.size();++i)
		cout<<vt[i]->Name<<endl;
	
	return 0;
}

以上代码是为了验证FindTree()的，输出结果应该为"A,B,E,G"。输出结果：