通过字符串（括号表示法）创建一个二叉树（C语言实现）_括号表示法创建二叉树

通过字符串（括号表示法）创建一个二叉树（C语言实现）

写在前面：该篇文章参考文献：数据结构教程（第五版） 李春葆 主编

实现步骤

假设采用括号表示法表示的二叉树字符串str是正确的，用ch 扫描str，其中只有四类字符，其处理如下。

• 单个字符：结点的值
• （：表示一棵子树的开始
• ）：表示一棵子树的结束
• ，：表示一棵右子树的开始

算法设计

• 先构造根结点N，再构造左子树L,最后构造右子树R
• 构造右子树R时，找不到N了，所以需要保存N
• 而括号（子树）是按照最近原则匹配的，所以使用一个栈保存N

ch扫描采用括号表示法表示二叉树的字符串：
A(B(D(,G)),C(E,F))

1. 若ch=’(’：表示前面刚创建的结点p存在孩子结点，需要将其进栈作为栈顶结点，并置空k=1，表示开始处理左孩子结点；
2. 若ch=’)’：表示栈顶结点的左右孩子结点处理完毕，退栈；
3. 若ch=’，’：表示开始处理右孩子结点，置k=2；
4. 其他情况（结点值）：
   创建p结点用于存放ch
   当k=1时，将p作为栈顶元素的左孩子结点；
   当k=2时，将p作为栈顶元素的右孩子结点；

源代码

头文件 btree.h

#pragma once
typedef char ElemType;

typedef struct node {
   
	ElemType data;		//数据元素
	struct node *lchild;	//指向左孩子的结点
	struct node *rchild;	//指向右孩子的结点
}BTNode;
1
2
3
4
5
6
7
8
9

函数实现 btree.cpp

#include<iostream>
#define MaxSize 20   //最大结点数
#include"btree.h"

void CreateBTree(BTNode *&b, char *str)
{
   
	BTNode *St[MaxSize], *p;   //St数组作为顺序栈，保存双亲结点
	int top = -1, k,</
1
2
3
4
5
6
7
8