1、实验目的
（1）熟悉二叉树结点的结构。
（2）掌握对二叉树基本操作的实现。
（3）理解遍历的概念，会利用递归方法编写对二叉树结构进行遍历的算法。
（4）理解二叉树的线索化过程是基于对二叉树进行遍历，而线索二叉树上的线索又为相应的遍历提供了方便。
2、实验要求
（1）二叉树的存储及基本操作的实现。
（2）二叉树及线索二叉树的相关运算的实现。
3、实验内容
（1）抽象数据类型定义
typedef struct BiTNode
{
TElemType data; //结点数据类型定义
struct BiTNode *lchild,*rchild; //定义指向相同类型结构体的左孩子与右孩子指针
}BiTNode,*BiTree; //定义结构体，同时定义其结构体指针
本次二叉树上机中，首先定义二叉树存储结构，然后通过各子函数实现各种功能，子函数如下：
#include"queue.h" //队列头文件，层次遍历时的基础函数
#include"stack.h" //栈头文件，中序线索二叉树及遍历时的基础函数
void createBiTree(BiTree &T) // 生成二叉树，键盘输入，可生成任意的二叉树
void preOrder(BiTree T) // 递归先序遍历二叉树，并输出
void midOrder(BiTree T) // 递归中序遍历二叉树，并输出
void lastOrder(BiTree T) // 递归后续遍历二叉树，并输出
void levelorder(BiTree T) //非递归层次遍历二叉树，并输出
void nodgzhongxu(BiTree T) //非递归中序遍历二叉树，并输出
int Count(BiTree T,int &num) // 计算二叉树所有节点数目
void searchK(BiTree T,int k,int &a) //前序查找第k个节点的值，同理可实现中
//序后序节点值得查询
（2）存储结构定义及算法思想
存储结构如下：
void createBiTree(BiTree &T) {
char a,b;int c;
cout<<"请输入结点数据"< if(c!=' '){ //首先判断是够输入为空，如空，则头节点为空 T=(BiTree)malloc(sizeof(BiTNode)); //开辟二叉树节点空间 T->data=c; //将键盘输入的值赋给头结点 while(1){ cout<<"是否输入左孩子"< switch(a){ case 'y': createBiTree(T->lchild);break; case 'n': T->lchild=NULL;break; //实现输入错误的判断，能从新输入 default:cout<<"输入有误，请从新输入"< if(a=='y'||a=='n') break; } while(1){ cout<<"是否输入右孩子"< switch(b){ case 'y': createBiTree(T->rchild);break; case 'n': T->rchild=NULL;break; //实现输入错误的判断，能从新输入 default:cout<<"输入有误，请从新输入"< if(b=='y'||b=='n') break; } } else T=NULL; } 层次遍历函数： void levelorder(BiTree T){ BiTree p; SqQueue *q;InitQueue(q); //定义并初始化队列，通过队列实现节点的暂时存储 enQueue(q,T); while(!QueueEmpty(q)){ deQueue(q,p); cout< if(p->lchild!=NULL) enQueue(q,p->lchild); //通过if的条件判断，实现结点的层次存储 if(p->rchild!=NULL) enQueue(q,p->rchild); } } 非递归的中序遍历原理大致同层次遍历相同，是通过入栈和退栈，实现结点的存储与退栈输出，通过查询栈是否为空，判断遍历时候结束。 （3）实验结果与分析 （4）实验心得 本次二叉树上机实习，因为层次遍历与非递归中序遍历用到了队列和栈，复习了原来的知识，同时也尝试将这两类基础函数作为头文件使用，收货颇丰。同时在写线索二叉树时，遇到了一些理解困难，因为上课时这个知识点没怎么听，意识到了上课认真听讲的重要性，同时也要加强动手实践，拓宽知识面。 源代码见附录: 源代码： #include using namespace std; typedef int TElemType; typedef struct BiTNode { TElemType data; struct BiTNode *lchild,*rchild; }BiTNode,*BiTree; #include"queue.h" #include"stack.h" void createBiTree(BiTree &T) { char a,b;int c; cout<<"请输入结点数据"< if(c!=' ') { T=(BiTree)malloc(sizeof(BiTNode)); T->data=c; while(1) { cout<<"是否输入左孩子"< switch(a) { case 'y': createBiTree(T->lchild);break; case 'n': T->lchild=NULL;break; default:cout<<"输入有误，请从新输入"< if(a=='y'||a=='n') break; } while(1) { cout<<"是否输入右孩子"< switch(b) { case 'y': createBiTree(T->rchild);break; case 'n': T->rchild=NULL;break; default:cout<<"输入有误，请从新输入"< if(b=='y'||b=='n') break; } } else T=NULL; } int Count(BiTree T,int &num) { if(T) { num++; Count(T->lchild,num); Count(T->rchild,num); } return num; } void preOrder(BiTree T) { if(T) { cout< preOrder(T->lchild); preOrder(T->rchild); } } void midOrder(BiTree T) { if(T) { midOrder(T->lchild); cout< midOrder(T->rchild); } } void lastOrder(BiTree T) { if(T) { lastOrder(T->lchild); lastOrder(T->rchild); cout< } } void levelorder(BiTree T) { BiTree p; SqQueue *q;InitQueue(q); enQueue(q,T); while(!QueueEmpty(q)) { deQueue(q,p); cout< if(p->lchild!=NULL) enQueue(q,p->lchild); if(p->rchild!=NULL) enQueue(q,p->rchild); } } void nodgzhongxu(BiTree T) { SqStack *s;InitStack(s) ;BiTree p=T; while(p||!StackEmpty(s)) { while(p) { Push(s,p); p=p->lchild; } if(!StackEmpty(s)) { p=Pop(s); cout< p=p->rchild; } } } void searchK(BiTree T,int k,int &a) { if(T) { a++; if(a==k) cout<<"该结点数据为："< { searchK(T->lchild,k,a); searchK(T->rchild,k,a); } } } void main() { BiTree T; int select=0; int num=0,a=0; while(1) { cout<<" 请选择功能 "< switch(select) { case 1: createBiTree(T);break; case 2: preOrder(T);cout< cout<<"请输入您要查询哪个结点"< case 9: free(T);exit(0);break; default :break; } } }下载本文
