实验五 二叉树的递归及非递归遍历及其应用

1.实验目的
熟练掌握二叉树的二叉链表存储结构的c语言实现。掌握二叉树的基本操作，前序、中序、后序遍历二叉树的3种方法。了解非递归遍历过程中“栈”的作用和状态，而且能灵活运用遍历算法实现二叉树的其他操作。
2.实验内容
（1）二叉树的·二叉链表创建
（2）二叉树的前、中、后序遍历的递归方法和非递归算法的实现
（3）求二叉树中叶子结点数目的递归算法
（4）编写求二叉树深度的递归算法
（5）编写判断二叉树是否相等的递归算法
（6）编写求二叉树左右子树互换的递归算法
（7）编写二叉树层序遍历的算法
（8）编写判断二叉树是否是完全二叉树的算法
创建二叉树的二叉链表结构，前、中、后、层序遍历的递归函数显示不同的遍历序列，结合习题了解二叉树遍历的应用实例。编写前、中、后、层序遍历的非递归函数，注意用以前做过的栈和队列做辅助存储结构。掌握用遍历算法求解其他问题的方法。

#include<stdio.h>
#include<stdlib.h>
#define TRUE 1
#define FALSE 0
#define ERROR 0
#define OK 1
#define OVERFLOW 0
typedef int Status;
typedef char TElemType;

typedef struct BiTNode {
 TElemType data;
 struct BiTNode *lchild, *rchild;
}BiTNode, *BiTree;


Status CreateBiTree(BiTree *T)
{
 TElemType ch;
 scanf_s("%c", &ch);
 if (ch == '#') *T = NULL;//空树
 else
 {
  if (!(*T = (BiTNode*)malloc(sizeof(BiTNode))))//开辟结点空间
  {
   printf("内存分配失败");
   exit(OVERFLOW);
  }
  (*T)->data = ch;//数据域赋值
  CreateBiTree(&(*T)->lchild);//创建左子树 注意：传递的是左子树结点的地址
  CreateBiTree(&(*T)->rchild);//创建右子树
 }
 return OK;
}


Status PrintElement(TElemType e)
{//输出元素e的值
 printf("%c", e);
 return OK;
}


Status PreOrderTraverse(BiTree T, Status(*Visit)(TElemType e))
{
 if (T)
 {
  if (Visit(T->data))//访问根结点
   if (PreOrderTraverse(T->lchild, Visit))//访问左子树
    if (PreOrderTraverse(T->rchild, Visit))//访问右子树
     return OK;
  return ERROR;
 }
 else
  return OK;
}


Status InOrderTraverse(BiTree T, Status(*Visit)(TElemType e))
{
 if (T)
 {
  if (InOrderTraverse(T->lchild, Visit))//访问左子树
   if (Visit(T->data))//访问根结点
    if (InOrderTraverse(T->rchild, Visit))//访问右子树
     return OK;
  return ERROR;
 }
 else
  return OK;
}


Status PostOrderTraverse(BiTree T, Status(*Visit)(TElemType e))
{
 if (T)
 {
  if (PostOrderTraverse(T->lchild, Visit))//访问左子树
   if (PostOrderTraverse(T->rchild, Visit))//访问右子树
    if (Visit(T->data))//访问根结点
     return OK;
  return ERROR;
 }
 else
  return OK;
}


int main()
{
 BiTree T;
 printf("输入二叉树中的数据元素：");
 CreateBiTree(&T);
 printf("先序遍历二叉树的序列是：");
 PreOrderTraverse(T, PrintElement);
 printf("\n");
 printf("中遍历二叉树的序列是：");
 InOrderTraverse(T, PrintElement);
 printf("\n");
 printf("后序遍历二叉树的序列是：");
 PostOrderTraverse(T, PrintElement);
 printf("\n");
 system("pause");
 return 0;
}

#include<stdio.h>
#include<stdlib.h>
#define TRUE 1
#define FALSE 0
#define ERROR 0
#define OK 1
#define OVERFLOW 0
typedef int Status;
typedef char TElemType;

typedef struct BiTNode {
 TElemType data;
 struct BiTNode *lchild, *rchild;
}BiTNode, *BiTree;

Status CreateBiTree(BiTree *T)
{
 TElemType ch;
 scanf_s("%c", &ch);
 if (ch == '#') *T = NULL;//空树
 else
 {
  if (!(*T = (BiTNode*)malloc(sizeof(BiTNode))))//开辟结点空间
  {
   printf("内存分配失败");
   exit(OVERFLOW);
  }
  (*T)->data = ch;//数据域赋值
  CreateBiTree(&(*T)->lchild);//创建左子树 注意：传递的是左子树结点的地址
  CreateBiTree(&(*T)->rchild);//创建右子树
 }
 return OK;
}


Status PrintElement(TElemType e)
{//输出元素e的值
 printf("%c", e);
 return OK;
}


Status PreOrderTraverse(BiTree T, Status(*Visit)(TElemType e))
{
 if (T)
 {
  if (Visit(T->data))//访问根结点
   if (PreOrderTraverse(T->lchild, Visit))//访问左子树
    if (PreOrderTraverse(T->rchild, Visit))//访问右子树
     return OK;
  return ERROR;
 }
 else
  return OK;
}


int LeafNodes(BiTree T)
{
 int numl, numr;
 if (T == NULL)//树空
 {
  // printf("树空");
  return 0;
 }
 else if ((T->lchild == NULL) && (T->rchild == NULL))
 {
  // printf("只有根结点");
  return 1;
 }
 else
 {
  numl = LeafNodes(T->lchild);
  numr = LeafNodes(T->rchild);
  return numl + numr;
 }
}


int Depth(BiTree T)
{
 int depthl, depthr;
 if (T == NULL)
 {
  //printf("树空");
  return 0;
 }
 else if (T->lchild == NULL && T->rchild == NULL)
 {
  //printf("只有根结点");
  return 1;
 }
 else
 {
  depthl = Depth(T->lchild);
  depthr = Depth(T->rchild);
 }
 return (depthl > depthr ? depthl : depthr) + 1;
}


Status ExchangeTree(BiTree *T)
{
 BiTree p;
 if ((*T)->lchild || (*T)->rchild)
 {//非叶子结点，交换左、右子女
  p = (*T)->lchild;
  (*T)->lchild = (*T)->rchild;
  (*T)->rchild = p;
  ExchangeTree(&(*T)->lchild);
  ExchangeTree(&(*T)->rchild);
 }
 return OK;
}


int main()
{
 BiTree T;
 int leafnode, treedepth;
 printf("输入二叉树中的数据元素：");
 CreateBiTree(&T);
 leafnode = LeafNodes(T);
 printf("此二叉树的叶子结点数是%d\n", leafnode);
 treedepth = Depth(T);
 printf("此二叉树的深度是%d\n", treedepth);
 ExchangeTree(&T);
 printf("交换左右子树后的先序序列是：");
 PreOrderTraverse(T, PrintElement);
 printf("\n");
 system("pause");
 return 0;
}

二叉树交换左右子树对树的形状有一定要求

#include<stdio.h>
#include<stdlib.h>
#define TRUE 1
#define FALSE 0
#define ERROR 0
#define OK 1
#define OVERFLOW 0
typedef int Status;
typedef char TElemType;
typedef struct BiTNode {
 TElemType data;
 struct BiTNode *lchild, *rchild;
}BiTNode, *BiTree;


Status CreateBiTree(BiTree *T)
{
 TElemType ch;
 scanf_s("%c", &ch);
 if (ch == '#') *T = NULL;//空树
 else
 {
  if (!(*T = (BiTNode*)malloc(sizeof(BiTNode))))//开辟结点空间
  {
   printf("内存分配失败");
   exit(OVERFLOW);
  }
  (*T)->data = ch;//数据域赋值
  CreateBiTree(&(*T)->lchild);//创建左子树 注意：传递的是左子树结点的地址
  CreateBiTree(&(*T)->rchild);//创建右子树
 }
 return OK;
}


Status PrintElement(TElemType e)
{//输出元素e的值
 printf("%c", e);
 return OK;
}


Status PreOrderTraverse(BiTree T, Status(*Visit)(TElemType e))
{
 if (T)
 {
  if (Visit(T->data))//访问根结点
   if (PreOrderTraverse(T->lchild, Visit))//访问左子树
    if (PreOrderTraverse(T->rchild, Visit))//访问右子树
     return OK;
  return ERROR;
 }
 else
  return OK;
}




/*
Status EqualTwoTree(BiTree T1, BiTree T2)
{//先序遍历判断两棵二叉树是否相等
 Status flag;
 if (T1 == NULL && T2 == NULL)
  flag = TRUE;//两棵树都为空
 else if (T1 == NULL || T2 == NULL)
  flag = FALSE;//两棵树有一棵树为空
 else
 {
  if (T1->data == T2->data)      flag = TRUE;
  else { flag = FALSE;  return flag; }
  if (flag)
  {
   EqualTwoTree(T1->lchild, T2->lchild);
   EqualTwoTree(T1->rchild, T2->rchild);
  }
 }
 return flag;
}
*/



Status EqualTwoTree(BiTree T1, BiTree T2)
{
 if (T1 == NULL && T2 == NULL)
  return TRUE;
 if (T1 != NULL && T2 != NULL && T1->data&&T2->data&&EqualTwoTree(T1->lchild, T2->lchild) && EqualTwoTree(T1->rchild, T2->rchild))
  return FALSE;
 return FALSE;
}


int main()
{
 BiTree T1, T2;
 printf("输入二叉树T1中的数据元素：");
 CreateBiTree(&T1);
 getchar();
 printf("先序遍历二叉树T1的序列是：");
 PreOrderTraverse(T1, PrintElement);
 printf("\n");
 printf("输入二叉树T2中的数据元素：");
 CreateBiTree(&T2);
 printf("先序遍历二叉树T2的序列是：");
 PreOrderTraverse(T2, PrintElement);
 printf("\n");
 if (EqualTwoTree(T1, T2))
  printf("两棵树相等\n");
 else
  printf("两棵树不相等\n");
 system("pause");
 return 0;
}

1.代码中注释掉的那个判断二叉树是否相等函数有bug存在，但我到目前为止还没有找到，又或者是主函数存在问题，希望有同学能帮忙指正。
2.输入第一个树之后要用ffush(stdin)清楚缓存区，或者用getchar()接受回车键

#include<stdio.h>
#include<stdlib.h>
#define TRUE 1
#define FALSE 0
#define ERROR 0
#define OK 1
#define OVERFLOW 0
#define MAXQSIZE 100//最大队列长度
typedef int Status;
typedef char TElemType;

typedef struct BiTNode {
 TElemType data;
 struct BiTNode *lchild, *rchild;
}BiTNode, QElemType, *BiTree;

typedef struct {
 QElemType *base;//初始化的动态分配存储空间
 int front;//头指针，若队列不空，指向队列头元素
 int rear;//尾指针，若队列不空，指向队列尾元素的下一个位置
    //他们并不是真正的指针，只是用于指示位置
}SqQueue;


Status InitQueue(SqQueue* Q)
{//构造一个空队列Q
 Q->base = (QElemType*)malloc(MAXQSIZE * sizeof(QElemType));
 if (!Q->base)
  exit(OVERFLOW);//存储分配失败
 Q->front = Q->rear = 0;
 return OK;
}


int QueueLength(SqQueue  Q)
{//返回Q中元素的个数，即队列的长度
 return (Q.rear - Q.front + MAXQSIZE) % MAXQSIZE;
}


Status QueueEmpty(SqQueue Q)
{
 {
  if (Q.rear == Q.front)
   return OK;
  else return ERROR;
 }
}


Status EnQueue(SqQueue*Q, QElemType e)
{//插入元素e作为Q的新的队列元素
 if ((Q->rear + 1) % MAXQSIZE == Q->front)
  //if后边不要带 ; 很坑虽然能运行程序，
  //但会直接进入下一个语句，退出EnQueue()函数
 {
  printf("当前队列已满");
  return ERROR;
 }
 Q->base[Q->rear] = e;
 Q->rear = (Q->rear + 1) % MAXQSIZE;
 return OK;
}


Status DeQueue(SqQueue*Q, QElemType *e)
{//出队列
 if (Q->front == Q->rear)
 {
  printf("当前队列为空");
  return ERROR;
 }
 *e = Q->base[Q->front];
 Q->front = (Q->front + 1) % MAXQSIZE;
 return OK;
}


Status CreateBiTree(BiTree *T)
{
 TElemType ch;
 scanf_s("%c", &ch);
 if (ch == '#') *T = NULL;//空树
 else
 {
  if (!(*T = (BiTNode*)malloc(sizeof(BiTNode))))//开辟结点空间
  {
   printf("内存分配失败");
   exit(OVERFLOW);
  }
  (*T)->data = ch;//数据域赋值
  CreateBiTree(&(*T)->lchild);//创建左子树 注意：传递的是左子树结点的地址
  CreateBiTree(&(*T)->rchild);//创建右子树
 }
 return OK;
}


Status PrintElement(TElemType e)
{//输出元素e的值
 printf("%c", e);
 return OK;
}


Status PreOrderTraverse(BiTree T, Status(*Visit)(TElemType e))
{
 if (T)
 {
  if (Visit(T->data))//访问根结点
   if (PreOrderTraverse(T->lchild, Visit))//访问左子树
    if (PreOrderTraverse(T->rchild, Visit))//访问右子树
     return OK;
  return ERROR;
 }
 else
  return OK;
}


Status SeqTraverse(BiTree T)
{
 SqQueue Q;
 InitQueue(&Q);
 EnQueue(&Q, *T);
 BiTree root = T;
 while (!QueueEmpty(Q))
 {
  DeQueue(&Q, root);
  printf("%c", root->data);
  if (root->lchild)
   EnQueue(&Q, *root->lchild);
  if (root->rchild)
   EnQueue(&Q, *root->rchild);
 }
 return OK;
}


int main()
{
 BiTree T;
 printf("输入二叉树中的数据元素：");
 CreateBiTree(&T);
 printf("先序遍历二叉树的序列是：");
 PreOrderTraverse(T, PrintElement);
 printf("\n");
 printf("层序遍历二叉树的序列是：");
 SeqTraverse(T);
 printf("\n");
 system("pause");
 return 0;
}

#include<stdio.h>
#include<stdlib.h>
#define TRUE 1
#define FALSE 0
#define ERROR 0
#define OK 1
#define OVERFLOW 0
#define MAXQSIZE 100//最大队列长度
typedef int Status;
typedef char TElemType;
typedef struct BiTNode {
 TElemType data;
 struct BiTNode *lchild, *rchild;
}BiTNode, *BiTree, *QElemType;


typedef struct {
 QElemType *base;//初始化的动态分配存储空间
 int front;//头指针，若队列不空，指向队列头元素
 int rear;//尾指针，若队列不空，指向队列尾元素的下一个位置
    //他们并不是真正的指针，只是用于指示位置
}SqQueue;


Status InitQueue(SqQueue* Q)
{//构造一个空队列Q
 Q->base = (QElemType*)malloc(MAXQSIZE * sizeof(QElemType));
 if (!Q->base)
  exit(OVERFLOW);//存储分配失败
 Q->front = Q->rear = 0;
 return OK;
}


int QueueLength(SqQueue  Q)
{//返回Q中元素的个数，即队列的长度
 return (Q.rear - Q.front + MAXQSIZE) % MAXQSIZE;
}


Status QueueEmpty(SqQueue Q)
{
 {
  if (Q.rear == Q.front)
   return OK;
  else return ERROR;
 }
}


Status EnQueue(SqQueue*Q, QElemType e)
{//插入元素e作为Q的新的队列元素
 if ((Q->rear + 1) % MAXQSIZE == Q->front)
  //if后边不要带 ; 很坑虽然能运行程序，
  //但会直接进入下一个语句，退出EnQueue()函数
 {
  // printf("当前队列已满");
  return ERROR;
 }
 Q->base[Q->rear] = e;
 Q->rear = (Q->rear + 1) % MAXQSIZE;
 return OK;
}


Status DeQueue(SqQueue*Q, QElemType *e)
{//出队列
 if (Q->front == Q->rear)
 {
  // printf("当前队列为空");
  return ERROR;
 }
 *e = Q->base[Q->front];
 Q->front = (Q->front + 1) % MAXQSIZE;
 return OK;
}


Status CreateBiTree(BiTree *T)
{
 TElemType ch;
 scanf_s("%c", &ch);
 if (ch == '#') *T = NULL;//空树
 else
 {
  if (!(*T = (BiTNode*)malloc(sizeof(BiTNode))))//开辟结点空间
  {
   printf("内存分配失败");
   exit(OVERFLOW);
  }
  (*T)->data = ch;//数据域赋值
  CreateBiTree(&(*T)->lchild);//创建左子树 注意：传递的是左子树结点的地址
  CreateBiTree(&(*T)->rchild);//创建右子树
 }
 return OK;
}


Status PrintElement(TElemType e)
{//输出元素e的值
 printf("%c", e);
 return OK;
}
Status PreOrderTraverse(BiTree T, Status(*Visit)(TElemType e))
{
 if (T)
 {
  if (Visit(T->data))//访问根结点
   if (PreOrderTraverse(T->lchild, Visit))//访问左子树
    if (PreOrderTraverse(T->rchild, Visit))//访问右子树
     return OK;
  return ERROR;
 }
 else
  return OK;
}


Status IsCompleteBiTree(BiTree T) {
 if (!T)return TRUE;             // 若为一个空树，则直接结束
 int flag = 0;               //设立一个flag，若某结点有左右孩子则为0;若某一个空了，则为1
 SqQueue Q;
 BiTree* e;
 e = (BiTree *)malloc(sizeof(BiTree));
 InitQueue(&Q);
 EnQueue(&Q, T);             //将根结点入队列
 while (DeQueue(&Q, e)) {     //当队列不空时
  if (!(*e)) {             //若当前元素为空，则flag = 1，直接进行下一个循环
   flag = 1;
   continue;
  }
  else if (flag) {        //若当前元素不为空，且flag == 1，则证明该树不为完全二叉树
   return FALSE;
  }
  else {
   EnQueue(&Q, (*e)->lchild);
   EnQueue(&Q, (*e)->rchild);
  }
 }
 return TRUE;
}


int main()
{
 BiTree T;
 printf("输入二叉树中的数据元素：");
 CreateBiTree(&T);
 printf("先序遍历二叉树的序列是：");
 PreOrderTraverse(T, PrintElement);
 printf("\n");
 if (IsCompleteBiTree(T))
  printf("是完全二叉树\n");
 else
  printf("不是完全二叉树\n");
 system("pause");
 return 0;
}