BTNode* CreateTree()
{
  BTNode* node1 = (BTNode*)malloc(sizeof(BTNode));
  BTNode* node2 = (BTNode*)malloc(sizeof(BTNode));
  BTNode* node3 = (BTNode*)malloc(sizeof(BTNode));
  BTNode* node4 = (BTNode*)malloc(sizeof(BTNode));
  BTNode* node5 = (BTNode*)malloc(sizeof(BTNode));
  BTNode* node6 = (BTNode*)malloc(sizeof(BTNode));
  BTNode* node7 = (BTNode*)malloc(sizeof(BTNode));
  node1->data = 4;
  node2->data = 2;
  node3->data = 7;
  node4->data = 1;
  node5->data = 3;
  node6->data = 6;
  node7->data = 9;
  node1->left = node2;
  node1->right = node3;
  node2->left = node4;
  node2->right = node5;
  node3->left = node6;
  node3->right = node7;
  node4->left = node4->right = NULL;
  node5->left = node5->right = NULL;
  node6->left = node6->right = NULL;
  node7->left = node7->right = NULL;
  return node1;
}

//求树的节点总个数
//后序遍历的思想：
//分治算法，先求左子树节点个数，再求右子树节点个数，再+1，这个+1就是加上自己
int TreeSize(BTNode* root)
{
  if (root == NULL)
  {
    return 0;
  }
  //int lSize = TreeSize(root->left);
  //int rSize = TreeSize(root->right);
  //return lSize + rSize + 1;
  //或者
  return TreeSize(root->left) + TreeSize(root->right) + 1;
}

//求整棵树的高度
//后序遍历的思想：先求左子树的高度，再求右子树的高度
//比较左右子树的高度，再+1，这个+1就是加自己本身的高度
//也是分治的算法思想
int TreeHeight(BTNode* root)
{
  //空树的高度为0
  if (root == NULL)
  {
    return 0;
  }
  int lHeight = TreeHeight(root->left);
  int rHeight = TreeHeight(root->right);
  return lHeight > rHeight ? lHeight + 1 : rHeight + 1;
  //注意：建议一定不要用下面的方法：
  //原因，这就相当于年级长要统计一班和二班的人数，叫各班班长统计，各班班长叫舍长统计
  //舍长辛辛苦苦统计了宿舍人数，上报之后，发现年纪长给只知道一班的人数更多，却忘了每个班的人数
  //又屁颠屁颠问班长给人数，更挫的是，班长居然也忘了刚刚统计的人数，又去问宿舍长人数，
  //更更挫的是，每个宿舍的宿舍长居然也忘了刚刚点的人数，又重新点一遍。
  //这样虽然能计算出来，但是效率大大大大降低
  //return TreeHeight(root->left) > TreeSize(root->right) ? TreeSize(root->left) + 1 : TreeSize(root->right) + 1;
}

//求树的所有叶子节点个数
//后序遍历，分治思想
//先求左子树的叶子节点个数，再求右子树叶子节点个数，再加起来
//求叶子节点的方法，该节点左右子树均为空，就是叶子节点
int TreeLeafSize(BTNode* root)
{
  //空树叶子节点为0
  if (root == NULL)
  {
    return 0;
  }
  //叶子节点
  if (root->left == NULL && root->right == NULL)
  {
    return 1;
  }
  return TreeLeafSize(root->left) + TreeLeafSize(root->right);
}

int TreeLevelKSize(BTNode* root, int k)
{
  //层数必须大于0
  assert(k > 0);
  //空树第几层都是0
  if (root == NULL)
  {
    return 0;
  }
  //这个if相当于在统计
  if (k == 1)
  {
    return 1;
  }
  //求左子树第k-1层节点个数+ 右子树第k-1层节点个数
  return TreeLevelKSize(root->left,k-1) + TreeLevelKSize(root->right,k-1);
}

BTNode* TreeFindX(BTNode* root, BTDataType x)
{
  if (root == NULL)
  {
    return NULL;
  }
  if (root->data == x)
  {
    return root;
  }
  //千万不能这样写，效率大大降低，同样的事情做了两遍
  //if (!TreeFindX(root->left, x))
  //{
  //  return TreeFindX(root->left, x);
  //}
  BTNode* Lret = TreeFindX(root->left, x);
  if (Lret != NULL)
  {
    return Lret;
  }
  //这个else包含了右子树找得到和找不到的情况，找不到就返回NULL
  else
  {
    return TreeFindX(root->right, x);
  }
  //也可以这样写,左子树右子树都用指针接收，如果都找不到，就返回NULL
  也可以定义右子树的返回值指针
  //BTNode* Rret = TreeFindX(root->right, x);
  //if(Rret!=NULL)
  //{
  //  return TreeFindX(root->right, x);
  //}
  //如果在子树找不到，就返回NULL，如果整棵树都找不到，也返回NULL
  //return NULL;
}

/思路：遍历第k层，相当于子树遍历第k-1层
//遍历第k层
void BTOrderK(BTNode* root, int k)
{
  if (root == NULL)
  {
    return;
  }
  if (k == 1)
  {
    printf("%d ", root->data);
    return;
  }
  BTOrderK(root->left, k - 1);
  BTOrderK(root->right, k - 1);
}

// 判断二叉树是否是完全二叉树,根据完全二叉树的性质，层序遍历把每个节点都放入队列
//然后依次出队，如果遇到NULL，判断队列是否为空
//如果队列为空,是完全二叉，否则，不是完全二叉树
bool BinaryTreeComplete(BTNode* root)
{
  //全部先入队，然后再出队，如果出队过程遇到空节点，判断队列是否为空，如果为空，就是完全二叉树
  Queue qt;
  QueueInit(&qt);
  BTNode* tmp = root;
  QueuePush(&qt, tmp);
  while (!QueueEmpty(&qt))
  {
    tmp = QueueFront(&qt);
    if (tmp != NULL)
      QueuePop(&qt);
    else
      break;
    //对于树来说即使是空节点，也要入队
    QueuePush(&qt, tmp->left);
    QueuePush(&qt, tmp->right);
  }
  //出了循环后，判断队列中的节点的值是否为NULL,只要有一个不为空，就不是完全二叉
  while (!QueueEmpty(&qt))
  {
    tmp = QueueFront(&qt);
    if (tmp != NULL)
    {
      return false;
    }
    QueuePop(&qt);
  }
  return true;
}

void BTDestroy(BTNode* root)
{
  if (root == NULL)
    return;
  BTDestroy(root->left);
  BTDestroy(root->right);
  free(root);
  //置空其实不起作用，要改变 *root，用**root
  root = NULL;
}