#pragma once
//Queue.h
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <stdbool.h>
#include "BinaryTree.h"
typedef BTNode* QNodeDataType;
typedef struct QueueNode
{
  struct QueueNode* next;
  QNodeDataType data;
}QNode;
typedef struct Queue
{
  QNode* head;
  QNode* tail;
  int size;
}Queue;
extern void QueueInit(Queue* pq);
extern void QueueDestroy(Queue* pq);
extern void QueuePush(Queue* pq, QNodeDataType x);
extern void QueuePop(Queue* pq);
extern int QueueSize(Queue* pq);
extern bool QueueEmpty(Queue* pq);
extern QNodeDataType QueueFront(Queue* pq);
extern QNodeDataType QueueBack(Queue* pq);

#define _CRT_SECURE_NO_WARNINGS 1
//Queue.c
#include "Queue.h"
void QueueInit(Queue* pq)
{
  assert(pq);
  pq->head = NULL;
  pq->tail = NULL;
  pq->size = 0;
}
void QueueDestroy(Queue* pq)
{
  assert(pq);
  //由于每一个结点都是malloc出来的，所以
  //需要遍历逐一释放队列内的结点，防止内存泄露
  QNode* cur = pq->head;
  while (cur)
  {
    //先保存需要释放的结点del，释放后cur迭代地走下去
    //直到cur为空就全部释放完了
    QNode* del = cur;
    cur = cur->next;
    free(del);
    del = NULL;
  }
  pq->head = NULL;
  pq->tail = NULL;
  pq->size = 0;
}
void QueuePush(Queue* pq, QNodeDataType x)
{
  assert(pq);
  //申请结点
  QNode* newNode = (QNode*)malloc(sizeof(QNode));
  if (newNode == NULL)
  {
    perror("");
    return;
  }
  newNode->data = x;
  newNode->next = NULL;
  //第一次插入时由于队列为空，所以pq->head和pq->tail
  //都为空，则应该直接赋值结点的结构体给p->head和pq->tail
  //如果直接pq->tail->next = newNode程序会崩的，因为pq->tail为空
  //不能访问
  if (pq->head == NULL)
  {
    pq->head = pq->tail = newNode;
  }
  else
  {
    //插入到尾部
    pq->tail->next = newNode;
    //newNode更新为新的尾结点
    pq->tail = newNode;
  }
  //队列的数据数目+1
  pq->size++;
}
void QueuePop(Queue* pq)
{
  assert(pq);
  //删除的前提是不能队列为空
  assert(!QueueEmpty(pq));
  //如果只有一个结点的话，那删掉这个结点
  //同时把尾指针要置为NULL，不置空的话
  //尾指针就是一个野指针，存在越界访问的风险
  if (pq->head->next == NULL)
  {
    free(pq->head);
    pq->head = pq->tail = NULL;
  }
  else
  {
    //先保存下一个结点的地址，再释放当前的结点
    QNode* next = pq->head->next;
    free(pq->head);
    pq->head = next;
  }
  //数目-1
  pq->size--;
}
int QueueSize(Queue* pq)
{
  assert(pq);
  return pq->size;
}
bool QueueEmpty(Queue* pq)
{
  assert(pq);
  return pq->size == 0;
}
QNodeDataType QueueFront(Queue* pq)
{
  assert(pq);
  assert(!QueueEmpty(pq));
  return pq->head->data;
}
QNodeDataType QueueBack(Queue* pq)
{
  assert(pq);
  assert(!QueueEmpty(pq));
  return pq->tail->data;
}

#pragma once
//BinaryTree.h
#include <stdio.h>
#include <assert.h>
#include <stdlib.h>
#include <stdbool.h>
typedef char BTDataType;
typedef struct BinaryTreeNode
{
  struct BinaryTreeNode* left;
  struct BinaryTreeNode* right;
  BTDataType val;
}BTNode;
// 通过前序遍历的数组"ABD##E#H##CF##G##"构建二叉树
extern BTNode* BinaryTreeCreate(BTDataType* a, int* pi);
// 二叉树销毁
extern void BinaryTreeDestory(BTNode* root);
// 二叉树节点个数
extern int BinaryTreeSize(BTNode* root);
// 二叉树叶子节点个数
extern int BinaryTreeLeafSize(BTNode* root);
// 二叉树第k层节点个数
extern int BinaryTreeLevelKSize(BTNode* root, int k);
// 二叉树查找值为x的节点
extern BTNode* BinaryTreeFind(BTNode* root, BTDataType x);
// 二叉树前序遍历 
extern void BinaryTreePrevOrder(BTNode* root);
// 二叉树中序遍历
extern void BinaryTreeInOrder(BTNode* root);
// 二叉树后序遍历
extern void BinaryTreePostOrder(BTNode* root);
// 层序遍历
extern void BinaryTreeLevelOrder(BTNode* root);
// 判断二叉树是否是完全二叉树
extern bool BinaryTreeComplete(BTNode* root);

#define _CRT_SECURE_NO_WARNINGS 1
//BinaryTree.c
#include "BinaryTree.h"
#include "Queue.h"
BTNode* BinaryTreeCreate(BTDataType* a, int* pi)
{
  assert(a);
  //如果遇到‘#’，那说明遇到NULL了，pi指向的下标需要++
  //跳过这个字符‘#’，然后返回一颗NULL树
  if (a[*pi] == '#')
  {
    (*pi)++;
    return NULL;
  }
  //动态开辟一颗子树
  BTNode* root = (BTNode*)malloc(sizeof(BTNode));
  if (root == NULL)
  {
    perror("malloc fail");
    return NULL;
  }
  //给这棵树赋值数组对应的字符
  root->val = a[*pi];
  (*pi)++;
  //再递归构造棵树的左子树和右子树
  root->left = BinaryTreeCreate(a, pi);
  root->right = BinaryTreeCreate(a, pi);
  //最后返回这颗树
  return root;
}
void BinaryTreeDestory(BTNode* root)
{
  //如果遇到空树就返回
  if (root == NULL)
  {
    return;
  }
  //递归销毁这棵树的左子树和右子树
  BinaryTreeDestory(root->left);
  BinaryTreeDestory(root->right);
  //最后把这棵树的根销毁
  free(root);
  root = NULL;
}
int BinaryTreeSize(BTNode* root)
{
  //如果遇到空树，就返回0
  if (root == NULL)
  {
    return 0;
  }
  //否则就返回左子树的结点数+右子树的结点数+自己本身
  return BinaryTreeSize(root->left) + BinaryTreeSize(root->right) + 1;
}
int BinaryTreeLeafSize(BTNode* root)
{
  //如果遇到空树就返回，那证明后面就没有子树了，也就没有叶子节点，返回0
  if (root == NULL)
  {
    return 0;
  }
  //如果这棵树的左子树和右子树都为NULL，那证明这个结点就是叶子节点(根据叶子节点的定义)，返回1
  if (root->left == NULL && root->right == NULL)
  {
    return 1;
  }
  //否则就返回左子树的叶子节点的个数+右子树叶子节点的个数
  else
  {
    return BinaryTreeLeafSize(root->left) + BinaryTreeLeafSize(root->right);
  }
}
int BinaryTreeLevelKSize(BTNode* root, int k)
{
  //如果遇到空树，那就证明要么这一层就是所求的第K层的，要么就是
  //还没递归到第K层就出现了空树，无论是哪一种情况都说明这一层和
  //后面都不会有位于第K层的节点了，所以返回0
  //
  if (root == NULL)
  {
    return 0;
  }
  //如果K递减到，说明这一个跟节点就位于第K层，返回1
  if (k == 1)
  {
    return 1;
  }
  //否则就返回左子树的第K-1层的节点+右子树第K-1层的节点树
  return BinaryTreeLevelKSize(root->left, k - 1) + BinaryTreeLevelKSize(root->right, k - 1);
}
BTNode* BinaryTreeFind(BTNode* root, BTDataType x)
{
  //如果遇到空树就证明这一颗子树找不到x
  if (root == NULL)
  {
    return NULL;
  }
  //如果这棵树的根节点的值就是查找的x，就返回这个根节点
  //返回上一层调用这个函数的栈帧
  if (root->val == x)
  {
    return root;
  }
  //如果根节点不是要找的，就递归到左子树查找x
  BTNode* leftFind = BinaryTreeFind(root->left, x);
  //找到了就返回
  if (leftFind)
  {
    return leftFind;
  }
  //左子树找不到就递归到右子树查找
  BTNode* rightFind = BinaryTreeFind(root->right, x);
  //找到了就返回
  if (rightFind)
  {
    return rightFind;
  }
  //如果根不是，左子树找不到，右子树找不到，那就不可能找到这个值了
  //这里返回NULL是返回到上一层调用这个函数的栈帧中，并不是直接得出
  //结果，等到返回到第一层调用这个函数的栈帧后依然找不到这个值才是
  //真正的在这一整棵树都找不到这个值，建议话递归展开图理解
  return NULL;
  // 不能写成
  // return BinaryTreeFind(root->left, x) || BinaryTreeFind(root->right, x);
  // 因为这里要求的是返回节点的地址，
  //“||”是逻辑运算符，只能得到逻辑结果，即真或者加(0为假，非0为真)
  // 所以这样写的话直接返回的逻辑结果是布尔值，并不符合要求
  //不建议写成
  /*return BinaryTreeFind(root->left, x)
    ? BinaryTreeFind(root->left, x)
    : BinaryTreeFind(root->right, x);*/
    //因为如果在左子树找到了这个节点，但是由于没有保存
    //导致返回的时候又要再找一遍，如果这棵树的深度越深，
    //那么再找一遍的话越往下的子树呗反复调用的次数就越多
    //大大降低了效率
}
void BinaryTreePrevOrder(BTNode* root)
{
  //如果遇到空树就打印一个‘#’，再返回，
  // 这样能够更加直观地反映这棵树的真实的形状
  if (root == NULL)
  {
    printf("%c ",'#');
    return;
  }
  //否则先访问它的根节点，再递归访问它的左子树，最后递归访问它的右子树(这里的访问是打印)
  printf("%c ", root->val);
  BinaryTreePrevOrder(root->left);
  BinaryTreePrevOrder(root->right);
}
void BinaryTreeInOrder(BTNode* root)
{
  if (root == NULL)
  {
    printf("%c ", '#');
    return;
  }
  BinaryTreeInOrder(root->left);
  printf("%c ", root->val);
  BinaryTreeInOrder(root->right);
}
void BinaryTreePostOrder(BTNode* root)
{
  if (root == NULL)
  {
    printf("%c ", '#');
    return;
  }
  BinaryTreePostOrder(root->left);
  BinaryTreePostOrder(root->right);
  printf("%c ", root->val);
}
void BinaryTreeLevelOrder(BTNode* root)
{
  //如果传过来的是空树，那就直接返回了
  if (root == NULL)
  {
    return;
  }
  //否则创建一个队列
  Queue q;
  //初始化队列
  QueueInit(&q);
  //先把根节点入队列
  QueuePush(&q, root);
  //当队列为空的时候循环就结束了
  while (!QueueEmpty(&q))
  {
    //取队列头的元素
    BTNode* front = QueueFront(&q);
    //打印代表访问
    printf("%c ", front->val);
    //如果根节点的左孩子不为空，就把左孩子带进队列
    if (front->left)
    {
      QueuePush(&q, front->left);
    }
    //如果右孩子不为空，就把右孩子带进队列
    if (front->right)
    {
      QueuePush(&q, front->right);
    }
    //队列头的元素出队列
    QueuePop(&q);
  }
  //销毁队列
  QueueDestroy(&q);
}
bool BinaryTreeComplete(BTNode* root)
{
  //如果是空树，那么也认为是完全二叉树
  if (root == NULL)
  {
    return true;
  }
  //创建一个队列
  Queue q;
  QueueInit(&q);
  QueuePush(&q, root);
  while (!QueueEmpty(&q))
  {
    //取队列头的元素
    BTNode* front = QueueFront(&q);
    //队头元素出队列
    QueuePop(&q);
    //只要front不是NULL，就进它的左右孩子
    if (front)
    {
      QueuePush(&q, front->left);
      QueuePush(&q, front->right);
    }
    //遇到空就可以跳出循环去判断是否为完全二叉树了
    else
    {
      break;
    }
  }
  //只要队列不为空就一直判断是否存在有效节点
  while (!QueueEmpty(&q))
  {
    BTNode* front = QueueFront(&q);
    QueuePop(&q);
    //如果遇到不为空的节点，即有效节点，就判定不是完全二叉树
    //返回false
    if (front)
    {
      QueueDestroy(&q);
      return false;
    }
  }
  //来到这里证明队列为空都没找到有效节点，证明该树是完全二叉树
  QueueDestroy(&q);
  return true;
}

#define _CRT_SECURE_NO_WARNINGS 1
//test.c
#include "BinaryTree.h"
int main()
{
  char arr[] = "124##5##3#5##";
  int i = 0;
  BTNode* root = BinaryTreeCreate(arr, &i);
  BinaryTreePrevOrder(root);
  printf("\n");
  BinaryTreeInOrder(root);
  printf("\n");
  BinaryTreePostOrder(root);
  printf("\n");
  BinaryTreeLevelOrder(root);
  printf("\n");
  int ret = BinaryTreeComplete(root);
  if (ret == 1)
  {
    printf("root是完全二叉树\n");
  }
  else
  {
    printf("root不是完全二叉树\n");
  }
  printf("BinaryTreeSize:%d\n", BinaryTreeSize(root));
  printf("BinaryTreeLeafSize:%d\n", BinaryTreeLeafSize(root));
  printf("BinaryTreeLevelKSize:%d\n", BinaryTreeLevelKSize(root, 3));
  BTNode* find = BinaryTreeFind(root, '9');
  if (find)
  {
    printf("%c\n", find->val);
  }
  else
  {
    printf("NULL\n");
  }
  BinaryTreeDestory(root);
  root = NULL;
  return 0;
}