假设二叉树中每个结点的值为单个字符， 设计一个算法将一棵以二叉链方式存储的二叉树 b 转换成对应的顺序存储结构 a。——含具体实现工程

假设二叉树中每个结点的值为单个字符， 设计一个算法将一棵以二叉链方式存储的二叉树 b 转换成对应的顺序存储结构 a。——李春葆数据结构第五版第七章，P246，第十题

思路解析：

解：设二叉树的顺序存储结构类型为SqBTree，先将顺序存储结构a中所有元素置为‘#’（表示空结点）。将b转换成a的递归模型如下：
f(b，a，i) -> a[i]=’#’; 当b=NULL
f(b，a，i) -> 由b结点data域值建立a[i]元素; f(b->lchild，a，2*i); f(b->rchild，a，2*i+1); 其他情况
调用方式为：f(b，a，1)（a的下标从1开始）。

对应的算法如下：
void Ctree(BTNode *b,SqBTree a,int i)
{ if (b!=NULL)
{ a[i]=b->data;
Ctree(b->lchild,a,2*i);
Ctree(b->rchild,a,2*i+1);
}
else a[i]=’#’;
}

具体实现：

我用VC++6.0做的工程，共建了5个源代码文件，代码可访问https://github.com/COCO5666/Date_Structure下载（Chapter07/Ch07_10）

vc6.0（完整绿色版）（支持XP、Win7、Win8、Win10）

假设二叉树中每个结点的值为单个字符， 设计一个算法将一棵以二叉链方式存储的二叉树 b 转换成对应的顺序存储结构 a。——含具体实现工程

LiBTree.h

这里为了避免因重复包含LiBTree.h而造成结构体类型（LBTNode）重复定义的错误发生，使用了#ifndef语句：

#ifndef LiBTree_H

#define LiBTree_H

//代码段

#endif

上面这句话的意思是如果没有定义过LiBTree_H那么定义LiBTree_H并执行”代码段”，如果已经定义过则会跳过下面的所有语句，#endif用于结束条件编译，编译时与前面最近的#if、#ifdef或#ifndef作为一对，经常一起使用，来进行判断是否编译两者之间的部分代码段（或称程序段）。

#ifndef LiBTree_H

#define LiBTree_H

#include <cstdio>
#include <malloc.h>

#define ElemType char
#define MaxSize 500

typedef struct node
{
	ElemType data;
	struct node *lchild;
	struct node *rchild;
}LBTNode;

void CreateLiBTree(LBTNode *&b, char *str);
void DispLiBTree(LBTNode *b);
void DestroyLiBTree(LBTNode *&b);

#endif

SqBTree.h

#include "LiBTree.h"

#include <cstdio>
#include <iostream>

using namespace std;

#define ElemType char
#define MaxSize 500

typedef ElemType SBTree[MaxSize];
typedef ElemType SBTNode;

void CreateSqBTFromLiBT(SBTNode *&SB, LBTNode *LB, int index=1);
void CreateSqBTree(SBTNode *&b, char *str);
void DispSqBTree(SBTNode *b, int index=1);
void DestroySqBTree(SBTNode *b);

LiBTree.cpp

#include "LiBTree.h"

void CreateLiBTree(LBTNode *&b, char *str)
{
	LBTNode *St[MaxSize], *p;
	int top=-1,k,j=0;
	char ch;
	b = NULL;
	ch = str[j];
	while(ch!='\0')
	{
		switch(ch)
		{
		case '(':top++;St[top]=p;k=1;break;
		case ')':top--;break;
		case ',':k=2;break;
		default:p=(LBTNode *)malloc(sizeof(LBTNode));
			p->data=ch;
			p->lchild=p->rchild=NULL;
			if(b==NULL)
			{
				b=p;
			}
			else
			{
				switch(k)
				{
				case 1:St[top]->lchild=p;break;
				case 2:St[top]->rchild=p;break;
				}
			}
		}
		j++;
		ch=str[j];
	}
}

void DispLiBTree(LBTNode *b)
{
	if(b!=NULL)
	{
		printf("%c", b->data);
		if(b->lchild!=NULL || b->rchild!=NULL)
		{
			printf("(");
			DispLiBTree(b->lchild);
			if(b->rchild!=NULL)
			{
				printf(",");
			}
			DispLiBTree(b->rchild);
			printf(")");
		}
	}
}

void DestroyLiBTree(LBTNode *&b)
{
	if(b!=NULL)
	{
		DestroyLiBTree(b->lchild);
		DestroyLiBTree(b->rchild);
		free(b);
	}
}

SqBTree.cpp

#include "SqBTree.h"

void CreateSqBTFromLiBT(SBTNode *&SB, LBTNode *LB, int index)
{
	static bool flag = true;
	if(flag)
	{
		SB = (SBTNode *)malloc(sizeof(SBTree));
		flag = false;
		for(int j=0; j<MaxSize; j++)
		{
			SB[j]='#';
		}
	}
	if(LB!=NULL)
	{
		SB[index-1] = LB->data;
		CreateSqBTFromLiBT(SB, LB->lchild, 2*index);
		CreateSqBTFromLiBT(SB, LB->rchild, 2*index+1);
	}
	else
	{
		SB[index] = '#';
	}
}

void CreateSqBTree(SBTNode *&b, char *str)
{
	b = (SBTNode *)malloc(sizeof(SBTree));
	int j=0, index=1;
	for(;j<MaxSize;j++)
	{
		b[j]='#';
	}
	j=0;
	char ch;
	ch = str[j];
	while(ch!='\0')
	{
		switch(ch)
		{
		case '(':index=index*2;break;
		case ')':index=index/2;break;
		case ',':index=index+1;break;
		default:
			b[index-1]=ch;break;
		}
		j++;
		ch=str[j];
	}
}


void DispSqBTree(SBTNode *b, int index)
{
	if(b[index-1]!='#')
	{
		printf("%c", b[index-1]);
		if(b[2*index-1]!='#' || b[2*index] !='#')
		{
			printf("(");
			DispSqBTree(b, 2*index);
			if(b[2*index] != '#')
				printf(",");
			DispSqBTree(b, 2*index+1);
			printf(")");
		}
	}
}

void DestroySqBTree(SBTNode *b)
{
	if(b!=NULL)
	{
	free(b);
	b = NULL;
	}
}

mian.cpp

#include "LiBTree.h"
#include "SqBTree.h"

#include "string.h"
#include <iostream>

using namespace std;

int main()
{
	char str[]="A(B,C)";
	int i;
	SBTNode *SB, *SB2;
	LBTNode *LB;

	CreateLiBTree(LB, str);
	DispLiBTree(LB);
	cout  << endl;

	CreateSqBTree(SB, str);
	for(i=0; i<10; i++)
		cout << SB[i];
	cout << endl;
	DispSqBTree(SB);
	cout << endl;

	CreateSqBTFromLiBT(SB2, LB);
	for(i=0; i<10; i++)
		cout << SB2[i];
	cout << endl;
	DispSqBTree(SB2);
	cout << endl;

	DestroyLiBTree(LB);
	DestroySqBTree(SB);
	DestroySqBTree(SB2);
	return 0;
}

今天的文章假设二叉树中每个结点的值为单个字符， 设计一个算法将一棵以二叉链方式存储的二叉树 b 转换成对应的顺序存储结构 a。——含具体实现工程分享到此就结束了，感谢您的阅读。