假设二叉树T采用如下定义的存储结构: (本题10分) typedef struct Node { DataType data; struct Node *lchild,*rchild; } *BiTree; 其中,结点的lchild域和rchild域已分别填有指向其左、右孩子结点的指针, 编写一个递归算法,计算一棵二叉树的深度。
时间: 2024-03-21 16:37:58 浏览: 16
好的,这是一道关于二叉树深度的问题。以下是递归算法的实现:
```
int getDepth(BiTree T) {
if (T == NULL) {
return 0; // 空树深度为0
} else {
int leftDepth = getDepth(T->lchild); // 左子树深度
int rightDepth = getDepth(T->rchild); // 右子树深度
return (leftDepth > rightDepth ? leftDepth : rightDepth) + 1; // 取左右子树深度的最大值加1
}
}
```
这里使用了递归的思想,首先判断树是否为空,如果为空,则深度为0;否则递归计算左子树和右子树的深度,取其最大值加1即为整棵树的深度。
相关问题
已知二叉树结点的定义如下: typedef struct Node{ DataType data; struct Node *LChild; struct Node *Rchild; }BiTNode, *BiTree; 若用二叉链表作为二叉树的存储表示,请设计代码求二叉树中度为 1 的结点个数。
好的,我会根据您的要求,使用 ChitGPT 来回答您的问题。
对于这个问题,我们可以遍历整个二叉树,统计度为 1 的节点个数。具体的实现可以使用递归来实现,遍历当前节点的左右子树,统计当前节点度为 1 的子树的数量,并加上当前节点的度数,最后返回结果即可。
以下是具体的代码实现:
```
int countSingleDegreeNodes(BiTree root) {
if (root == NULL) {
return 0;
}
int count = 0;
if (root->LChild == NULL && root->Rchild != NULL) {
count++;
} else if (root->LChild != NULL && root->Rchild == NULL) {
count++;
}
count += countSingleDegreeNodes(root->LChild);
count += countSingleDegreeNodes(root->Rchild);
return count;
}
```
在这个代码中,我们首先检查当前节点的度数,如果是 1 则增加计数器,然后递归遍历左右子树,并将它们的结果相加作为最终的结果返回。
希望这个解答对您有帮助,如果您还有其他问题,可以继续问我。
typedef struct BiTNodefElemType data ; struct BiTNode * lchild , * rchild ; BiTNode * BiTree ;
这段代码是一个二叉树的定义和声明,其中包含了一个结构体 `BiTNode` 和一个指向该结构体的指针 `BiTree`。结构体 `BiTNode` 包含了一个成员变量 `data`,用来存储节点的数据,以及两个指向左子树和右子树的指针 `lchild` 和 `rchild`。
`typedef struct BiTNodefElemType data;` 这行代码是对 `data` 的数据类型进行定义,但是你没有给出 `data` 的具体类型。如果你想要使用这段代码,需要在 `typedef` 之前定义 `data` 的数据类型。
然后,`struct BiTNode * lchild, * rchild;` 这行代码声明了两个指向 `struct BiTNode` 类型的指针,分别表示左子树和右子树。
最后,`BiTNode * BiTree;` 这行代码声明了一个指向 `struct BiTNode` 类型的指针 `BiTree`,用来表示整个二叉树的根节点。
需要注意的是,你在代码中使用了 `BiTNode *` 来声明指针变量,但是在结构体定义中使用了 `struct BiTNode *`。这可能是一个笔误,请确保在代码的其他部分中使用一致的命名。