能否提供一个C语言实现的二叉树链式存储结构的示例代码,包括其创建、插入节点、以及前序、中序和后序遍历方法?此外,还请展示如何分别输出所有叶子结点和分支结点,以及计算并输出该二叉树的高度?
时间: 2024-12-02 07:20:56 浏览: 34
在C语言中,我们可以使用结构体来表示二叉树的节点,并通过链式存储结构实现。以下是一个简单的二叉树链式存储的示例代码:
```c
#include <stdio.h>
#include <stdlib.h>
// 定义二叉树节点结构体
typedef struct TreeNode {
int data;
struct TreeNode* left;
struct TreeNode* right;
} TreeNode;
// 创建新节点
TreeNode* createNode(int value) {
TreeNode* newNode = (TreeNode*)malloc(sizeof(TreeNode));
newNode->data = value;
newNode->left = NULL;
newNode->right = NULL;
return newNode;
}
// 插入节点到二叉搜索树
void insert(TreeNode** root, int value) {
if (*root == NULL) {
*root = createNode(value);
} else if (value < (*root)->data) {
insert(&(*root)->left, value);
} else {
insert(&(*root)->right, value);
}
}
// 前序遍历
void preOrderTraversal(TreeNode* node) {
if (node != NULL) {
printf("%d ", node->data);
preOrderTraversal(node->left);
preOrderTraversal(node->right);
}
}
// 中序遍历
void inOrderTraversal(TreeNode* node) {
if (node != NULL) {
inOrderTraversal(node->left);
printf("%d ", node->data);
inOrderTraversal(node->right);
}
}
// 后序遍历
void postOrderTraversal(TreeNode* node) {
if (node != NULL) {
postOrderTraversal(node->left);
postOrderTraversal(node->right);
printf("%d ", node->data);
}
}
// 打印叶子节点
void printLeaves(TreeNode* node) {
if (node != NULL) {
if (node->left == NULL && node->right == NULL) {
printf("%d ", node->data);
}
printLeaves(node->left);
printLeaves(node->right);
}
}
// 计算并打印分支节点
void printBranches(TreeNode* node) {
if (node != NULL) {
printf("%d ", node->data);
printBranches(node->left);
printBranches(node->right);
}
}
// 计算二叉树高度
int height(TreeNode* node) {
if (node == NULL) {
return 0;
} else {
int leftHeight = height(node->left);
int rightHeight = height(node->right);
return (leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1);
}
}
int main() {
TreeNode* root = NULL;
// 插入一些节点
insert(&root, 50);
insert(&root, 30);
insert(&root, 20);
insert(&root, 40);
insert(&root, 70);
insert(&root, 60);
insert(&root, 80);
// 遍历和打印结果
printf("Preorder traversal: ");
preOrderTraversal(root);
printf("\n");
printf("Inorder traversal: ");
inOrderTraversal(root);
printf("\n");
printf("Postorder traversal: ");
postOrderTraversal(root);
printf("\n");
printf("Leaf nodes: ");
printLeaves(root);
printf("\n");
printf("Branch nodes: ");
printBranches(root);
printf("\n");
printf("Tree height: %d\n", height(root));
return 0;
}
```
在这个例子中,我们首先创建了一个二叉搜索树,然后演示了如何进行前序、中序和后序遍历。接着,我们展示了如何找出所有的叶节点和分支节点,以及计算二叉树的高度。
阅读全文