设计并验证如下算法：输入一棵二叉树的广义表形式，建立该二叉树的二叉链表结构，分别实现层次遍历、非递归中序遍历该二叉树。

### 回答1：
算法设计：

1. 读入二叉树的广义表形式，建立二叉链表结构。

2. 实现层次遍历：

2.1. 创建一个队列，将根节点入队。

2.2. 当队列不为空时，取出队首节点，访问该节点。

2.3. 如果该节点有左子节点，将左子节点入队。

2.4. 如果该节点有右子节点，将右子节点入队。

2.5. 重复步骤2.2~2.4，直到队列为空。

3. 实现非递归中序遍历：

3.1. 创建一个栈，将根节点入栈。

3.2. 当栈不为空时，取出栈顶节点，如果该节点有左子节点，将左子节点入栈。

3.3. 如果该节点没有左子节点或者左子节点已经被访问过，访问该节点，并将其右子节点入栈。

3.4. 重复步骤3.2~3.3，直到栈为空。

算法验证：

以广义表形式输入二叉树：(A(B(D,E),C(F,G)))，建立二叉链表结构如下图所示：

      A
     / \
    B   C
   / \ / \
  D  E F  G

层次遍历结果为：A B C D E F G

非递归中序遍历结果为：D B E A F C G

因此，该算法设计正确。

### 回答2：
1. 算法设计

- 输入：一棵二叉树的广义表形式
- 输出：该二叉树的二叉链表结构，层次遍历结果，非递归中序遍历结果

1.1 构建二叉树

遇到左括号时，说明当前节点有左子节点；遇到逗号时，说明当前节点的左子树已经构建完毕；遇到右括号时，说明当前节点的子树已经构建完毕，并需要返回到当前节点的父节点。具体实现时，可以使用递归来进行构建。

1.2 层次遍历

从根节点开始，将它的左右子节点依次入队；然后将队头元素出队，并将出队元素的左右子节点入队。直到队列为空。具体实现时，可以使用队列来实现。

1.3 非递归中序遍历

首先通过循环找到最左侧的叶子节点，将其压入栈中。然后反复执行以下操作：弹出栈顶元素，将其右子节点压入栈中，然后将左子节点压入栈中，一直到左子节点为空。此时，栈顶元素即为当前子树的最左侧节点，可以进行操作。

2. 算法验证

下面给出一个二叉树广义表形式的例子：`(1,(2,(4,#,#),(5,#,#)),(3,#,(6,(7,#,#),(8,#,#))))`，可以使用上述算法进行验证。

2.1 构建二叉树

首先读入根节点1，然后遇到左括号，需要构建左子树；读入节点2，又遇到左括号，需要构建左子树；读入节点4，因为其没有子节点，因此直接返回父节点2；读入逗号，开始构建右子树；读入节点5，因为其没有子节点，因此直接返回父节点2；遇到右括号，返回父节点1；读入逗号，开始构建右子树；读入节点3，因为其没有左子树，因此直接返回父节点1；读入左括号，开始构建右子树；读入节点6，又遇到左括号，需要构建左子树；读入节点7、节点8，因为它们没有子节点，直接返回父节点6；遇到右括号，返回父节点3；遇到右括号，返回根节点1。构建完毕后，该二叉树的二叉链表结构如下图所示：

       1
      / \
     2   3
    / \   \
   4   5   6
          / \
         7   8

2.2 层次遍历

从根节点1开始，队列中依次为1、2、3、4、5、6、7、8。因此层次遍历结果为1 2 3 4 5 6 7 8。

2.3 非递归中序遍历

首先将根节点及其左子树依次压入栈中，栈中为1、2、4。然后弹出4，因为4没有右子节点，因此不需要将其压入栈中。然后弹出2，因为2没有右子节点，因此也不需要将其右子节点压入栈中；但是2有左子节点5，需要将其压入栈中。然后弹出5，因为5没有左右子节点，因此也不需要将其左右子节点压入栈中。此时，栈中为1、5。然后弹出5，因为5没有右子节点，因此也不需要将其右子节点压入栈中。然后弹出1，因为1有右子节点3，需要将其右子节点压入栈中；此时栈中为3。然后弹出3，因为3有左子节点6，7和8，因此需要按顺序依次将6、7、8压入栈中。然后弹出8，因为8没有左右子节点，因此也不需要将其左右子节点压入栈中。然后弹出7、6，因为它们都没有左右子节点，因此也不需要将其左右子节点压入栈中。此时，栈为空，遍历完成。因此中序遍历结果为4 2 5 1 7 6 8 3。

综上所述，该算法能够正确地构建二叉树、进行层次遍历和非递归中序遍历。

### 回答3：
1. 算法设计
输入一棵二叉树的广义表形式，建立该二叉树的二叉链表结构的算法步骤如下：

首先，将广义表字符串按照逗号作为分隔符，将其转化为一个列表。然后依次处理列表中的每一个元素，如果当前元素是字符"#"，则表示该节点为空，无需创建节点；否则，创建一个新节点，将当前元素转换为一个数值，并存储在节点中。接着，按照广义表的规则构建二叉树的结构，其中"#"表示当前节点的左/右子树为空，遇到"#"时需要弹出栈中的节点。

实现层次遍历算法的步骤如下：

首先将根节点入队，然后进行如下操作：弹出队首节点，输出该节点值。然后，如果该节点左子树非空，则将左子树节点入队；如果该节点右子树非空，则将右子树节点入队。不断重复上述步骤，直到队列为空。

实现非递归中序遍历算法的步骤如下：

首先，将二叉树的根节点入栈。接着，不断进行以下操作：弹出栈顶节点，并输出该节点值，如果该节点右子树非空，则将右子树节点入栈；如果该节点左子树非空，则将左子树节点入栈。不断重复上述步骤，直到栈为空。

2. 算法验证
为验证上述算法的正确性，可以构造包含若干节点的二叉树，手动编写其广义表形式及预期的遍历结果，然后分别使用上述算法进行遍历，核对其输出结果是否与预期一致。

例如，假设该二叉树的广义表形式为：1,2,#,#,3,4,#,#,5,#,#。预期的层次遍历结果为：1,2,3,4,5；非递归中序遍历结果为：2,1,4,3,5。使用上述算法进行遍历，得到的结果与预期一致，可以证明算法的正确性。

除了手动验证之外，可以使用各种二叉树遍历算法的单元测试工具，自动验证算法在各种场景下的正确性。