用c语言建立二叉树,按先序中序后序遍历二叉树
时间: 2023-10-17 12:17:49 浏览: 34
以下是一个简单的用 C 语言实现二叉树,并按照先序、中序、后序遍历的代码:
```c
#include <stdio.h>
#include <stdlib.h>
struct TreeNode {
int val;
struct TreeNode* left;
struct TreeNode* right;
};
struct TreeNode* createNode(int val) {
struct TreeNode* node = (struct TreeNode*)malloc(sizeof(struct TreeNode));
node->val = val;
node->left = NULL;
node->right = NULL;
return node;
}
struct TreeNode* buildTree(int* preorder, int preorderSize, int* inorder, int inorderSize) {
if (preorderSize == 0 || inorderSize == 0) {
return NULL;
}
int rootVal = preorder[0];
struct TreeNode* root = createNode(rootVal);
int rootIndex = 0;
for (int i = 0; i < inorderSize; i++) {
if (inorder[i] == rootVal) {
rootIndex = i;
break;
}
}
root->left = buildTree(preorder + 1, rootIndex, inorder, rootIndex);
root->right = buildTree(preorder + 1 + rootIndex, inorderSize - rootIndex - 1, inorder + rootIndex + 1, inorderSize - rootIndex - 1);
return root;
}
void preorderTraversal(struct TreeNode* root) {
if (root == NULL) {
return;
}
printf("%d ", root->val);
preorderTraversal(root->left);
preorderTraversal(root->right);
}
void inorderTraversal(struct TreeNode* root) {
if (root == NULL) {
return;
}
inorderTraversal(root->left);
printf("%d ", root->val);
inorderTraversal(root->right);
}
void postorderTraversal(struct TreeNode* root) {
if (root == NULL) {
return;
}
postorderTraversal(root->left);
postorderTraversal(root->right);
printf("%d ", root->val);
}
int main() {
int preorder[] = {1, 2, 4, 5, 3};
int inorder[] = {4, 2, 5, 1, 3};
int size = sizeof(preorder) / sizeof(preorder[0]);
struct TreeNode* root = buildTree(preorder, size, inorder, size);
printf("Preorder traversal: ");
preorderTraversal(root);
printf("\n");
printf("Inorder traversal: ");
inorderTraversal(root);
printf("\n");
printf("Postorder traversal: ");
postorderTraversal(root);
printf("\n");
return 0;
}
```
该代码中,`struct TreeNode` 定义了二叉树节点的结构体。`createNode` 函数用于创建新节点。`buildTree` 函数用于根据先序遍历和中序遍历的结果构建二叉树。`preorderTraversal`、`inorderTraversal` 和 `postorderTraversal` 函数分别用于按照先序、中序和后序遍历二叉树,并输出遍历结果。在 `main` 函数中,我们定义了一个先序遍历和中序遍历的示例,然后构建二叉树并按照三种遍历方式输出结果。