cstreeexample.cpp

所有关于二叉树的算法实现

#include <stdio.h>
#include <malloc.h>
#include <ctype.h>
#include <conio.h>
//#include <string.h>
typedef char ElemType;
char Str[256]; int Sn,Ln;

// 树的孩子兄弟二叉链表存储结构
typedef struct CSNode
{
	ElemType data; //叶子结点的值
	struct CSNode *Child1; //左孩子链表指针
	struct CSNode *Sibling; //右孩子链表指针
}*CSTree;

// 链栈(队列)类型
typedef struct SNode
{
	struct CSNode *tnode; //数据域
	struct SNode *next; //指针域
}*LinkStack;

// 构造一个带头结点的空链栈(队列)S
int StackInit(LinkStack &S)
{
	S=(LinkStack) malloc(sizeof(SNode));
	if(!S) return 0;
	S->next=NULL;
	return 1;
}//StackInit

// 向链栈S的栈顶压入一个新的数据元素Tdata
int StackPush(LinkStack &S,CSTree Tdata)
{
	LinkStack p=(LinkStack) malloc(sizeof(SNode));
	if(!S) return 0; //存储分配失败
	p->tnode=Tdata;
	p->next=S->next;
	S->next=p;
	return 1;
}//StackPush

// 弹出链栈S中的栈顶元素，并用Tdata返回
void StackPop(LinkStack &S,CSTree &Tdata)
{
	LinkStack p=S->next;
	if(p)
	{
		S->next=p->next;
		Tdata=p->tnode;
		free(p);
	}else Tdata=NULL;
}//StackPop

// 向链队列S插入新的数据元素Tdata和Tlevel
int StackInsert(LinkStack &S,CSTree Tdata)
{
	LinkStack p=(LinkStack) malloc(sizeof(SNode));
	if(!p) return 0; //存储分配失败
	LinkStack q=S;
	while(q->next) q=q->next;
	p->tnode=Tdata;
	q->next=p;
	p->next=NULL;
	return 1;
}//StackInsert

// 删除链队列S中的队首元素，并用Tdata和Tlevel返回
void StackDelete(LinkStack &S,CSTree &Tdata)
{
	LinkStack p=S->next;
	if(p)
	{
		S->next=p->next;
		Tdata=p->tnode;
		free(p);
	}else Tdata=NULL;
}//StackPop

// 去掉字符串型树中不符合要求的字符
void CSTreeString(char *St)
{
	int i=0,j=0,k=0;
	char ch=St[0];
	while(ch && !isalnum(ch))
	{
		++j;
		ch=St[j];
	}//while
	while(ch && ch!=';')
	{
		if(ch=='('||ch==')'||ch==','||isalnum(ch))
		{
			St[k]=ch;
			++k;
		}//if
		++j;
		ch=St[j];
	}//while
	St[k]='\0';
	int i1=0;
	ch=St[0];
	while(ch && ch!=';')
	{
		Str[j]=St[j];
		++j;
		ch=St[j];
	}//while
	while(!i1)
	{
		ch=Str[1];
		while(ch && ch!=';')
		{
			St[i1]=Str[i1+1];
			++i1;
			ch=Str[i1+1];
		}//while
		if(i1>0) St[i1]='\0';
		j=k=0;
		char ch2;
		ch=St[0];
		Str[0]=' ';
		while(ch && ch!=';')
		{
			i=0;
			ch2=St[j+1];
			if(ch=='(' && ch2==')')
			{
				j+=2;
				i=1;
				i1=0;
			}//if
			if(ch=='(' && ch2=='(')
			{
				++j;
				i1=0;
			}//if
			if(ch==')' && ch2=='(')
			{
				++j;
				i1=0;
			}//if
			if(ch==',' && !isalnum(ch2))
			{
				++j;
				i=1;
				i1=0;
			}//if
			if((isalnum(ch) || ch==')') && isalnum(ch2))
			{
				k+=2;
				Str[k-1]=ch;
				Str[k]=',';
				++j;
				ch=St[j];
				i1=0;
			}//if
			if(!i)
			{
				++k;
				Str[k]=ch;
				++j;
			}//if
			ch=St[j];
		}//while-ch
		Str[k+1]='\0';
	}//while-i1
	i=k=0;
	while(ch && ch!=';')
	{
		if(ch=='(') ++k;
		if(ch==')') --k;
		if(k<0) break;
		++i;
		ch=St[i];
	}//while
	if(k!=0) printf("\nBracket is not matching.\n");
}//CSTreeString

// 构造一个带头结点的空(树)孩子兄弟二叉链表T
int CSTreeInit(CSTree &T)
{
	T=(CSTree) malloc(sizeof(CSNode));
	if(!T) return 0;
	T->Child1=T->Sibling=NULL;
	return 1;
}//CSTreeInit

// 根据字符串型树建立树的孩子兄弟二叉链表存储结构T
void CSTreeCreate(CSTree &T)
{
	LinkStack S;
	StackInit(S);
	CSTree p,q=T;
	Sn=1;
	char ch=Str[Sn];
	while(ch && ch!=';')
	{
 		if(isalnum(ch))
		{
			CSTreeInit(p);
			p->data=ch;
			if(Str[Sn-1]!=',') q->Child1=p;
			else q->Sibling=p;
		}
		else if(ch=='(') StackPush(S,q);
		else if(ch==')') StackPop(S,p);
		++Sn;
		ch=Str[Sn];
		q=p;
	}//while
}//CSTreeCreate

// 根据树的孩子兄弟二叉链表输出字符串型树T
void CSTreePrintS(CSTree T)
{
	if(!T) return;
	printf("%c",T->data);
	if(T->Child1)
	{
		printf("(");
		CSTreePrintS(T->Child1);
	}//if
	if(T->Sibling)
	{
		printf(",");
		CSTreePrintS(T->Sibling);
	}//if
	if(!T->Sibling)
	{
		printf(")");
		return;
	}//if
}//CSTreePrintS

// 输出孩子兄弟二叉链表树Tl的存储结构
void BiTreePrintS(CSTree T)
{
	if(!T) return;
	printf("\n%d  %c  %d  %d",T,T->data,T->Child1,T->Sibling);
	if(T->Child1) BiTreePrintS(T->Child1);
	else if(!T->Sibling) return;
	if(T->Sibling) BiTreePrintS(T->Sibling);
	while(!T->Sibling) return;
}//BiTreePrintS

// 根据树的孩子兄弟二叉链表求树T的深度(高度)
int CSTreeDepth(CSTree T)
{
	if(!T) return 0;
	if(T->Child1)
	{
		++Sn;
		if(Sn>Ln) Ln=Sn;
		CSTreeDepth(T->Child1); --Sn;
	}//if
	if(T->Sibling) CSTreeDepth(T->Sibling);
	return Ln;
}//CSTreeDepth

// 根据字符串型树求树T的深度(高度)
int CSTreeDepthS(char *St)
{
	char ch=St[1];
	int i=0,j=0,k=1;
	while(ch && ch!=';')
	{
		if(ch=='(')
		{
			++i;
			if(i>j) j=i;
		}//if
		if(ch==')') --i;
		++k;
		ch=St[k];
	}//while
	return j+1;
}//CSTreeDepthS

// 在树的孩子兄弟二叉链表T中查找数据元素x的递归算法(查找成功时返回该结点的指针)
CSTree CSTreeSearch(CSTree T, ElemType x)
{
	if(!T) return NULL;
	if(T->data==x) return T;
	CSTree p;
	if(T->Child1)
	{
		p=CSTreeSearch(T->Child1,x);
		if(p) return p;
	}//if
	if(T->Sibling)
	{
		p=CSTreeSearch(T->Sibling,x);
		if(p) return p;
	}//if
	return NULL; //查找失败出口
}//CSTreeSearch

// 求树的孩子兄弟二叉链表T中值为x的数据元素所在的层次
int CSTreeLevel(CSTree T,ElemType x)
{
	if(!T) return 0;
	if(T->data==x) return 1;
	if(T->Child1)
	{
		++Sn;
		if(CSTreeLevel(T->Child1,x)) return 1;
		--Sn;
	}//if
	if(T->Sibling && CSTreeLevel(T->Sibling,x)) return 1;
	return 0;
}//CSTreeLevel

// 先根遍历孩子兄弟二叉链表树T的递归算法(深度优先遍历)
void PreOrder(CSTree T)
{
	if(!T) return;
	printf("%c ",T->data);
	if(T->Child1) PreOrder(T->Child1);
	if(T->Sibling) PreOrder(T->Sibling);
}//PreOrder

// 先根遍历孩子兄弟二叉链表树T的非递归算法
void PreOrderS(CSTree T)
{
	LinkStack S;
	if(!StackInit(S)) return;
	CSTree p=T->Child1;
	while(p)
	{
		while(p->Child1)
		{
			printf("%c ",p->data);
			StackPush(S,p);
			p=p->Child1;
		}//while
		printf("%c ",p->data);
		while(p && !p->Sibling) StackPop(S,p);
		if(p && p->Sibling) p=p->Sibling;
	}//while
}//PreOrderS

// 层序遍历孩子兄弟二叉链表树T的非递归算法(广度优先遍历)
void LevelOrder(CSTree T)
{
	LinkStack S;
	if (!StackInit(S)) return;
	CSTree p=T->Child1;
	StackInsert(S,p);
	while(S->next)
	{
		StackDelete(S,p); //出队
		printf("%c ",p->data);
		if(!p->Child1) loop;
		p=p->Child1;
		StackInsert(S,p);
		while(p->Sibling)
		{
			p=p->Sibling;
			StackInsert(S,p);
		}//while
	}//while
}//LevelOrder


void main()
{
	//char s0[]="A(B,C(e),D)";
	char s0[]=",R( (A(D E(1)) ,(B(F-(,),() G,H)C(0));";
	//char s0[]="A(B(D(a),b), C(E(c,d),F(G(f),e)));";
	//char s0[]="a(b(c(e),d(j,f(g,h),k)),o)";
	printf("\nSt= %s",s0); CSTreeString(s0); printf("\nStr=%s",Str); 

	CSTree p,q; CSTreeInit(p); CSTreeCreate(p);
	q=p->Child1; printf("\n\n T= %c(",q->data); CSTreePrintS(q->Child1);
	printf("\n\nBiT=(T Data Child1st Sibling)"); BiTreePrintS(p);

	Ln=Sn=0; printf("\n\nCSTreeDepth= %d",CSTreeDepth(p)); 
	printf("   CStringDepth= %d\n",CSTreeDepthS(Str)); 

	Sn=0; char s='C'; printf("\nElement %c at %d\n",s,CSTreeSearch(p,s));

	printf("\nPre-T= "); PreOrder(p->Child1);
	printf("\nPreST= "); PreOrderS(p);

	Sn=0; CSTreeLevel(p,s); printf("\n\n %c at Level %d ",s,Sn);

	printf("\n\nLevelOrder= "); LevelOrder(p);

	printf("\n\n");
	free(p); p->Child1=p->Sibling=NULL;
}