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

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

问题：从控制台中输入一串“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;
}

输出为：

至此结束！！！！！

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

---