一、使用链表前序遍历创建二叉树（递归）

步骤

1. 创建二叉树函数，以根节点作为返回值；
2. 创建一棵二叉树结点，并初始化；
3. 为此二叉树结点申请存储空间；
4. 向数据域输入元素数据；
5. 考虑终止条件：当输入特殊字符’0’时，停止创建，即二叉树元素输入完毕；
6. 循环体中：访问左子树（调用函数自身）；访问右子树（调用函数自身）；
7. 循环体外，返回根节点。

二、二叉树的遍历

递归：前序、中序、后续

前序递归遍历：
若被遍历的二叉树非空，则：

1. 访问根结点；
2. 以前序遍历原则遍历根结点的左子树；
3. 以前序遍历原则遍历根结点的右子树。

非递归：前序、层次

前序非递归遍历：

1. 声明一个结点，作为当前结点；
2. 声明一个栈，用来存储返回的结点位置；
3. 若树不为空，则首先访问树的根结点并输出打印；
4. 判断当前结点是否有左右孩子（开始循环）；
5. 如果有右孩子，则将有孩子的地址压入栈中记忆；
6. 如果有左孩子，则向左移动，并输出打印；
7. 如果没有左孩子，则弹出栈顶元素（记忆处）作为当前结点，并输出打印；
8. 循环终止条件：存储栈为空。

层次非递归遍历（用栈实现队列的功能）：

1. 声明一个结点，作为当前结点；
2. 声明一个栈，用来存储返回的结点位置；
3. 若树不为空则开始循环；
4. 将当前结点的数据输出；
5. 若当前结点有右孩子，则将右孩子压入堆栈；
6. 若有左孩子，则将左孩子压入堆栈；
7. 弹出栈顶元素并移动；
8. 终止条件：存储栈为空。

三、完全二叉树的创建（使用数组）

完全二叉树的性质：

1. 对于一棵有n个结点的完全二叉树，其任意结点 i (1<=i<=n)，如果 i = 1, 则结点 i 是二叉树的根，无双亲; 如果 i>1,则其双亲parent(i)是结点 i/2。
2. 如果 2i>n; 则结点 i 无左孩子（结点 i 为叶子结点 ）; 否则其左孩子lchild(i)是结点 2i。
3. 如果 2i+1>n, 则结点 i 无右孩子; 否则其右孩子rchild(i)是结点 2i+1。

利用队列：

先生成所有结点并入队，再指出其父子关系。

步骤

生成二叉树（函数返回值为根节点地址）：

1. 创建结点链域：结构体；
2. 创建一个队列：使用数组实现，并初始化：front=1,rear=1；
3. 声明根结点与子节点；
4. 声明一个结点：为结点分配内存，并初始化后入队；
5. 队头结点为根节点；
6. 所有结点入队后匹配父子关系，循环条件为队列不为空；
7. 从队列的第一个结点开始，使用完全二叉树的性质开始匹配。