实验五报告
课程名称： 数据结构 实验名称：二叉树的创建与遍历
实验日期
2011/11/16
一、实验目的：
通过上机实验进一步掌握栈、队列、二叉树的存储结构及基本操作的实现方法。
二、实验内容与要求：
基于二叉链表存储结构实现二叉树的基本运算，要求：
⑴能建立非空二叉树；
⑵实现二叉树的先、中、后序递归遍历算法；
⑶实现二叉树的非递归的先（或中、或后）序遍历算法及层序遍历算法；
⑷记录运行结果并对递归算法和非递归算法的效率加以分析。
三、算法设计 结构体的定义：
typedef struct BiTNote{
struct Node{
}; 类的定义： cla CStack{
//栈 private:
};
cla LinkQueue{ //队列 public: BiTree base; BiTree top; int stacksize; //当前空间分配量 static const int STACK_INIT_SIZE=100; static const int STACKINCREMENT=10; CStack();
void Push(BiTree T); //入栈 void Pop(BiTree &T); //出栈 bool StackEmpty(); //判断是否是空栈 friend cla CBiTree; Node(BiTree &d):num(d),next(NULL){} BiTree num; Node *next; char data; struct BiTNote *lchild,*rchild; }BiTNote,*BiTree; public:
}; LinkQueue(); bool QueueEmpty(); void EnQueue(BiTree &T); void DeQueue(BiTree &T); friend cla CBiTree; int length; //队列元素的个数 Node *front;
//队列的头指针 Node *rear;
//队列的尾指针 private: cla CBiTree{ public:
}; CStack::CStack ():stacksize(STACK_INIT_SIZE){ //构造函数，初始化
} void CStack::Push(BiTree T){...} //入栈 void CStack::Pop(BiTree &T) {...} //出栈 bool CStack::StackEmpty() {} int i=0; //全局变量
int CBiTree::CreatBiTree(BiTree &T) {}//构造二叉树 //LinkQueue类函数的实现 LinkQueue::LinkQueue (){} bool LinkQueue::QueueEmpty (){} void LinkQueue::EnQueue (BiTree &T){} void LinkQueue::DeQueue(BiTree &T){} int CBiTree::PreOrderTraverse1(BiTree T, int (*Visit)(char)) {...} //前序遍历（递归） int CBiTree::InOrderTraverse(BiTree T, int (*Visit)(char)) {...} //中序遍历（递归） int CBiTree::PostOrderTraverse(BiTree T, int (*Visit)(char)) {...}//后序遍历（递归） int CBiTree::PreOrderTraverse2(BiTree T, int (*Visit)(char)) { //前序遍历（非递归）
BiTree p=T; while(p!=NULL||!s.StackEmpty ()) { BiTree p=(BiTree)malloc( STACK_INIT_SIZE*sizeof(BiTNote)); base=p; top=base; int CreatBiTree(BiTree &T); //建立二叉树
int PreOrderTraverse1(BiTree T,int (*Visit)(char e));
//前序遍历（递归） int PreOrderTraverse2( BiTree T,int (*Visit)(char e));
//前序遍历（非递归）
int InOrderTraverse(BiTree T,int (*Visit)(char e));
//中序遍历（递归） int PostOrderTraverse(BiTree T,int (*Visit)(char e)); //后序遍历（递归） int LevelOrderTraverse(BiTree T,int (*Visit)(char e)); //层序遍历（非递归） CStack s; LinkQueue link; private:
}
} while(p!=NULL){
} if(!s.StackEmpty ()){
} s.Pop(p); p=p->rchild; Visit(p->data ); s.Push (p); p=p->lchild; return 1; int CBiTree::LevelOrderTraverse(BiTree T, int (*Visit)(char)) //层序遍历（非递归） {
} //main.cpp #include\"BiTree.h\" #include\"Function.h\" #include int PrintData(char e){
}
int main(){
CBiTree Tree; BiTree T; T=(BiTree)malloc(sizeof(BiTNote)); cout
link.EnQueue(T); while(!link.QueueEmpty()) {
} return 0; BiTree p; link.DeQueue(p); Visit(p->data); link.EnQueue(p->lchild); link.EnQueue(p->rchild);
} cout
四、测试结果
五、心得体会
这次实验尝试用C++写，好长时间没接触了，所以写的比较吃力，在写的过程中温习了C++的一些知识，但代码写的很乱，没有用模板，C++的引用也忘了等。这次还发现自己对指针还是不熟练（一个指针赋值的小错误多花了好多时间才找到）。总之觉得自己的编程水平很有待提高。
