华科数据结构二叉树实验报告.doc

课 程 实 验 报 告

课程名称： 数据结构

专业班级：计算机科学与技术130*班
学 号： *
姓 名： **
指导教师： ***
报告日期： 2015.5.13

计算机科学与技术学院

目 录

实验三 基于二叉链表的二叉树实现
4.1 问题描述 1
4.2 系统设计 1
4.3 系统实现 1
4.4 效率分析 14
实验总结与评价 16

实验三 基于二叉链表的二叉树实现
4.1 问题描述
基于二叉链表，实现常见的，基本的运算。
4.2 系统设计
4.2.1实现如下功能：
1.InitBitree
2.DestroyBitree
3.CreatBiTree
4.ClearBitree
5.BiTreeEmpty
6.BiTreeDepth
7.Value
8.Root
9.Assign
10.Parent
11.Leftchild
12.RightChild
13.LeftSibling
14.RightSibling
15.InsertChild
16.DeleteChild
17.PreOrderTraverse
18.InOrderTraverse
19.PostOrderTraverse
20.LevelOrderTraverse
4.4.2.系统采用二叉链表存储结构：
typedef struct
{
TElemType data;
struct BiTNode *lchild,*rchild; //左右孩子指针
}BiTNode, *BiTree;
4.4.3.存储数据类型如下：
typedef struct
{
int num;
char c;
}TElemType;
4.3 系统实现

4.3.1. InitBiTree(BiTree *T)
初始条件：二叉树根结点不存在
操作结果：为根结点分配一个空间，将根结点数据值置为空字符，代表该树为空树
int InitBiTree(BiTree *T)
{

if(*T = (BiTNode*)malloc(sizeof(BiTNode))) //分配节点空间
{
(*T)->data.c = ' ';//节点置空
(*T)->lchild = NULL;
(*T)->rchild = NULL;
return 1;
}
else
return 0;
}
4.3.2. DestroyBiTree(BiTree T)
初始条件：二叉树存在
操作步骤：递归释放左右子树，最后释放双亲节点
操作结果：释放所有二叉树节点
int DestroyBiTree(BiTree T)
{
if(!T)
{

return 0;
}
else
{
if(!T->lchild)
DestroyBiTree(T->lchild);//递归销毁左子树
if(!T->rchild)
DestroyBiTree(T->rchild);//递归销毁右子树
free(T);
}

return 1;

}
4.3.3. CreateBiTree(BiTree *T)

初始条件：二叉树已被初始化
操作步骤：采用递归先序创建二叉树，其中，空节点用
操作结果：成功创建二叉树
int CreateBiTree(BiTree *T)
{
char ch;
getchar();
scanf("%c",&ch);
if(ch == '#'){
*T = NULL;
return 0;
}
else {
if(!(*T = (BiTNode *)malloc(sizeof(BiTNode))))exit(0);
(*T)->data.c = ch;
CreateBiTree(&((*T)->lchild));//递归创建左子树
CreateBiTree(&((*T)->rchild));//递归创建右子树
}
return 1;
}
4.3.4. ClearBiTree(BiTree T)

初始条件：二叉树存在
操作步骤：使用DestroyBitree函数释放所有节点，然后重新初始化
操作结果：二叉树置空
int ClearBiTree(BiTree T)
{
DestroyBiTree(T);
InitBiTree(&T); //不同于Destroy的是之后又给头结点分配空间置空
}
4.3.5．BiTreeEmpty(BiTree T)
初始条件：二叉树T存在
操作步骤：判断二叉树是否为空
操作结果：二叉树为空则返回1，不为空则返回0
int BiTreeEmpty(BiTree T)
{
if(T->data.c==' ')
return 1;
else
return 0;
}
4.3.6. BiTreeDepth(BiTree T)
初始条件：二叉树存在
操作步骤：递归返回树的深度，递归出口为树根结点为空
操作结果：返回树的深度
int BiTreeDepth(BiTree T)
{
int deep=0;
if(T){
int lchilddeep=BiTreeDepth(T->lchild); //递归计算左子树深度
int rchilddeep=BiTreeDepth(T->rchild); //递归计算右子树深度
deep=lchilddeep>=rchilddeep?lchilddeep+1:rchilddeep+1;
}
return deep;

}
4.3.7. Root(BiTree T)
初始条件：二叉树存在
操作步骤：返回根结点
BiTNode* Root(BiTree T)
{
if(BiTreeEmpty(T))
return NULL;
else
return T;
}

4.3.8．Value(BiTree T,TElemType e)
初始条件：二叉树存在
操作步骤：递归查找与传入节点值相等的节点
操作结果：若该节点存在，则返回1，若不存在，则返回0
int Value(BiTree T,TElemType e)//返回e的值
{
if(!T)return 0;
if(T->data.c == e.c)return 1;
if(Value(T->lchild,e)) return 1; //递归查找左子树
if(Value(T->rchild,e)) return 1; //递归查找右子树
return 0;

}

4.3.9. Assign(BiTree T, BiTNode *e, TElemType value)
初始条件：二叉树存在，传入一个节点值value ，将其中节点e的值修改为value
操作步骤： 判断节点是否在树T中，若在，则修改其数据，为value
操作结果：若成功，e值被修改为value，并返回1，否则，修改失败，返回0
int Assign(BiTree T, BiTNode *e, TElemType value)
{
if(Value(T,value))
{
(*e).data = value;
return 1;
}

else
return 0;

}
4.3.10. Parent(BiTree T,TElemType e)
初始条件：二叉树存在，e是其中一个节点
操作步骤： 利用队列，先将根结点入队，在队列不为空的时候，出队，再将判断其左子树和右子树是否有与之相同的，若有，返回节点值，否则，将其左右孩子入队，返回循环，直到查找到该节点，返回该节点值，或者是未查找到返回空。
操作结果：返回e的双亲，或者不存在双亲时，返回空字符
TElemType Parent(BiTree T,TElemType e)
{
LinkQueue q;
QElemType a;
if(T)
{
InitQueue(&q); // 初始化队列
EnQueue(&q,T); // 树根入队
BiTNode *p,*r;
while(!QueueEmpty(q)) //队不空
{
DeQueue(&q,&a); //出队元素赋值给a
p = a->lchild;
r = a->rchild;
if(a->lchild&&p->data.c==e.c||a->rchild&&r->data.c==e.c)
//找到e(是其左或右孩子)
return a->data; // 返回e的双亲的值
else //没找到e,则入队其左右孩子指针(如果非空)
{
if(a->lchild)
EnQueue(&q,a->lchild);
if(a->rchild)
EnQueue(&q,a->rchild);
}
}
}
TElemType s;
s.c = ' ';
return s; // 树空或没找到e
}
4.3.12. LeftChild(BiTree T,TElemType e)
初始条件：二叉树存在，e是其中一个节点
操作步骤： 递归调用函数查找左孩子，若存在，返回左孩子数值，若不存在，则返回空字符
操作结果：返回e的左孩子，或者返回空字符
TElemType LeftChild(BiTree T,TElemType e)
{
TElemType s;
s.c = ' ';
BiTNode *p;
if(T==NULL)
return s;
if(T->data.c == e.c)
{
p = T->lchild;
if(p)
return p->data;
else
return s;
}
else
{
LeftChild(T->lchild,e); //递归查找左子树
LeftChild(T->rchild,e);//递归查找右子树
}

return s;

}
4.3.13. RightChild(BiTree T,TElemType e)
初始条件：二叉树存在，e是其中一个节点
操作步骤： 递归调用函数查找右孩子，若存在，返回右孩子数值，若不存在，则返回空字符
操作结果：返回e的右孩子，或者返回空字符
TElemType RightChild(BiTree T,TElemType e)
{
TElemType s;
s.c = ' ';
BiTNode *p;
if(T==NULL)
return s;
if(T->data.c == e.c)
{
p = T->rchild;
if(p)
return p->data;
else
return s;
}

RightChild(T->lchild,e); //递归查找左子树
RightChild(T->rchild,e); //递归查找右子树

}
4.3.14. LeftSibling(BiTree T, TElemType e)
初始条件：二叉树存在，e是其中一个节点
操作步骤： 先查找e的双亲，然后根据双亲判断，其左孩子是否存在，若存在，则返回左孩子，不存在则返回空
操作结果：返回e的左兄弟，不存在左兄弟时返回空
TElemType LeftSibling(BiTree T, TElemType e)
{
TElemType a;
BiTree p;
BiTree q,r;
TElemType s;
s.c = ' ';
if(T)
{
a=Parent(T,e);
p=Point(T,a); //找到双亲节点
if(p==NULL)
return s;
q = p->lchild;
r = p->rchild;
if(p->lchild&&p->rchild&&r->data.c==e.c) // p存在左右孩子且右孩子是e
return q->data; //返回p的左孩子(e的左兄弟)
}
return s; // 树空或没找到e的左兄弟
}
4.3.15. RightSibling(BiTree T, TElemType e)
初始条件：二叉树存在，e是其中一个节点
操作步骤： 先查找e的双亲，然后根据双亲判断，其右孩子是否存在，若存在，则返回右孩子，不存在则返回空
操作结果：返回e的左右兄弟，不存在右兄弟时返回空
TElemType RightSibling(BiTree T, TElemType e)
{
TElemType a;
BiTree p;
BiTree q,r;
TElemType s;
s.c = ' ';
if(T) //非空树
{
a=Parent(T,e); // a为e的双亲
p=Point(T,a); // p为指向结点a的指针
if(p==NULL)
return s;
q = p->lchild;
r = p->rchild;
if(p->lchild&&p->rchild&&q->data.c==e.c) //p存在左孩子且右孩子是e
return r->data; // 返回p的左孩子(e的左兄弟)
}
return s; //树空或没找到e的左兄弟
}
4.3.16. InsertChild(BiTree T,TElemType p,int LR,BiTree C)
初始条件：二叉树存在，p指向某个节点，LR为0或1，非空二叉树c与T不相交且右子树为空
操作步骤：当树C右子树为空时，根据LR，其值为0，将C插为左子树，当LR为1时，将C插为右子树，将断开部分连接为C的右子树。
操作结果：将C根据LR的值连接为T的子树
int InsertChild(BiTree T,TElemType p,int LR,BiTree C)
{
BiTNode *t,*c,*m,*n;
t = T;
c = C;
if(t == NULL||c == NULL)return 0;
if(c->rchild != NULL){
printf("二叉树C含有右子树！\n"); //判断C是否含有右子树
return 0;
}
m = Point(t,p); //找到p所在节点
if(LR){
n = m->rchild;
m->rchild = c;
c->rchild = n; //插入为右子树
}
else{
n = m->lchild;
m->lchild = c;
c->rchild = n; //插入为左子树
}
return 1;
}
4.3.17. DeleteChild(BiTree T,TElemType p,int LR)
初始条件：二叉树T存在
操作步骤：当p指向的节点存在时，根据LR的值删除其左子树，或右子树
操作结果：根据LR的值，删除以p为根节点的子树
int DeleteChild(BiTree T,TElemType p,int LR){
BiTNode *q;
q = T;
if(q == NULL)return 0;
q = Point(q,p); //找到p指向的节点
if(LR){
q->rchild = NULL; //删除右子树
}
else{
q->lchild = NULL; //删除左子树
}
return 1;
}
4.3.18. PreOrderTraverse(BiTree T, int (*visit)(TElemType e))
初始条件：二叉树存在
操作步骤： 利用传入的visit函数进行显示递归进行遍历，先遍历根节点，然后遍历左子树，然后遍历右子树
操作结果：先序遍历整个二叉树
int PreOrderTraverse(BiTree T, int (*visit)(TElemType e))
{
if(T)
{
visit(T->data);
PreOrderTraverse(T->lchild,visit);
PreOrderTraverse(T->rchild,visit);
}
}
4.3.19. InOrderTraverse(BiTree T,int (*visit)(TElemType e))
初始条件：二叉树T存在
操作步骤：利用传入的visit函数进行显示递归进行遍历，先遍历左子树，然后遍历根节点，然后遍历右子树
操作结果：中序遍历整个二叉树
int InOrderTraverse(BiTree T,int (*visit)(TElemType e))
{
if(T)
{
InOrderTraverse(T->lchild,visit);//遍历左子树
visit(T->data);//输出根节点值
InOrderTraverse(T->rchild,visit);//遍历右子树
}
}
4.3.20. PostOrderTraverse(BiTree T,int (*visit)(TElemType e))
初始条件：二叉树T存在
操作步骤：利用传入的visit函数进行显示，递归进行遍历，先遍历左子树，然后遍历右子树，然后遍历根节点

操作结果：后序遍历二叉树
int PostOrderTraverse(BiTree T,int (*visit)(TElemType e))
{
if(T)
{
PostOrderTraverse(T->lchild,visit);//遍历左子树

PostOrderTraverse(T->rchild,visit);//遍历右子树
visit(T->data);//输出根节点值
}
}

4.3.21. LevelTraverse(BiTree T,int (*visit)(TElemType e))
初始条件： 二叉树存在
操作步骤： 利用队列，先将根节点入队，然后队列顺序出队，出队元素的左右子树存在时，将他们入队，之后对该元素调用visit函数，直到队列为空
操作结果：按层遍历整个二叉树
int LevelTraverse(BiTree T,int (*visit)(TElemType e))
{
BiTNode *p;
LinkQueue Q;
InitQueue(&Q);
p = T;
if(p) EnQueue(&Q,p);
while(!QueueEmpty(Q)){
DeQueue(&Q,&p);
if(p->lchild)EnQueue(&Q,p->lchild);
if(p->rchild)EnQueue(&Q,p->rchild);
if(!visit(p->data)) return 0;
}
return 1;
}

4.3.22. Save(BiTree T,FILE *pf)
初始条件： 二叉树存在
操作步骤： 递归进行保存，先序保存，节点为空时，保存节点值为“#”
操作结果：保存整个二叉树到指定文件
int Save(BiTree T,FILE *pf)
{
char c = '#';
if(T == NULL)
fwrite(&c, sizeof(char), 1, pf);
else
{
fwrite(&(T->data.c), sizeof(char), 1, pf);
Save(T->lchild, pf);
Save(T->rchild, pf);
}
return 1;

}

4.3.23. Load(BiTree *T, FILE *pf)
初始条件： 初始化过二叉树
操作步骤： 递归进行读取，先序创建二叉树，过程类似与CreatBitree
操作结果：将文件中的二叉树恢复到系统中
int Load(BiTree *T, FILE *pf)
{
char c;
fread(&c, sizeof(char), 1, pf);
if(c == '#')
*T = NULL;
else
{
*T = (BiTree )malloc(sizeof(BiTNode));
(*T)->data.c = c;
Load(&((*T)->lchild), pf);
Load(&((*T)->rchild), pf);
}
return 1;
}
4.4 效率分析
4.4.1. InitBiTree(BiTree *T)
效率分析：执行常数运算，时间复杂度为O(1)
4.4.2. DestroyBiTree(BiTree T)
效率分析：递归释放二叉树节点，对每一个节点操作一次，时间复杂度为O(n)
4.4.3. CreateBiTree(BiTree *T)
效率分析：递归建立二叉树，对每一个节点操作一次，时间复杂度为O(n)
4.4.4. ClearBiTree(BiTree T)
效率分析：算法与Destroy相同，为O(n)
4.4.5．BiTreeEmpty(BiTree T)
效率分析：执行常数运算，时间复杂度为O(1)
4.4.6. BiTreeDepth(BiTree T)
效率分析：执行常数运算，时间复杂度为O(1)
4.4.7. Root(BiTree T)
效率分析：执行常数运算，时间复杂度为O(1)
4.4.8．Value(BiTree T,TElemType e)
效率分析：递归查找二叉树，对每一个节点操作一次，时间复杂度为O(n)
4.4.9. Assign(BiTree T, BiTNode *e, TElemType value)
效率分析：基础为Value，时间复杂度为O(n)
4.4.10. Parent(BiTree T,TElemType e)
效率分析：队列进行处理，时间复杂度由节点数决定，时间复杂度为O(n)
4.4.12. LeftChild(BiTree T,TElemType e)
效率分析：递归查找二叉树，与节点数有关，时间复杂度为O(n)
4.4.13. RightChild(BiTree T,TElemType e)
效率分析：递归查找二叉树，与节点数有关，时间复杂度为O(n)
4.4.14. LeftSibling(BiTree T, TElemType e)
效率分析：函数基于Parent与Point，时间复杂度为O(n)
4.4.15. RightSibling(BiTree T, TElemType e)
效率分析：函数基于Parent与Point，时间复杂度为O(n)
4.4.16. InsertChild(BiTree T,TElemType p,int LR,BiTree C)
效率分析：函数基于Point，时间复杂度为O(n)
4.4.17. DeleteChild(BiTree T,TElemType p,int LR)
效率分析：函数基于Point，时间复杂度为O(n)
4.4.18. PreOrderTraverse(BiTree T, int (*visit)(TElemType e))
效率分析：递归遍历，对每一个节点操作一次，时间复杂度为O(n)
4.4.19. InOrderTraverse(BiTree T,int (*visit)(TElemType e))
效率分析：递归遍历，对每一个节点操作一次，时间复杂度为O(n)
4.4.20. PostOrderTraverse(BiTree T,int (*visit)(TElemType e))
效率分析：递归遍历，对每一个节点操作一次，时间复杂度为O(n)
4.4.21. LevelTraverse(BiTree T,int (*visit)(TElemType e))
效率分析：队列遍历，对每一个节点操作一次，时间复杂度为O(n)
4.4.22. Save(BiTree T,FILE *pf)
效率分析：递归保存，对每一个节点操作一次，时间复杂度为O(n)
4.4.23. Load(BiTree *T, FILE *pf)
效率分析：递归建立，对每一个节点操作一次，时间复杂度为O(n)