2叉树问题.cpp

1） 以二叉链表或三叉链表作为二叉树的存储结构； 2） 以某一种遍历的次序录入二叉树的元素

	
typedef struct BiTNode
{
			TElemType data;
			struct BiTNode *lchild;
			struct BiTNode *rchild;
}BiTNode,*BiTree;
	typedef struct BiThrNode
{
		TElemType data;
		struct BiThrNode *lchild,*rchild,*next;
}BiThrNode,*BiThrTree;
typedef enum{OPTR,OPND}ElemTag;
typedef struct TNode
{
		ElemTag tag;
		union data
		{
			int optr;
			char opnd;
		}data;
		TNode *lchild;
		TNode *rchild;
		}TNode,*TNLink;

Status PreOrderCreateBiTree(BiTree &T)
{//创建二叉树。输入先序序列，添加空格将节点补为度为2。
		TElemType ch;
		ch = getchar();
		if(ch == ' ')
			T = NULL;
		else
			{
				if(!(T = (BiTNode *)malloc(sizeof(BiTNode))))
					return ERROR;
				T->data = ch;
				if(PreOrderCreateBiTree(T->lchild))
					if(PreOrderCreateBiTree(T->rchild))
						return OK;
				return ERROR;
			}
		return OK;
}//end of PreOrderCreateBiTree

Status Visit(TElemType e)
{
		printf("%c",e);
		return OK;
}//end of Visit
	
	需求2：
	建树过程同上，这里只给出线索化算法及基于线索树的后序遍历。
	Status PostOrderThreading(BiThrTree &Thrt,BiThrTree T)
{//后序遍历二叉树T，并将其后序线索化，Thrt指向头节点
	//extern BiThrTree pre;
	if(!(Thrt = (BiThrTree)malloc(sizeof(BiThrNode))))
		return ERROR;
	Thrt->data = ' ';
	Thrt->lchild = NULL;
	Thrt->rchild = NULL;	
	if(!T)
		Thrt->next = Thrt;
	else
	{
		pre = Thrt;
		InThreading(T);
		pre->next = Thrt;
	}
	return OK;
}//end of PostOrderThreading

void InThreading(BiThrTree p)
{
	extern BiThrTree pre;
	if(p)
	{
		InThreading(p->lchild);
		InThreading(p->rchild);
		pre->next = p;
		pre = p;
	}
}//end of InThreading

void PostOrderTraverse_Thr(BiThrTree T,Status (*Visit)(TElemType(e)))
{
	BiThrTree p;
	p = T->next;
	while(p != T)
	{
		Visit(p->data);
		p = p->next;
	}
	Visit(p->data);
	printf("\n");
}//end of PostOrderTraverse_Thr

需求3

Status PreOrderCreateBiTree(TNLink &T)
{//创建二叉树。输入先序序列，添加空格将节点补为度为2。
	TElemType ch;
	TElemType z[6];
	int i;
	int d;
	ch = getchar();
	if(ch == ' ')
		T = NULL;
	else
		{
			if(!(T = (TNode *)malloc(sizeof(TNode))))
				return ERROR;
			if(In(ch))			//In(ch)函数用来判断ch是否为操作符
			{
				T->tag = OPND;
				T->data.opnd = ch;
			}
			else if(ch >= '0' && ch <= '9')
			{
				i = 0;
				do
				{
					z[i] = ch;
					i++;
					ch = getchar();
				}while(ch >= '0' && ch <= '9');
				z[i] = '\0';
				d = atoi(z);
				T->tag = OPTR;
				T->data.optr = d;
			}
			else return ERROR;
			if(PreOrderCreateBiTree(T->lchild))
				if(PreOrderCreateBiTree(T->rchild))
					return OK;
			return ERROR;
		}
	return OK;
}//end of PreOrderCreateBiTree