btree.cpp

一个非递归建立二差树的算法!输入先序带结束符号的序列建立二叉树!原创

//说明：关于建立二叉树的问题,这几天一直在考虑
//主要建立方法有六种(包括可行和不可行的)
//1.输入带结束符号的先序序列,递归建立二叉树
//2.输入带结束符号的中序序列,递归建立二叉树
//3.输入带结束符号的后序序列,递归建立二叉树
//4.输入带结束符号的先序序列,非递归建立二叉树
//5.输入带结束符号的中序序列,非递归建立二叉树
//6.输入带结束符号的后序序列,非递归建立二叉树
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
//1.输入带结束符号的先序序列,递归建立二叉树
typedef struct Tree
{
	char data;
    Tree *lchild,*rchild;
	int left,right;
}Tree;

Tree * PreCreate()
{
	char c;
	Tree *root;
	if ((c=getchar())=='0') return NULL;
	else
	{
		root=(Tree *)malloc(sizeof(Tree));
		root->data=c;
		root->lchild=PreCreate();
		root->rchild=PreCreate();
	}
	return root;
}

typedef struct Stack
{
	Tree *data;
    Stack *next;
	Stack *top;
}Stack;

void Push(Tree *p,Stack *L)
{
	Stack *t;
	t=(Stack *)malloc(sizeof(Stack));
	t->data=p;
	t->next=L->top;
	L->top=t;
}

Tree *Pop(Stack *L)
{
	Tree *p;
	Stack *q;
	if (L->top->next==NULL) return NULL;
	else
	{
		q=L->top;
		p=q->data;
		L->top=q->next;
		free(q);
	}
	return p;
}

Tree *GetTop(Stack *L)
{
	return L->top->data;
}

void PrintTreePre(Tree *t)
{
	if (t!=NULL)
	{
		printf("%c ",t->data);
        PrintTreePre(t->lchild);
		PrintTreePre(t->rchild);
	}
}

Tree * PreCreate(char *s) //s为一个字符串
{//输入带结束符号的先序序列,非递归建立二叉树,结束符号为#,函数返回根节点的指针
	Tree *p,*root,*q;//定义一些节点,p用来表示移动根节点,root用来表示树的根节点,q表示当前申请的节点
	Stack *L;//定义一个栈
	int i=0;//这个是字符串的下标
	L=(Stack *)malloc(sizeof(Stack));//申请栈的节点空间
	L->next=NULL;//该头节点的next域为空
	L->top=L;//栈顶指向该节点
	if (s[i]=='0'||s[i]=='#')
	{
		root=NULL;//如果第一个字符为空，那么就直接返回空
		return root;
	}
	else  //如果第一个字符不为空
	{
		p=(Tree *)malloc(sizeof(Tree));//直接申请节点空间 
		p->data=s[i];//设置节点数据域为这个自符
		p->lchild=NULL;//节点左孩子为空
		p->rchild=NULL;//节点右孩子为空
		root=p;//这个就是根节点了
		Push(p,L);//把这个节点入栈
	}
    i++;//下标加1
	while (s[i]!='#')//如果不是结束符号，就循环
	{
		while (s[i]!='0'&&s[i]!='#')//如果不是0或者结束符号
		{
			q=(Tree *)malloc(sizeof(Tree));//直接申请节点空间 
			q->data=s[i];//设置节点数据域为这个自符
			q->lchild=NULL;//节点左孩子为空
			q->rchild=NULL;//节点右孩子为空
            p=GetTop(L);//获取栈顶的元素
			p->lchild=q;//左孩子赋值
			Push(q,L);//把这个节点压栈
			i++;//下标加1
		}
		if(L->top->next!=NULL&&s[i]!='#')
		{
			p=GetTop(L);//把栈顶元素给p
			i++;//下标加1
			if (s[i]=='#') break;//看看是不是结束符号,是的话,就退出循环
			if(s[i]!='0')//如果不是0的话
			{
		    	q=(Tree *)malloc(sizeof(Tree));//直接申请节点空间 
		    	q->data=s[i];//设置节点数据域为这个自符
		    	q->lchild=NULL;//节点左孩子为空
		    	q->rchild=NULL;//节点右孩子为空
				p->rchild=q;//右孩子赋值
				Pop(L);//出栈
                Push(q,L);//把这个节点压栈
			}
			i++;//下标加1
		}
	}
	return root;
}
void main()
{
	Tree *T1,*T2,*T3,*T4,*T5,*T6,*T7;
	char *s1,*s2,*s3,*s4,*s5,*s6,*s7;
	s1="ABC00D0E00f00#";
	s2="DBA00C00E00#";
	s3="ABC0000#";
	s4="a0b0c00#";
	s5="dbac000e00fg000#";
	s6="abd00e00cf00g00#";
	s7="ABC00DG000EF000#";
	T1=PreCreate(s1);
	PrintTreePre(T1);
		printf("\n");
	T2=PreCreate(s2);
	PrintTreePre(T2);
		printf("\n");
	T3=PreCreate(s3);
	PrintTreePre(T3);
		printf("\n");
	T4=PreCreate(s4);
	PrintTreePre(T4);
		printf("\n");
	T5=PreCreate(s5);
	PrintTreePre(T5);
		printf("\n");
	T6=PreCreate(s6);
	PrintTreePre(T6);
		printf("\n");
	T7=PreCreate(s7);
	PrintTreePre(T7);
		printf("\n");
}