关于线索二叉树的性能分析

　　最近刚学完数据结构中关于树的部分，我对其中的线索二叉树产生了浓厚的兴趣。线索二叉树通过设置Ltag,Rtag标志，并事先线索化来提高整个二叉树的遍历速度，是个典型的通过牺牲空间来提升速度的例子。但是，它究竟浪费了多少空间，提升了多少的速度，在实际的应用中究竟值不值得用这些空间来换的这些速度？我决定通过一系列实验来分析线索二叉树的性能，以此解决这些问题。

　　 测试时间性能大概的思路是这个样子的：分别建立一般二叉树和线索二叉树(都是满二叉树)，然后调用它们各自的遍历函数，记录函数运行的时间，做比较；再通过控制二叉树的深度，记录遍历时间随二叉树结点个数变化的变化，并做比较。

　　 后加：其实分析下哈，一般二叉树的访问其实就是不停的CALL调用而线索二叉树则是不停的判断，访问N个节点的一般二叉树大概要进行2*N次CALL，而线索二叉树则要执行N次的判断，再加上CALL调用要比判断要花时间，所以，线索二叉树的遍历比一般二叉树节省时间在理论上也是说的通的呵。

　　 空间性能的测试就简单的多咯，线索二叉树就是每个结点多了两个bool型变量，4个字节啊，在每组时间比较后，拿数据量*4，不是浪费的空间的大小吗？呵！

　　 介绍下环境先。我的硬件环境是：CPU IntelP4，1.70HZ；359M RAM（256+128M，不知怎么的就变成359M了），软件环境：Windows 2000/SP2,Visual C++ 7.0。

　　 首先给出一般二叉树和线索二叉树的存储结构。

typedef struct BNode//一般二叉树
{
　 int data;
　 BNode *lchild,*rchild;
}*BTree;

typedef struct BThNode//线索二叉树
{
　 int data;
　 bool LTag,RTag;//当Tag=false时表示不是线索
　 BThNode *lchild,*rchild;
}*BThTree;
　　 下面给出几个测试时所用的函数：二叉树构造函数：

CreateTree(int depth,int OwnDepth,BTree *tree);
　　 时钟工具：

QueryPerformanceFrequency(LARGE_INTRGER);::QueryPerformanceCounter(LARGE_INTRGER);
　　 二叉树线索化函数

InOrderThreading (BThTree *thread,BThTree *tree);
　　 一般二叉树的中序遍历函数：

InOrderTraverse(Btree tree,void (*Visit)());
　　 线索二叉树的中序遍历函数：

InOrderTraverse_Thr(BthTree tree,void (*Visit)());
　　 结点访问函数：Visit()

　　 1、二叉树构造函数CreateTree(int depth,int OwnDepth,BTree *tree)

　　 功能：构造深度为depth的一般二叉树和线索二叉树

　　 参数：depth-----二叉树的深度

　　OwnDepth----表示第一个结点所在深度

　　 Tree-----要构造的二叉树

void CreateTree(int depth,int OwnDepth,BTree *tree/*BThTree *tree*/)
{
　 if(OwnDepth<depth)//当前结点小于树的深度时，继续构造
　 {
　　 BTree p,q;
　　 if(!(*tree))//构造根结点
　　 {
　　　 *tree=new BNode;//tree=new BThNode;
　　　 (*tree)->data=0;
　　　 (*tree)->lchild=(*tree)->rchild=NULL;
　　　 //(*tree)->LTag=(*tree)->RTag=false;//构造线索二叉树使用
　　　 printf("created Number %d floor/n",OwnDepth);
　　　 CreateTree(depth,OwnDepth,tree);
　　 }
　　 else//构造子结点 {
　　　 p=new BNode;//p=new BThNode;
　　　 q=new BNode;//q=new BThNode;
　　　 p->data=0;
　　　 q->data=0;
　　　 p->lchild=p->rchild=NULL;
　　　 q->lchild=q->rchild=NULL;

　　　 //q->LTag=q->RTag=false;
　　　 //p->LTag=p->RTag=false;
　　　 (*tree)->lchild=p;
　　　 (*tree)->rchild=q;
　　　 printf("created Number %d floor/n",OwnDepth+1);
　　　 printf("created Number %d floor/n",OwnDepth+1);
　　　 CreateTree(depth,OwnDepth+1,&p);//递归调用构造函数
　　　 CreateTree(depth,OwnDepth+1,&q);
　　 }
　 }
}
　　 2、一个记时工具，0.1微秒级别的，绝对够用，呵呵

QueryPerformanceFrequency(LARGE_INTRGER);-----获取CPU的频率

QueryPerformanceCounter(LARGE_INTRGER);----获取CPU时间
　　 3、二叉树的线索化函数

InOrderThreading(BThTree *thread,BThTree *tree)-----具体函数定义在清华C语言版《数据结构》P134
　　 功能：为二叉树tree中序线索化