利用二叉链从储方式建立一棵二叉树,转向(逆时针转向90°),输出二叉树,输出先序、中序和后序遍历序列,并输出度为一的内节点个数(c语言编写代码)
时间: 2024-12-15 09:24:47 浏览: 11
先序中序后序三种方法遍历一棵二叉树
5星 · 资源好评率100%
在C语言中,我们可以利用二叉链表存储二叉树的数据结构,然后通过迭代的方式实现二叉树的转向操作以及遍历。这里是一个简化的示例,首先创建二叉树,然后转向并遍历:
```c
#include <stdio.h>
#include <stdlib.h>
typedef struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
struct TreeNode *next; // 存储下个节点的指针,用于实现双向链表
} TreeNode;
// 创建一个新的二叉树节点
TreeNode* createNode(int val) {
TreeNode* node = (TreeNode*)malloc(sizeof(TreeNode));
node->val = val;
node->left = NULL;
node->right = NULL;
node->next = NULL;
return node;
}
// 向左转操作
void rotateLeft(TreeNode** root) {
if (*root == NULL || (*root)->left == NULL)
return;
TreeNode* pivot = (*root)->left;
(*root)->left = pivot->right;
if ((*root)->left != NULL)
(*root)->left->next = *root;
pivot->right = *root;
pivot->next = (*root)->left;
*root = pivot;
}
// 先序遍历
void preOrderTraversal(TreeNode* root) {
if (root != NULL) {
printf("%d ", root->val);
preOrderTraversal(root->left);
preOrderTraversal(root->right);
}
}
// 中序遍历
void inOrderTraversal(TreeNode* root) {
if (root != NULL) {
inOrderTraversal(root->left);
printf("%d ", root->val);
inOrderTraversal(root->right);
}
}
// 后序遍历
void postOrderTraversal(TreeNode* root) {
if (root != NULL) {
postOrderTraversal(root->left);
postOrderTraversal(root->right);
printf("%d ", root->val);
}
}
// 计算度为一的内节点个数
int countNodesWithDegreeOne(TreeNode* root) {
int count = 0;
while (root != NULL) {
if (root->left == NULL && root->right == NULL)
count++;
root = root->next;
}
return count;
}
int main() {
// 假设已经构建好了一个二叉链表示的树
TreeNode* root = ...; // 实际上需要在这里填充实际的二叉链表节点
// 转向90度(这里只做一次左旋)
rotateLeft(&root);
// 输出遍历结果
printf("Preorder traversal: ");
preOrderTraversal(root);
printf("\nInorder traversal: ");
inOrderTraversal(root);
printf("\nPostorder traversal: ");
postOrderTraversal(root);
printf("\nNumber of nodes with degree one: %d\n", countNodesWithDegreeOne(root));
return 0;
}
```
请注意,这只是一个简化版的例子,实际应用中你需要根据具体的二叉链表示形式来调整上述函数。同时,为了完整地创建二叉链,你需要提供一个完整的树构建函数或者直接初始化`root`节点。
阅读全文