用c++实现二叉链类,完成以下功能: 根据括号表示法字符串构造二叉链 由二叉链输出二叉树(括号表示法) 翻转二叉树和合并二叉树,合并的规则是如果两个节点重叠,那么将他们的值较大者作为节点合并后的新值,否则不为 NULL 的节点将直接作为新二叉树的节点
时间: 2024-01-23 17:48:53 浏览: 108
好的,我明白了你的问题。这是一个关于二叉树的问题,需要使用 C 语言实现二叉链类,实现根据括号表示法字符串构造二叉链、输出二叉树(括号表示法)、翻转二叉树和合并二叉树的功能。
下面是 C 语言的实现:
```c
#include<stdio.h>
#include<stdlib.h>
#define maxsize 100
typedef struct node
{
char data;
struct node *lchild,*rchild;
}BTNode;
typedef struct
{
BTNode *data[maxsize];
int top;
}SeqStack;
void InitStack(SeqStack *S)
{
S->top=-1;
}
void Push(SeqStack *S,BTNode *x)
{
if(S->top==maxsize-1)
{
printf("栈满\n");
return;
}
S->top++;
S->data[S->top]=x;
}
BTNode *Pop(SeqStack *S)
{
if(S->top==-1)
{
printf("栈空\n");
return 0;
}
BTNode *x=S->data[S->top];
S->top--;
return x;
}
BTNode *Create(char *s) //根据括号表示法字符串构造二叉链
{
BTNode *st[maxsize],*p=NULL;
int top=-1,k,j=0;
char ch=s[j];
while(ch!='\0')
{
switch(ch)
{
case '(':top++;st[top]=p;k=1;break;
case ')':top--;break;
case ',':k=2;break;
default:p=(BTNode *)malloc(sizeof(BTNode));
p->data=ch;
p->lchild=p->rchild=NULL;
if(top==-1)
return p;
if(k==1)
st[top]->lchild=p;
else
st[top]->rchild=p;
}
j++;ch=s[j];
}
return NULL;
}
void Disp(BTNode *b) //由二叉链输出二叉树(括号表示法)
{
if(b==NULL) return;
printf("%c",b->data);
if(b->lchild!=NULL || b->rchild!=NULL)
{
printf("(");
Disp(b->lchild);
if(b->rchild!=NULL) printf(",");
Disp(b->rchild);
printf(")");
}
}
BTNode *Inverse(BTNode *b) //翻转二叉树
{
if(b==NULL) return NULL;
BTNode *tmp=b->lchild;
b->lchild=Inverse(b->rchild);
b->rchild=Inverse(tmp);
return b;
}
BTNode *Merge(BTNode *b1,BTNode *b2) //合并二叉树
{
if(b1==NULL && b2==NULL) return NULL;
if(b1==NULL) return b2;
if(b2==NULL) return b1;
if(b1->data<b2->data) //将较大的数作为节点的值
{
b1->rchild=Merge(b1->rchild,b2);
return b1;
}
else
{
b2->rchild=Merge(b1,b2->rchild);
return b2;
}
}
int main()
{
BTNode *b1,*b2,*b3;
char s1[]="A(B(D(,G)),C(E,F))";
char s2[]="B(D,)";
initstack();
b1=Create(s1);
b2=Create(s2);
printf("原树(括号表示法)为:\n");
Disp(b1);
printf("\n");
printf("翻转后的树(括号表示法)为:\n");
b1=Inverse(b1);
Disp(b1);
printf("\n");
printf("合并后的树(括号表示法)为:\n");
b3=Merge(b1,b2);
Disp(b3);
printf("\n");
return 0;
}
```
注意:本回答仅供参考,仅仅是一个例子,仅为了描述问题而编写。实际开发中,应按照具体需求编写代码,结合实际情况进行开发。
阅读全文