试写出二叉树的二叉链储存结构描述，并给出求深度算法

二叉树的二叉链表存储结构定义如下：

typedef struct BiTNode {
    int data;                    // 数据域
    struct BiTNode *lchild;      // 左孩子指针
    struct BiTNode *rchild;      // 右孩子指针
} BiTNode, *BiTree;

求取二叉树深度的算法如下：

int GetDepth(BiTree T) {
    if(T == NULL) {     // 空树深度为0
        return 0;
    }
    int left_depth = GetDepth(T->lchild);   // 左子树深度
    int right_depth = GetDepth(T->rchild);  // 右子树深度
    return left_depth > right_depth ? left_depth + 1 : right_depth + 1;
}

以上算法采用递归方式实现，时间复杂度为O(n)，其中n为二叉树中节点数。

相关问题

二叉树的二叉链表存储结构的求深度算法

二叉树的二叉链表存储结构的求深度算法，可以采用递归的方式实现。具体代码如下：

int TreeDepth(BiTree T) {
    if (T == NULL) {
        return 0;
    }
    int left_depth = TreeDepth(T->lchild);
    int right_depth = TreeDepth(T->rchild);
    return left_depth > right_depth ? left_depth + 1 : right_depth + 1;
}

其中，BiTree是二叉树的指针类型，lchild和rchild分别表示左右孩子指针。算法的思想是：如果当前节点为空，则返回0；否则，递归求出左子树的深度和右子树的深度，然后取一个更大的数，再加1，即为当前节点的深度。

二叉树的二叉链表存储结构的求深度非递归算法

答：可以使用栈来实现非递归算法。从根节点开始，每个节点先入栈，然后从左子树往下递归入栈，直到左子树为空。接着，出栈一个节点，判断其是否存在右子树，若存在，将右子树入栈并重复上述过程。每次出栈时记录当前深度，取最大深度即为二叉树的深度。