我强大的二叉树（先序、层序创建，先序、中序、后序、层序遍历）

要赶快些，要不然我们寝室就要断电了！
好了，经过四天的艰苦奋斗，我终于完成了一个比较强大的东西了。是什么东西呢？不是什么软件，不是什么程序，而是我自定义的一个数据结构！这个数据结构是二叉树。这个二叉树课不简单，因为它可以进行先序建立、层序建立，并且能够支持先序、中序、后序、层序的遍历。这个数据结构是我这四天来最有成果的一个了。因此我花费了超过24小时。想想自己在上课、吃饭、睡觉、上厕所都在想这个数据结构。能够有这个东西的横空出世，对我来说可真是可喜可贺啊。
今天晚上一直在研究层序创建二叉树的问题。昨天研究的是层序遍历二叉树的问题，因此我自己创建了一个链式队列（详见http://student.csdn.net/space.php?uid=999749&do=blog&id=48348）。有了这个队列，我就可以顺利地使用队列来进行层序遍历了。层序遍历的基本思想是：首先把根节点压入队尾，然后判断是否队列为空。如果为空，则退出循环。（当然没有出队的元素队伍是不会为空的）随后在循环体内进行出队操作，然后调用目标函数，再对左右孩子进行插入队尾的操作。如此循环，知道队列为空为之。这样的效果还真的不错。有了队列这个数据结构，我只需要几条语句就可以搞定层序遍历。
但是层序建立二叉树就没有那么简单了。其原因比较复杂，不好言传。但是今天晚上在我的努力下终于完成了。下面就是我为了编写这个功能而写的伪代码：

若根为空，则创建根节点。
将根节点进队，
如果队未空，则进入循环：
{
删除队首元素，并取出来，
填充队首元素，
若左孩子满足条件，则创建左孩子，并且进队，
若右孩子满足条件，则创建右孩子，并且进队，
}

说得简单，但是实现起来可是非常的困难的。我一遍又一遍地调试程序，到了现在，这个程序终于成功了。下面是我这个庞大二叉树的代码：

/*-------------------------------------------
蒋轶民制作：E-mail：[e-mail]
---------------------------------------------
文件名：JBiTree.h
---------------------------------------------
作用：这是一种二叉树的模板，它可以应用于任何
的需要二叉树的非线性结构的程序中。
---------------------------------------------
调用规范：①若将任意的类型运用于此，必须重载
==运算符，因为在判断两个数据类型的对象是否相
等的时候必须要用到它。②使用之前必须先定义类
型再包含该文件。例如：
typedefstruct
{
chara
intb;
unsignedlongc;
};
#include"JBiTree.h"
③若用char类型进行实例化，那么给形参sizeofObj
传入的值必须减一。因为字符串是带'/0'的。
④具体函数的参数说明：
voidSetImportData(CustomType*importObj,
intsizeofObj,CustomTypedefaultObj);
importObj：导入数据数组的首地址
sizeofObj：数据数组的总大小，通常是sizeof(..)
defaultObj：默认忽略建立树的结构数据

boolCreateJBiTreeByPreOrder(JBiTreeNode
<CustomType>*current);
current：当前传入的数据节点，通常是GetRoot()
相同参数的函数：
CreateJBiTreeByLevelOrder()

voidPreOrderTraverse(
JBiTreeNode<CustomType>*current,
bool(*Visit)(CustomTypee));
current：当前传入的数据节点，通常是GetRoot()
Visit：具体的应用函数形参
相同参数的函数：
InOrderTraverse()
PostOrderTraverse()
LevelOrderTraverse()
⑤在建立二叉树的时候，必须设置导入数据，不然会出错。// 更新于11月13日
-------------------------------------------*/
#ifndef_JBITREE_H_
#define_JBITREE_H_

#include"JChainQueue.h"

//可将任何类型应用于此
template<typenameCustomType>
structJBiTreeNode//二叉树节点结构体（三叉节点）
{
JBiTreeNode():lchild(0),rchild(0){}
CustomTypeelem;
JBiTreeNode*lchild,*rchild;
};//JBiTreeNode

//可将任何类型应用于此
template<typenameCustomType>
classJBiTree//二叉树类
{
public:
JBiTree():root(0),importData(0),startData(0),nodeCount(0){}//默认构造函数
~JBiTree(){}//默认析构函数
voidSetImportData(CustomType*importObj,intsizeofObj,CustomTypedefaultObj);//设置导入的数据
JBiTreeNode<CustomType>*GetRoot(void);//获取根节点
boolCreateJBiTreeByPreOrder(JBiTreeNode<CustomType>*current);//先序创建二叉树
boolCreateJBiTreeByLevelOrder(JBiTreeNode<CustomType>*current);//层序创建二叉树
voidPreOrderTraverse(JBiTreeNode<CustomType>*current,bool(*Visit)(CustomTypee));//先序遍历二叉树
voidInOrderTraverse(JBiTreeNode<CustomType>*current,bool(*Visit)(CustomTypee));//中序遍历二叉树
voidPostOrderTraverse(JBiTreeNode<CustomType>*current,bool(*Visit)(CustomTypee));//后序遍历二叉树
voidLevelOrderTraverse(JBiTreeNode<CustomType>*current,bool(*Visit)(CustomTypee));//层序遍历二叉树
private:
JBiTreeNode<CustomType>*root;
CustomType*importData,*startData;
CustomTypedefaultData;
intnodeCount;
};

//设置导入的数据
template<typenameCustomType>
voidJBiTree<CustomType>::SetImportData(CustomTypeimportObj[],intsizeofObj,CustomTypedefaultObj)
{
startData=importData=importObj;
nodeCount=sizeofObj/sizeof(CustomType);
defaultData=defaultObj;
}

//获取根节点
template<typenameCustomType>
JBiTreeNode<CustomType>*JBiTree<CustomType>::GetRoot(void)
{
returnroot;
}


//层序创建二叉树
template<typenameCustomType>
boolJBiTree<CustomType>::CreateJBiTreeByLevelOrder(JBiTreeNode<CustomType>*current)
{
JChainQueue<JBiTreeNode<CustomType>*>temp;
CustomType*dataTraverse=importData+1;//声明一个遍历的指针，从第二个元素开始

if(importData==startData+nodeCount||*importData==defaultData)
returnfalse;//若输入数据区为空且头结点为空则返回错误，因为不能创建树
if(current==root)//若当前为根节点则创建根节点
{
root=newJBiTreeNode<CustomType>;
current=root;
}elsereturnfalse;
temp.EnterQueue(current);
while(!temp.IsEmpty())
{
current=temp.DeleteQueue();
while(*importData==defaultData)
importData++;
current->elem=*importData;
importData++;
if(dataTraverse!=startData+nodeCount)
{
if(*dataTraverse!=defaultData)
temp.EnterQueue(current->lchild=newJBiTreeNode<CustomType>);
dataTraverse++;
}
if(dataTraverse!=startData+nodeCount)
{
if(*dataTraverse!=defaultData)
temp.EnterQueue(current->rchild=newJBiTreeNode<CustomType>);
dataTraverse++;
}
}
returntrue;
}
//先序遍历二叉树
template<typenameCustomType>
voidJBiTree<CustomType>::PreOrderTraverse(JBiTreeNode<CustomType>*current,bool(*Visit)(CustomTypee))
{
if(current)
{
(*Visit)(current->elem);
PreOrderTraverse(current->lchild,Visit);
PreOrderTraverse(current->rchild,Visit);
}
}

//中序遍历二叉树
template<typenameCustomType>
voidJBiTree<CustomType>::InOrderTraverse(JBiTreeNode<CustomType>*current,bool(*Visit)(CustomTypee))
{
if(current)
{
InOrderTraverse(current->lchild,Visit);
(*Visit)(current->elem);
InOrderTraverse(current->rchild,Visit);
}
}
//后序遍历二叉树
template<typenameCustomType>
voidJBiTree<CustomType>::PostOrderTraverse(JBiTreeNode<CustomType>*current,bool(*Visit)(CustomTypee))
{
if(current)
{
PostOrderTraverse(current->lchild,Visit);
PostOrderTraverse(current->rchild,Visit);
(*Visit)(current->elem);
}
}
//层序遍历二叉树
template<typenameCustomType>
voidJBiTree<CustomType>::LevelOrderTraverse(JBiTreeNode<CustomType>*current,bool(*Visit)(CustomTypee))
{
JChainQueue<JBiTreeNode<CustomType>*>temp;
if(current==0)return;//当前节点为空则返回
temp.EnterQueue(current);//将根节点入队列
while(!temp.IsEmpty())
{
current=temp.DeleteQueue();
(*Visit)(current->elem);
if(current->lchild)temp.EnterQueue(current->lchild);
if(current->rchild)temp.EnterQueue(current->rchild);
}
}
//先序创建二叉树
template<typenameCustomType>
boolJBiTree<CustomType>::CreateJBiTreeByPreOrder(JBiTreeNode<CustomType>*current)
{
if(importData==startData+nodeCount||*importData==defaultData)
returnfalse;//若输入数据区为空且头结点为空则返回错误，因为不能创建树
if(current==root)//若当前为根节点则创建根节点
{
root=newJBiTreeNode<CustomType>;
current=root;
}
current->elem=*importData;
importData++;
if(importData!=startData+nodeCount)
{
if(*importData!=defaultData)
{
current->lchild=newJBiTreeNode<CustomType>;
CreateJBiTreeByPreOrder(current->lchild);
}
elseimportData++;
}
if(importData!=startData+nodeCount)
{
if(*importData!=defaultData)
{
current->rchild=newJBiTreeNode<CustomType>;
CreateJBiTreeByPreOrder(current->rchild);
}
elseimportData++;
}
returntrue;
}
#endif

下面是我随便使用一个实例进行调用：

#include<iostream>
#include"JBiTree.h"
usingnamespacestd;
boolDisplay(chare)
{
cout<<e;
returntrue;
}

intmain(intargc,char**argv)
{
JBiTree<char>jbtr;
chardis[]="124___3579____68AC__D__B___";
//chardis[]="1234_56";
//chardis[]="1245____36__7_89___";
jbtr.SetImportData(dis,sizeof(dis)-1,'_');
//jbtr.CreateJBiTreeByLevelOrder(jbtr.GetRoot());
jbtr.CreateJBiTreeByPreOrder(jbtr.GetRoot());
jbtr.LevelOrderTraverse(jbtr.GetRoot(),Display);
return0;
}

二叉树很有用。因为在游戏开发中有些图像的索引是BSP树，而BSP树就是二叉树的一种。这次写的二叉树不仅仅是加深对二叉树的理解，而且是对我后续游戏的开发也是非常有帮助的。我希望自己强大的二叉树能够派上用场。

今天没有什么时间了，而且这个二叉树的模型还有诸多潜在的错误。希望大家能够将我的代码下载出来，并进行测试。并将错误反馈给我。我对大家的工作表示无尽的感谢。

更新于11月13日：大家难道没有发现吗？我的二叉树缺少了一个最重要的东西。销毁二叉树！如果不销毁的话，那么就会造成内存泄露这个重大的错误！这个东西我怎么会忘记呢！没办法，还是先这样吧。以后等我维护的时候再添加这个功能吧。现在先打记一下。