给定一棵用二叉链表表示的二叉树,其根指针为 root,试写出求二叉树结点的数的算法
时间: 2023-06-12 22:01:54 浏览: 70
好的,下面是求二叉树结点个数的算法:
1. 如果二叉树为空,则结点个数为0,直接返回。
2. 分别递归计算左右子树的结点个数,记为leftCount和rightCount。
3. 结点个数为左右子树的结点个数之和再加1(根结点)。
4. 返回结点个数。
实现代码如下(采用递归方式):
```python
def countNodes(root):
if root is None:
return 0
leftCount = countNodes(root.left)
rightCount = countNodes(root.right)
return leftCount + rightCount + 1
```
希望能够帮到您!
相关问题
给定一棵用二叉链表表示的二叉树,其根指针为 root,试写出求二叉树结点的数的算法。
当您输入 "给定一棵用二叉链表表示的二叉树,其根指针为 root,试写出求二叉树结点的数的算法。" 时,我的ChitGPT AI将给予以下回答:
可以使用递归的方式来求解二叉树结点的数。具体地,对于一棵二叉树,其结点数等于其左子树的结点数加上右子树的结点数再加上1(根结点)。
因此,可以定义一个递归函数countNodes,以某个结点为根的子树作为参数,返回该子树中的结点数。具体实现方式如下:
int countNodes(struct TreeNode* root) {
if (root == NULL) {
return 0;
}
return countNodes(root->left) + countNodes(root->right) + 1;
}
其中,当给出的子树为空时,其结点数为0;否则,使用递归计算其左子树和右子树的结点数,并相加1(根结点数),即可得到该子树的结点数。
希望以上回答能够帮助您。
设二叉树为以二叉链表为存储结构,且树中结点的关键字均不同。用c语言编写算法,判别给定二叉树是否为二叉排序树
可以使用中序遍历二叉树,将遍历结果存储在一个数组中,然后判断数组是否为升序排列即可。
具体实现代码如下:
```c
#include <stdio.h>
#include <stdlib.h>
// 二叉树结点定义
typedef struct node {
int data; // 结点数据
struct node *left; // 左子树指针
struct node *right; // 右子树指针
} Node;
// 中序遍历二叉树,将结果存储在数组中
void inorder(Node *root, int arr[], int *index) {
if (root == NULL) {
return;
}
inorder(root->left, arr, index);
arr[(*index)++] = root->data;
inorder(root->right, arr, index);
}
// 判断数组是否为升序排列
int isSorted(int arr[], int n) {
for (int i = 0; i < n - 1; i++) {
if (arr[i] > arr[i+1]) {
return 0;
}
}
return 1;
}
// 判断给定二叉树是否为二叉排序树
int isBST(Node *root) {
int arr[100]; // 存储中序遍历结果的数组
int index = 0; // 数组下标
inorder(root, arr, &index);
return isSorted(arr, index);
}
// 创建二叉树结点
Node* createNode(int data) {
Node *node = (Node*) malloc(sizeof(Node));
node->data = data;
node->left = NULL;
node->right = NULL;
return node;
}
int main() {
// 创建二叉排序树
Node *root = createNode(4);
root->left = createNode(2);
root->left->left = createNode(1);
root->left->right = createNode(3);
root->right = createNode(6);
root->right->left = createNode(5);
root->right->right = createNode(7);
// 判断是否为二叉排序树
if (isBST(root)) {
printf("给定二叉树是二叉排序树\n");
} else {
printf("给定二叉树不是二叉排序树\n");
}
return 0;
}
```
输出结果:
```
给定二叉树是二叉排序树
```