本次主要是针对二叉树的基本操作,另外还有二叉树相似的判断和叶子结点的计数,这些方法中都用到了递归。关于结构体的预定义还是会放在之前的博客(数据结构常用于定义总结)中
/*-------二叉树的二叉链结点结构定义------*/
#define TElemType char
typedef struct BiTNode{ // 结点结构
TElemType data; // 结点数据
struct BiTNode *lchild, *rchild; // 左右 孩子指针
} BiTNode, *BiTree;
/*-----------基本操作的函数-------------*/
//按照二叉树的定义初始化一个空树
Status InitBiTree(BiTree *bt){
*bt = (BiTree )malloc(sizeof(BiTNode));
if (!bt)return OVERFLOW;
*bt = NULL;
return OK;
}
//构造二叉链表表示的二叉树T
//按先序次序输入二叉树中结点的值(一个字符),空格字符表示空树
Status CreateBiTree(BiTree *T){
TElemType ch;
printf_s("请输入数据:");
scanf_s("%c", &ch);
getchar(); //getchar()用于处理回车占字符的问题
if (ch == '#')
*T = NULL;
else{
*T = (BiTree)malloc(sizeof(BiTNode));
if (!T)return OVERFLOW; // 若内存分配失败,则返回OVERFLOW
(*T)->data = ch; // 生成根结点
CreateBiTree(&((*T)->lchild)); //构建左子树
CreateBiTree(&((*T)->rchild)); //构建右子树
}
return OK;
}
//先序遍历二叉树T,对每个结点的值进行输出打印(表示已经访问过)
void PreOrderTraverse(BiTree T){
if (!T)return; // 若为一个空树,则直接结束
printf_s("%c", T->data); // 显示结点数据,可以更改为其它对结点操作
PreOrderTraverse(T->lchild);// 先遍历左孩子
PreOrderTraverse(T->rchild);// 再遍历右孩子
}
//中序遍历二叉树T,对每个结点的值进行输出打印(表示已经访问过)
void InOrderTraverse(BiTree T){
if (!T)return; // 若为一个空树,则直接结束
InOrderTraverse(T->lchild);// 先遍历左孩子
printf_s("%c", T->data); // 显示结点数据,可以更改为其它对结点操作
InOrderTraverse(T->rchild);// 再遍历右孩子
}
//后序遍历二叉树T,对每个结点的值进行输出打印(表示已经访问过)
void PostOrderTraverse(BiTree T){
if (!T)return; // 若为一个空树,则直接结束
PostOrderTraverse(T->lchild);// 先遍历左孩子
PostOrderTraverse(T->rchild);// 再遍历右孩子
printf_s("%c", T->data); // 显示结点数据,可以更改为其它对结点操作
}
//层序遍历二叉树T,对每个结点的值进行输出打印(表示已经访问过)
void LevelOrderTraverse(BiTree T){
if (!T)return; // 若为一个空树,则直接结束
SqQueue Q;
BiTree* e;
e = (BiTree *)malloc(sizeof(BiTree));
InitQueue(&Q);
EnQueue(&Q, T); //将根结点入队列
while (!IsQueueEmpty(Q)){ //当队列不空时
DeQueue(&Q, e); //取出队首元素
printf_s("%c", (*e)->data);
if ((*e)->lchild)EnQueue(&Q, (*e)->lchild);//当队首元素左子树存在时让其入队列
if ((*e)->rchild)EnQueue(&Q, (*e)->rchild);//当队首元素右子树存在时让其入队列
}
printf_s("\n");
}
Status SimilarBiTree(BiTree B, BiTree T){
if (!B && !T)return TRUE; // 若两棵二叉树都为空树,则相似
if (!B && T || B && !T)return FALSE; //若其中一棵为空树,而另一棵不为,则不相似
if (SimilarBiTree(B->lchild, T->lchild) && SimilarBiTree(B->rchild, T->rchild)){
return TRUE;
}
return FALSE;
}
int Count(BiTree T){
if (!T)return 0; //空树有0个叶子结点
if (!T->lchild && !T->rchild)return 1;
else {
return Count(T->lchild) + Count(T->rchild);
}
}