【数据结构与算法】two X 树的遍历以及功能实现（下）

int BTreeHeight(BTNode* root)
{
  if (root == NULL)
  {
    return 0;
  }
  int h = 0;
  if (BTreeHeight(root->left) > BTreeHeight(root->right))
  {
      h = BTreeHeight(root->left) + 1;
  }
  else
  {
    h = BTreeHeight(root->right) + 1;
  }
  return h;
}

int BTreeHeight(BTNode* root)
{
  if (root == NULL)
  {
    return 0;
  }
  int leftHeight = BTreeHeight(root->left);
  int rightHeight = BTreeHeight(root->right);
  return leftHeight > rightHeight ? leftHeight + 1 : rightHeight+ 1;
}

int BTreeLevelKSize(BTNode* root, int k)
{
  assert(k > 0);
  if (root == NULL)
    return 0;
  if (k == 1)
    return 1;
  return BTreeLevelKSize(root->left, k - 1) 
         + BTreeLevelKSize(root->right, k - 1);
}

BTNode* BTreeFind(BTNode* root,BTDataType x)
{
  if (root == NULL)
    return NULL;
  if (root->data == x)
    return root;
  int ret1 = BTreeFind(root->left, x);
  if (ret1)
    return ret1;
  int ret2 = BTreeFind(root->right, x);
  if (ret2)
    return ret2;
  return NULL;
}

typedef struct BTNode* QDataType;//注意这个地方的类型
typedef struct QueueNode
{ 
  QDataType data;
  struct QueueNode* next;
}QNode;
typedef struct Queue
{
  QNode* phead;
  QNode* ptail;
  int size;
}Queue;//表示队列整体,一个是出数据，一个是入数据.
typedef int BTDataType;
typedef struct BinaryTreeNode
{
  BTDataType data;
  struct BinaryTreeNode* left;
  struct BinaryTreeNode* right;
}BTNode;

void LevelOrder(BTNode* root)
{
  Queue q;//在函数内部，定义了一个队列q，并通过调用QueueInit函数对队列进行初始化。
  QueueInit(&q);
    //如果根节点root不为空，将根节点入队，即调用QueuePush函数将root指针插入到队列q中。
  if (root)
    QueuePush(&q,root);
  while (!QueueEmpty(&q))
  {
    BTNode* front = QueueFront(&q);//首先通过调用QueueFront函数获取队列q的队首元素，并将其赋值给指针变量front
    QueuePop(&q);//调用QueuePop函数将队首元素出队
    printf("%d ", front->data);//通过printf函数打印front指向的节点的数据值
    //如果front的左子节点不为空，将左子节点入队，
    //即调用QueuePush函数将front->left指针插入到队列q中   
        if (front->left)
      QueuePush(&q, front->left);//后面这个参数是一个值，不是地址
    //如果front的右子节点不为空，将右子节点入队，
    //即调用QueuePush函数将front->right指针插入到队列q中。
    if (front->right)
      QueuePush(&q, front->right);//后面这个参数是一个值，不是地址
//循环体内的操作完成后，继续下一次循环，直到队列q为空。
  }
//最后，打印换行符表示层序遍历结束，
//并调用QueueDestroy函数销毁队列q，释放内存。
  printf("\n");
  QueueDestroy(&q);
}

bool BTreeComplete(BTNode* root)
{
  Queue q;
  QueueInit(&q);
  if (root)
    QueuePush(&q,root);
  while (!QueueEmpty(&q))//遍历树直到找到第一个空节点
  {
  BTNode* front= QueueFront(&q);
  QueuePop(&q);
  //遇到空就跳出
  if (front == NULL)
  {
    break;
  }
  QueuePush(&q, front->left);
  QueuePush(&q, front->right);
  }
  // 检查后面的节点有没有非空
  // 有非空，不是完全二叉树
  while (!QueueEmpty(&q))//由于中途遇到空，所以跳出循环，这次循环是为了检查后面元素是否为空
  {
    BTNode* front = QueueFront(&q);
    QueuePop(&q);
    if (front)
    {
      QueueDestroy(&q);
      return false;
    } 
  }
  QueueDestroy(&q);
  return true;
}