构建如下图二叉树,要求使用括号表示法输入二叉树并转化为二叉树的链式存储结构;横向输出二叉树;求二叉树的高度;统计二叉树中的节点个数;中序遍历该二叉树(采用递归算法);层序遍历该二叉树;
时间: 2023-11-14 13:12:48 浏览: 276
设二叉树采用链式存储结构,试设计一个算法计算一颗给定二叉树叶子节点的数目
5星 · 资源好评率100%
对于这个问题,我可以给你提供以下的信息和代码示例:
1. 二叉树的括号表示法:使用一对括号表示一个节点,其中左括号后面跟着节点的值,右括号前面跟着节点的值,如果一个节点为null,则用"()"表示。例如,下面的二叉树:
1
/ \
2 3
/ \
4 5
用括号表示法可以表示为:`(1(2()())(3(4()())(5()())))`
2. 二叉树的链式存储结构:可以使用结构体定义节点,其中包含指向左右子节点的指针。例如:
```c
struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
};
```
3. 二叉树横向输出:可以使用递归实现,每层节点先输出右子树,再输出当前节点,最后输出左子树。例如:
```c
void printTree(struct TreeNode* root, int depth) {
if (root == NULL) return;
printTree(root->right, depth+1);
for (int i = 0; i < depth; i++) {
printf(" ");
}
printf("%d\n", root->val);
printTree(root->left, depth+1);
}
```
4. 二叉树高度:可以使用递归实现,分别计算左右子树的高度,取最大值加1。例如:
```c
int treeHeight(struct TreeNode* root) {
if (root == NULL) return 0;
int leftHeight = treeHeight(root->left);
int rightHeight = treeHeight(root->right);
return (leftHeight > rightHeight ? leftHeight : rightHeight) + 1;
}
```
5. 二叉树节点个数:可以使用递归实现,分别计算左右子树的节点个数,加上当前节点。例如:
```c
int countNodes(struct TreeNode* root) {
if (root == NULL) return 0;
int leftNodes = countNodes(root->left);
int rightNodes = countNodes(root->right);
return leftNodes + rightNodes + 1;
}
```
6. 中序遍历:可以使用递归实现,先遍历左子树,再访问当前节点,最后遍历右子树。例如:
```c
void inorderTraversal(struct TreeNode* root) {
if (root == NULL) return;
inorderTraversal(root->left);
printf("%d ", root->val);
inorderTraversal(root->right);
}
```
7. 层序遍历:可以使用队列实现,先将根节点入队,然后每次取出队头节点,访问它,再将它的左右子节点入队。例如:
```c
void levelOrderTraversal(struct TreeNode* root) {
if (root == NULL) return;
struct TreeNode* queue[1000];
int front = 0, rear = 0;
queue[rear++] = root;
while (front != rear) {
struct TreeNode* node = queue[front++];
printf("%d ", node->val);
if (node->left != NULL) queue[rear++] = node->left;
if (node->right != NULL) queue[rear++] = node->right;
}
}
```
以上就是我提供的一些关于二叉树的信息和代码示例,希望能对你有所帮助。
阅读全文