2.要求二叉树按二叉链表形式存储。\n\n(1)写一个建立二叉树的算法。\n\n(2)写一个判别给定的二叉树是否是完全二叉树的算法。

### 回答1：
(1) 建立二叉树的算法：

1. 定义二叉树结构体，包含数据域和左右子树指针。
2. 读入二叉树的节点数据，若为0则表示该节点为空，否则创建一个新节点并将数据存入。
3. 递归建立左子树和右子树，直到读入的数据为0或者到达叶子节点。

(2) 判别给定的二叉树是否是完全二叉树的算法：

1. 对于一颗二叉树，从根节点开始按层次遍历，将每个节点依次入队列。
2. 如果队列中的节点有右子树但没有左子树，则不是完全二叉树。
3. 如果队列中的节点出现了空节点，那么空节点后面的所有节点都必须是空节点，否则不是完全二叉树。
4. 如果遍历完整棵树都没有发现不符合条件的情况，则是完全二叉树。

### 回答2：
(1)建立二叉树的算法：
二叉树按二叉链表形式存储，可以使用递归的方式建立二叉树。具体实现步骤如下：

1.先定义一个二叉树结构体，包括节点值，左右子树指针。
struct TreeNode {
int val;
TreeNode* left;
TreeNode* right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

2.定义建树函数，以先序遍历序列为输入参数。
TreeNode* createTree(vector<int>& preorder, int& index) {
if (index >= preorder.size() || preorder[index] == -1) {
index++;
return NULL;
}
TreeNode* root = new TreeNode(preorder[index++]);
root->left = createTree(preorder, index);
root->right = createTree(preorder, index);
return root;
}

3.调用该函数建立二叉树。
vector<int> preorder = {1,2,4,-1,-1,5,-1,-1,3,6,-1,-1,7,-1,-1};
int index = 0;
TreeNode* root = createTree(preorder, index);

该算法的时间复杂度为O(n)，因为每个节点都要遍历一次。

(2)判别给定二叉树是否是完全二叉树的算法：
完全二叉树是指除了最后一层之外，其它层的节点数均达到最大值，最后一层从左到右依次填满，不允许有空缺。实现判断算法的步骤如下：

1.广度优先遍历二叉树，将所有节点按从上到下、从左到右的顺序保存到队列中。
queue<TreeNode*> q;
q.push(root);

2.对于第一个缺少右儿子或两个儿子的节点，后面的节点必须没有子节点才能是完全二叉树。
bool isCompleteTree(TreeNode* root) {
if (root == NULL) return true;
queue<TreeNode*> q;
q.push(root);
bool flag = false;
while (!q.empty()) {
TreeNode* cur = q.front();
q.pop();
if (cur->left) {
if (flag) return false;
q.push(cur->left);
} else {
flag = true;
}
if (cur->right) {
if (flag) return false;
q.push(cur->right);
} else {
flag = true;
}
}
return true;
}

该算法的时间复杂度为O(n)，因为每个节点都需要遍历一次。

### 回答3：
1. 建立二叉树的算法
二叉树有很多种建立方式，其中一种常见的方式是使用先序遍历的方式来建立二叉树，即从根节点开始，按照先序遍历的顺序依次遍历各个节点。具体实现如下：

typedef struct TreeNode {
int data;
struct TreeNode *leftChild;
struct TreeNode *rightChild;
} TreeNode, *Tree;

void createTree(Tree &t) {
int data;
scanf("%d", &data);
if (data == -1)
t = NULL;
else {
t = (Tree)malloc(sizeof(TreeNode));
t->data = data;
createTree(t->leftChild);
createTree(t->rightChild);
}
}

首先读入一个节点的数据，如果数据为-1，表示该节点不存在，返回NULL；否则，分配一块内存作为该节点，设置该节点的数据域为data。接下来，递归创建左子树和右子树，分别将它们设置为当前节点的左子树和右子树。注意，这里的t是传入的二叉树指针的地址，因此需要使用指针的指针或者引用。

2. 判断完全二叉树的算法
完全二叉树是指除最后一层外，其他每层都被充分填满，并且最后一层从左到右依次填满的二叉树。对于一个二叉树，可以采用层序遍历的方式来判断它是否是完全二叉树。具体实现如下：

bool isCompleteTree(Tree t) {
if (!t)
return true;
queue<Tree> q;
q.push(t);
bool flag = false;
while (!q.empty()) {
Tree node = q.front();
q.pop();
if (node->leftChild) {
if (flag)
return false;
q.push(node->leftChild);
}
else
flag = true;
if (node->rightChild) {
if (flag)
return false;
q.push(node->rightChild);
}
else
flag = true;
}
return true;
}

首先将根节点入队，然后进行层序遍历，对于一个节点，若其左子树非空，则将其左子树入队；否则，记录下来这是第一个空节点，接下来如果还有节点的左子树或右子树非空，说明该树不是完全二叉树；如果没有，则说明该树是完全二叉树。