数据结构与算法----2.7 由二叉树的广义表形式建立二叉树的二叉链表

[c++]代码库

#include <iostream>
using namespace std;
typedef char TElemType;
typedef struct BiTNode
{
    TElemType data;
	BiTNode *lc,*rc;
}*BiTree;

void CreateBiTree(BiTree &T, TElemType s[], int &i);
void CreateBiTree(BiTree &T, TElemType s[]) ;//由二叉树的广义表形式建立二叉树的二叉链表
void BiTreeLists(BiTree &T);//广义表形式输出
void Build(char s[]);

int main()
{
	BiTree T1;char s1[]="A(B(X(E,F),D),C(X(H,X),G)";
    cout<<"二叉树的广义表形式为："<<s1<<endl;
	CreateBiTree(T1,s1);
	cout<<"二叉树(广义表形式)输出为：";
	BiTreeLists(T1);
	cout<<endl;
	return 0;
}
void CreateBiTree(BiTree &T, TElemType s[], int &i) //建立二叉树
{  
	i++;
	if (s[i] == '#') { T = NULL; return; }
	T = new BiTNode;
	T->data = s[i];    
	if (!s[i+1]||s[i+1]==','|| s[i + 1] == ')')
	{
		T->lc = NULL;	T->rc = NULL;	return;
	}
	i++;
	CreateBiTree(T->lc, s, i);
	i++;
	CreateBiTree(T->rc, s, i);
	i++;
}

void CreateBiTree(BiTree &T, TElemType s[]) 
{
	int i = -1;
	CreateBiTree(T, s, i);
}


void BiTreeLists(BiTree &T)
{
	if(!T) {cout<<'#';return;}
	cout<<T->data;
	if(T->lc ||T->rc)
	{
		cout<<'(';
		BiTreeLists(T->lc);
		cout<<',';
		BiTreeLists(T->rc);
		cout<<')';
	}
}