/***
*DynaLnkBiTree.cpp - 动态链式二叉树,即二叉树的动态链式存储实现
*
*
*题目:实验6-1 二叉树的动态链式存储实现
*
*
****/
#include <stdlib.h>
#include <stdio.h>
#include <malloc.h>
#include <memory.h>
#include <assert.h>
#include "DynaLnkBiTree.h"
/*------------------------------------------------------------
操作目的: 初始化二叉树
初始条件: 无
操作结果: 构造空二叉树
函数参数:
BinTree *T 待初始化的二叉树
返回值:
bool 操作是否成功
------------------------------------------------------------*/
bool InitBinTree(BinTree *T)
{
*T = NULL;
return true;
}
/*------------------------------------------------------------
操作目的: 销毁二叉树
初始条件: 二叉树T已存在
操作结果: 销毁二叉树
函数参数:
BinTree *T 待销毁的二叉树
返回值:
无
------------------------------------------------------------*/
void DestroyBinTree(BinTree *T)
{
assert(T != NULL);
DestroyBinTree(&(*T)->l);
DestroyBinTree(&(*T)->r);
free(T);
*T = NULL;
}
/*------------------------------------------------------------
操作目的: 创建二叉树
初始条件: 二叉树T已存在
操作结果: 销毁二叉树
函数参数:
BinTree *T 二叉树T
返回值:
bool 操作是否成功
参考提示:
请按照教材131页算法6.4的方式来创建二叉树。
------------------------------------------------------------*/
bool CreateBinTree(BinTree *T)
{
char c=NULL;
scanf("%c",c);
fflush(stdin);
if (c == ' ')
{
*T = NULL;
return true;
}
else
{
T = (BinTree*)malloc(sizeof(BinTNode));
if (*T == NULL)
{
return false;
}
(*T)->data = c;
CreateBinTree(&(*T)->l);
CreateBinTree(&(*T)->r);
}
return true;
}
/*------------------------------------------------------------
操作目的: 清空二叉树
初始条件: 二叉树T已存在
操作结果: 清空二叉树
函数参数:
BinTree *T 待清空的二叉树
返回值:
无
------------------------------------------------------------*/
void ClearBinTree(BinTree *T)
{
assert( T != NULL);
ClearBinTree(&(*T)->l);
ClearBinTree(&(*T)->r);
T = NULL;
}
/*------------------------------------------------------------
操作目的: 二叉树判空
初始条件: 二叉树T已存在
操作结果: 若T为空,则返回true;否则返回false
函数参数:
BinTree T 二叉树T
返回值:
bool 二叉树是否为空
------------------------------------------------------------*/
bool BinTreeEmpty(BinTree T)
{
if (T)
{
return false;
}
return true;
}
/*------------------------------------------------------------
操作目的: 二叉树求深度
初始条件: 二叉树T已存在
操作结果: 返回二叉树T的深度
函数参数:
BinTree T 二叉树T
返回值:
int 二叉树的深度
------------------------------------------------------------*/
int BinTreeDepth(BinTree T)
{
int l,r;
if (T == NULL)
{
return 0;
}
if (T->l == NULL && T->r == NULL)
{
return 1;
}
l = BinTreeDepth(T->l) + 1;
r = BinTreeDepth(T->r) + 1;
return l>r ? l:r;
}
/*------------------------------------------------------------
操作目的: 得到二叉树的根结点
初始条件: 二叉树T已存在
操作结果: 返回二叉树T的根结点
函数参数:
BinTree T 二叉树T
返回值:
BinTNode* 二叉树的根结点指针
------------------------------------------------------------*/
BinTNode *Root(BinTree T)
{
assert(T != NULL);
return T;
}
/*------------------------------------------------------------
操作目的: 判断结点n是否为树T的合法结点
初始条件: 二叉树T已存在
操作结果: n为T的结点返回true,否则返回false
函数参数:
BinTree T 二叉树T
BinTNode* n 二叉树的结点n
返回值:
bool 结点n是否存在与二叉树T中
------------------------------------------------------------*/
bool NodeExist(BinTree T, BinTNode* n)
{
assert(T != NULL);
assert(n != NULL);
if (T == n)
{
return true;
}
else if (NodeExist(T->l,n))
{
return true;
}
else if (NodeExist(T->r,n))
{
return true;
}
else
{
return false;
}
}
/*------------------------------------------------------------
操作目的: 得到二叉树指定结点的值
初始条件: 二叉树T已存在,n是二叉树T中的结点
操作结果: 返回结点n的值
函数参数:
BinTree T 二叉树T
BinTNode* n 二叉树结点n
返回值:
ElemType 结点n的值
------------------------------------------------------------*/
ElemType Value(BinTree T, BinTNode* n)
{
assert(n != NULL);
if (NodeExist(T,n))
{
return n->data;
}
}
/*------------------------------------------------------------
操作目的: 对二叉树的指定结点赋值
初始条件: 二叉树T已存在,n是二叉树T中的结点
操作结果: 操作成功返回true,操作失败返回false
函数参数:
BinTree T 二叉树T
BinTNode* n 二叉树结点n
ElemType e 结点值
返回值:
无
------------------------------------------------------------*/
void Assign(BinTree T, BinTNode* n, ElemType e)
{
assert(T !=NULL);
assert(n != NULL);
if (NodeExist(T,n))
{
T->data = e;
}
}
/*------------------------------------------------------------
操作目的: 得到二叉树指定结点的父结点
初始条件: 二叉树T已存在,n是二叉树T中的结点
操作结果: 如果二叉树结点n有父结点则返回父结点指针,否则返回NULL
函数参数:
BinTree T 二叉树T
BinTNode* n 二叉树结点n
返回值:
BinTNode* 父结点指针
------------------------------------------------------------*/
BinTNode* Parent(BinTree T, BinTNode* n)
{
assert(n!=NULL);
//空、
if (T==NULL)
{
return NULL;
}
if (T->l == NULL && T->r == NULL)
{
return NULL;
}
if(T->l == n || T->r == n)
{
return T;
}
//3.有左右
BinTree tmp;
if (tmp == Parent(T->l,n)!=NULL)
{
return tmp;
}
if (tmp == Parent(T->r,n)!=NULL)
{
return tmp;
}
}
/*------------------------------------------------------------
操作目的: 得到二叉树指定结点的左孩子
初始条件: 二叉树T已存在,n是二叉树T中的结点
操作结果: 如果二叉树结点n有左孩子则返回左孩子结点指针,否则返回NULL
函数参数:
BinTree T 二叉树T
BinTNode* n 二叉树结点n
返回值:
BinTNode* 左孩子结点指针
------------------------------------------------------------*/
BinTNode* LeftChild(BinTree T, BinTNode* n)
{
assert(T != NULL);
assert(n != NULL);
if (LeftChild(T->l,n))
{
return T->l;
}
return NULL;
}
/*------------------------------------------------------------
操作目的: 得到二叉树指定结点的右孩子
初始条件: 二叉树T已存在,n是二叉树T中的结点
操作结果: 如果二叉树结点n有右孩子则返回右孩子结点指针,否则返回NULL
函数参数:
BinTree T 二叉树T
BinTNode* n 二叉树结点n
返回值:
BinTNode* 右孩子结点指针
------------------------------------------------------------*/
BinTNode* RightChild(BinTree T, BinTNode* n)
{
assert(T != NULL);
assert(n != NULL);
if (RightChild(T->r,n))
{
return T->r;
}
return NULL;
}
/*------------------------------------------------------------
操作目的: 得到二叉树指定结点的左兄弟
初始条件: 二叉树T已存在,n是二叉树T中的结点
操作结果: 如果二叉树结点n有左兄弟则返回左兄弟结点指针,否则返回NULL
函数参数:
BinTree T 二叉树T
BinTNode* n 二叉树结点n
返回值:
BinTNode* 左兄弟结点指针
------------------------------------------------------------*/
BinTNode* LeftSibling(BinTree T, BinTNode* n)
{
BinTree tmp;
tmp = Parent(T,n);
if (tmp->l)
{
return tmp->l;
}
return NULL;
}
/*------------------------------------------------------------
操作目的: 得到二叉树指定结点的右兄弟
初始条件: 二叉树T已存在,n是二叉树T中的结点
操作结果: 如果二叉树结点n有右兄弟则返回右兄弟结点指针,否则返回NULL
函数参数:
BinTree T 二叉树T
BinTNode* n 二叉树结点n
返回值:
BinTNode* 右兄弟结点指针
------------------------------------------------------------*/
BinTNode* RightSibling(BinTree T, BinTNode* n)
{
BinTree tmp;
tmp = Parent(T,n);
if (tmp->r)
{
return tmp->r;
}
return NULL;
}
/*------------------------------------------------------------
操作目的: 在二叉树中插入结点
初始条件: 二叉树T已存在,p是二叉树T中的结点,n为待插入的结点
操作结果: 在二叉树的p结点之前插入结点n
函数参数:
BinTree T 二叉树T
BinTNode* p 二叉树结点p
LR d 二叉树结点p成为新结点n的左孩子或者右孩子
BinTNode* p 待插入结点n
返回值:
无
------------------------------------------------------------*/
void InsertNode(BinTree T, BinTNode* p, LR d, BinTNode* n)
{
assert(n != NULL);
//2.找p的位置,找p的父节点
BinTree tmp;
tmp = Parent(T,p);
if (tmp != NULL)
{
if (tmp->l == p)
{
tmp->l = n;
n->l = p;
n->r = NULL;
}
if (tmp->r == p)
{
tmp->r = n;
n->r = p;
n->l = NULL;
}
}
}
/*------------------------------------------------------------
操作目的: 在二叉树中删除结点
初始条件: 二叉树T已存在,p是二叉树T中的结点
操作结果: 删除二叉树的p结点
函数参数:
BinTree T 二叉树T
BinTNode* p 二叉树结点p
LR d 结点p的左孩子或者右孩子来取代p
返回值:
无
------------------------------------------------------------*/
void DeleteNode(BinTree T, BinTNode* p, LR d)
{
assert(NodeExist(T,p));
BinTree tmp;
tmp = Parent(T,p);
if (tmp != NULL)
{
if (tmp->l == p)
{
tmp->l = p->l;
tmp->l = p->r;
free(p);
p = NULL;
}
if (tmp->r == p)
{
tmp->r = p->l;
tmp->r = p->r;
free(p);
p = NULL;
}
}
}
/*------------------------------------------------------------
操作目的: 先序遍历二叉树
初始条件: 二叉树T已存在
操作结果: 先序的方式,对二叉树的每个结点调用(*fp)一次且仅一次
函数参数:
BinTree T 二叉树T
*fp 访问函数指针
返回值:
无
------------------------------------------------------------*/
void PreOrderTraverse(BinTree T, void (*fp)(ElemType))
{
assert(T != NULL);
(*fp)(T->data);
PreOrderTraverse(T->l,fp);
PreOrderTraverse(T->r,fp);
}
/*------------------------------------------------------------
操作目的: 中序遍历二叉树
初始条件: 二叉树T已存在
操作结果: 中序的方式,对二叉树的每个结点调用(*fp)一次且仅一次
函数参数:
BinTree T 二叉树T
*fp 访问函数指针
返回值:
无
------------------------------------------------------------*/
void InOrderTraverse(BinTree T, void (*fp)(ElemType))
{
assert(T != NULL);
InOrderTraverse(T->l,fp);
(*fp)(T->data);
InOrderTraverse(T->r,fp);
}
/*------------------------------------------------------------
操作目的: 后序遍历二叉树
初始条件: 二叉树T已存在
操作结果: 后序的方式,对二叉树的每个结点调用(*fp)一次且仅一次
函数参数:
BinTree T 二叉树T
*fp 访问函数指针
返回值:
无
------------------------------------------------------------*/
void PostOrderTraverse(BinTree T, void (*fp)(ElemType))
{
assert(T != NULL);
PostOrderTraverse(T->l,fp);
PostOrderTraverse(T->r,fp);
(*fp)(T->data);
}
/*------------------------------------------------------------
操作目的: 层序遍历二叉树
初始条件: 二叉树T已存在
操作结果: 层序的方式,对二叉树的每个结点调用(*fp)一次且仅一次
函数参数:
BinTree T 二叉树T
*fp 访问函数指针
返回值:
无
------------------------------------------------------------*/
void LevelOrderTraverse(BinTree T, void (*fp)(ElemType))
{
BinTree q[100];
int front = 0;
int rear =1;
q[0]=T;
while(front<rear)
{
if (q[front])
{
fp(q[front]->data);
q[rear++] = q[front]->l;
q[rear++] = q[front]->r;
front++;
}
else
{
front++;
}
}
}