1.设计一个用于计算二叉树的深度的算法，已知二叉链表的结构为：Ichild|data rchild。请你首先定义一个二叉链表（4分），再编写相应的算法（8分）。

### 回答1：

定义一个二叉链表：struct Node{ int data; Node *lchild; Node *rchild; };编写算法：int getDepth(Node *root) { if(root == NULL) return 0; int ldepth = getDepth(root->lchild); int rdepth = getDepth(root->rchild); return ldepth > rdepth ? ldepth + 1 : rdepth + 1; }

### 回答2：
首先，我们可以定义一个二叉链表的结构体节点如下：

struct TreeNode {
int data;
struct TreeNode* rchild;
struct TreeNode* lchild;
};

其中，data表示节点的值，rchild表示右子节点指针，lchild表示左子节点指针。

接下来，我们可以编写计算二叉树深度的算法，例如使用递归方式：

int getDepth(struct TreeNode* root) {
if (root == NULL) {
return 0; // 空树的深度为0
} else {
int leftDepth = getDepth(root->lchild); // 递归计算左子树深度
int rightDepth = getDepth(root->rchild); // 递归计算右子树深度
return (leftDepth > rightDepth) ? (leftDepth + 1) : (rightDepth + 1); // 返回较大深度加上根节点的深度
}
}

以上算法的思路是先判断二叉树是否为空，若为空，则深度为0，否则，分别递归计算左子树和右子树的深度，并返回较大深度加上根节点的深度。

例如，对于以下二叉树：

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

使用上述算法计算深度，树的深度为4。

### 回答3：
首先，我们可以定义一个二叉链表的结点类Node，包含两个属性：数据data和左右子节点Ichild和rchild。

class Node:
    def __init__(self, data):
        self.data = data
        self.Ichild = None
        self.rchild = None

接下来，我们可以通过创建节点实例，并建立它们之间的连接，构建二叉树。例如，我们创建一个二叉树如下：

# 构建一个例子的二叉树
root = Node(1)
root.Ichild = Node(2)
root.rchild = Node(3)
root.Ichild.Ichild = Node(4)
root.Ichild.rchild = Node(5)

接下来，我们编写一个计算二叉树深度的算法。这个算法使用递归的方式来计算深度。对于每个节点，我们计算它的左右子树的深度，并返回左右子树深度中的最大值加1。

def binary_tree_depth(root):
    if root is None:
        return 0
    else:
        left_depth = binary_tree_depth(root.Ichild)
        right_depth = binary_tree_depth(root.rchild)
        return max(left_depth, right_depth) + 1

我们可以测试一下算法：

# 测试二叉树深度计算算法
print(binary_tree_depth(root))

这个例子中，二叉树的深度为3，该算法可以正常计算出结果。