2023.4.14二叉树PTA做题_数据结构pta6-4 括号表示法创建二叉树

一，括号表示法构造二叉树

1.题目

本题要求使用括号表示法构造二叉树，并先序遍历输出二叉树。写出CreateBTNodePre函数。

如：括号表示法: A ( B ( D , F ( E , ) ) , C ( G ( , H ) , I ) )

构造的二叉树如下：
则先序遍历二叉树为：A B D F E C G H I
二叉树结构定义如下：

typedef char ElemType;
typedef struct node
{
    ElemType data;                //数据元素
    struct node *lchild;        //指向左孩子
    struct node *rchild;        //指向右孩子
} BTNode;

1
2
3
4
5
6
7
8

函数接口定义：

void CreateBTNodePre(BTNode *&b,char *str); //根据括号表示法的str，创建二叉树b,并先序输出二叉树。

1
2

注意：输出遍历序列时，每个结点字符之后均有空格符。

裁判测试程序样例：

#include <stdio.h>
#include <malloc.h>
#define MaxSize 100
typedef char ElemType;
typedef struct node
{
    ElemType data;                //数据元素
    struct node *lchild;        //指向左孩子
    struct node *rchild;        //指向右孩子
} BTNode;
void CreateBTNodePre(BTNode *&b,char *str); //根据括号表示法的str，创建二叉树b，并先序输出二叉树。

int main()
{    BTNode *b;
    char str[100];
    scanf("%s",str);  
    CreateBTNodePre(b,str);  //括号表示法创建二叉树 ,并先序输出二叉树。
    return 0;
}
void CreateBTNodePre(BTNode *&b,char *str)        //由str串创建二叉树，并先序输出二叉树。
{

/* 请在这里填写答案 ，写出函数体实现代码*/

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

2.算法思路

  
  假设采用括号表示法存储的二叉树字符串str是正确的，用ch扫描str，只有四类情况

• 结点的值
• （：当前指针指向它的左孩子
• ）：当前指针指向它的父亲
• ，表示当前指针指向它的右孩子
    
    通过创建数组栈来存放该分支的亲代，通过先序遍历算法处理左右分支，新建节点作为栈顶结点的左右孩子创立二叉树，最后先序输出该二叉树。

3.源码

BTNode*chr[10],*p;//创建顺序栈
int top=-1,k,j=0;//top作为栈顶指针
char ch;
b=NULL;
ch=str[0];
for(;ch!='\0';)//遍历str中的每个字符
{
    switch(ch)
    {
            case'(':top++;chr[top]=p;k=1;break;//处理左孩子节点
            case')':top--;break;//返回栈顶的父亲节点
            case',':k=2;break;//开始处理右孩子节点
        default:p=(BTNode*)malloc(sizeof(BTNode));//创建一个节点，由p指向它
            p->data=ch; // 存放节点值
            p->lchild=p->rchild=NULL;
            if(b==NULL) //如果没有根节点，直接入
                b=p;
            else {
                if(k==1)chr[top]->lchild=p;//作为左孩子
                else if(k==2) chr[top]->rchild=p;//作为右孩子
            } 
    }
    j++;
    ch=str[j];
}
for(int n=0;str[n]!='\0';n++)//先序输出二叉树
{
    if(str[n]!='('&&str[n]!=')'&&str[n]!=',')printf("%c ",str[n]);//这里记得不能限制str中的字符全为大写，有测试点
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29