1 二叉树的创建

整体思路

• 将数组里的元素一直分为根，左子树，右子树，遇到#就返回NULL，链接到上层递归的左子树或者右子树，一定要把一个节点的左子树全部递归完才能返回到右子树。
• 这种方法也可以scanf一个数组里的元素，然后构建出一个二叉树。

代码实现 

TreeNode* TreeCreate(char* a, int* pi)
{if (a[*pi] == '#'){(*pi)++;return NULL;}TreeNode* root = (TreeNode*)malloc(sizeof(TreeNode));if (root == NULL){perror("malloc fail");exit(-1);}root->data = a[(*pi)++];root->left = TreeCreat(a, pi);root->right = TreeCreate(a, pi);return root;
}

递归展开图

2 二叉树的销毁

• 销毁二叉树使用前序、中序或者后序都可以
• 后序最方便，前序中序都需要先保存左右孩子再销毁，后序都遍历完了再一个一个销毁，很方便。

代码实现 

方法1：二级指针

//销毁二叉树
void DestoryTree(TreeNode** root)
{if (*root == NULL)return;DestoryTree(*((*root)->left));DestoryTree(*((*root)->right));free(*root);*root = NULL;
}

方法2：在main函数里面手动销毁

• void DestoryTree(TreeNode* root)
  {if (root == NULL)return;DestoryTree(root->left);DestoryTree(root->right);free(root);
  }int main()
  {TreeNode* root = CreateTree();DestoryTree(root);root = NULL;return 0;
  }

3 判断二叉树是否是完全二叉树

整体思路

• 只要不连续，就不是完全二叉树。
• 层序遍历（全部元素都入队列，空也入队列）
• 遇到空了就跳出循环

进入另外一个循环

• 查看从空开始后面的元素是否都是NULL
• 若全是NULL则证明是完全二叉树
• 若还有非空元素则证明不是完全二叉树

注意：当第一个空pop的时候，所有的元素都已经进队列了。（可以画图理解）

代码实现

// 判断二叉树是否是完全二叉树
bool TreeComplete(TreeNode* root)
{Queue q;QueueInit(&q);if (root)QueuePush(&q, root);int levelSize = 1;while (!QueueEmpty(&q)){TreeNode* front = QueueFront(&q);QueuePop(&q);if (front == NULL)break;QueuePush(&q, front->left);QueuePush(&q, front->right);}// 前面遇到空以后，后面还有非空就不是完全二叉树while (!QueueEmpty(&q)){TreeNode* front = QueueFront(&q);QueuePop(&q);if (front){QueueDestroy(&q);return false;}}QueueDestroy(&q);return true;
}