将字符串的内容转换为一棵二叉树

2024-06-18 23:58

本文主要是介绍将字符串的内容转换为一棵二叉树,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

问题:从控制台中输入一串“A(B(C,D(,E)),F(G,H(M,N(,Q))))“,将其转化建立一棵二叉树。
从这个问题我们可以知道,首先我们需要将这个字符串所表示的二叉树用代码的方式建立起来。我们先来看看这个字符串所表示的二叉树:
在这里插入图片描述
下面我们开始分析这个二叉树建立的思路:
(1)读取第一个字符建立第一个节点即为根节点;
(2)继续读取下一个字符,如果遇到“(”,那么当前节点为父节点,并且下一个节点为左孩子(左节点);如果遇到“,”那么下一个节点即为右孩子(右节点);
我们可以借助一个栈来存放所有的父节点(即为有左孩子或者右孩子的节点),依次来构建我们的二叉树,下面给出我们的具体的实现代码:
这里的节点类是一个类的模板,适合存取基本的数据类型或者我们自定义的类型,也就是所有的类型都可以存储,这是为了实现节点存储的通用性:

#pragma once
template<class T>
class BNode
{
public:BNode();BNode(T t);~BNode();public:/*左孩子*/BNode<T> *leftChild;/*右孩子*/BNode<T> *rightChild;/*j节点的值*/T t;};template<class T>
inline BNode<T>::BNode()
{
}template<class T>
inline BNode<T>::BNode(T t)
{this->t = t;
}template<class T>
inline BNode<T>::~BNode()
{
}

当然,如果你想简单点的实现的话,可以直接就定义个结构体:

struct LNode
{char  value;LNode* rightChild;LNode* leftChild;
};

这样也是可以的,这样比较简单。解决该问题我们就选择简单的实现吧,就使用

```cpp
struct TNode
{//节点的值char  value;//指向左孩子的指针TNode* rightChild;//指向右孩子的指针TNode* leftChild;
};

下面是开始建立二叉树并返回二叉树的根节点:

//根据嵌套括号表示法的字符串生成链式存储的二叉树
TNode*  CreateTreeNode(const char* str)
{char ch;Stack<TNode*> *stack = new Stack<TNode*>();TNode* root = NULL;TNode  *p = NULL;int  k, j = 0;  //k决定谁是左、右孩子、j为str指针while ((ch = str[j++]) != '\0'){switch (ch){case '(':stack->push(p);           //根节点入栈 k = 1;                    //1为左孩子 break;case ',':k = 2;                   //2为右孩子 break;case ')':stack->pop();                  //父节点出栈 break;default://创建一个节点p = new TNode();//给节点赋值p->value = ch;if (root == NULL)        //树为空时 {root = p;}else                   //树非空时 {switch (k){case 1:stack->getTop()->leftChild = p;           //父节点的左孩子 break;case 2:stack->getTop()->rightChild = p;          //父节点的右孩子 break;}}break;}}return root;
}

为了便于理解,下面我会用图解的方式来展示二叉树的建立过程:
第一步相当于:
在这里插入图片描述
第二步:
遇到“(”,则父节点入栈,此时p仍是为指向A的这个节点,而k更新为 k=1;
在这里插入图片描述
第三步:
在这里插入图片描述
此时节点A的左节点为B,k=1;
第四步:
)
此时p指向B节点,k=1,B节点入栈;
第五步:
在这里插入图片描述
此时p指向C节点,k=1;
第六步:
在这里插入图片描述
此时p指向c节点,k=2;
第七步:
在这里插入图片描述
此时p指向D节点,k=2;
第八步:
在这里插入图片描述
此时p指向D节点,k=1,父节点D入栈;
第九步:
在这里插入图片描述
此时p指向D节点,k = 2;
第十步:
在这里插入图片描述
此时p指向E节点,k = 2;
第十一步:
在这里插入图片描述
此时p指向E节点,k = 2,栈弹出节点D元素;
第十二步:
在这里插入图片描述
此时p指向E节点,k = 2,栈弹出节点B元素;
第十三步:
在这里插入图片描述
此时p指向E节点,k = 2,栈弹出节点B元素;
之后重复以上步骤一直到结束。。。。。。
最终的p ==NULL 和stack栈为空;
到此,我们就建好了一棵二叉树,下面为了检验,我们开始进行调试,笔者这里采用了代码简单的前序遍历递归的方式:


```cpp
void PrintTree(TNode* root)
{if (root == NULL){return;}cout << root->value;PrintTree(root->leftChild);PrintTree(root->rightChild);}

下面是main函数的执行:```cpp
int main()
{const char* p = "A(B(C,D(,E)),F(G,H(M,N(,Q))))";PrintTree(CreateTreeNode(p));system("pause");return 0;
}

输出为:
在这里插入图片描述
至此结束!!!!!

这篇关于将字符串的内容转换为一棵二叉树的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!


原文地址:
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.chinasem.cn/article/1073430

相关文章

详解MySQL中JSON数据类型用法及与传统JSON字符串对比

《详解MySQL中JSON数据类型用法及与传统JSON字符串对比》MySQL从5.7版本开始引入了JSON数据类型,专门用于存储JSON格式的数据,本文将为大家简单介绍一下MySQL中JSON数据类型... 目录前言基本用法jsON数据类型 vs 传统JSON字符串1. 存储方式2. 查询方式对比3. 索引

linux批量替换文件内容的实现方式

《linux批量替换文件内容的实现方式》本文总结了Linux中批量替换文件内容的几种方法,包括使用sed替换文件夹内所有文件、单个文件内容及逐行字符串,强调使用反引号和绝对路径,并分享个人经验供参考... 目录一、linux批量替换文件内容 二、替换文件内所有匹配的字符串 三、替换每一行中全部str1为st

从入门到精通详解LangChain加载HTML内容的全攻略

《从入门到精通详解LangChain加载HTML内容的全攻略》这篇文章主要为大家详细介绍了如何用LangChain优雅地处理HTML内容,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编一起学习一下... 目录引言:当大语言模型遇见html一、HTML加载器为什么需要专门的HTML加载器核心加载器对比表二

MySQL字符串常用函数详解

《MySQL字符串常用函数详解》本文给大家介绍MySQL字符串常用函数,本文结合实例代码给大家介绍的非常详细,对大家学习或工作具有一定的参考借鉴价值,需要的朋友参考下吧... 目录mysql字符串常用函数一、获取二、大小写转换三、拼接四、截取五、比较、反转、替换六、去空白、填充MySQL字符串常用函数一、

Kotlin Map映射转换问题小结

《KotlinMap映射转换问题小结》文章介绍了Kotlin集合转换的多种方法,包括map(一对一转换)、mapIndexed(带索引)、mapNotNull(过滤null)、mapKeys/map... 目录Kotlin 集合转换:map、mapIndexed、mapNotNull、mapKeys、map

Python中反转字符串的常见方法小结

《Python中反转字符串的常见方法小结》在Python中,字符串对象没有内置的反转方法,然而,在实际开发中,我们经常会遇到需要反转字符串的场景,比如处理回文字符串、文本加密等,因此,掌握如何在Pyt... 目录python中反转字符串的方法技术背景实现步骤1. 使用切片2. 使用 reversed() 函

MySQL查询JSON数组字段包含特定字符串的方法

《MySQL查询JSON数组字段包含特定字符串的方法》在MySQL数据库中,当某个字段存储的是JSON数组,需要查询数组中包含特定字符串的记录时传统的LIKE语句无法直接使用,下面小编就为大家介绍两种... 目录问题背景解决方案对比1. 精确匹配方案(推荐)2. 模糊匹配方案参数化查询示例使用场景建议性能优

关于集合与数组转换实现方法

《关于集合与数组转换实现方法》:本文主要介绍关于集合与数组转换实现方法,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录1、Arrays.asList()1.1、方法作用1.2、内部实现1.3、修改元素的影响1.4、注意事项2、list.toArray()2.1、方

MySQL 获取字符串长度及注意事项

《MySQL获取字符串长度及注意事项》本文通过实例代码给大家介绍MySQL获取字符串长度及注意事项,本文通过实例代码给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的朋友参考下吧... 目录mysql 获取字符串长度详解 核心长度函数对比⚠️ 六大关键注意事项1. 字符编码决定字节长度2

利用Python脚本实现批量将图片转换为WebP格式

《利用Python脚本实现批量将图片转换为WebP格式》Python语言的简洁语法和库支持使其成为图像处理的理想选择,本文将介绍如何利用Python实现批量将图片转换为WebP格式的脚本,WebP作为... 目录简介1. python在图像处理中的应用2. WebP格式的原理和优势2.1 WebP格式与传统