由中序遍历和后序遍历确定先序遍历的C语言算法
时间: 2024-05-25 12:18:08 浏览: 10
1. 定义一个结构体Node,表示二叉树节点,包含val、left、right三个成员变量;
2. 定义一个函数buildTree,接收两个参数,分别是中序遍历序列inorder和后序遍历序列postorder,返回一个Node类型的指针,表示重建的二叉树的根节点;
3. 在buildTree函数中,先判断inorder和postorder的长度是否相等,如果不相等,则返回空指针NULL;
4. 然后取postorder中最后一个元素作为根节点的值,创建一个新节点,并将其赋值给根节点指针root;
5. 在inorder中查找根节点的位置,将inorder序列分为左右两个子序列,分别对应左子树和右子树;
6. 在postorder中,将左子树和右子树的节点分别提取出来,分别对应左子树和右子树的后序遍历序列;
7. 递归调用buildTree函数,重建左子树和右子树,分别将返回值赋值给root节点的left和right成员变量;
8. 最后返回root指针,表示重建的二叉树的根节点;
9. 定义一个函数preorderTraversal,接收一个Node类型的指针root,表示二叉树的根节点,输出先序遍历序列;
10. 在preorderTraversal函数中,先判断root指针是否为空,如果为空,则直接返回;
11. 输出root节点的值,然后递归调用preorderTraversal函数,输出左子树的先序遍历序列,再递归调用preorderTraversal函数,输出右子树的先序遍历序列。
相关问题
编写二叉树的递归遍历算法,给定二叉树的扩展先序遍历序列,输出二叉树的先序遍历,中序遍历和后序遍历的结点序列和叶子结点和和结点个数的c语言代码
以下是对应的 C 语言代码:
```c
#include <stdio.h>
#include <stdlib.h>
typedef struct TreeNode {
int val;
struct TreeNode* left;
struct TreeNode* right;
} TreeNode;
// 创建一棵二叉树
TreeNode* createTree(int* pos) {
char* s = "AB##C##";
char ch = s[(*pos)++];
if (ch == '#') {
return NULL;
}
TreeNode* root = (TreeNode*)malloc(sizeof(TreeNode));
root->val = ch;
root->left = createTree(pos);
root->right = createTree(pos);
return root;
}
// 先序遍历
void preOrder(TreeNode* root) {
if (root == NULL) {
return;
}
printf("%c ", root->val);
preOrder(root->left);
preOrder(root->right);
}
// 中序遍历
void inOrder(TreeNode* root) {
if (root == NULL) {
return;
}
inOrder(root->left);
printf("%c ", root->val);
inOrder(root->right);
}
// 后序遍历
void postOrder(TreeNode* root) {
if (root == NULL) {
return;
}
postOrder(root->left);
postOrder(root->right);
printf("%c ", root->val);
}
// 计算叶子结点个数
int countLeaves(TreeNode* root) {
if (root == NULL) {
return 0;
}
if (root->left == NULL && root->right == NULL) {
return 1;
}
return countLeaves(root->left) + countLeaves(root->right);
}
// 计算结点个数
int countNodes(TreeNode* root) {
if (root == NULL) {
return 0;
}
return countNodes(root->left) + countNodes(root->right) + 1;
}
int main() {
int pos = 0;
TreeNode* root = createTree(&pos);
printf("先序遍历:");
preOrder(root);
printf("\n");
printf("中序遍历:");
inOrder(root);
printf("\n");
printf("后序遍历:");
postOrder(root);
printf("\n");
printf("叶子结点个数:%d\n", countLeaves(root));
printf("结点个数:%d\n", countNodes(root));
return 0;
}
```
利用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;
}
```
在程序中,我们首先定义了二叉树的结构体,包括结点的数据域和左右子树指针。然后定义了先序遍历、中序遍历和后序遍历的函数,这些函数都是递归实现的。最后定义了创建二叉树的函数,也是递归实现的。在主函数中,我们首先输入二叉树的先序遍历序列,然后调用创建二叉树的函数创建二叉树,最后分别调用先序遍历、中序遍历和后序遍历的函数输出遍历结果。