假設二叉樹中每一個結點的值爲單個字符， 設計一個算法將一棵以二叉鏈方式存儲的二叉樹 b 轉換成對應的順序存儲結構 a。——含具體實現工程

假設二叉樹中每一個結點的值爲單個字符， 設計一個算法將一棵以二叉鏈方式存儲的二叉樹 b 轉換成對應的順序存儲結構 a。——李春葆數據結構第五版第七章，P246，第十題node

思路解析：

解：設二叉樹的順序存儲結構類型爲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開始）。ios

對應的算法以下：
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]='#';
}git

具體實現：

我用VC++6.0作的工程，共建了5個源代碼文件，代碼可訪問https://github.com/COCO5666/Date_Structure下載（Chapter07/Ch07_10）github

vc6.0（完整綠色版）（支持XP、Win七、Win八、Win10）算法

https://blog.csdn.net/COCO56/article/details/84570964數據結構

LiBTree.hspa

這裏爲了不因重複包含LiBTree.h而形成結構體類型（LBTNode）重複定義的錯誤發生，使用了#ifndef語句：.net

#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.hcode

#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;
}