数据结构二叉树――建立二叉树、中序递归遍历、非递归遍历、层次遍历

数据结构二叉树――

编写函数实现：建立二叉树、中序递归遍历、借助栈实现中序非递归遍历、借助队列实现层次遍历、求高度、结点数、叶子数及交换左右子树。

("."表示空子树)

#include<stdio.h>
#include<stdlib.h>
//***********二叉树链表节点结构
typedef char DataType;

typedef struct Node
{
 DataType data;
 struct Node*LChild;
 struct Node*RChild;
}BiTNode,*BiTree;

void Insert_tree(BiTree *T)
{
 char ch;
 ch = getchar();
 if (ch == '.')//"."表示空子树
  *T = NULL;
 else 
 {
  *T = (BiTree)malloc(sizeof(BiTNode));
  (*T)->data = ch;
  Insert_tree(&((*T)->LChild));
  Insert_tree(&((*T)->RChild));
 }
}

//*************二叉树的中序递归遍历
void InOrder(BiTree root)
{
 if (root != NULL)
 {
  InOrder(root->LChild);
  printf("%c ",root->data);
  InOrder(root->RChild);
 }
}
//****************二叉树的中序非递归遍历算法（调用栈操作）
#define Stack_Size 50

typedef struct //顺序栈结构
{
 BiTree elem[Stack_Size];
 int top;   //用来存放栈顶元素的下标，top为-1表示空栈
}SeqStack;

void InitStack(SeqStack *S)// 顺序栈初始化
{
 S->top = -1;  //制造一个空栈
}

int Push(SeqStack *S, BiTree x)  //顺序进栈
{
 if (S->top == Stack_Size - 1)
  return 0;  //栈已满
 S->top++;
 S->elem[S->top] = x;
 return 1;
}

int Pop(SeqStack * S, BiTree *x)//顺序出栈
{
 if (S->top == -1)  //栈为空
  return 0;
 else
 {
  *x = S->elem[S->top];
  S->top--;
  return 1;
 }
}

int IsEmpty(SeqStack *s)
{
 return s->top == -1 ? 0 : 1;
}

void InOrder_2(BiTree root)   //二叉树的中序非递归遍历
{
 BiTree p;
 SeqStack S;
 InitStack(&S);
 p = root;
 while (p != NULL|| IsEmpty(&S))
 {
  if (p != NULL)
  {
   Push(&S, p);
   p = p->LChild;
  }
  else
  {
   Pop(&S,&p);
   if(p != NULL)
   printf("%c ", p->data);
   p = p->RChild;
  }
 }
}

//***********************借助队列实现二叉树的层次遍历
#define MAXSIZE 50
typedef struct
{
 BiTree element[MAXSIZE];
 int front;
 int rear;
}SeqQueue;

void InitQueue(SeqQueue *Q)//循环队列初始化
{
 Q->front = 0;
 Q->rear = 0;
}

int EnterQueue(SeqQueue *Q,BiTree x) //循环队列入队
{
 if ((Q->rear + 1) % MAXSIZE == Q->front)
  return 0;
 Q->element[Q->rear] = x;
 Q->rear = (Q->rear + 1) % MAXSIZE;
 return 1;
}

int IsEmpty_Q(SeqQueue *Q)//判断是否为空
{
 return(Q->rear == Q->front) ? 0 : 1;
}

int EeleteQueue(SeqQueue *Q,BiTree *x)  //循环队列出队
{
 if (Q->front == Q->rear)
  return 0;
 *x = Q->element[Q->front];
 Q->front = (Q->front + 1) % MAXSIZE;
 return 1;
}

int Layer_Order(BiTree root)
{
 SeqQueue Q;
 BiTree p;
 InitQueue(&Q);
 if (root == NULL)
  return 0;
 EnterQueue(&Q, root);
 while (IsEmpty_Q(&Q))
 {
  EeleteQueue(&Q,&p);
  printf("%c ", p->data);
  if(p->LChild)
  EnterQueue(&Q,p->LChild);
  if(p->RChild)
  EnterQueue(&Q,p->RChild);
 }
 return 1;
}

//***********************二叉树的高度(后序遍历)
int PostTreeDepth(BiTree bt)
{
 int hl, hr, max;
 if (bt != NULL)
 {
  hl = PostTreeDepth(bt->LChild);
  hr = PostTreeDepth(bt->RChild);
  max = hl > hr ? hl : hr; //使用三目运算符 为书写方便
  return (max + 1);
 }
 else
  return 0;
}
//***********************二叉树的结点个数

int Order(BiTree root)
{
 static int ordercount = 0;//static 定义静态变量，在静态区存储，程序运行结束释放，用于实现在原先基础上加“1”，实现统计数字的效果（与下文运用全局变量目的一致）
 if (root != NULL)
 {
  ordercount++;
  Order(root->LChild);
  Order(root->RChild);
 }
 return ordercount;
}

//***********************二叉树的叶子个数
int LeafCount = 0;//定义全局变量，它的内存在程序执行完之后才释放，用于实现在原先基础上加“1”，实现统计数字的效果
void leaf(BiTree root)  //后序遍历统计叶子结点数目
{
 //int LeafCount = 0;
 if (root != NULL)
 {
  leaf(root->LChild);
  leaf(root->RChild);
  if ((root->LChild == NULL) && (root->RChild == NULL))
   LeafCount++;
 }
 //return LeafCount;
}
//***********************交换二叉树每个结点的左子树和右子树
void Exchange(BiTree root)
{
 BiTree temp = NULL;
 if (root != NULL)
 {
  temp = root->LChild;
  root->LChild = root->RChild;
  root->RChild = temp;
  Exchange(root->LChild);
  Exchange(root->RChild);
 }
}

void menu()
{
 printf("***********************************************\n");
 printf("*                  MENU                       *\n");
 printf("***********************************************\n");
 printf("* 1.输入字符序列,建立二叉树的二叉链表   *\n");
 printf("* 2.二叉树的中序递归遍历                *\n");
 printf("* 3.二叉树的中序非递归遍历              *\n");
 printf("* 4.借助队列实现二叉树的层次遍历        *\n");
 printf("* 5.求二叉树的高度                      *\n");
 printf("* 6.求二叉树的结点个数                  *\n");
 printf("* 7.求二叉树的叶子个数                  *\n");
 printf("* 8.交换二叉树每个结点的左子树和右子树  *\n");
 printf("* 0.退出                                *\n");
 printf("***********************************************\n");
 printf("***********************************************\n");
 printf("请输入选择序号:->");
}

int main()
{
 int choose = 1;
 BiTree TT = NULL;
 while (choose)
 {
  menu();
  scanf_s("%d", &choose);
  getchar();//为不影响二叉树的输入，将输入缓存中的回车（\n）取出
  switch (choose)
  {
  case 1:
   Insert_tree(&TT);
   break;
  case 2:
   InOrder(TT);
   printf("\n");
   break;
  case 3:
   InOrder_2(TT);
   printf("\n");
   break;
  case 4:
   Layer_Order(TT);
   printf("\n");
   break;
  case 5:
   printf("高度 = %d\n",PostTreeDepth(TT));
   break;
  case 6:
   printf("节点个数 = %d \n",Order(TT));
   break;
  case 7:
   leaf(TT);
   printf("叶子个数 = %d\n", LeafCount);
   break;
  case 8:
   Exchange(TT);
   InOrder(TT);
   printf("\n");
   break;
  default:
   break;
  }
 }
 system("pause");
 return 0;
}