(1)已知某二叉树（三叉链表）的根结点地址root，该树中各结点的左、右孩子指针域已正确填充，写一个算法将所有结点的双亲指针域正确填充。

题意为已知某二叉树（三叉链表）的根结点地址为 root，该树中各结点的左、右孩子指针域已正确填充，写一个算法将所有结点的双亲指针域正确填充。

答案：

在前序遍历二叉树的同时，维护一个指针记录当前节点的父节点，每当访问一个节点时，将该节点的双亲指针指向父节点即可。

具体做法为：

先将根节点入栈，然后循环执行以下操作：

1.弹出栈顶节点并访问该节点。

2.如果该节点有右孩子，则将右孩子入栈。

3.如果该节点有左孩子，则将左孩子入栈。

4.将当前节点的双亲指针指向父节点，如果当前节点是根节点，则将父节点指针设为NULL。

代码如下：

def fill_parent_pointer(root):
    stack = []   # 建立一个栈，先将根节点入栈
    stack.append((root, None))
    while stack:
        node, parent = stack.pop()   # 弹出栈顶节点
        node.parent = parent         # 将当前节点的双亲指针指向父节点
        # 如果该节点有右孩子，则将右孩子入栈
        if node.right:
            stack.append((node.right, node))
        # 如果该节点有左孩子，则将左孩子入栈
        if node.left:
            stack.append((node.left, node))
        # 如果当前节点是根节点，则将父节点指针设为NULL
        if node == root:
            node.parent = None

其中 node.parent 表示节点的双亲指针域，node.left 和 node.right 分别表示节点的左孩子和右孩子指针域。