[二叉树] △ 已知前序序列、中序序列 创建 二叉树(二叉链表)(严蔚敏《数据结构》6.65)

本文主要是介绍[二叉树] △ 已知前序序列、中序序列 创建 二叉树(二叉链表)(严蔚敏《数据结构》6.65),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

题目来源:严蔚敏《数据结构》C语言版本习题册 6.65

【题目】6.65
已知一棵二叉树的前序序列和中序序列分别存于两个一维数组中,试编写算法建立该二叉树的二叉链表。

【答案】

// 6.65 前序序列、中序序列-->二叉链表
BiTNode* PreInOrderToBiTree(char *prestr, char *instr, int prestart, int preend, int instart, int inend) {char e;int root,leftlen,rightlen;BiTNode *p;e=prestr[prestart];p = (BiTNode *)malloc(sizeof(BiTNode)); if (!p) exit(OVERFLOW);p->data=e;p->lchild=NULL;p->rchild=NULL;//找到e在中序中所在的位置for (root=instart; instr[root]!=e && root<=inend; root++);if (root>inend) return NULL; //出错//构建左子树leftlen = root - instart; //左子树长度if (leftlen) p->lchild = PreInOrderToBiTree(prestr, instr, prestart+1, prestart+leftlen, instart, instart+leftlen-1);//构建右子树rightlen = inend - root; //右子树长度if (rightlen) p->rchild = PreInOrderToBiTree(prestr, instr, preend-rightlen+1, preend, inend-rightlen+1, inend);return p;
}

【完整代码】

/*
@Desc:二叉链表 无头结点
@Vesrion:0.0.1
@Time:20180922创建
*/#include<stdio.h>
#include<stdlib.h>
#include<string.h>#ifndef BASE
#define BASE
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
#define OVERFLOW -2
typedef int Status;
typedef int bool;
#endif#define TElemType char //固定为char,若修改需要修改方法
typedef struct BiTNode { // 结点结构TElemType      data;struct BiTNode  *lchild, *rchild; // 左右孩子指针
}BiTNode, *BiTree;
void visit(TElemType e) {printf("%c", e);
}
#define SElemType BiTNode*
#include"SqStack.h"#define maxSize 50 //本文件中 队列、栈 最大的内容// 递归遍历
void PreOrder(BiTree T); // 先序遍历二叉树
void InOrder(BiTree T); // 中序遍历二叉树
void PostOrder(BiTree T); // 后序遍历二叉树// 6.65 前序序列、中序序列-->二叉链表
BiTNode* PreInOrderToBiTree(char *prestr, char *instr, int prestart, int preend, int instart, int inend) {char e;int root,leftlen,rightlen;BiTNode *p;e=prestr[prestart];p = (BiTNode *)malloc(sizeof(BiTNode)); if (!p) exit(OVERFLOW);p->data=e;p->lchild=NULL;p->rchild=NULL;//找到e在中序中所在的位置for (root=instart; instr[root]!=e && root<=inend; root++);if (root>inend) return NULL; //出错//构建左子树leftlen = root - instart; //左子树长度if (leftlen) p->lchild = PreInOrderToBiTree(prestr, instr, prestart+1, prestart+leftlen, instart, instart+leftlen-1);//构建右子树rightlen = inend - root; //右子树长度if (rightlen) p->rchild = PreInOrderToBiTree(prestr, instr, preend-rightlen+1, preend, inend-rightlen+1, inend);return p;
}int main() {
/* 6.65
ABCDEFHIJ
CBEFDAHJI
*/char prestr[maxSize],instr[maxSize];BiTree T;scanf("%s", prestr);scanf("%s", instr);T = PreInOrderToBiTree(prestr, instr, 0, strlen(prestr)-1, 0, strlen(instr)-1 );printf("二叉链表:\n");PreOrder(T);printf("\n");InOrder(T);printf("\n");PostOrder(T);printf("\n");return 0;
}// 先序遍历二叉树
void PreOrder(BiTree T) { // - 递归if (!T) return ;visit(T->data);PreOrder(T->lchild);PreOrder(T->rchild);
}
// 中序遍历二叉树
void InOrder(BiTree T) { // - 递归if (!T) return ;InOrder(T->lchild);visit(T->data);InOrder(T->rchild);
}
// 后序遍历二叉树
void PostOrder(BiTree T) { // - 递归if (!T) return ;PostOrder(T->lchild);PostOrder(T->rchild);visit(T->data);
}

这篇关于[二叉树] △ 已知前序序列、中序序列 创建 二叉树(二叉链表)(严蔚敏《数据结构》6.65)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/705508

相关文章

C++链表的虚拟头节点实现细节及注意事项

《C++链表的虚拟头节点实现细节及注意事项》虚拟头节点是链表操作中极为实用的设计技巧,它通过在链表真实头部前添加一个特殊节点,有效简化边界条件处理,:本文主要介绍C++链表的虚拟头节点实现细节及注... 目录C++链表虚拟头节点(Dummy Head)一、虚拟头节点的本质与核心作用1. 定义2. 核心价值二

python如何创建等差数列

《python如何创建等差数列》:本文主要介绍python如何创建等差数列的问题,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录python创建等差数列例题运行代码回车输出结果总结python创建等差数列import numpy as np x=int(in

怎么用idea创建一个SpringBoot项目

《怎么用idea创建一个SpringBoot项目》本文介绍了在IDEA中创建SpringBoot项目的步骤,包括环境准备(JDK1.8+、Maven3.2.5+)、使用SpringInitializr... 目录如何在idea中创建一个SpringBoot项目环境准备1.1打开IDEA,点击New新建一个项

如何使用Maven创建web目录结构

《如何使用Maven创建web目录结构》:本文主要介绍如何使用Maven创建web目录结构的问题,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录创建web工程第一步第二步第三步第四步第五步第六步第七步总结创建web工程第一步js通过Maven骨架创pytho

MySQL 用户创建与授权最佳实践

《MySQL用户创建与授权最佳实践》在MySQL中,用户管理和权限控制是数据库安全的重要组成部分,下面详细介绍如何在MySQL中创建用户并授予适当的权限,感兴趣的朋友跟随小编一起看看吧... 目录mysql 用户创建与授权详解一、MySQL用户管理基础1. 用户账户组成2. 查看现有用户二、创建用户1. 基

Python中使用uv创建环境及原理举例详解

《Python中使用uv创建环境及原理举例详解》uv是Astral团队开发的高性能Python工具,整合包管理、虚拟环境、Python版本控制等功能,:本文主要介绍Python中使用uv创建环境及... 目录一、uv工具简介核心特点:二、安装uv1. 通过pip安装2. 通过脚本安装验证安装:配置镜像源(可

Java中实现线程的创建和启动的方法

《Java中实现线程的创建和启动的方法》在Java中,实现线程的创建和启动是两个不同但紧密相关的概念,理解为什么要启动线程(调用start()方法)而非直接调用run()方法,是掌握多线程编程的关键,... 目录1. 线程的生命周期2. start() vs run() 的本质区别3. 为什么必须通过 st

Linux链表操作方式

《Linux链表操作方式》:本文主要介绍Linux链表操作方式,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录一、链表基础概念与内核链表优势二、内核链表结构与宏解析三、内核链表的优点四、用户态链表示例五、双向循环链表在内核中的实现优势六、典型应用场景七、调试技巧与

Macos创建python虚拟环境的详细步骤教学

《Macos创建python虚拟环境的详细步骤教学》在macOS上创建Python虚拟环境主要通过Python内置的venv模块实现,也可使用第三方工具如virtualenv,下面小编来和大家简单聊聊... 目录一、使用 python 内置 venv 模块(推荐)二、使用 virtualenv(兼容旧版 P

Linux lvm实例之如何创建一个专用于MySQL数据存储的LVM卷组

《Linuxlvm实例之如何创建一个专用于MySQL数据存储的LVM卷组》:本文主要介绍使用Linux创建一个专用于MySQL数据存储的LVM卷组的实例,具有很好的参考价值,希望对大家有所帮助,... 目录在Centos 7上创建卷China编程组并配置mysql数据目录1. 检查现有磁盘2. 创建物理卷3. 创