04071505667.cpp

数据结构的部分算法程序。相对来说是通用算法中效率比较高的程序

//仿照650，668题
typedef char TElemType;
#include "04071505tree.h"
typedef tree QElemType;
#include"04071505queue.h"
#include"fstream.h"
//创建结点
void CreateNode(tree &T, TElemType C)
{
    T=new BiTNode;
	T->data=C;  
    T->FirstChild=T->NextSibling=NULL;
}
//子函数，实现由二元组建立二叉链表
void CreateTree1(tree &T,TElemType fn[])
{ 
    LQueue Q;
	ifstream ft;
	tree P,S,Pr;  
    TElemType F,C;
	T=NULL; 
	ft.open(fn,ios::nocreate);//打开文件    
    if (!ft) return;
	QueueInit(Q);  //队列初始化
    while (!ft.eof())//没有到文件尾时进行循环
	{
        ft>>F>>C;   //读入数据
        if (C=='^') break;//表示树为空
        if (F=='^')//根结点
		{
			CreateNode(T,C);
			Enqueue(Q,T);
			P=T;
		}
        else //非根结点时
		{
			while(true)
			{
				if(P->data!=F)Dequeue(Q,P);
				else break;
			}
            CreateNode(S,C);//建立中间结点
            if (!P->FirstChild)P->FirstChild=S;//如果孩子为空，建立
            else Pr->NextSibling=S;  //实际上，如果有孩子，那么这样循环，上一步及下一步共同保证了调用Pr时，Pr不空
            Pr=S;
			Enqueue(Q,S);
		}
   }
    ft.close();  //关闭文件
}


void main()//主函数
{
	tree T;
	TElemType fn[]="1.txt";//给文件名赋值
    CreateTree1(T,fn);     //调用子函数，测试
	cout<<"该树为："<<endl;
	PreorderListsT(T,visit);           //输出，便于检验
}