C语言如何实现以前序和中序遍历确定一颗二叉树
时间: 2024-06-01 17:14:04 浏览: 15
C语言实现以前序和中序遍历确定一颗二叉树的方法是,先根据前序遍历的第一个节点确定根节点,然后在中序遍历序列中找到根节点的位置,根据根节点的位置可以将中序遍历序列分为左子树和右子树两个部分。然后根据左子树和右子树的节点数量,在前序遍历序列中找到左子树和右子树的对应位置。这样就可以递归的构建出整棵二叉树。
相关问题
利用C语言实现利用二叉树创建、遍历算法,编写程序,创建一颗二叉树,实现对二叉树的先序遍历、中序遍历和后序遍历的。
以下是利用C语言实现二叉树创建、遍历算法的程序,包括创建二叉树、先序遍历、中序遍历和后序遍历:
```c
#include <stdio.h>
#include <stdlib.h>
// 定义二叉树结构体
typedef struct BiTNode {
char data;
struct BiTNode *lchild, *rchild;
} BiTNode, *BiTree;
// 先序遍历
void preOrder(BiTree T) {
if (T != NULL) {
printf("%c ", T->data);
preOrder(T->lchild);
preOrder(T->rchild);
}
}
// 中序遍历
void inOrder(BiTree T) {
if (T != NULL) {
inOrder(T->lchild);
printf("%c ", T->data);
inOrder(T->rchild);
}
}
// 后序遍历
void lastOrder(BiTree T) {
if (T != NULL) {
lastOrder(T->lchild);
lastOrder(T->rchild);
printf("%c ", T->data);
}
}
// 创建二叉树
void createBiTree(BiTree *T) {
char ch;
scanf("%c", &ch);
if (ch == '#') {
*T = NULL;
} else {
*T = (BiTree)malloc(sizeof(BiTNode));
(*T)->data = ch;
createBiTree(&((*T)->lchild));
createBiTree(&((*T)->rchild));
}
}
int main() {
BiTree T;
printf("请输入二叉树的先序遍历序列(#表示空结点):\n");
createBiTree(&T);
printf("先序遍历结果为:");
preOrder(T);
printf("\n中序遍历结果为:");
inOrder(T);
printf("\n后序遍历结果为:");
lastOrder(T);
printf("\n");
return 0;
}
```
在程序中,我们首先定义了二叉树的结构体,包括结点的数据域和左右子树指针。然后定义了先序遍历、中序遍历和后序遍历的函数,这些函数都是递归实现的。最后定义了创建二叉树的函数,也是递归实现的。在主函数中,我们首先输入二叉树的先序遍历序列,然后调用创建二叉树的函数创建二叉树,最后分别调用先序遍历、中序遍历和后序遍历的函数输出遍历结果。
输入一颗二叉树的先序和中序遍历序列,输出其后序遍历序列,C语言
以下是一种C语言实现方式:
```c
#include <stdio.h>
#include <stdlib.h>
#define MAX_SIZE 100
// 定义二叉树结点结构体
typedef struct TreeNode {
char val;
struct TreeNode* left;
struct TreeNode* right;
} TreeNode;
// 根据先序和中序遍历序列构建二叉树
TreeNode* buildTree(char* preorder, char* inorder, int size) {
if (size == 0) {
return NULL;
}
// 从先序遍历序列中取出根节点的值
char root_val = *preorder;
// 在中序遍历序列中查找根节点的值
int root_index;
for (root_index = 0; root_index < size; root_index++) {
if (*(inorder + root_index) == root_val) {
break;
}
}
// 创建根节点
TreeNode* root = malloc(sizeof(TreeNode));
root->val = root_val;
// 递归构建左子树
root->left = buildTree(preorder + 1, inorder, root_index);
// 递归构建右子树
root->right = buildTree(preorder + root_index + 1, inorder + root_index + 1, size - root_index - 1);
return root;
}
// 后序遍历二叉树
void postorderTraversal(TreeNode* root) {
if (root == NULL) {
return;
}
postorderTraversal(root->left);
postorderTraversal(root->right);
printf("%c ", root->val);
}
int main() {
char preorder[MAX_SIZE] = {'A', 'B', 'D', 'E', 'C', 'F'};
char inorder[MAX_SIZE] = {'D', 'B', 'E', 'A', 'F', 'C'};
int size = 6;
TreeNode* root = buildTree(preorder, inorder, size);
postorderTraversal(root);
return 0;
}
```
在这个程序中,我们首先定义了一个 `TreeNode` 结构体,用来表示二叉树的结点。然后定义了一个 `buildTree` 函数,用来根据先序和中序遍历序列构建二叉树。最后定义了一个 `postorderTraversal` 函数,用来后序遍历二叉树。在 `main` 函数中,我们使用给定的先序和中序遍历序列构建二叉树,并输出后序遍历序列。